1、第第5 5章章 数组和广义表数组和广义表5.1 5.1 数组的定义和运算数组的定义和运算5.2 5.2 数组的顺序存储和实现数组的顺序存储和实现5.3 5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 5.3.1 5.3.1 三角矩阵三角矩阵 5.3.2 5.3.2 带状矩阵带状矩阵 5.3.3 5.3.3 稀疏矩阵稀疏矩阵5.4 5.4 广义表广义表5.5 5.5 总结与提高总结与提高 5.1 数组的定义和运算数组的定义和运算数组是一种数据类型。从逻辑结构上看，数组可以数组是一种数据类型。从逻辑结构上看，数组可以看成是一般线性表的扩充。二维数组可以看成是线看成是一般线性表的扩充。二维数组可以看成
2、是线性表的线性表。例如：性表的线性表。例如：Amn=a12 a12 a1j a1na21 a22 a2j a2n ai1 ai2 aij ain am1 am2 amj amnAmn=a12 a12 a1j a1na21 a22 a2j a2n ai1 ai2 aij ain am1 am2 amj amnA=（ 1 2 j n)我们可以把二维数组看成一个线性表：我们可以把二维数组看成一个线性表：A=( 1 2 j n)，其中，其中 j（1j n）本身也）本身也是一个线性表，称为列向量。是一个线性表，称为列向量。矩阵矩阵Amn看成看成n个列向量的线性表个列向量的线性表,即即 j=(a1j,a2
3、j, ,amj)Amn=a12 a12 a1j a1na21 a22 a2j a2n ai1 ai2 aij ain am1 am2 amj amnB 1 2 i m我们还可以将数组我们还可以将数组Amn看成另外一个线性表看成另外一个线性表:B=( 1，, 2,， ， m)，其中，其中 i（1i m）本身也是一个线性表，）本身也是一个线性表，称为行向量，即：称为行向量，即： I= （ai1，ai2， ，aij ，ain）。）。上面二维数组的例子，介绍了数组的结构特性，实上面二维数组的例子，介绍了数组的结构特性，实际上数组是一组有固定个数的元素的集合。由于这际上数组是一组有固定个数的元素的集合。
4、由于这个性质，使得对数组的操作不象对线性表的操作那个性质，使得对数组的操作不象对线性表的操作那样，可以在表中任意一个合法的位置插入或删除一样，可以在表中任意一个合法的位置插入或删除一个元素。个元素。对于数组的操作一般只有两类：对于数组的操作一般只有两类：（1）获得特定位置的元素值；）获得特定位置的元素值；（2）修改特定位置的元素值。）修改特定位置的元素值。数组的抽象数据类型定义（数组的抽象数据类型定义（ADT Array）数据对象：数据对象：D= aj1j2jn| n0，称为数组的维数，称为数组的维数，ji是是数组的第数组的第i维下标，维下标，1jibi，bi为数组第为数组第i维的长度，维的长
5、度， aj1j2jn ElementSet 数据关系：数据关系：R=R1,R2,RnRi= | 1jkbk，1kn 且且ki，1jibi-1， aj1 jijn ，aj1 ji+1jn D，i=1，n 基本操作：基本操作：（1）InitArray(A,n,bound1,boundn)： 若维数若维数n和各维的长和各维的长度合法，则构造相应的数组度合法，则构造相应的数组A，并返回，并返回TRUE； （2）DestroyArray（A）：）： 销毁数组销毁数组A； （3）GetValue（A，e, index1, ,indexn）：）： 若下标合法，若下标合法，用用e返回数组返回数组A中由中由in
6、dex1, ,indexn所指定的元素的值。所指定的元素的值。 （4）SetValue（A，e，index1, ,indexn）：）： 若下标合法，若下标合法，则将数组则将数组A中由中由index1, ,indexn所指定的元素的值置为所指定的元素的值置为e。 注意：这里定义的数组下标是从注意：这里定义的数组下标是从1开始，与开始，与C语言的语言的数组略有不同。数组略有不同。5.2 数组的顺序存储和实现数组的顺序存储和实现 对于数组对于数组A，一旦给定其维数，一旦给定其维数n及各维长度及各维长度bi（1in），则该数组中元素的个数是固定的，不可），则该数组中元素的个数是固定的，不可以对数组做插
7、入和删除操作，不涉及移动元素操作，以对数组做插入和删除操作，不涉及移动元素操作，因此对于数组而言，采用顺序存储法比较合适。因此对于数组而言，采用顺序存储法比较合适。 数组的顺序存储结构有两种：数组的顺序存储结构有两种：一种是按行序存储，如：高级语言一种是按行序存储，如：高级语言BASIC、COBOL和和PASCAL语言都是以行序为主。语言都是以行序为主。另一种是按列序存储，如：高级语言中的另一种是按列序存储，如：高级语言中的FORTRAN语言语言就是以列序为主。就是以列序为主。 对于二维数组对于二维数组Amxn以 行 为 主 的 存 储 序 列 为以 行 为 主 的 存 储 序 列 为 ： a
8、1 1 , a12, a1n ,a21 ,a22 ,a2n , ,am1 ,am2 , , amn以 列 为 主 存 储 序 列 为以 列 为 主 存 储 序 列 为 ： a11, a21, am1 ,a12 ,a22 , ,am2 , ,a1n ,a2n , ,amn 假设有一个假设有一个342的三维数组的三维数组A ，其逻辑结构图为：其逻辑结构图为：列列行行纵纵 以二维数组以二维数组Amn为例，假设每个元素只占一为例，假设每个元素只占一个存储单元，个存储单元，“以行为主以行为主”存放数组，下标从存放数组，下标从1开始，首元素开始，首元素a11的地址为的地址为Loc1,1 求任意元素求任意元
9、素aij的地址的地址 ，可由如下计算公式得到：，可由如下计算公式得到：Loci,j=Loc1,1+n (i-1)+(j-1) 其中其中n为第为第2维的长度维的长度 如果每个元素占如果每个元素占size个存储单元个存储单元 ，则任意元，则任意元素素aij的地址计算公式为：的地址计算公式为： Loci,j=Loc1,1 + (n(i-1)+j-1)size 若首元素的地址为若首元素的地址为Loc0,0，每个元素占，每个元素占size个个存储单元，则二维数组中元素存储单元，则二维数组中元素aij的存储位置可由如的存储位置可由如下计算公式得到：下计算公式得到：Loci,j=Loc0,0+（ni+j）*
10、size 其中其中n为第为第2维的长度维的长度三维数组三维数组A（1.r , 1.m , 1.n）可以看成是）可以看成是r个个mn的的二维数组二维数组 ，如下图所示：如下图所示： 假定每个元素占一个存储单元，采用以行为主序假定每个元素占一个存储单元，采用以行为主序的方法存放的方法存放 ，首元素，首元素a111的地址为的地址为Loc1,1,1，ai11的地的地址为址为Loci,1,1=Loc1,1,1+(i-1)*m*n ，那么求任意元，那么求任意元素素aijk的地址计算公式为：的地址计算公式为：Loci,j,k=Loc1,1,1+(i-1)*m*n+(j-1)*n+(k-1)其中其中1i，1j
11、，1k。 如果将三维数组推广到一般情况，即：用如果将三维数组推广到一般情况，即：用j1，j2，j3代替数组下标代替数组下标i，j，k；并且；并且j1，j2，j3的下限为的下限为c1，c2，c3，上限分别为，上限分别为d1，d2，d3，每个元素占一个，每个元素占一个存储单元。存储单元。则三维数组中任意元素则三维数组中任意元素a(j1，j2，j3)的地址为：的地址为：Locj1，j2，j3=Locc1,c2,c3+1*(d2-c2+1)*(d3-c3+1)*(j1-c1) +1*(d3-c3+1)*(j2-c2)+1*(j3-c3)其中其中l为每个元素所占存储单元数。为每个元素所占存储单元数。 例
12、例令令1=1*(d2-c2+1)*(d3-c3+1), 2=1*(d3-c3+1), 3=1，则：，则：Locj1,j2,j3=Locc1,c2,c3+ 1*(j1-c1)+ 2*(j2-c2)+ 3(j3-c3) =Locc1,c2,c3+ i*(ji-ci) （1i3） 由公式可知由公式可知Locj1,j2,j3与与j1,j2,j3呈线性关系。呈线性关系。 对于维数组对于维数组A(c1:d1,c2:d2，,cn,dn)，我们只要把上式推，我们只要把上式推广，就可以容易地得到维数组中任意元素广，就可以容易地得到维数组中任意元素aj1j2jn的存储的存储地址的计算公式。地址的计算公式。 Loc
13、j1，j2，jn=Locc1，c2，cn+ i (ji-ci) i=1n其中其中i =l (dk-ck+1) （1in） k=i+1n5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 特殊矩阵压缩存储的压缩原则是：对有规律的元素和值特殊矩阵压缩存储的压缩原则是：对有规律的元素和值相同的元素只分配一个存储单元，对于零元素不分配空间。相同的元素只分配一个存储单元，对于零元素不分配空间。5.3.1 三角矩阵三角矩阵三角矩阵大体分为：下三角矩阵、上三角矩阵和对称矩阵。三角矩阵大体分为：下三角矩阵、上三角矩阵和对称矩阵。对于一个对于一个n阶矩阵阶矩阵A来说：若当来说：若当ij时，有时，有aij=常量或零，则
14、此矩阵称为常量或零，则此矩阵称为上三角矩阵上三角矩阵若矩阵中的所有元素均满足若矩阵中的所有元素均满足aij=aji，则称此矩阵为，则称此矩阵为对称矩阵对称矩阵 对于下三角矩阵，按对于下三角矩阵，按“行序为主序行序为主序”进行存储，得到的序列进行存储，得到的序列为：为：a11,a21,a22,a31,a32,a33an1,an2ann。 由于下三角矩阵的元素个数为由于下三角矩阵的元素个数为n(n+1)/2，所以可压缩存储到一，所以可压缩存储到一个大小为个大小为n(n+1)/2的一维数组中。下三角矩阵中元素的一维数组中。下三角矩阵中元素aij(ij)，在一，在一维数组维数组A中的位置为：中的位置为
15、： LOC i ,j= LOC1,1+ i (i -1)/2+ j-1 下三角矩阵：下三角矩阵：A=a11a21 a22a31 a32 a33 an1 an2 an3 ann 同样，对于上三角矩阵，也可以将其压缩存储到一个大小同样，对于上三角矩阵，也可以将其压缩存储到一个大小为为n(n+1)/2的一维数组的一维数组C中。其中元素中。其中元素aij(i=jj(j-1)/2+i-1 当当ijk=5.3.2 带状矩阵带状矩阵带状矩阵：在矩阵带状矩阵：在矩阵A中，所有的非零元素都集中在以主对角中，所有的非零元素都集中在以主对角线为中心的带状区域中。最常见的是三对角带状矩阵。线为中心的带状区域中。最常见
16、的是三对角带状矩阵。 Ann =a11 a12a21 a22 a23 a32 a33 a34 a43 a44 a45 特点特点: i=1, j=1,2;当当 1in，j=i-1, i, i+1 i=n, j=n-1, n;时，时，aij非零，其他元素均为零。非零，其他元素均为零。 三对角带状矩阵的压缩存储，以行序为主序进行存储，三对角带状矩阵的压缩存储，以行序为主序进行存储，并且只存储非零元素。其方法为：并且只存储非零元素。其方法为：1. 确定存储该矩阵所需的一维向量空间的大小确定存储该矩阵所需的一维向量空间的大小 从三对角带状矩阵中可看出：除第一行和最后一行只有两从三对角带状矩阵中可看出：除
17、第一行和最后一行只有两个元素外，其余各行均有个元素外，其余各行均有3个非零元素。由此可得到一维向量个非零元素。由此可得到一维向量所需的空间大小为：所需的空间大小为：3n-2。2. 确定非零元素在一维数组空间中的位置确定非零元素在一维数组空间中的位置假设每个非零元素所占的空间的大小为假设每个非零元素所占的空间的大小为1个单元个单元LOCi , j = LOC1,1+2(i-1)+j-15.3.3 稀疏矩阵稀疏矩阵稀疏矩阵：指矩阵中大多数元素为零的矩阵。一般地，当非稀疏矩阵：指矩阵中大多数元素为零的矩阵。一般地，当非零元素个数只占矩阵元素总数的零元素个数只占矩阵元素总数的25%30%,或低于这个百
18、分或低于这个百分数时，我们称这样的矩阵为稀疏矩阵。数时，我们称这样的矩阵为稀疏矩阵。 0 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0M67=0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 0N67=随机稀疏矩阵的压缩存储方法随机稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序表三、三、 十字链表十字
19、链表1. 稀疏矩阵的三元组表表示法稀疏矩阵的三元组表表示法 对于稀疏矩阵的压缩存储要求在存储非零元素的同对于稀疏矩阵的压缩存储要求在存储非零元素的同时，还必须存储该非零元素在矩阵中所处的行号和列时，还必须存储该非零元素在矩阵中所处的行号和列号。我们将这种存储方法叫做稀疏矩阵的三元组表示号。我们将这种存储方法叫做稀疏矩阵的三元组表示法。法。 row col value该非零元素该非零元素所在的行号所在的行号该非零元素所该非零元素所在的列号在的列号该非零元素的该非零元素的值值每个非零元素在一维数组中的表示形式如图所示：每个非零元素在一维数组中的表示形式如图所示： 三元组表的类型说明：三元组表的类型
20、说明：#define MAXSIZE 1000 /*非零元素的个数最多为非零元素的个数最多为1000*/typedef structint row, col; /*该非零元素的行下标和列下标该非零元素的行下标和列下标*/ ElementType e； /*该非零元素的值该非零元素的值*/Triple;typedef struct Triple dataMAXSIZE+1; /* 非零元素的三元组表非零元素的三元组表 。data0未用未用*/int m, n, len; /*矩阵的行数、列数和非零元素的个数矩阵的行数、列数和非零元素的个数*/ TSMatrix； A的三元组顺序表图示的三元组顺序
21、表图示 A= A= 0 12 9 0 0 0 0 0 12 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 015 0 0 -7 0 0 0row col erow col e0 01 12 23 34 45 56 67 78 82 2 0 0 -3 -35 5 0 0 15 150 0 1 1 12 124 4 1 1 18 180 0 2 2 9 93 3 2
22、 2 24 245 5 3 3 -7 -72 2 5 5 14 14A.dataA.data6 67 78 8A.mA.mA.nA.nA.lenA.len1）用三元组表实现稀疏矩阵的转置运算）用三元组表实现稀疏矩阵的转置运算矩阵转置：指变换元素的位置，把位于（矩阵转置：指变换元素的位置，把位于（row，col）位置上）位置上的元素换到（的元素换到（col ，row）位置上，也就是说，把元素的行列）位置上，也就是说，把元素的行列互换。互换。 采用矩阵的正常存储方式时，实现矩阵转置的经典算法如下：采用矩阵的正常存储方式时，实现矩阵转置的经典算法如下： void TransMatrix（Elemen
23、tType sourcenm, ElementType destmn）/*Source和和dest分别为被转置的矩阵和转置后的矩阵（用二维数组表示）分别为被转置的矩阵和转置后的矩阵（用二维数组表示）*/ int i, j;for(i=0;im;i+) for (j=0;jm= A.n ; B-n= A.m ; B-len= A.len ; if(B-len0) j=0; for(k=0; kA.n; k+) for(i=0; idataj.row=A.datai.col B-dataj.col=A.datai.row; B-dataj.e=A.datai.e; j+;时间复杂度分析时间复杂度分
24、析 算法的基本操作为将算法的基本操作为将M.data中的中的三元组赋值到三元组赋值到N.dataN.data，是，是在两个循环中完成的，故算法的时间复杂度在两个循环中完成的，故算法的时间复杂度为为O(n len) ) 我们知道，若用二维数组存储矩阵，转置算法我们知道，若用二维数组存储矩阵，转置算法1的时的时间复杂度为间复杂度为O（ m m n n） 。当非零元的个数。当非零元的个数len和矩阵元素和矩阵元素个数个数m m n n 同数量级时，转置运算算法同数量级时，转置运算算法1的时间复杂度为的时间复杂度为O（ m m n n n）。由此可见：在这种情况下，用。由此可见：在这种情况下，用三元组
25、三元组顺序表存储矩阵，顺序表存储矩阵，虽然可能节省了存储空间，但时间复杂虽然可能节省了存储空间，但时间复杂度提高了度提高了，因此算法仅适于，因此算法仅适于len m m n n的情况。的情况。 该算法效率不高的原因是：对为实现该算法效率不高的原因是：对为实现M M到到N N的转置，该的转置，该算法算法对对M.data进行了多次扫描。能否在对进行了多次扫描。能否在对M.data一次扫一次扫描的过程中，完成描的过程中，完成M到到N 的转置？的转置？方法二：快速转置算法方法二：快速转置算法 下面介绍转置运算算法称为快速转置算法下面介绍转置运算算法称为快速转置算法算法分析：算法分析： 在在A.data
26、中，中， A的各列非零元对应的三元组是以行为主序存储的，的各列非零元对应的三元组是以行为主序存储的，故故M的各列非零元对应的三元组存储位置不是的各列非零元对应的三元组存储位置不是“连续连续”的。然而，的。然而，A的的各列非零元三元组的存储顺序却与各列非零元在各列非零元三元组的存储顺序却与各列非零元在A中的顺序一致。中的顺序一致。 如：如：A的第一列非零元素是的第一列非零元素是 -3、15，它们对应的三元组在，它们对应的三元组在A.data 中的中的存储顺序也是（存储顺序也是（3，1，-3）在前（）在前（6，1，15）后。）后。如果能先求得如果能先求得A各列第一个非零元三元组在各列第一个非零元三
27、元组在B.data中的位置，就能在对中的位置，就能在对A.data一次扫描的过程中，完成一次扫描的过程中，完成A到到B 的转置：的转置： 对对A.data一次扫描时，一次扫描时， 首先遇到各列的第一个非零元三元组，可按先首先遇到各列的第一个非零元三元组，可按先前求出的位置，将其放至前求出的位置，将其放至B.data中，当再次遇到各列的非零元三元组时中，当再次遇到各列的非零元三元组时，只须顺序放到对应列元素的后面。，只须顺序放到对应列元素的后面。 A = 0 12 12 9 0 0 0 0 0 0 0 0 0 0 0-3-3 0 0 0 0 14 0 0 0 2424 0 0 0 0 0 18
28、18 0 0 0 0 01515 0 0 -7 0 0 0row col e0123456782 2 0 0 -3 -35 5 0 0 15 150 0 1 1 12 124 4 1 1 18 180 2 93 2 245 3 -72 5 14A.data678A.mA.nA.lenA的各列非零元三元组的存储顺序存储顺序与各列非零元在A中的顺序一致row col e0123456782 0 -35 0 150 1 124 1 180 2 93 2 245 3 -72 5 14A.data678A.mA.nA.lenrow col e0123456781 0 123 5 -70 2 -32 3
29、240 5 152 0 95 2 141 4 18B.data768B.mB.nB.len各列第一个非零元三元组按先前求出的位置，放至T.data中各列后续的非零元三元组，顺序放到对应列元素的后面辅助向量辅助向量num 、cpot 为先求得为先求得M各列第一个非零元三元组在各列第一个非零元三元组在N.data中的位置。引入两个辅助中的位置。引入两个辅助向量向量num 、 position ： numcol：存储第：存储第col列非零元个数列非零元个数 position col：存储第：存储第col列第一个非零元三元组在列第一个非零元三元组在N.data中的位置中的位置 positioncol的
30、计算方法：的计算方法： position 0=0 position col= position col-1+numcol-1 1 = collen= A.len ; B-n= A.m ; B-m= A.n ;if(B-len)for(col=0;col=A.n;col+) numcol=0; for(t=0;t=A.len;t+) numA.datat.col+; /*计算每一列的非零元素的个数计算每一列的非零元素的个数*/ position0=0;for(col=1;colA.n;col+) /*求求col列中第一个非零元素在列中第一个非零元素在B.data 中的正确位置中的正确位置*/po
31、sitioncol=positioncol-1+numcol-1; for(p=0;pdataq.row=A.datap.col; B-dataq.col=A.datap.row; B-dataq.e=A.datap.e positioncol+; colcolnumcolnumcolPOSITIONPOSITIONcolcol0 1 2 3 4 5 60 1 2 3 4 5 62 22 28 81 11 10 00 01 13 35 52 26 67 78 80 1 120 2 92 0 -32 5 143 2 244 1 185 0 155 3 -7row col erow col eM.
32、dataT.data1 0 12第2列第一个非零元在b中的位置第3列第一个非零元在b中的位置2 0 90 2 -35 2 142 3 241 4 180 5 153 5 -74 4第2列第二个非零元在b中的位置6 62 2快速转置算法图示第3列第二个非零元在b中的位置第1列第一个非零元在b中的位置2 24 47 70 0第4 列第一个非零元在b中的位置求各列第1个非零元在b中位置求各列非零元个数扫描M.data实现M到T 的转置时间复杂度分析时间复杂度分析 该算法利用该算法利用两个辅助向量两个辅助向量num 、cpot ，实现了，实现了对对M.data一次一次扫描完成扫描完成M到到T 的转置。
33、的转置。 从时间上看，算法中有从时间上看，算法中有四个并列的单循环，四个并列的单循环，循环次数分别为循环次数分别为n、len 、n和和len，因而总的时间复杂度为，因而总的时间复杂度为O（n+len)，在，在A的非零元个数的非零元个数len和和m n n 同等数量级时，其时间复杂度为同等数量级时，其时间复杂度为O( m m n)n) ，和转置算法，和转置算法1的时的时间复杂度相同。由此可见，只有当间复杂度相同。由此可见，只有当len m m n n时，使用时，使用快速转置算法才快速转置算法才有意义。有意义。for (col=1; col=A.n; +col) for (t=1; t=A.len
34、; +t) for (col=2; col=A.n; +col) for (p=1; p=A.len; +p) 用三元组表实现稀疏矩阵的乘法运算用三元组表实现稀疏矩阵的乘法运算 设矩阵设矩阵M是是m1n1矩阵，矩阵，N是是m2n2矩阵；若可矩阵；若可以相乘，则必须满足矩阵以相乘，则必须满足矩阵M的列数的列数n1与矩阵与矩阵N的行数的行数m2相等，才能得到结果矩阵相等，才能得到结果矩阵Q=MN（一个（一个m1n2的矩阵）。的矩阵）。 数学中矩阵数学中矩阵Q中的元素的计算方法如下：中的元素的计算方法如下： Qij = MikNkj n1 k=1其中：其中：1im1，1jn2 根据数学上矩阵相乘的原
35、理，我们可以得到矩根据数学上矩阵相乘的原理，我们可以得到矩阵相乘的经典算法：阵相乘的经典算法：for(i=1;i=m1;i+) for(j=1;j=n2;j+) Qij=0; for(k=1;km=M.m; Q-n=N.n; Q-len=0; if(M.len*N.len!=0) for(arow=1; arow=M.m; arow+) /*逐行处理逐行处理M*/for(p=1;pfirstarow=Q-len+1; for(p=M.firstarow;pM.firstarow+1;p+) /*p指向指向M当前行当前行中每一个非零元素中每一个非零元素*/brow=M.datap.col; /*
36、 M中的列号应与中的列号应与N中的行号相等中的行号相等*/ if(browN.n) t=N.firstbrow+1; else t=N.len+1; for(q=N.firstbrow;qt;q+) ccol=N.dataq.col; /*乘积元素在乘积元素在Q中列号中列号*/ctempccol+=M.datap.e*N.dataq.e; /* for q */ /*求得求得Q中第中第crow行的非零元行的非零元*/for(ccol=1;ccoln；col+) /*压缩存储该非零元压缩存储该非零元*/if(ctempccol) if(+Q-lenMAXSIZE) return 0; Q-dat
37、aQ-len=arow, ccol, ctempccol; /* if */ /* for arow */ /*if*/ return(TRUE); /*返回返回TRUE表示求矩阵乘积成功表示求矩阵乘积成功*/ 2. 稀疏矩阵的链式存储结构：十字链表稀疏矩阵的链式存储结构：十字链表优点：它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产优点：它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算。生的新的零元素，实现矩阵的各种运算。在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除
38、了（row，col，value）以外，还要有两个域：）以外，还要有两个域：right： 用于链接同一行中的下一个非零元素；用于链接同一行中的下一个非零元素；down：用以链接同一列中的下一个非零元素。：用以链接同一列中的下一个非零元素。rowcolvaluedownright十字链表中结点的结构示意图：十字链表中结点的结构示意图：M.cheadM.rhead3 0 0 50 -1 0 02 0 0 01 1 31 4 52 2-13 1 2 十字链表的结构类型说明如下：十字链表的结构类型说明如下：typedef struct OLNode int row, col; /*非零元素的行和列下标非
39、零元素的行和列下标*/ ElementType value; struct OLNode * right,*down; /*非零元素所在行表列表的后继链域非零元素所在行表列表的后继链域*/ OLNode; *OLink; typedef struct OLink * row_head, *col_head; /*行、列链表的头指针向量行、列链表的头指针向量*/ int m, n, len; /*稀疏矩阵的行数、列数、非零元素的个数稀疏矩阵的行数、列数、非零元素的个数*/CrossList; 建立稀疏矩阵的十字链表算法：建立稀疏矩阵的十字链表算法：CreateCrossList (CrossLi
40、st * M)/*采用十字链表存储结构，创建稀疏矩阵采用十字链表存储结构，创建稀疏矩阵M*/ if(M!=NULL) free(M); scanf(“%d%d%d”&m,&n,&t); /*输入输入M行数、列数和非零元的个数行数、列数和非零元的个数*/ M-m=m;M-n=n;M-len=t; if(!(M-row_head=(Olink*)malloc(m+1)sizeof(OLink) exit(OVERFLOW); if(!(M-col_head=(OLink * )malloc(n+1)sizeof(OLink) exit(OVERFLOW); M-row_head =M-col_he
41、ad =NULL; /*初始化行、列头指针向量，各行、列链表为空的链表初始化行、列头指针向量，各行、列链表为空的链表*/scanf(“%d%d%d”&i,&j,&e);while(i!=0) if(!(p=(OLNode *) malloc(sizeof(OLNode) exit(OVERFLOW); p-row=i;p-col=j;p-value=e; /*生成结点生成结点*/ if(M-row_headi=NULL) M-row_headi=p; else /*寻找行表中的插入位置寻找行表中的插入位置*/for(q=M-row_headi; q-right&q-right-colright
42、) p-right=q-right; q-right=p; /*完成插入完成插入*/ if(M-col_headj=NULL) M-col_headj=p; else /*寻找列表中的插入位置寻找列表中的插入位置*/ for(q=M-col_headj; q-down&q-down-rowdown) p-down=q-down; q-down=p; /*完成插入完成插入*/ scanf(“%d%d%d”&i,&j,&e); 5.4 广义表广义表 广义表也是线性表的一种推广。广义表也是广义表也是线性表的一种推广。广义表也是n n个数据元素个数据元素（d d1 1，d d2 2，d d3 3，d
43、dn n）的有限序列，但不同的是，广义表中）的有限序列，但不同的是，广义表中的的d di i既可以是单个元素，还可以是一个广义表，既可以是单个元素，还可以是一个广义表，通常记作：通常记作：GL=GL=（d d1 1，d d2 2，d d3 3，d dn n）。）。GLGL是广义表的名字，通常用大是广义表的名字，通常用大写字母表示。写字母表示。n n是广义表的长度。是广义表的长度。若若 d di i是一个广义表，则称是一个广义表，则称d di i是广义表是广义表GLGL的子表。的子表。 在在GLGL中，中， d d1 1是是GLGL的表头，其余部分组的表头，其余部分组成的表（成的表（d d2 2
44、，d d3 3，d dn n）称为称为GLGL的表尾。由此可见，广义表的表尾。由此可见，广义表的定义是递归定义的。的定义是递归定义的。广义表广义表 LS = ( 1, 2, , n )的结构特点的结构特点:1) 广义表中的数据元素有相对次序次序；2) 广义表的长度长度定义为最外层包含元素个数；3) 广义表的深度深度定义为所含括弧的重数； 注意：“原子”的深度为 0 “空表”的深度为 1 4) 广义表可以共享共享；5) 广义表可以是一个递归递归的表。 递归表的深度是无穷值，长度是有限值。6) 任何一个非空广义表非空广义表 LS = ( 1, 2, , n) 均可分解为 表头表头 Head(LS)
45、 = 1 和 表尾表尾 Tail(LS) = ( 2, , n) 两部分。例如例如: D = ( E, F ) = (a, (b, c)，F )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( ) l l D=（）（） 空表；其长度为零。空表；其长度为零。l l
46、A=(a，(b，c)表长度为表长度为2的广义表，其中第一个元素是单个的广义表，其中第一个元素是单个数据数据a，第二个元素是一个子表（，第二个元素是一个子表（b，c）。）。l lB=（A，A，D）长度为）长度为3的广义表，其前两个元素为表的广义表，其前两个元素为表A，第三个元素为空表第三个元素为空表D。l lC=（a，C） 长度为长度为2递归定义的广义表，递归定义的广义表，C相当于无穷相当于无穷表表C=（a，（，（a，（，（a，（，（）。）。 例如：例如：head(A)=a 表表A的表头是的表头是a。tail(A)=(b，c) 表表A的表尾是的表尾是(b，c) ，广义表的表尾一定，广义表的表尾一
47、定是一个表。是一个表。从上面的例子可以看出：从上面的例子可以看出：（1）广义表的元素可以是子表，而子表还可以是子表）广义表的元素可以是子表，而子表还可以是子表，由，由此，广义表是一个多层的结构。此，广义表是一个多层的结构。 （2）广义表可以被其他广义表共享。如：广义表）广义表可以被其他广义表共享。如：广义表B就共享表就共享表A。在表。在表B中不必列出表中不必列出表A的内容，只要通过子表的名称就可的内容，只要通过子表的名称就可以引用该表。以引用该表。 （3）广义表具有递归性，如广义表）广义表具有递归性，如广义表C。 广义表中有两类结点广义表中有两类结点:一类是单个元素结点，一类是子表结点。一类是
48、单个元素结点，一类是子表结点。任何一个非空的广义表都可以将其分解成表头和表尾任何一个非空的广义表都可以将其分解成表头和表尾两部分，反之，一对确定的表头和表尾可以唯一地确两部分，反之，一对确定的表头和表尾可以唯一地确定一个广义表。定一个广义表。一个表结点可由三个域构成一个表结点可由三个域构成：标志域，指向表头的指：标志域，指向表头的指针域，指向表尾的指针域。而元素结点只需要两个域：针域，指向表尾的指针域。而元素结点只需要两个域：标志域和值域。标志域和值域。 通常采用头、尾指针的链表结构通常采用头、尾指针的链表结构表结点表结点:原子结点：原子结点：tag=0 datatag=1 hp tp 1)
49、表头、表尾分析法：构造存储结构的两种分析方法构造存储结构的两种分析方法: :若表头为原子，则为若表头为原子，则为空表空表 ls=NIL非空表非空表 lstag=1 指向表头的指针指向表尾的指针tag=0 data否则，依次类推。否则，依次类推。例如例如:L=(a, (x, y), (x) ) a (x, y), (x) ) (x, y) ( (x) ) x (y) (x) ( ) y ( ) (x) ( ) x ( )L = ( a, ( x, y ), ( ( x ) ) )a ( x, y ) ( ) 1 LL = ( )0 a 1 0 x 1 ( )x 0 x 0 y 1 1 1 1 2
50、) 子表分析法：若子表为原子，则为若子表为原子，则为空表空表 ls=NIL非空表非空表 1 指向子表1 的指针tag=0 data否则，依次类推。否则，依次类推。 1 指向子表2 的指针 1 指向子表n 的指针ls D 111Ac0b0a0 11 111BCa0广义表广义表A、B、C、D的存储结构图的存储结构图 广义表的头尾链表存储结构：广义表的头尾链表存储结构： typedef enum ATOM, LIST ElemTag; typedef struct GLNode ElemTag tag; union AtomType atom; struct struct GLNode * hp,
