《数据结构》课程PPT教学课件（2012）第5章 数组和广义表 Arrays & Lists（1/2）

第5章 数组和广义表(Arrays&Lists) 数组和广义表的特点：一种特殊的线性表 元素的值并非原子类型，可以再分解，表中元素也是一个 线性表（即广义的线性表）。 ②所有数据元素仍属同一数据类型。 5.1数组的定义 5.2数组的顺序表示和实现 5.3矩阵的压缩存储 5.4广义表的定义 5.5广义表的存储结构

1 第5章 数组和广义表（Arrays & Lists） ① 元素的值并非原子类型，可以再分解，表中元素也是一个 线性表（即广义的线性表）。 ② 所有数据元素仍属同一数据类型。 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 数组和广义表的特点：一种特殊的线性表

5.1数组的定义 数组：由一组名字相同、下标不同的变量构成 注意：这里讨论的数组与高级语言中的数组有所区别：高级 语言中的数组是顺序结构：而这里的数组既可以是顺序的， 也可以是链式结构，用户可根据需要选择。 判断：“数组的处理比其它复杂的结构要简单”，对吗？ 答：对的。因为 ①数组中各元素具有统一的类型； ②数组元素的下标一般具有固定的上界和下界，即数组一 旦被定义，它的维数和维界就不再改变。 ®数组的基本操作比较简单，除了结构的初始化和销毁之 外，只有存取元素和修改元素值的操作

2 5.1 数组的定义 数组： 由一组名字相同、下标不同的变量构成 注意： 这里讨论的数组与高级语言中的数组有所区别：高级 语言中的数组是顺序结构；而这里的数组既可以是顺序的， 也可以是链式结构，用户可根据需要选择。 答：对的。因为—— ① 数组中各元素具有统一的类型； ② 数组元素的下标一般具有固定的上界和下界，即数组一 旦被定义，它的维数和维界就不再改变。 ③数组的基本操作比较简单，除了结构的初始化和销毁之 外，只有存取元素和修改元素值的操作。 判断：“数组的处理比其它复杂的结构要简单”，对吗？

维数组的特点：1个下标，a:是a+1的直接前驱 二维数组的特点 2个下标，每个元素a受到两个关系 (行关系和列关系)的的束： a11a12.a1n a21a22.a2n 个m×n的二维数组可以 mn 看成是m行的一维数组，或 2ml am2.amn 者列的一维数组。 N维数组的特点：n个下标，每个元素受到n个关系约束 一个n维数组可以看成是由若干个n-1维数组组成的线性表

3 二维数组的特点： 一维数组的特点： 1个下标，ai 是ai+1的直接前驱 2个下标，每个元素ai,j受到两个关系 （行关系和列关系）的约束： 一个m×n的二维数组可以 看成是m行的一维数组，或 者n列的一维数组。 N维数组的特点： n个下标，每个元素受到n个关系约束 一个n维数组可以看成是由若干个n－1维数组组成的线性表。 a11 a12 . a1n a21 a22 . a2n . . . . am1 am2 . amn Amn =

N维数组的数据类型定义 n ARRAY=(D,R) 其中： 数据对象影D={a2jni为数组元素的第i维下标，a2.j∈Elemset) 数据关系：R={R1,R2, \.Rn Ri=ajjn.n aj.j2.ji.jn ajj2.j+1.n D) 基本操作：构造数组、销毁数组、读数组元素、写数组元素 数组的抽象数据类型定义略，参见教材P90

4 N维数组的数据类型定义 n_ARRAY = (D, R) 其中： Ri = {| aj1,j2,.ji.jn , aj1,j2,.ji+1.jn D } 数据关系：R = { R1 ,R2，. Rn } 数据对象：D = {aj1,j2.jn| ji为数组元素的第i 维下标 ，aj1,j2.jn Elemset} 数组的抽象数据类型定义略，参见教材P90 基本操作：构造数组、销毁数组、读数组元素、写数组元素

5.2数组的顺序存储表示和实现 问题：计算机的存储结构是一维的，而数组一般是多 维的，怎样存放？ 解决办法：事先约定按某种次序将数组元素排成一列序列， 然后将这个线性序列存入存储器中。 如：在二维数组中，我们既可以规定按行存储，也 可以规定按列存储。 注意： 若规定好了次序，则数组中任意一个元素的存放地址便有 规律可寻，可形成地址计算公式； 约定的次序不同，则计算元素地址的公式也有所不同； C和PASCAL中一般采用行优先顺序；FORTRAN采用列 优先。 5

5 5.2 数组的顺序存储表示和实现 问 题：计算机的存储结构是一维的，而数组一般是多 维的，怎样存放？ 解决办法：事先约定按某种次序将数组元素排成一列序列， 然后将这个线性序列存入存储器中。 例 如：在二维数组中，我们既可以规定按行存储，也 可以规定按列存储。 注意： • 若规定好了次序，则数组中任意一个元素的存放地址便有 规律可寻，可形成地址计算公式； • 约定的次序不同，则计算元素地址的公式也有所不同； • C和PASCAL中一般采用行优先顺序；FORTRAN采用列 优先

无论规定行优先或列优先，只要知道以下三要素便可随时求出 任一元素的地址（意义：数组中的任一元素可随机存取）y: ①开始结点的存放地址（即基地址 ②维数和每维的上、下界； ③每个数组元素所占用的单元数 ac1.c2 ac1,d2 a 补充：计算二维数组元素地址的通式 aal,c2.adl,d2 设一般的二维数组是A[c1.d1,c2d2],这里c1,c2不一定是0或1 则行优先存储时的地址公式为： LOC()=LOC(ac1,)+[(i-c)*(d2-c2+1)+j-C2)l 数组基址 之前的行 总列数，即 单个元素 数 第维长度 本行前面 的元素个数 长度 二 维数组列优先存储的通式为 LOC(aij)=LOC(ac1,c2)+[j-c2)*(di-c1+1)+i-c1)]*L 6

6 补充：计算二维数组元素地址的通式 设一般的二维数组是A[c1.d1, c2.d2]，这里c1,c2不一定是0或1 无论规定行优先或列优先，只要知道以下三要素便可随时求出 任一元素的地址（意义：数组中的任一元素可随机存取）： 二维数组列优先存储的通式为： LOC(aij)=LOC(ac1，c2 )+[(j-c2)*(d1-c1+1)+i-c1)]*L ac1,c2 . ac1,d2 . aij . ad1,c2 . ad1,d2 Amn = 单个元素 长度 aij之前的行 数 数组基址 总列数，即 第2维长度 aij本行前面 的元素个数 ①开始结点的存放地址（即基地址） ②维数和每维的上、下界； ③每个数组元素所占用的单元数 则行优先存储时的地址公式为： LOC(aij)=LOC(ac1，c2 )+[(i-c1)*(d2-c2+1)+j-c2)]*L

例1：如何求出a(3,2)的存储地址？ 0 1 2 3 a(0,0) a(0,1) a0,3) a(1,0) a(1,1) a(1,3) 2 。,。 .。 。,。 ，。,。 3 a(3,2) g 6 a(6,0) a(6,3) 要事先确定： ①是行优先方式还是列优先方式？ 否则无法 ②数组的首地址是多少？ 求出结果 ③每个元素的长度？ 7

7 a(0,0) a(0,1) . a(0,3) a(1,0) a(1,1) . a(1,3) . . . . . . a(3,2) . . . . . . . . . a(6,0) . . a(6,3) 0 1 2 3 0 1 2 3 4 5 6 例1：如何求出a(3,2)的存储地址？ 要事先确定： ①是行优先方式还是列优先方式？ ②数组的首地址是多少？ ③每个元素的长度？ 否则无法 求出结果

例2〖软考题】 ：一个二维数组A,行下标的范围是1到6，列 下标的范围是0到7，每个数组元素用相邻的6个字节存储，存 储器按字节编址。那么，这个数组的体积是288个字节。 答：V6lume=m*n*L六(6-1+1)*(7-01)*6=48*6=288 例3：已知二维数组Amm按行存储的元素地址公式是： L0c(a)=Loc(a1+[(i-1)*m+(Gj-1*K,请问按列存储的公式 相同吗？ 答：尽管是方阵，但公式仍不同。应为： Loc(a)Loc(a+[0-1)*m+(i-1)]*K 8

8 例3：已知二维数组Am,m按行存储的元素地址公式是： Loc(aij)= Loc(a11)+[(i-1)*m+(j-1)]*K , 请问按列存储的公式 相同吗？ 答：尽管是方阵，但公式仍不同。应为： Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K 例2〖软考题〗：一个二维数组A，行下标的范围是1到6，列 下标的范围是0到7，每个数组元素用相邻的6个字节存储，存 储器按字节编址。那么，这个数组的体积是 288 个字节。 答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288

例4：〖00年计算机系考研题〗：设数组a1.60,1.701 的基地址为2048，每个元素占2个存储单元，若以列序为主 序顺序存储，则元素a32,581的存储地址为8950 答：请注意审题！ 根据列优先公式Loc(a=Loc(aG)*m+(-*K 得：L0C(a32-58)=2048+1(58-1)*60+(32-1)1*2=8950 想一想：若数组是a0.59, 0.691,结果是否仍为8950？ 维界虽未变，但此时的a32,58]不 再是原来的a32,581 9

9 例4 ：〖00年计算机系考研题〗 ：设数组a[1.60, 1.70] 的基地址为2048，每个元素占2个存储单元，若以列序为主 序顺序存储，则元素a[32,58]的存储地址为 。 根据列优先公式Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K 得：LOC(a32,58)=2048+[(58-1)*60+(32-1)]*2＝8950 答：请注意审题！ 想一想：若数组是a[0.59, 0.69]，结果是否仍为8950？ 8950 维界虽未变，但此时的a[32,58]不 再是原来的a[32,58]

若是N维数组，其中任一元素的地址该如何计算？ 教材已给出低维优先的地址计算公式（见P93(5-2)式） 该式称为维数组的映像函数： Loc(jjz.j)=LOC(0,0,.+>C.j i=l 数组基址 鹅萄戆氨用 其中Cn=L,C1=b×C, 1<i<n 每个元素长度 第维长度 与所存元素个数有关的系数， 可用递推法求出 三维数组且列优先时的元素地址 要会计算！ 10

10 Loc(j1 ,j2 ,.jn )=LOC(0,0,.0)＋ 若是N维数组，其中任一元素的地址该如何计算？ = n i i i 1 C j 其中Cn=L, Ci-1=bi×Ci， 1<i≤n 每个元素长度 数组基址 前面若干元素占用 的地址字节总数 第i维长度 与所存元素个数有关的系数， 可用递推法求出 教材已给出低维优先的地址计算公式（见P93（5-2）式） 该式称为n维数组的映像函数： 三维数组且列优先时的元素地址 要会计算！