第5章 多维数组和广义表

1、第五章 多维数组和广义表算法演示上一页下一页返 回VC+2第五章第五章 多维数组和广义表多维数组和广义表 前面讨论的线性表、链表、栈和队列都是线性的数据结构，它们的逻辑特征是：每个数据元素至多有一个直接前驱和一个直接后继。本章要介绍的数组是指至少二维数组的多维数组，它是一种复杂的非线性结构，它的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。5.1 多维数组多维数组一、一维数组一、一维数组 一维数组可用向量（a1,a2,an）的形式来表示，因此，也把一维数组称为向量。向量中的每一个数据元素都具有统一的、相同的数据类型，数组元素的下标一般具有固定的上界和下界，同一个数组中的不同元素可通

2、过下标来标识。向量的逻辑特征是：每个数据元素至多有一个直接前驱和一个直接后继。向量是存储在计算机的连续存储空间中，可通过数组的地址求出每个元素的地址，因此，可以随机的进行存取。多维数组是向量的推广。 第五章 多维数组和广义表算法演示上一页下一页返 回VC+二、多维数组二、多维数组1、二维数组的表示、二维数组的表示 二维数组可表示成矩阵 的形式，矩阵的每一行和每一列都可以看成是一个向量，因此，二维数组可以看成是由m个行向量组成的(列)向量，也可以看成是由n个列向量组成的(行)向量。2、二维数组的逻辑结构、二维数组的逻辑结构 二维数组中的每个元素aij均属于两个向量：一个是第i行的行向量，另一个是

3、第j列的列向量。因此，除边界元素外，每个元素aij都恰好有两个直接前驱aij-1和ai-1j，两个直接后继aij+1和ai+1j。而除开始结点和终端结点外的边界结点都只有一个直接前驱和一个直接后继。开始结点没有前驱只有一个直接后继，终端结点只有一个直接前驱没有后继。因此，二维数组的逻辑结构是：每个元素至多有两个直接前驱和两个直接后继。3mnmmnnmnaaaaaaaaaA212222111211第五章 多维数组和广义表算法演示上一页下一页返 回VC+43、多维数组的逻辑结构、多维数组的逻辑结构1）三维数组：三维数组可以看成是以二维数组为元素的向量。三维数组的每个元素aijk至多有三个直接前驱和

4、三个直接后继。2）n维数组：n维数组可以看成是以n-1维数组为元素的向量。 n维数组的每个元素至多有n个直接前驱和n个直接后继。因此，多维数组的逻辑特征是：一个数据元素可能因此，多维数组的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。有多个直接前驱和多个直接后继。三、数组的顺序存储表示三、数组的顺序存储表示 由于计算机内存的结构是一维的，因此用内存来表示多维数组，必须将数组元素按某种次序排成线性序列后存人存储器。又由于数组一般不做插入和删除操作，即数组一旦建立，结构中元素个数和元素间关系不再发生变化。因此，一般采用顺序存储方法表示数组，通常有以下两种顺序存储方式。第五章 多维数组和

5、广义表算法演示上一页下一页返 回VC+1、 行优先顺序行优先顺序 将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。例如，二维数组Amn的按行优先存储的线性序列为： a11,a12,a1n,a21,a22,a2n,am1,am2,amn2、 列优先顺序列优先顺序 将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量后面。例如，二维数组Amn的按列优先存储的线性序列为： a11,a21,am1,a12,a22,am2,a1n,a2n,amn注意：注意：C语言中的数组是按行优先顺序存储的，数组元素下标的下界值为0。5第五章 多维数组和广义表算法演示上一页下一页返 回VC+四、数

6、组元素的地址计算公式四、数组元素的地址计算公式 按行优先方式顺序存储的数组，只要知道开始结点的存储地址、多维数组的维数和各维的上下界，以及数组元素在内存中占用的字节数，就可以求出每个元素的存储地址。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。 设二维数组Amn按行优先存储，各维的下界为0，上界分别为m-1,n-1，每个元素占内存的字节数为d，如果用LOC(a00)表示a00的地址，则aij的地址为：同理，三维数组Amnp按行优先存储，则aijk的地址为：6njmidjniaLOCaLOCij0,0)()()(00dkpjpniaLOCaLOCijk)()(

7、)(000pknjmi0 ,0,0第五章 多维数组和广义表算法演示上一页下一页返 回VC+7 75.2 矩阵的压缩存储矩阵的压缩存储一、常用矩阵的压缩存储一、常用矩阵的压缩存储1、对称矩阵、对称矩阵1）对称矩阵的定义：）对称矩阵的定义：如果n阶矩阵A的元素满足 ，则称A为n阶对称矩阵。2）对称矩阵的压缩存储：）对称矩阵的压缩存储：由于对称矩阵中的元素关于主对角线对称，所以只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享同一个存储空间，这样可以节约近一半的存储空间。按按“行优先顺序行优先顺序”存储下三角中的元素存储下三角中的元素 将下三角中的元素aij(ij)按线性序列a00,a10

8、,a11, an-10, an-11,an-1n-1的次序存放在一个含有n(n+1)/2个元素的向量sa中(因下三角元素总数为n(n+1)/2)。即将aij存放在sai(i+1)/2+j中(0in-1,0 ji)。njiaajiij,0第五章 多维数组和广义表算法演示上一页下一页返 回VC+对称对称矩阵中的元素矩阵中的元素aij和和sak之间的对应关系：之间的对应关系： 若ij，k=i(i+1)2+j 0kn(n+1)2 若ij，k=j(j+1)2+i 0kn(n+1)2 令I=max(i，j)，J=min(i，j)，则k和i，j的对应关系可统一为：k=I(I+1)2+J , 0kn(n+1)

9、/2。3）对称矩阵的地址计算公式 LOC(aij)=LOC(sak) =LOC(sa0)+kd=LOC(sa0)+(I(I+1)/2+J)d。2、三角矩阵、三角矩阵1）三角矩阵的定义：）三角矩阵的定义：把主对角线以下(不包括主对角线)的元素均为常数c的n阶矩阵，称为上三角矩阵；把主对角线以上(不包括主对角线)的元素均为常数c的n阶矩阵，称为下三角矩阵；上三角矩阵和下三角矩阵统称为三角矩阵。三角矩阵中的常数c在多数情况下为0。8第五章 多维数组和广义表算法演示上一页下一页返 回VC+2）三角矩阵的压缩存储：）三角矩阵的压缩存储：三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1

10、)/2个，因此，三角矩阵可压缩存储到含有n(n+1)/2+1个元素的向量sa中，其中c存放在向量的最后一个分量中。上三角矩阵中上三角矩阵中aij和和sak之间的对应关系之间的对应关系 上三角矩阵中，主对角线之上的第i行(0i(k-1)/2，则aij=0的矩阵A是k对角矩阵，其中k为奇数。特别，当k=3时，称为三对角矩阵。3）三对角矩阵的压缩存储：）三对角矩阵的压缩存储：三对角矩阵中非0元素正好有3n-2个，因此，三对角矩阵可压缩存储到含有3n-2个元素的向量sa中。三对角矩阵中三对角矩阵中aij和和sak之间的对应关系之间的对应关系 元素aij前共有i行，其中非0元素共有3i-1个；第i行中前

11、面已有i-1个0，所以aij前非0元素有j-(i-1)个，因此aij前已有的非零元素个数为： 3i-1+j-(i-1)=2i+j。按行优先顺序元素aij存放在sa2i+j中。第五章 多维数组和广义表算法演示上一页下一页返 回VC+11二、稀疏矩阵的压缩存储二、稀疏矩阵的压缩存储1、稀疏矩阵的定义：、稀疏矩阵的定义：设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即sdata中row和col中的内容，得到按列优先顺序存储的转置矩阵B的三元组表b-data；再将b-data重排成按行优先顺序的三元组表；130001060000004000200354A642data3-113data44

12、21data2-230data1300data0vcolrow稀疏矩阵三元组表13第五章 多维数组和广义表算法演示上一页下一页返 回VC+方法二：方法二：由于A的列是B的行，因此，按a-data的列序转置，所得到的转置矩阵B的三元组表b-data必定是按行优先存放的。我们将采用方法二来实现。4）算法步骤：第一步：第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。第二步：第二步：当三元组表非空（A矩阵的非零元个数不为0）时，根据A矩阵三元组表的结点空间data，将A的三元组表a-data置换为B的三元组表b-data。具体置换方法：具体置换方法：为保证B的三元组表是按

13、行优先存放的，对A中的每一列j(0ja-n-1)，通过从头至尾扫描三元组表a-data，找出所有列号等于j的那些三元组，将它们的行号和列号互换后依次放人b-data中，即可得到B的按行优先的压缩存贮表示。5）具体算法具体算法： 14用三元组表实现矩阵的转置运算的算法：用三元组表实现矩阵的转置运算的算法：void TransMatrix(TriTupleTable *b,TriTupleTable *a)/*a,*b是矩阵A、B的三元组表表示,求A转置为B int p,q,j; b-m=a-n; b-n=a-m; /A和B的行列总数互换 b-t=a-t; /非零元总数 if(b-t=0) pri

14、ntf(A中无非零元);exit(0);/退出 q=0; for(j=0;jn;j+) /对A的每一列 for(p=0;pt;p+) /扫描A的三元组表 if(a-datap.col=j) /找列号为j的三元组 b-dataq.row=a-datap.col; b-dataq.col=a-datap.row; b-dataq.v=a-datap.v; q+; 第五章 多维数组和广义表算法演示上一页下一页返 回VC+作业：习题作业：习题5.5 设两个mn稀疏矩阵A和B均以三元组表作为存储结构，试写出矩阵相加的算法，其结果存放在三元组表C中。提示：提示：矩阵相加就是将两个矩阵中同一位置的元素值相加

15、。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，需遍历A和B的两个三元组表的每个元素，分以下三种情况来考虑：1、当A和B的两个三元组对应的行标和列标都相等，如果对应的值相加不为0，加入C，否则不加入，再考虑它们的下一个三元组；2、当A与B的三元组行标相等，但A的三元组列标小于B的三元组列标，将A的三元组加入C，再考虑A的下一个三元组；3、当A与B的三元组的行标相等，但A的三元组列标大于B的三元组列标，将B的三元组加入C ，再考虑B的下一个三元组。最后再将A中或B中剩余三元组加入C。15第五章 多维数组和广义表算法演示上一页下一页返 回VC

16、+7 75.3广义表的概念广义表的概念一、广义表的概念一、广义表的概念1、广义表是n个元素a1，a2，an的有限序列。其中ai是原子或是一个广义表。通常记做LS=（a1，a2,.，an）LS是广义表的名字，n是它的长度。若ai是广义表，则称它为LS的子表。2、通常用圆括号将广义表括起来，用逗号分割其中的元素。书写时用大写字母表示广义表，小写字母表示原子。若广义表LS非空（n=1），则a1为LS的表头，其余元素（a2，an）组成LS的表尾。3、P67 广义表的例子 递归表，再入表，纯表和线性表4、广义表的图形表示与转换njiaajiij,0第五章 多维数组和广义表算法演示上一页下一页返 回VC+7 7二、广义表的运算二、广义表的运算1、取表头：、取表头：head(LS)2、取表尾