大学数据结构课件--第5章 数组和广义表

1、1 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 元素的值并非原子类型，可以再分解，表中元素也是元素的值并非原子类型，可以再分解，表中元素也是 一个线性表一个线性表 所有数据元素仍属于所有数据元素仍属于同一数据类型同一数据类型。数组和广义表是线性表的扩充：第5章 数组和广义表2注：注： 数组中的元素都具有统一的类型数组中的元素都具有统一的类型; ; 数组元素的下标一般都具有固定的上界和下界，即数组一旦数组元素的下标一般都具有固定的上界和下界，即数组一旦 被定义，它的维数和维界就不再发生改变；被定义，它的维数和维界就不再

2、发生改变； 数组的基本操作简单：初始化、销毁、存取元素和修改元素值数组的基本操作简单：初始化、销毁、存取元素和修改元素值 一维数组的特点：一维数组的特点：1 1个下标，个下标，aiai是是ai+1ai+1的直接前驱的直接前驱 二维数组的特点：二维数组的特点：2 2个下标，每个元素个下标，每个元素aijaij受两个关系受两个关系 （行关系和列关系）（行关系和列关系）的约束；的约束；数组：数组： 由一组名字相同、下标不同的变量构成由一组名字相同、下标不同的变量构成一个一个mn的二维数组可以的二维数组可以看成是看成是m行的一维数组，或行的一维数组，或者者n列的一维数组。列的一维数组。( )( )(

3、)( ) a00 a01 a1,n-1 a10 a11 a1,n-1 am-1,0 am-1,2 am-1,n-1 Amn=( )( )( )( )5.1 数组的定义3存储单元是存储单元是一维一维结构，而数组是个结构，而数组是个多维多维结构结构, ,则用一组连续存储单元存放数组的数据元素就有则用一组连续存储单元存放数组的数据元素就有个个次序约定次序约定问题。问题。二维数组可有两种存储方式： 1）以行序为主序 ； 2）以列序为主序。 a00 a01 a0,n-1 a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1 a00a01a0,n-1a10a11a1,n-1am-1,

4、0am-1,1am-1,n-1a00a10am-1,0a01a11am-1,1a0,n-1a1,n-1am-1,n-15.2 数组的顺序表示和实现4 （以行序为主序为例（以行序为主序为例）假设每个数据元素占L个存储单元，则二维数组Ab1b2中任一元素aij的存储位置可由下式确定：LOC（i，j）=LOC（0，0）+（b2 * i + j）* L对于数组，一旦规定了它的维数和各维的长度，便可为它分配存储空间。反之，只要给出一组下标便可求得相应数组元素的存储位置。数组基址数组基址总列数，即总列数，即第第2 2维长度维长度aij本行前面本行前面的元素个数的元素个数每个元素每个元素所占的存所占的存储单

5、元储单元若是若是N N维数组维数组Ab1b2bn，其中任一元素的地址，其中任一元素的地址: :LOC(j1,j2,jn)= LOC(0,0,0)+(j1b2bn+ j2b3bn+ jn-1bn+ jn ) L5.2 数组的顺序表示和实现5例例1：一个二维数组一个二维数组A，行下标的范围是，行下标的范围是1到到6，列下标的范围，列下标的范围 是是0到到7，每个数组元素用相邻的，每个数组元素用相邻的6个字节存储，存储器个字节存储，存储器 按字节编址。那么，这个数组的体积是按字节编址。那么，这个数组的体积是 个字节。个字节。例例2：设数组设数组a160,170的基地址为的基地址为2048，每个元素，

6、每个元素2个存个存 储单元，若以列序为主序顺序存储，则元素储单元，若以列序为主序顺序存储，则元素a32,58 的的 存储地址为存储地址为 。288例例3：已知二维数组已知二维数组M的每个元素占的每个元素占4个存储单元，数组行下标个存储单元，数组行下标 i的范围从的范围从0到到4，列下标，列下标j的范围从的范围从0到到5，数组，数组M按行存按行存 储时，元素储时，元素M35的地址和的地址和M按列存储时，元素按列存储时，元素_ 的地址相同。的地址相同。 A. M24 B. M34 C. M35 D. M445.2 数组的顺序表示和实现6压缩存储：为多个值相同的元素分配一个存储空间；对零元素不为多个

7、值相同的元素分配一个存储空间；对零元素不分配空间。分配空间。具备压缩条件的矩阵包括：对称矩阵、三角矩阵、对角矩阵、稀疏矩阵。对称矩阵、三角矩阵、对角矩阵、稀疏矩阵。稀疏矩阵：矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%5%）。）。5.3 矩阵的压缩存储7一、对称矩阵在一个在一个n n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质： aij=aji （0i0i，jn-1jn-1）则称则称A A为对称矩阵。为对称矩阵。 a11 a12 a13 . a1n a21 a22 a23 . a2n a31 a32 a33 . a3n . an1 an2 an3

8、 . ann1、对称矩阵的定义5.3.1 特殊矩阵82、对称矩阵的压缩存储对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。在下三角矩阵中，元素的总个数为的存储空间。在下三角矩阵中，元素的总个数为1+2+n=n(n+1)/2。按按行优先顺序行优先顺序存储主对角线存储主对角线(包括对角线包括对角线)以下的元素以下的元素 0123n(n-1)/2n(n+1)/2-1a11a21a22

9、a31an1ann a11 a12 a13 . a1n a21 a22 a23 . a2n a31 a32 a33 . a3n . an1 an2 an3 . ann5.3.1 特殊矩阵92、对称矩阵的压缩存储 a11 a12 a13 . a1n a21 a22 a23 . a2n a31 a32 a33 . a3n . an1 an2 an3 . ann元素元素aij的存放位置的存放位置 aij元素前有元素前有i-1行行(从第从第1行到第行到第i-1行行)，一共有：，一共有： 1+2+(i-1)=(i-1)(1+(i-1)2= i(i-1)/2个元素个元素; 在第在第i行上，行上，aij之前

10、恰有之前恰有j-1个元素个元素(即即ai1，ai2，ai,j-1)，因此有：，因此有： aij之前共有之前共有i(i-1)2+(j-1)个元素个元素aij和和sk之间的对应关系：之间的对应关系： i(i-1)/2+j-1 当当 ijj(j-1)/2+i-1 当当ijK=5.3.1 特殊矩阵10矩阵下三角部分元素是随机的，而上三角部分元素全部相同矩阵下三角部分元素是随机的，而上三角部分元素全部相同（为某常数（为某常数C C）或全为）或全为0 0。二、三角矩阵（1 1）上三角矩阵）上三角矩阵矩阵上三角部分元素是随机的，而下三角部分元素全部相同矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为

11、某常数（为某常数C C）或全为）或全为0 0。（2 2）下三角矩阵）下三角矩阵（b）下三角矩阵）下三角矩阵111110111000.-nnnnaaa0aa00a（a）上三角矩阵）上三角矩阵 111111100100.-nnnna000aa0aaa5.3.1 特殊矩阵11（3）下三角矩阵的压缩存储矩阵中共有矩阵中共有n(n+1)/2个非零元素，共需要个非零元素，共需要n(n+1)/2+1个存储空间。若将个存储空间。若将其存放到一维向量空间其存放到一维向量空间S0.Sn(n+1)/2中，则中，则SK与与aij的对应关系的对应关系为：为：当当ij时，时，aij是非零元素，是非零元素， aij前面有前

12、面有i行，共有行，共有1+2+3+i=i(i+1)/2个非零元素，个非零元素，aij前面有前面有j列，共列，共j个非零元素，即个非零元素，即k=i(i+1)/2+j；当；当ij时，时，aij是零元素，存放在最后一个存储单元是零元素，存放在最后一个存储单元Sn(n+1)/2中。中。 i(i+1)/2+j 当当 ijn(n+1)/2 当当ijK= 111110111000.-nnnnaaa0aa00a5.3.1 特殊矩阵12（4）上三角矩阵的压缩存储矩阵中共有矩阵中共有n(n+1)/2个非零元素，共需要个非零元素，共需要n(n+1)/2+1个存储空间。若将个存储空间。若将其存放到一维向量空间其存放

13、到一维向量空间S0.Sn(n+1)/2中，则中，则SK与与aij的对应关系的对应关系为：为：当当i j时时,aij是非零元素是非零元素, aij前面有前面有i行行,共有共有n+(n-1)+(n-2)+(n-(i-1)=i(n+n-(i-1)/2=i*n-i(i-1)/2个元素，个元素，aij前面有前面有j列，共列，共j-i个非零元素，个非零元素，即即k=i*n-i(i-1)/2+j-i；当；当ijK= 111111100100.-nnnna000aa0aaa5.3.1 特殊矩阵13三、对角矩阵 若矩阵中所有非零元素都集中在以主对角线为中心的带状若矩阵中所有非零元素都集中在以主对角线为中心的带状

14、区域中，区域外的值全为区域中，区域外的值全为0，则称为对角矩阵。常见的有，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。三对角矩阵、五对角矩阵、七对角矩阵等。66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa一个一个77的三对角矩阵的三对角矩阵5.3.1 特殊矩阵14对角矩阵的压缩存储我们仅讨论三对角矩阵的压缩存储。我们仅讨论三对角矩阵的压缩存储。在一个在一个n n的三对角矩阵中，只有的三对角矩阵中，只有n+n-1+n-1个非零元素，故个非零元素，故只需只

15、需3n-2个存储单元即可，零元已不占用存储单元。个存储单元即可，零元已不占用存储单元。故可将故可将n n三对角矩阵三对角矩阵A压缩存放到只有压缩存放到只有3n-2个存储单元的个存储单元的s向向量中，假设仍按行优先顺序存放，量中，假设仍按行优先顺序存放， sk与与aij的对应关系为：的对应关系为：3i或或 3j 当当i=j3i+1或或3j-2 当当i=j-13i-1 或或3j+2 当当i=j+1K=66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa5.3.1 特殊矩阵15稀

16、疏矩阵的存储：如何表示非零元素的位置信息如何表示非零元素的位置信息每个元素用一个三元组（每个元素用一个三元组（i，j，v）来表示。）来表示。1. 三元组表：0 12 9 0 0 00 0 0 0 0 0-3 0 0 0 14 00 0 24 0 0 00 18 0 0 0 015 0 0 7 0 0i j v12345678 1 2 12 1 3 9 3 1 -3 3 5 14 4 3 24 5 2 18 6 1 15 6 4 -7注意：注意：为更可靠描述，通常再加一个为更可靠描述，通常再加一个“总体总体”信息：即信息：即总行数、总列数、非总行数、总列数、非零元素总个数零元素总个数。06 6

17、8 5.3.2 稀疏矩阵16例：试还原出下列三元组所表示的稀疏矩阵。试还原出下列三元组所表示的稀疏矩阵。 64612221123134445366116ijvalue646640 2 0 012 0 0 03 0 0 00 0 0 40 0 6 016 0 0 05.3.2 稀疏矩阵172. 十字链表： i j v down right指向同一列中下一非零元素指向同一行中下一非零元素3 0 0 50 1 0 02 0 0 01 1 31 4 53 1 22 2 -15.3.2 稀疏矩阵181、定义广义表是线性表的推广，也称为列表（lists）。记为：LS=（a1，a2，an）广义表名广义表名n

18、是表长在广义表中约定： ai可以是单个元素，也可以是广义表，分别称为可以是单个元素，也可以是广义表，分别称为原子原子和和子表子表; ; 用小写字母表示元素，用用小写字母表示元素，用大写字母大写字母表示列表名称；表示列表名称； 当当LSLS非空时，称第一个元素为非空时，称第一个元素为表头表头(Head)(Head)，其余元素组成的表，其余元素组成的表 ( (a2 2，an)n)为为表尾表尾(Tail)(Tail)。v 任何一个非空表，表头可能是原子，也可能是列表，但任何一个非空表，表头可能是原子，也可能是列表，但 表尾一定是列表。表尾一定是列表。5.4 广义表的定义19例1：求下列广义表的长度。

19、(1) A=( )(2) B=(e)(3) C=(a，(b，c，d)(4) D=（A ，B，C）(5) E=(a，E)n=0，因为因为A A是空表是空表n=1，表中元素表中元素e e是原子是原子n=2，a a 为原子，为原子，(b,c,d)(b,c,d)为子表为子表D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表共享表E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E为为递归表递归表n=3，3 3个元素都是子表个元素都是子表n=2，a a 为原子，为原子，E E为子表为子表表中元素个数表中元素个数5.4 广义表的定义20abcdABDCe A=( a , (b, A

20、) )例2：试用图形表示下列广义表（设 代表子表， 代表元素） e D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) )Aab的长度为的长度为2，深度为，深度为的长度为的长度为3，深度为，深度为3深度括号的重数深度括号的重数5.4 广义表的定义21广义表两种特殊的基本操作：广义表两种特殊的基本操作：GetHead 【 L 】取表头（可能是原子或列表）GetTail 【 L 】 取表尾（一定是列表）（1）GetTail【 (b，k，p，h ) 】 =（2）GetHead 【(a,b)，(c,d) 】=（3）GetTail 【(a,b)，(c,d) 】=（4）GetTail 【

21、GetHead 【(a,b)，(c,d) 】 】=（5）GetTail 【(e) 】=（6）GetHead 【( ) 】=（7）GetTail 【( ) 】=(k,p,h)(a,b)(c,d)(b)( )( )( )5.4 广义表的定义22利用GetHead和GetTail操作，把原子banana分别从下列广义表中分离出来。 (1) L1=(apple,pear,banana,orange) (2) L2=(apple,pear),(banana,orange) (3) L3=(apple),(pear),(banana),(orange) GetHead【GetTail 【 GetTail

22、【 L1 】 】 】GetHead【GetHead 【 GetTail 【 L2 】 】 】GetHead【GetHead 【 GetTail 【 GetTail 【 GetHead 【 L3 】练习23由于广义表的元素可以是不同结构（原子或列表），难以用顺由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构，通常用序存储结构，通常用链式结构链式结构，每个，每个元素元素用一个结点表示。用一个结点表示。注意：列表的元素可以是原子或列表，所以结点可能有两种形式注意：列表的元素可以是原子或列表，所以结点可能有两种形式1. 原子结点：原子结点：表示原子，设表示原子，设2 2个域个域标志域标

23、志域 数值域数值域02. 列表结点：列表结点：表示列表，设表示列表，设3 3个域个域标志域标志域 表头指针表头指针表尾指针表尾指针15.5 广义表的存储结构24 A =( ) 10e C =( a ,( b , c , d ) ) 110a0b例：例： B=( e ) A=NULL1 E=(a, E) 0a111(b,c,d)(b,c,d)1(c,d)c01(d)d05.5 广义表的存储结构251. 数组可视为一种广义线性表；数组可视为一种广义线性表；2. 数组的存储有行优先和列优先两种不同的顺序；数组的存储有行优先和列优先两种不同的顺序；3. 对于稀疏矩阵，有较好的压缩存储方法；对于稀疏矩阵

24、，有较好的压缩存储方法；4. 广义表（列表）是线性表的推广，也是一种线性结构；广义表（列表）是线性表的推广，也是一种线性结构；5. 任何一个非空表，任何一个非空表，表头可能是原子，也可能是列表；但表头可能是原子，也可能是列表；但表尾一定是列表。表尾一定是列表。第5章 小结26教学要求：教学要求：1 1、了解数组的两种存储表示方法，并掌握数组在以行为主、了解数组的两种存储表示方法，并掌握数组在以行为主 的存储结构中的地址计算方法。的存储结构中的地址计算方法。2 2、了解稀疏矩阵的两种压缩存储方法。、了解稀疏矩阵的两种压缩存储方法。3 3、掌握广义表的结构特点及其存储表示方法，会对非空、掌握广义表的结构特点及其存储表示方法，会对非空 广义表进行分解。广义表进行分解。第5章 数组和广义表271、设有二维数组、设有二维数组A6*8，每个元素用相邻的，每个元素用相邻的6个字节存储，已知个字节存储，已知A的的基址是基址是1000，则，则A的体积是的体积是 。若以行序为主序进行存储，