【精品数据结构】数组与十字链表.PPTVIP

§4.1 数组 数组是一种十分常用的结构 大多数程序设计语言都直接支持数组类型 数组的基本操作主要是元素定位 本节的主要内容是讨论数组的存贮映射方法 §4.1.1 数组的定义与运算 数组是由一组类型相同的数据元素构成，每个数据元素称为一个数组元素（简称元素） 每个元素受n 个线性关系约束（n≥1），若它在第1～第n个线性关系中的序号分别为i1、i2……in, 则称它的下标为i1、i2……in，若该数组的名为A，则记下标为i1、i2……in,的元素为，称该数组为n维数组。 §4.1.1 数组的定义与运算 数组的另一个定义 数组定义为一个元素可直接按序号寻址的线性表 A=(A1, A2, …, Am) 若Ai是简单元素（不是数组），则A是一维数组；若Ai是（k-1)维数组，则A是k维数组。 §4.1.1 数组的定义与运算 §4.1.1 数组的定义与运算 一维数组的操作 给定一组下标，读出相应的元素。 给定一组下标，修改相应的元素。 §4.1.2 数组的存储结构与寻址问题 要求元素的存储地址能根据它的下标（即逻辑关系）计算出来，一般只采用顺序存储结构 偏移地址（相对地址） 选定一个基准（参考）存贮单元，问题中所涉及的地址值均以此参考单元为基准（为起点） 设i1、i2、…、in为某n维数组中的一个元素的下标，则用Loc(i1, i2, …, in)表示此元素的相对地址 可以将多维数组影射为一维结构，然后运用顺序存储方式。 §4.1.3 一维数组的存贮与寻址 设一维数组为 A=(a0, a1, …, an) 则它的元素ai的相对地址为 Loc(i)=i · c 若数组下标范围为 闭区间[l1,h1]内的整数，即 A=( ) 则元素ai的相对地址为 Loc(i)=(i-l1) · c §4.1.4 二维数组的存贮 二维数组的阵列形状 a11 a12 … a1n a21 a22 … a2n 　　A = …… 　　　　　 am1 am2 … amn 常用的映射方法有两种：按行与按列 §4.1.4 二维数组的存贮 (一) 按行存贮 先行后列：先存贮行号较小的元素，行号相同者，先存贮列号较小者。 　a11 a12 … a1n a21 a22 … a2n …… am1 am2 … amn ────── ─────── ────── 第1行元素 第2行元素 第m行元素 §4.1.4 二维数组的存贮 (一) 按行存贮 设二维数组的行下标与列下标变化范围分别为闭区间[l1, h1]与[l2, h2]，按行存储，任一元素aij的相对地址计算公式为 Loc(i, j) = ( (h2 - l2+1) (i-l1) + (j-l2) ) · c §4.1.4 二维数组的存贮 (一) 按行存贮 【例4.1】.设某二维数组的两个下标的范围分别为[-1, 2]与[0, 1]，它的元素按行存贮的次序为（用ai表示元素，每个元素占两个单元）： §4.1.4 二维数组的存贮 (二)按列存贮 先列后行，即先存贮列号较小者，列号相同者先存贮行号较小者 　 a11 a21 … am1 a12 a22 … am2 …… a1n a2n … amn ────── ─────── ────── 第1列元素 第2列元素 第n列元素 任一元素aij的相对地址计算公式为 Loc(i, j) = ( (j-l2) (h1 – l1+1) + (i-l1) ) · c §4.1.5 多维数组的存贮 (一)按行存贮 “左”下标优先的存贮方法 【例4.1】设某三维数组的三个下标范围分别为 [2,4]，[0,1]，[1,3] 则它按行存贮的次序为 　 a201 a202 a203 a211 a212 a213 （接下行） 　　 a301 a302 a303 a311 a312 a313　（接下行） a401 a402 a403 a411 a412 a413 §4.1.5 多维数组的存贮 (一)按行存贮 “设n维数组第k维的下标范围是[lk, hk]，记 dk = hk - lk + 1，jk = ik - lk，k= 1,