第五章数组和广义表

《第五章数组和广义表》由会员分享，可在线阅读，更多相关《第五章数组和广义表（57页珍藏版）》请在金锄头文库上搜索。

1、数据结构数据结构第一页，编辑于星期五：十八点 三十六分。 第五章第五章 数组和广义表数组和广义表n n5.1 数组的定义n n5.2 数组的顺序表示和实现n n5.3 矩阵的压缩存储5.3.1 特殊矩阵5.3.2 稀疏矩阵5.4 广义表的定义5.5 广义表的存储结构第二页，编辑于星期五：十八点 三十六分。数组和广义表可看成是一种特殊的线性表，数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数组元素本身也是一种线性其特殊在于，表中的数组元素本身也是一种线性表。表。5.1 数组的定义数组是我们最熟悉的数据类型，在早期的数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据

2、类型。高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：是向量的推广。例如，二维数组：a a1111 a a1212 a a1n1n a a2121 a2222 a a2n2n am1m1 a am2m2 a amnmn Amn=第三页，编辑于星期五：十八点 三十六分。可以看成是由个行向量组成的向量，也可以看成是个可以看成是

3、由个行向量组成的向量，也可以看成是个列向量组成的向量。列向量组成的向量。 在在C C语言中，一个二维数组类型可以定义为其分量类语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，型为一维数组类型的一维数组类型，也就是说， typedef Elemtype Array2mn;typedef Elemtype Array2mn; 等价于： typedef Elemtype Array1n;typedef Elemtype Array1n; typedef Array1 Array2m; 同理，一个n n维数组类型可以定义为其数据元素为维数组类型可以定义为其数据元素为

4、n-1n-1维数组类型的一维序组类型。维数组类型的一维序组类型。 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。第四页，编辑于星期五：十八点 三十六分。 5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。 第五页，编辑于星期五：十八点 三十六分。通常有两种顺序存储方式

5、：行优先顺序行优先顺序将数组元素按行排列，第将数组元素按行排列，第i+1i+1个行向量紧个行向量紧接在第接在第i i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： a a1111,a,a1212,a,a1n1n,a,a2121,a,a2222,a2n2n,a,am1m1,am2m2,a,amn 在在PASCALPASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序列优先顺序将数组元素按列向量排列，第将数组元素按列向量排列，第j+1j+1个列个列向量紧接在第向量紧接在第j j个列向量之后，个列向量之后，A A的的m*n个元素按列优先顺序存储的线性序列为：a1111,a,a2

6、121,a,am1,a,a1212,a2222,am2m2,an1n1,a,an2n2,a,anm在在FORTRANFORTRAN语言中，数组就是按列优先顺序存储的。语言中，数组就是按列优先顺序存储的。第六页，编辑于星期五：十八点 三十六分。 以上规则可以推广到多维数组的情况：行优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。 按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以

7、在相同的时间内存取，即顺序存储的数组是一个随机存取结构。第七页，编辑于星期五：十八点 三十六分。例如，二维数组例如，二维数组A1.b1,1.b2按按“行优先顺序行优先顺序”存存储在内存中，假设每个元素占用储在内存中，假设每个元素占用L L个存储单元。个存储单元。 元素aijij的存储地址应是数组的基地址加上排在a aij前面的元素所占用的单元数。因为前面的元素所占用的单元数。因为a aijij位于第i i行、第j j列，前面列，前面i-1i-1行一共有行一共有(i-1) b2 2个元素（ b b2 2是数组第二维的下界），第i i行上a aijij前面又有前面又有j-1个元素，故它前面一共有(

8、i-1) b(i-1) b2 2+j-1个元素，因此，个元素，因此，a aijij的地址计算函数为： LOC(aLOC(aij)=LOC(a)=LOC(a1111)+(i-1)*b)+(i-1)*b2+j-1*L+j-1*L同样，三维数组同样，三维数组Aijkijk按按“行优先顺序行优先顺序”存储，其地址计存储，其地址计算函数为：算函数为：LOC(aijkijk)=LOC(a)=LOC(a111111)+(i-1)*b)+(i-1)*b2*b*b3 3+(j-1)*b+(j-1)*b3 3+(k-1)*L+(k-1)*L第八页，编辑于星期五：十八点 三十六分。 上述讨论均是假设数组各维的下界是

9、1，更一般的二维数组是Ac1.b1,c2.b2，这里c1,c2不一定是1。aij前一共有i-c1行，二维数组一共有b2-c2+1列，故这i-c1行共有(i-c1)*(b2-c2+1)个元素，第i行上aij前一共有j-c2个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(ac1c2)+(i-c1)*(b2-c2+1)+j-c2)*L 例如，在C语言中，数组各维下标的下界是0，b长度的数组下标为0.b-1。因此在C语言中，二维数组ab1b2的地址计算公式为： LOC(aij)=LOC(a00)+(i*b2+j)*L 第九页，编辑于星期五：十八点 三十六分。n n推广：已知n维数组每

10、维长度分别为b1,b2,bn.，每个元素占L个存储单元，则：LOC( j1,j2,jn )=LOC(0,0,0)+(b2*b3*bn*j1+b3*bn*j2+bn*jn-1+jn)*L=LOC(0,0,0)+(c1*j1+c2*j2+cn-1*jn-1+cn*jn) n n其中: cnL，ci-1=bi*ci , 2=i=n第十页，编辑于星期五：十八点 三十六分。数组的顺序存储表示与实现：#include #define MAX_DIM 8typedef struct / 数组结构Elemtype *base; / 数组元素基址int dim; /数组维数int *bounds; /数组维界基

11、址int *constants; /数组映象函数常量基址 Array; /此结构表示的优点可以实现去态维数的数组Status Initarray(Array &A,int dim , )/数组初始化if (dimMAX_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim*sizeof(int); if (!A.bounds) exit(OVERFLOW); elemtotal=1;/计算数组元素总个数第十一页，编辑于星期五：十八点 三十六分。va_start(ap, dim);for(i=0;idim;i+)A.boundsi=va

12、_arg(ap, int); if (A.boundsi=0;i-)A.constantsi=A.boundsi+1*A.constantsi+1;return OK;第十二页，编辑于星期五：十八点 三十六分。Status Destory(Array &A)if (!A.base) return ERROR; free(A.base);A.base=NULL; if (!A.bounds) return ERROR; free(A.bounds);A.bounds=NULL; if (!A.constants) return ERROR; free(A.constants); A.consta

13、nts=NULL;Status Locate(Array A,va_list ap, int &off)/求元素在A中的相对地址放在off中,元素下标存放在ap中。 off=0; for(i=0;iA.dim;i+) ind= va_arg(ap, int); if(ind=A.boundsi) return OVERFLOW; off+=A.constantsi*ind; return OK;第十三页，编辑于星期五：十八点 三十六分。Status Value(array A,Elemtype &e, )va_start(ap, e);if(result=Locate(A,ap,off)=0)

14、 return result;e=*(A.base+off);return OK;Status Assign(Array &A,Elemtype e, )va_start(ap, e);if(result=Locate(A,ap,off)=0) return result;*(A.base+off) = e;return OK;第十四页，编辑于星期五：十八点 三十六分。 5.3 矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的数学在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述

15、为一个二维数组。矩阵在这种存就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为运算也非常简单，并且存储的密度为1 1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为大量的零元素的情况下，看起来存储密度仍为1 1，但，但实际上占用了许多单元去存储重复的非零元素或实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大浪费，为了节零元素，这对高阶矩阵会造成极大浪费，为了节省存

16、储空间，我们可以对这类矩阵进行压缩存储：省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。对零元素不分配空间。第十五页，编辑于星期五：十八点 三十六分。特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1 1、对称矩阵、对称矩阵 在一个n n阶方阵A A中，若元素满足下述性质： aij=a=aji 1i,jn 1i,jn则称则称A为对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空

17、间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先第十六页，编辑于星期五：十八点 三十六分。顺序顺序”存储主对角线（包括对角线）以下的元素，其存储形存储主对角线（包括对角线）以下的元素，其存储形式如图所示：式如图所示：1 5 1 3 7 a1 5 1 3 7 a1111 5 0 8 0 0 a 5 0 8 0 0 a2121 a a 22 22 1 8 9 2 6 a 1 8 9 2 6 a3131 a a3232 a a3333 3 0 2 5 1 . 3 0 2 5 1 . 7 0 6 1 3 a 7 0 6 1 3 an 1n 1 a a n 2 n 2 a a n 3n 3

18、a a n nn n 图图 5.1 5.1 对称矩阵对称矩阵在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i i个元素，元素总个元素，元素总数为：数为： 1+2+n=n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量素存放在一个向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中。为了便于中。为了便于访问对称矩阵访问对称矩阵A A中的元素，我们必须在中的元素，我们必须在a aij和和sak sak 第十七页，编辑于星期五：十八点 三十六分。之间找一个对应关系。 若ij，则ai j在下三角形中。 ai

19、j之前的i-1行（从第1行到第i-1行）一共有1+2+i-1=i(i-1)/2个元素，在第i行上， ai j之前恰有j-1个元素（即ai1,ai2,ai j-1），因此有： k=i*(i-1)/2+j-1 0kn(n+1)/2 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j-1)/2+i-1 0 kn(n+1)/2 令 i=max(i,j)， j=min(i,j)，则k和 i, j的对应关系可统一为： k=i*(i-1)/2+j-1 0 kn(n+1)/2 第十八页，编辑于星期五：十八点 三十六分。因此，aij的地址可用下列式

20、计算： LOC(aij)=LOC(sak) =LOC(sa0)+k*L=LOC(sa0)+i*(i-1)/2+j-1*L 有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在sak中找到矩阵元素aij，反之，对所有的k=0,1,2,n(n-1)/2-1，都能确定sak中的元素在矩阵中的位置(i,j)。由此，称san(n+1)/2为阶对称矩阵A的压缩存储，见下图：k=0 1 2 3 n(n-1)/2 n(n+1)/2-1a11a21a22a31an 1 an,n第十九页，编辑于星期五：十八点 三十六分。2、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的

21、下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。 a11 a12 a 1 n a11 c c c a21 a 2 n a21 a22 c . . c c a n n an 1 an 2 .an n (a)上三角矩阵 (b)下三角矩阵 图5.2 三角矩阵第二十页，编辑于星期五：十八点 三十六分。三角矩阵中的重复元素c c可共享一个存储空间，其可共享一个存储空间，其余的元素正好有余的元素正好有n(n+1)/2n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa0.n(n+1)/2sa0.n(n+1)/2中，其中中

22、，其中c c存放在向量的存放在向量的最后一个分量中。最后一个分量中。3 3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。如的若干条对角线上的元素之外，其余元素皆为零。如P96P96图图5.4 00第二十一页，编辑于星期五：十八点 三十六分。上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系

23、，仍能对矩阵的元素进行随机存取。 5.3.2 稀疏矩阵 什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。第二十二页，编辑于星期五：十八点 三十六分。精确点，设在的矩阵A中，有t个非零元素。令=t/(m*n)，称为矩阵的稀疏因子。通常认为e0.05时称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组

24、及其行列数唯一确定。第二十三页，编辑于星期五：十八点 三十六分。例如，下列三元组表(1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7) 加上加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。 0 12 9 0 0 0 0 0 0 -3 0 0 150 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0

25、0 14 0 9 0 0 24 0 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 0 0 24 0 0 0 0 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 图图5.5 5.5 稀疏矩阵稀疏矩阵M M和和T TM=T=第二十四页，编辑于星期五：十八点 三十六分。一、三元组顺序表 假设

26、以顺序存储结构来表示三元组表，则可得到假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法稀疏矩阵的一种压缩存储方法三元顺序表。三元顺序表。 #define MAXSIZE 12500#define MAXSIZE 12500 typedef struct typedef struct int i,j; int i,j; ElemType e; ElemType e; Triple; typedef struct Triple dataMAXSIZE+1; int mu,nu,tu; int mu,nu,tu; TSMatrix; TSMatrix;第二十五页，编辑于星期五：十

27、八点 三十六分。图图5.55.5中所示的稀疏矩阵中所示的稀疏矩阵M M及其对应转置矩阵及其对应转置矩阵T T的三元的三元组的表示分别为：组的表示分别为： i i j v j v 1 2 12 1 2 12 1 3 9 1 3 9 3 1 -3 3 1 -3 3 6 14 3 6 14 4 3 24 4 3 24 5 2 18 5 2 18 6 1 15 6 1 15 6 4 -7 i j v1 3 -31 3 -31 6 152 1 122 5 182 5 183 1 93 4 243 4 244 6 -74 6 -76 3 14 6 3 14 第二十六页，编辑于星期五：十八点 三十六分。下面

28、以矩阵的转置为例，说明在这种压缩存储结下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。构上如何实现矩阵的运算。 一个一个mnmn的矩阵的矩阵A，它的转置，它的转置B B是一个是一个nmnm的矩阵，的矩阵，且且aij=bjiaij=bji，1im1im，1jn1jn，即，即A A的行是B B的列，的列，A的列是B的行。的行。 将将A A转置为转置为B B，就是将，就是将A的三元组表的三元组表a.dataa.data置换为表置换为表B B的三元组表的三元组表b.datab.data，如果只是简单地交换a.dataa.data中中i i和和j j的内容，那么得到的b.datab.d

29、ata将是一个按列优将是一个按列优先顺序存储的稀疏矩阵先顺序存储的稀疏矩阵B B，要得到按行优先顺序存储的b.datab.data，就必须重新排列三元组的顺序。 由于由于A的列是的列是B的行，因此，按的行，因此，按a.dataa.data的列序转的列序转置，所得到的转置矩阵置，所得到的转置矩阵B B的三元组表的三元组表b.datab.data必定是按行必定是按行优先存放的。优先存放的。第二十七页，编辑于星期五：十八点 三十六分。按这种方法设计的算法，其基本思想是：对按这种方法设计的算法，其基本思想是：对A A中的每一中的每一列列 col(1coln)，通过从头至尾扫描三元表，通过从头至尾扫描三

30、元表a.data，找出所有列号等于，找出所有列号等于colcol的那些三元组，将它们的行号和列号互换后依次放入b.datab.data中，中，即可得到即可得到B B的按行优先的压缩存储表示。的按行优先的压缩存储表示。第二十八页，编辑于星期五：十八点 三十六分。Status TransposeSMatrix( TSMatrix M0,TSMatrix &T)Status TransposeSMatrix( TSMatrix M0,TSMatrix &T)T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu

31、)q=1;q=1;for(col=1;col=M.nu;col+)for(col=1;col=M.nu;col+) for(p=0;p=M.tu;p+)for(p=0;p=M.tu;p+) if(M.datap.j=col)if(M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; q+; return OK;return OK; 第二十九页，编辑于星期五：十八点 三十六分。分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(nu*tu)，即矩阵的列数和非零元的个

32、数的乘积成正比。而一般传统矩阵的转置算法为： for(col=1;col=nu;+col) for(row=1;row=mu;+row) Tcolrow=Mrowcol; 其时间复杂度为O(mu*nu)。当非零元素的个数t和mu*nu同数量级时，算法TransposeSMatrix的时间复杂度为O(mu*nu2)。第三十页，编辑于星期五：十八点 三十六分。三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于t=m*n的情况。下面给出另外一种称之为快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入

33、B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。第三十一页，编辑于星期五：十八点 三十六分。为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。 为此，需要设置两个一维数组num1.n和cpot1.nnum1.n：统计M中每列非零元素的个数，例如num11记录第记录第1列非零元素的个数。第三十二页，编辑于星期五：十八点 三十六分。 cpot1.n：由递推

34、关系得出M中的每列第一个非零元素在B中的位置。 算法通过cpot数组建立位置对应关系： cpot1=1 cpotcol=cpotcol-1+numcol-1 2=col=a.n 例如：图5.4中的矩阵M和相应的三元组A可以求得numcol和 cpotcol的值如下： col 1 2 3 4 5 6 7 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 9第三十三页，编辑于星期五：十八点 三十六分。12 v A i j v第一列元素个数 第二列元素个数 第三列元素个数numcpotq=cpotcol 21vpqcol=2第三十四页，编辑于星期五：十八点 三十六分。

35、Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T)Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) if (T.tu)for (col=1;col=M.nu;+col) numcol=0;for (col=1;col=M.nu;+col) numcol=0;for (t=1;t=M.tu;+t) +numM.datat.j;for (t

36、=1;t=M.tu;+t) +numM.datat.j;cpot1=1;cpot1=1;for (col=2;col=M.nu;+col) cpotcol=cpotcol-for (col=2;col=M.nu;+col) cpotcol=cpotcol-1+numcol-1;1+numcol-1;for (p=1;p=M.tu; +p)for (p=1;p=M.tu; +p)col=M.datap.j; q=cpotcol;col=M.datap.j; q=cpotcol;T.dataq.i=M.datap.j; T.dataq.j=M.datap.i;T.dataq.i=M.datap.j

37、; T.dataq.j=M.datap.i;T.dataq.e=M.datap.e; +cpotcol;T.dataq.e=M.datap.e; +cpotcol; return OK;return OK; 第三十五页，编辑于星期五：十八点 三十六分。算法分析这个算法仅比前一个算法多用了两个辅助向量，然而其时间复杂度降为O(nu+tu)，当tu和mu*nu等数量级时，其时间复杂度为O(mu*nu)，与经典算法的时间复杂度相同。第三十六页，编辑于星期五：十八点 三十六分。二、带行表的三元组 有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组

38、表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。其类型描述如下：第三十七页，编辑于星期五：十八点 三十六分。typedef struct triple dataMAXSIZE+1; int rposMAXRC+1; int mu,nu,tu; RLSMatrix; 下面讨论两个稀疏矩阵相乘的例子，容易看出这种下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。表示方法的优越性。第三十八页，编辑于星期五：十八点 三十六分。两个矩阵相乘的经典算法也是大家所熟悉的。若两个矩阵相乘的经典算法也是大家所熟悉的。若设设Q=

39、M*NQ=M*N 其中，其中，MM是是m1*n*n1矩阵，N是是mm2 2*n*n2 2矩阵。矩阵。当当n n1 1=m=m2 2时有：时有：for(i=1;i=m1;+i)for(i=1;i=m1;+i) for(j=1;j=n2;+j) qij=0； for(k=1;k=n1;+k) for(k=1;k=n1;+k) qij+=mik*nkj; qij+=mik*nkj; 此算法的复杂度为此算法的复杂度为O(mO(m1 1*n1 1*n2 2)。第三十九页，编辑于星期五：十八点 三十六分。当当M和和N是稀疏矩阵并用三元组表存储结构时，就不能套是稀疏矩阵并用三元组表存储结构时，就不能套用上述

40、算法。假设用上述算法。假设M和N N分别为：分别为：30 5 040 -1 0 052 0 0 0M= 0 2 1 0-2 4 0 0N=则Q=M*N为： -10 26 -1 0 0 4Q=第四十页，编辑于星期五：十八点 三十六分。它们的三元组分别为：i j e i j e i j e 1 1 3 1 2 2 1 1 -10 1 3 5 2 1 1 1 2 26 3 2 -1 3 1 -2 2 1 -1 3 1 2 3 2 4 3 2 4 M.data N.data Q.data第四十一页，编辑于星期五：十八点 三十六分。稀疏矩阵相乘的基本思想是：为了扫描M M一次就可以一次就可以实现算法，在

41、处理实现算法，在处理M M的每个元素时，求出该元素对的每个元素时，求出该元素对Q Q的可能贡献。得到了该元素的所有贡献，也就不用再次访问该元素了。比如对于M中的（中的（1,31,3，5 5），这个元素对Q Q中的（中的（1,1）位置贡献-10-10，对，对Q Q中的中的（1,21,2）位置贡献）位置贡献2020。也就是说，对于。也就是说，对于M M中每个元素中每个元素M M，找到N N 中所有满足（中所有满足（M M的列等于的列等于N的行）条件的元素，求得它们的乘积。这个乘积会对Q Q中的某个位中的某个位置有所贡献。注意到，这个贡献只是置有所贡献。注意到，这个贡献只是Q Q中该位置最终中该位置

42、最终结果的一部分。为了便于操作，为结果的一部分。为了便于操作，为Q Q的每一位置各设的每一位置各设一累加变量，其初值为零，然后扫描数组一累加变量，其初值为零，然后扫描数组M，求得相，求得相应元素的乘积并累加到适当的累加变量上。应元素的乘积并累加到适当的累加变量上。第四十二页，编辑于星期五：十八点 三十六分。（1 1）由于）由于MM中的每一行，只和Q中的相应行有关。每处理MM的一行，就得到的一行，就得到QQ的相应行，因此可以对MM进行逐行处理。为了找到进行逐行处理。为了找到M中同一行的所有元素，可中同一行的所有元素，可以利用以利用MM的的rposrpos值。值。（2 2）为求QQ的值，只需在的值

43、，只需在M.dataM.data和和N.data中找到中找到相应的各对元素（即相应的各对元素（即M.dataM.data中的中的j值和值和N.dataN.data中的中的i i值值相等的各对元素）相乘即可。为了找到相等的各对元素）相乘即可。为了找到N N中匹配的所有中匹配的所有数据，可以利用数据，可以利用N N的的rposrpos值。值。（3 3）对QQ的每一个元素设计一累计和的变量，其初值的每一个元素设计一累计和的变量，其初值为零，其累加值为零，其累加值Qij也可能为零。因此乘积矩阵也可能为零。因此乘积矩阵QQ中的元素是否为非零元，只有在求得其累加值后才能得知。因此，额外设计一中间数组tem

44、ptemp，先求得累计求和的中间结果放到先求得累计求和的中间结果放到temptemp（QQ的一行），的一行），然后再压缩到然后再压缩到Q.data中去第四十三页，编辑于星期五：十八点 三十六分。 计算计算QM M N N的过程大致如下：的过程大致如下：Q初始化；初始化；if (Q是非零矩阵是非零矩阵) /) /逐行求积逐行求积for (arow=1; arow=M.mu; +arow) for (arow=1; arow=0n=0个元素个元素a a1 1,a,a2,a,a3 3,a,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元

45、素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。 广义表是广义表是n(n=0)个元素个元素a1,a2 2,a3,an的有限序的有限序列，其中列，其中a ai i或者是原子项，或者是一个广义表。通常或者是原子项，或者是一个广义表。通常记作记作LS=LS=（a a1 1,a2 2,a,a3 3,an) )。LSLS是广义表的名字，n为它的长度，当n=0n=0时为空表。若a ai i是广义表，则称它为LSLS的子表。的子表。广义表的深度指的是广义表中括弧的重数。广义表的深度指的是广义表中括弧的重数。第四十七页，编辑于星期五：十八点 三十六分。n n通常用圆括号将广义表括起来，用逗号分

46、隔其中的元素。通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区别原子和广义表，书写时用大写字母表示广义表，为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表用小写字母表示原子。若广义表LSLS（n=1)非空，则非空，则a1a1是是LS的表头，其余元素组成的表的表头，其余元素组成的表(a2,an)(a2,an)称为称为LSLS的表的表尾。尾。n n显然广义表是递归定义的，因为在定义广义表时又用显然广义表是递归定义的，因为在定义广义表时又用到了广义表的概念。广义表的例子如下：到了广义表的概念。广义表的例子如下：n n(1)A=(1)A=（）（）AA是一个空表，其

47、长度为零。是一个空表，其长度为零。n n(2)B=(2)B=（e e）表表B B只有一个原子只有一个原子e e，B B的长度为的长度为1 1。n n(3)C=（a,(b,c,d)a,(b,c,d)表表C C的长度为的长度为2 2，两个元素分别为原子a a和子表和子表(b,c,d)(b,c,d)。n n(4)D=(4)D=（A，B B，C C）表表D D的长度为的长度为3，三个元素，三个元素A,B,CA,B,C都是广义表。显然，将子表的值代入后，则有都是广义表。显然，将子表的值代入后，则有D=( D=( ),(e),(a,(b,c,d),(e),(a,(b,c,d)。第四十八页，编辑于星期五：十

48、八点 三十六分。n n(5)E=(5)E=（a, E）这是一个递归的表，它的长度为这是一个递归的表，它的长度为2 2，E相当于一个无限的广义表相当于一个无限的广义表E=(a,(a,(a,(a,).E=(a,(a,(a,(a,).从上述定义和例子可推出广义表的三个性质：从上述定义和例子可推出广义表的三个性质：n n广义表的元素可以是子表，而子表的元素还可以是子表。由此，广义表是一个多层次的结构，可以用图形象地表示。P108P108n n广义表可为其它表所共享。例如在上述例（广义表可为其它表所共享。例如在上述例（4 4）中，）中，广义表广义表A A，B B，C为为D D的子表，则在的子表，则在D

49、D中可以不必列出子表的值，而是通过子表的名称来引用。n n广义表可以是一个递归的表，如例（5 5）。第四十九页，编辑于星期五：十八点 三十六分。n n由表头、表尾的定义可知：任何一个非空广义表其表由表头、表尾的定义可知：任何一个非空广义表其表头可能是广义表，也可能是广义表，而其表尾必定是头可能是广义表，也可能是广义表，而其表尾必定是广义表。广义表。对于对于B=(e)B=(e) GetHead(B)=e, GetTail(B)=()GetHead(B)=e, GetTail(B)=()对于对于D D(A,B,C)(A,B,C) GetHead(D)=A, GetTail(D)=(B,C)GetH

50、ead(D)=A, GetTail(D)=(B,C)由于(B,C)(B,C)为非空广义表，则可继续分解得到：为非空广义表，则可继续分解得到：GetHead(B,C)=B GetTail(B,C)=(C)GetHead(B,C)=B GetTail(B,C)=(C)n n 注意广义表（）和( ( ) )( ( ) )不同。前者是长度为不同。前者是长度为0 0的空的空表，对其不能做求表头的和表尾的运算；而后者是表，对其不能做求表头的和表尾的运算；而后者是长度为长度为1 1的非空表（只不过该表中唯一的一个元素是空的非空表（只不过该表中唯一的一个元素是空表）。对其可进行分解，得到表头和表尾均为空表（表

51、）。对其可进行分解，得到表头和表尾均为空表（ ）。）。第五十页，编辑于星期五：十八点 三十六分。n n5.5 5.5 广义表的存储结构广义表的存储结构n n由于广义表由于广义表(a1,a2,a3,an)(a1,a2,a3,an)中的数据元素可以具有不同的结构（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。n n由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。下面介绍两种广义表的链式存储结构。n n1、表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子域只需两个域：标

52、志域和值域。n n表结点表结点原子结点原子结点 tag=1 hp tp tag=0 atom第五十一页，编辑于星期五：十八点 三十六分。广义表的头尾链表存储表示广义表的头尾链表存储表示typedef enumATOM, LIST ElemTag;/ATOM=0typedef enumATOM, LIST ElemTag;/ATOM=0表示原子，LISTLIST1 1表示子表表示子表typedef struct GLNodetypedef struct GLNodeElemTag tag;ElemTag tag;unionunionAtomType atom;struct struct GLNo

53、de *hp, *tp; ptr; /ptrstruct struct GLNode *hp, *tp; ptr; /ptr是表结点是表结点的指针域，的指针域，ptr.hpptr.hp和和ptr.tpptr.tp分别指示表头和表尾。分别指示表头和表尾。; ;*GList;*GList;第五十二页，编辑于星期五：十八点 三十六分。第五十三页，编辑于星期五：十八点 三十六分。 tag=1 hp tp tag=0 atom tp2 2广义表的扩展线性链表存储表示，如下图广义表的扩展线性链表存储表示，如下图: :表结点原子结点第五十四页，编辑于星期五：十八点 三十六分。广义表的扩展线性链表存储表示：t

54、ypedef enum ATOM, LISTElemTag;typedef enum ATOM, LISTElemTag;typedef struct GLNodetypedef struct GLNodeElemTag tag;unionunionAtomType atom;struct GLNode *hp;struct GLNode *hp; ;struct GLNode *tp;struct GLNode *tp;*GList;*GList;第五十五页，编辑于星期五：十八点 三十六分。第五十六页，编辑于星期五：十八点 三十六分。n n习题n n5.7, 5.18, 5.19n n5.10(5)(7),5.11(4)(6),5.12(1),5.13(1),n n实验4.1第五十七页，编辑于星期五：十八点 三十六分。