第05章_数组和广义表A

1、1第第5 5章章 数组和广义表数组和广义表 （Arrays & ListsArrays & Lists）5.1 5.1 数组的定义数组的定义5.2 5.2 数组的顺序存储表示和实现数组的顺序存储表示和实现5.3 5.3 矩阵的压缩存储矩阵的压缩存储5.4 5.4 广义表的定义广义表的定义5.5 5.5 广义表的存储结构广义表的存储结构25.1 数组的基本概念数组的基本概念 数组：数组： 由一组名字相同、下标不同的变量构成由一组名字相同、下标不同的变量构成 数组中各元素具有数组中各元素具有统一的类型统一的类型； 数组元素的下标一般具有数组元素的下标一般具有固定的上界和下界固定的上

2、界和下界，即数组一，即数组一旦被定义，它的维数和维界就不再改变。旦被定义，它的维数和维界就不再改变。数组的数组的基本操作比较简单，基本操作比较简单，除了结构的初始化和销毁之除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。外，只有存取元素和修改元素值的操作。数组的特点：数组的特点：3二维数组的特点：二维数组的特点：一维数组的特点：一维数组的特点：1 1个下标，个下标，a ai i 是是a ai+1i+1的直接前驱的直接前驱2 2个下标，个下标，每个元素每个元素ai,j受到两个关系受到两个关系（行关系和列关系）的约束：（行关系和列关系）的约束：一个一个mn的二维数组可以的二维数组可以看

3、成是看成是m行的一维数组，或行的一维数组，或者者n列的一维数组。列的一维数组。N N维数组的特点：维数组的特点：n n个下标，个下标，每个元素受到每个元素受到n n个关系约束个关系约束一个一个n维数组可以看成是维数组可以看成是由由若干个若干个n1维数组维数组组成的线性表。组成的线性表。 a11 a12 a1n a21 a22 a2n am1 am2 amn Amn=4N维数组的数据类型定义维数组的数据类型定义n_ARRAY = (D, R)其中： Ri = | aj1,j2,jijn , aj1,j2,ji+1jn D 数据关系：数据关系：R = R1 ,R2，. Rn 数据对象：数据对象：D

4、 = aj1,j2jn| ji为数组元素的第为数组元素的第i 维下标维下标 ，aj1,j2jn Elemset数组的抽象数据类型定义略，数组的抽象数据类型定义略，参见教材参见教材P90P90构造数组、销毁数组、读数组元素、写数组元素构造数组、销毁数组、读数组元素、写数组元素基本操作：基本操作：55.2 数组的顺序存储表示和实现数组的顺序存储表示和实现问题：问题：计算机的存储结构是一维的，而数组一般是多计算机的存储结构是一维的，而数组一般是多 维的，怎样存放？维的，怎样存放？解决办法：解决办法：事先约定按某种次序将数组元素排成一列序列，事先约定按某种次序将数组元素排成一列序列， 然后将这个线性序

5、列存入存储器中。然后将这个线性序列存入存储器中。例如：例如：在二维数组中，我们既可以规定按在二维数组中，我们既可以规定按行行存储，也存储，也 可以规定按可以规定按列列存储存储。注意：注意： 若规定好了次序，则数组中任意一个元素的存放地址便有若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；规律可寻，可形成地址计算公式； 约定的次序不同，则计算元素地址的公式也有所不同；约定的次序不同，则计算元素地址的公式也有所不同； C C和和PASCALPASCAL中一般采用中一般采用行优先行优先顺序；顺序；FORTRANFORTRAN采用采用列优先列优先。6设一般的二维数组是设

6、一般的二维数组是AcAc1 1.d.d1 1, c, c2 2.d.d2 2 ，这里这里c c1 1,c,c2 2不一定是不一定是0 0或或1 1无论规定行优先或列优先，只要知道以下三要素便可随时求出无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址任一元素的地址（意义：数组中的任一元素可随机存取）：（意义：数组中的任一元素可随机存取）：二维数组二维数组列优先列优先存储的通式为：存储的通式为：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+(i-c1)*L ac1,c2 ac1,d2 aij ad1,c2 ad1,d2 Amn=单个元素单个元素长度

7、长度aij之前的行数之前的行数数组基址数组基址总列数，即总列数，即第第2 2维长度维长度aij本行前面本行前面的元素个数的元素个数开始结点的存放地址（即基地址）开始结点的存放地址（即基地址）维数和每维的上、下界；维数和每维的上、下界；每个数组元素所占用的单元数每个数组元素所占用的单元数则则行优先行优先存储时的地址公式为：存储时的地址公式为：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+(j-c2)*L7a(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) 012 3【例例】如何求出如何求出的存储地址？的存储地

8、址？要事先确定：要事先确定：是行优先方式还是列优先方式？是行优先方式还是列优先方式？数组的首地址是多少？数组的首地址是多少？每个元素的长度？每个元素的长度？8【例例】已知二维数组已知二维数组Am,m按按行行存储的元素地址公式是：存储的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K , 请问按请问按列列存储的公式相存储的公式相同吗？同吗？答：尽管是方阵，但公式仍不同。应为：答：尽管是方阵，但公式仍不同。应为： Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K 【例例】(软考题软考题)：一个二维数组一个二维数组A，行下标的范围是，行下标的范

9、围是1到到6，列下标的范围是列下标的范围是0到到7，每个数组元素用相邻的，每个数组元素用相邻的6个字节存储，个字节存储，存储器按字节编址。那么，这个数组的体积是存储器按字节编址。那么，这个数组的体积是 个字节。个字节。 答：答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=2889【例例】(00年计算机系考研题年计算机系考研题) ：设数组设数组a160, 170的的基地址为基地址为2048，每个元素占，每个元素占2个存储单元，若以个存储单元，若以列序为主序列序为主序顺序存储，则元素顺序存储，则元素a32,58的存储地址为的存储地址为 。根据列优先公式根据列优先公

10、式 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K得：得：LOC(a32,58)=2048+(58-1)*60+(32-1)*28950答：请注意审题！答：请注意审题！10Loc(jLoc(j1 1,j,j2 2, ,j jn n)=LOC(0,0,)=LOC(0,0,0)0)若是若是N维数组，其中任一元素的地址该如何计算？维数组，其中任一元素的地址该如何计算？niii1jC其中其中Cn=L, Ci-1=biCi， 1in每个元素长度每个元素长度数组基址数组基址前面若干元素占用前面若干元素占用的地址字节总数的地址字节总数第第i i维长度维长度与所存元素个数有关的系数，与所存

11、元素个数有关的系数，可用递推法求出可用递推法求出教材已给出教材已给出低维优先低维优先的地址计算公式的地址计算公式（见（见P93P93（5-25-2）式）式）该式称为该式称为n n维数组的映像函数维数组的映像函数：三维数组且列优先时的元素地址三维数组且列优先时的元素地址要会计算！要会计算！11#define MAX_ARRAY_DIM 8 /假设最大维数为假设最大维数为8 8 typedef struct ELemType *base; /数组元素基址数组元素基址 int dim; /数组维数数组维数 int *bound; /数组各维长度信息保存区基址数组各维长度信息保存区基址 int *co

12、nstants; /数组映像函数常量的基址数组映像函数常量的基址 Array;即即Ci信息保存区信息保存区数组的基本操作函数说明（有数组的基本操作函数说明（有5个）个）（请阅读教材（请阅读教材P93-95P93-95）N维数组的顺序存储表示维数组的顺序存储表示（见教材见教材P93P93）12行指针向量行指针向量a11a12a1nam1am2amn补充：补充：用用带行指针向量的单链表带行指针向量的单链表来表示。来表示。注：注：链式数组的运算请参见链式数组的运算请参见“稀疏矩阵的转置稀疏矩阵的转置”注意：注意： 本章所讨论的数组与高级语言中的数组有所区别：本章所讨论的数组与高级语言中的数组有所区别

13、：高级语言中的数组只是顺序结构；而本章的数组既可以是顺高级语言中的数组只是顺序结构；而本章的数组既可以是顺序的，也可以是序的，也可以是链式结构链式结构，用户可根据需要选择。，用户可根据需要选择。135.3 5.3 矩阵的压缩存储讨论：讨论：1. 什么是压缩存储？什么是压缩存储？若多个数据元素的若多个数据元素的值都相同值都相同，则只分配一个元素值的存储空间，则只分配一个元素值的存储空间，且零元素不占存储空间。且零元素不占存储空间。2. 所有二维数组（矩阵）都能压缩吗？所有二维数组（矩阵）都能压缩吗？未必，要看矩阵是否具备以上压缩条件。未必，要看矩阵是否具备以上压缩条件。3. 什么样的矩阵具备以上

14、压缩条件？什么样的矩阵具备以上压缩条件？ 一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。阵等。4. 什么叫什么叫稀疏矩阵？稀疏矩阵？矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%5%）重点介绍稀疏矩阵的压缩和相应的操作。重点介绍稀疏矩阵的压缩和相应的操作。14一、稀疏矩阵的压缩存储一、稀疏矩阵的压缩存储问题：问题：如果只存储如果只存储稀疏矩阵中的非零元素，那这些元素的稀疏矩阵中的非零元素，那这些元素的位置信息位置信息该如何表示？该如何表示？解决思路：解决思路：对每个非零元素对每个非零元素增开增开若干存

15、储单元，用来存放其所在的若干存储单元，用来存放其所在的行号行号和和列号列号，便可准确反映该元素所在位置。，便可准确反映该元素所在位置。实现方法：实现方法：将每个非零元素用一个三元组将每个非零元素用一个三元组（i，j，aij）来表示，则每个）来表示，则每个稀疏矩阵可用一个稀疏矩阵可用一个来表示。来表示。二、稀疏矩阵的操作二、稀疏矩阵的操作15【例例】写出右图所示稀疏矩写出右图所示稀疏矩阵的压缩存储形式。阵的压缩存储形式。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 0解：解：至少有至少有4 4种种

16、存储形式。存储形式。用用表示：表示：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 0三元素组表中的每个结点三元素组表中的每个结点（i，j，aij）对应于稀疏矩对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表阵的一个非零元素，它包含有三个数据项，分别表示该元素的示该元素的 、 和和 。 行下标行下标列下标列下标元素值元素值16法法2 2：用用十字链表十字链表表示表示用途：用途：方便稀疏矩阵的方便稀疏矩阵的加减加减运算运算方法：方法：每个非每个非0元素占用元素占用5个域个域right dow

17、nvji同一同一列列中下一非中下一非零元素的指针零元素的指针同一同一行行中下一非中下一非零元素的指针零元素的指针十字链表的特点：十字链表的特点：每行非零元素每行非零元素链接成带表头结点的循环链表；链接成带表头结点的循环链表；每列非零元素每列非零元素也链接成带表头结点的循环链表。也链接成带表头结点的循环链表。则每个非零元素既是行循环链表中的一个结点；又是列循环则每个非零元素既是行循环链表中的一个结点；又是列循环链表中的一个结点，即链表中的一个结点，即呈十字链状。呈十字链状。122100H19311825稀疏矩阵的加减稀疏矩阵的加减运算容易实现运算容易实现17用用表示：表示：0 12 9 0 0

18、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 0121213931-3351443245218611564-7注意：注意：为更可靠描述，为更可靠描述，通常再加一行通常再加一行“总体总体”信息：即总行数、总信息：即总行数、总列数、非零元素总个列数、非零元素总个数数668ijvalue稀疏矩阵压缩存储的缺点：稀疏矩阵压缩存储的缺点：将失去随机存将失去随机存取功能取功能 ！18【例例】下面的三元组表表示一个稀疏矩阵，试还原出下面的三元组表表示一个稀疏矩阵，试还原出它的稀疏矩阵。它的稀疏矩阵。 646122211231344

19、45366116ijvalue646 0 2 0 012 0 0 0 3 0 0 0 0 0 0 4 0 0 6 016 0 0 019typedef structtypedef struct Triple Triple datadataMAXSIZE+1; MAXSIZE+1; /三元组表，以行为主序存入一三元组表，以行为主序存入一维向量维向量 data data 中中 int int mumu; ; /矩阵总行数矩阵总行数 intint nu nu; ; /矩阵总列数矩阵总列数 int tu; int tu; /矩阵中非零元素总个数矩阵中非零元素总个数 TsMatrixTsMatrix; ; 三元组表的顺序存储表示三元组表的顺序存储表示（见教材（见教材P98P98）对三元组表对三元组表的整