数据结构讲义5

1、2022-3-221柳 青Email: School of Software , Yunnan University 数据结构数据结构(Data Structure)2022-3-222第五章第五章 数组和广义表数组和广义表v5.1 数组的定义数组的定义v5.2 数组的顺序表示和实现数组的顺序表示和实现v5.3 矩阵的压缩存储矩阵的压缩存储 5.3.1 特殊矩阵特殊矩阵 5.3.2 稀疏矩阵稀疏矩阵v5.4 广义表的定义广义表的定义v5.5 广义表的存储结构广义表的存储结构2022-3-223v数组和广义表数组和广义表可看成是一种特殊的线性表，其特殊在于，表中可看成是一种特殊的线性表，其特殊在

2、于，表中的数据元素本身也是一种线性表。的数据元素本身也是一种线性表。v数组数组是是n(nn(n1)1)个相同类型数据元素构成的有限序列，且该有限个相同类型数据元素构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。序列存储在一块地址连续的内存单元中。 v数组数组的抽象数据类型的抽象数据类型 ADT ArrayADT Array定义见定义见P90P90。v由于数组中各元素具有统一的类型，并且数组元素的下标一般由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是

3、一维数组的推广。例如，二维数组：更为简单。多维数组是一维数组的推广。例如，二维数组：5.1 5.1 数组的定义数组的定义nmmmnnn11211101122212021121110110201000aaamaaaaaaaaaaaaaA2022-3-224v可看作可看作A=A=（a0, a1, ., am-1a0, a1, ., am-1），即由），即由m m个行向个行向量组成的向量，其中量组成的向量，其中 aiai = =（ai0, ai1 ., ai0, ai1 ., ain-1ain-1）。）。 v在在C C语言中，一个二维数组类型可以定义为其分量类型为语言中，一个二维数组类型可以定义为其

4、分量类型为一维数组类型的一维数组类型，也就是说，一维数组类型的一维数组类型，也就是说， typedeftypedef elemtypeelemtype array2mn; array2mn; 等价于：等价于： typedeftypedef elemtypeelemtype array1n; array1n; typedeftypedef array1 array2m; array1 array2m; v数组一旦被定义，它的维数和维界就不再改变。因此，数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修除了结构的初始化和销毁之外，数组只有存取元素和修改

5、元素值的操作。改元素值的操作。5.1 5.1 数组的定义数组的定义2022-3-225 由于计算机的内存结构是一维的，因此用一维内存来表示由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的

6、方法来表示数组。此，一般都是采用顺序存储的方法来表示数组。 通常有通常有两种顺序存储两种顺序存储方式：方式：行优先顺序行优先顺序将数组元素按行排列，第将数组元素按行排列，第i+1i+1个行向量紧接在个行向量紧接在第第i i个行向量后面。在个行向量后面。在PASCALPASCAL、C C语言中，数组就是按行优先顺序语言中，数组就是按行优先顺序存储的。存储的。列优先顺序列优先顺序将数组元素按列向量排列，第将数组元素按列向量排列，第j+1j+1个列向量紧个列向量紧接在第接在第j j个列向量之后。在个列向量之后。在FORTRANFORTRAN语言中，数组就是按列优先顺语言中，数组就是按列优先顺序存储的

7、。序存储的。5.2 5.2 数组的顺序表示数组的顺序表示2022-3-226v二维数组二维数组A Amnmn的地址公式：的地址公式： LOC(aLOC(aijij)=LOC(a)=LOC(a0000)+(i)+(i* *n+jn+j) )* *d dv三维数组三维数组A Amnpmnp的地址公式为：的地址公式为：LOC(aLOC(aijkijk)=LOC(a)=LOC(a000000)+(i)+(i* *n n* *p+jp+j* *p+kp+k) )* *d dn 一维数组一维数组A Am m的地址公式：的地址公式：LOC(aLOC(ai i)=LOC(a)=LOC(a0 0)+i)+i*

8、*d d （设每个元素占用（设每个元素占用 d d个存储单元）。个存储单元）。5.2 5.2 数组的顺序表示数组的顺序表示2022-3-227v上述讨论均假设数组各维的下界是上述讨论均假设数组各维的下界是0 0，更一般的二维数组，更一般的二维数组是是AcAc1 1.d.d1 1,c,c2 2.d.d2 2 ，这里，这里c c1 1,c,c2 2不一定是不一定是0 0。a aijij前一共有前一共有i-ci-c1 1行，二维数组一共有行，二维数组一共有d d2 2-c-c2 2+1+1列，故这列，故这i-ci-c1 1行共有行共有(i-(i-c c1 1) )* *(d(d2 2-c-c2 2+

9、1)+1)个元素，第个元素，第i i行上行上a aijij前一共有前一共有j-cj-c2 2个元素，个元素，因此，因此，二维数组二维数组a aijij的地址计算函数为：的地址计算函数为： LOC(aLOC(aijij)=LOC(a)=LOC(ac c1 1c c2 2)+(i-c)+(i-c1 1) )* *(d(d2 2-c-c2 2+1)+j-c+1)+j-c2 2)* *d ddimiLOCdimimmmimmmiLOCiiiLOCnnjnjkkjnnnnnn*)()0 , 0 , 0( *)( )0 , 0 , 0(),(111143232121n n n维数组维数组A Am m1 1

10、m m2 2m mn n的地址公式：的地址公式：5.2 5.2 数组的顺序表示数组的顺序表示2022-3-228 在程序设计中时，矩阵通常采用二维数组表示，可以对其元素在程序设计中时，矩阵通常采用二维数组表示，可以对其元素进行随机存取，各种矩阵运算也非常简单。进行随机存取，各种矩阵运算也非常简单。 在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素时，为了节省存储空间，可以对这类矩阵进行压缩存储：素时，为了节省存储空间，可以对这类矩阵进行压缩存储： 为相为相同的非零元素只分配一个存储空间；对零元素不分配空间。同的非零元素只分配一个存储

11、空间；对零元素不分配空间。5.3.1 5.3.1 特殊矩阵特殊矩阵 特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。1 1、对称矩阵、对称矩阵 在一个在一个n n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质：a aijij= =a ajiji ，0i,jn-10i,jn-1，则称，则称A A为对称矩阵。为对称矩阵。5.3 5.3 矩阵的压缩存储矩阵的压缩存储2022-3-229 对称矩阵中的元素关于主对角线对称，所以只要存储矩阵中对称矩阵中的元素关于主对角线对称，所以只要存储矩阵中上三角或下三角中的元素即可。按上三角或

12、下三角中的元素即可。按“行优先顺序行优先顺序”存储主对角存储主对角线（包括对角线）以下的元素时，其存储形式如下所示：线（包括对角线）以下的元素时，其存储形式如下所示： 1 5 1 3 7 1 5 1 3 7 a a0000 5 0 8 0 0 5 0 8 0 0 a a10 10 a a 11 11 1 8 9 2 6 1 8 9 2 6 a a2020 a a2121 a a2323 3 0 2 5 1 3 0 2 5 1 . 7 0 6 1 3 7 0 6 1 3 a an-1 0n-1 0 a an-1 1 n-1 1 a an-1 2n-1 2 a an-1 n-1n-1 n-1 在这

13、个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为：个元素，元素总数为：n(n+1)/2n(n+1)/2。因此，可以按行优先顺序将对称矩阵。因此，可以按行优先顺序将对称矩阵A A中的中的n n2 2个元素个元素压缩存放在一个向量压缩存放在一个向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中。为了便于访问对称中。为了便于访问对称矩阵矩阵A A中的元素，必须在中的元素，必须在a aijij和和saksak 之间找一个对应关系。之间找一个对应关系。5.3 5.3 矩阵的压缩存储矩阵的压缩存储2022-3-2210 若若ijij，则，则a aijij

14、在下三角形中。在下三角形中。a aijij之前的之前的i i行（从第行（从第0 0行到第行到第i-i-1 1行）一共有行）一共有1+2+1+2+i=i(i+1)/2+i=i(i+1)/2个元素，在第个元素，在第i i行上行上a aijij之前有之前有j j个个元素（即元素（即a ai0i0,a,ai1i1,a,ai2i2, ,a,aij-1ij-1），因此有：），因此有： k=ik=i* *(i+1)/2+j 0kn(n+1)/2 (i+1)/2+j 0kn(n+1)/2 若若ijij，则，则a aijij是在上三角矩阵中。因为是在上三角矩阵中。因为a aijij= =a ajiji，所以只要

15、交换，所以只要交换上述对应关系式中的上述对应关系式中的i i和和j j即可得到：即可得到： k=jk=j* *(j+1)/2+i 0 kn(n+1)/2 (j+1)/2+i 0 kn(n+1)/2 即：即： 5.3 5.3 矩阵的压缩存储矩阵的压缩存储jiijjjijiik,2) 1(,2) 1(思考：如何由思考：如何由k值求值求i，j？ an-1,n-1an-1 0a20a11a10a00k=0 1 2 3 n(n-1)/2 n(n+1)/2-12022-3-22112 2、三角矩阵、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩以主对角线划分，三角矩阵有上三角和下三角两种

16、。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。大多数情况下，三角矩阵常数为零。 a a0000 a a0101 a a0 n-10 n-1 a a0000 c c c c c a c a1111 a a1 n-11 n-1 a a1010 a a1111 c c . . . c c c c a an-1 n-1n-1 n-1 a an-1 0n-1 0 a an-1 1

17、n-1 1 a an-1 n-1 n-1 n-1 (a)(a)上三角矩阵上三角矩阵 (b)(b)下三角矩阵下三角矩阵5.3 5.3 矩阵的压缩存储矩阵的压缩存储2022-3-2212 三角矩阵中的重复元素三角矩阵中的重复元素c c可共享一个存储空间，其余元素共有可共享一个存储空间，其余元素共有n(n+1)/2n(n+1)/2个，因此三角矩阵可压缩存储到向量个，因此三角矩阵可压缩存储到向量sa0.n(n+1)/2sa0.n(n+1)/2中，其中中，其中c c存放在向量的最后一个分量中，上三角矩阵中，主对角线之上的第存放在向量的最后一个分量中，上三角矩阵中，主对角线之上的第p p行行(0pn)(0

18、p11时，元素时，元素a aijij=0=0。 在三对角矩阵里除满足条件在三对角矩阵里除满足条件i=0i=0，j=0j=0、1 1，或，或i=n-1j=n-2i=n-1j=n-2、n-1n-1或或1in-1,j=i-11in-1,j=i-1、i i、i+1i+1的元素的元素a aijij外，其余元素都是零。外，其余元素都是零。 对这种矩阵，也可按行优先顺序压缩存储到一个向量中。除第对这种矩阵，也可按行优先顺序压缩存储到一个向量中。除第0 0行和第行和第n-n-1 1行是行是2 2个元素外，每行的非零元素都要是个元素外，每行的非零元素都要是3 3个，因此，需存储的元素个数为个，因此，需存储的元素

19、个数为3n-23n-2。 数组数组sasa中的元素中的元素saksak 与三对角带状矩阵中的元素与三对角带状矩阵中的元素a aijij存在一一对应关系，存在一一对应关系，在在a aijij之前有之前有i i行行, ,共有共有2+32+3* *(i-1)(i-1)个非零元素，在第个非零元素，在第i i行行a aijij之前有之前有j-i+1j-i+1个非零个非零元素，这样，非零元素元素，这样，非零元素a aijij的地址为：的地址为： k=2+3k=2+3* *(i-1)+j-i+1=2(i-1)+j-i+1=2* *i+ji+j5.3 5.3 矩阵的压缩存储矩阵的压缩存储2022-3-2215

20、 设在的矩阵设在的矩阵A A中，有中，有s s个非零元素。令个非零元素。令 e=e=s/(ms/(m* *n)n)，称，称e e为矩阵的为矩阵的稀疏因子。通常认为稀疏因子。通常认为e0.05e0.05时称之为稀疏矩阵。时称之为稀疏矩阵。 在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（素的同时，还必须同时记下它所在的行和列的位置（i,ji,j) )。反之，一。

21、反之，一个三元组个三元组( (i,j,ai,j,aijij) )唯一确定了矩阵唯一确定了矩阵A A的一个非零元。因此，稀疏矩阵可的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。由表示非零元的三元组及其行列数唯一确定。5.3.2 5.3.2 稀疏矩阵稀疏矩阵5.3 5.3 矩阵的压缩存储矩阵的压缩存储i i（行行行行）j j（列列列列）v v（值值值值）2022-3-2216 0 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 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0

22、 0 0 0 0 0 7 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 0 0 0 0 0 0 M=T=5.3 5.3 矩阵的压缩存储矩阵的压缩存储 例如，三元组表例如，三元组表:(1,2,12),(1,3,9),(3,1,-:(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7) 3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7) 加上加上(6,7)(6,7)这一对行、列值便可作为下列矩阵这一对行、列

23、值便可作为下列矩阵M M的另一种描的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。同的压缩存储方法。2022-3-2217 假设以顺序存储结构来表示三元组表，则可得到稀疏矩假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法阵的一种压缩存储方法三元组顺序表。三元组顺序表。5.3 5.3 矩阵的压缩存储矩阵的压缩存储 #define maxsize 10000 typedef int datatype; typedef struct int i,j; datatype v; triple; typed

24、ef struct triple datamaxsize+1; int m,n,t; /行、列、非零个数 tripletable;一、三元组顺序表三元组顺序表2022-3-2218矩阵的转置运算矩阵的转置运算 设有一个设有一个m mn n的矩阵的矩阵A A，则它的转置，则它的转置B B是一个是一个n nm m的矩阵的矩阵且：且：aijaij=bjibji ，1im1im，1jn1jn， 即即A A的行是的行是B B的列，的列，A A的列是的列是B B的行。的行。 将将A A转置为转置为B B，就是将，就是将A A的三元组表的三元组表a.dataa.data置换为表置换为表B B的三的三元组表元

25、组表b.datab.data，如果只是简单地交换，如果只是简单地交换a.dataa.data中中i i和和j j的内容，的内容，那么得到的那么得到的b.datab.data将是一个按列优先顺序存储的稀疏矩阵将是一个按列优先顺序存储的稀疏矩阵B B，要得到按行优先顺序存储的要得到按行优先顺序存储的b.datab.data，就必须重新排列三元组，就必须重新排列三元组的顺序。的顺序。 由于由于A A的列是的列是B B的行，因此，按的行，因此，按a.dataa.data的列序转置，所得的列序转置，所得到的转置矩阵到的转置矩阵B B的三元组表的三元组表b.datab.data必定是按行优先存放的。必定是

26、按行优先存放的。5.3 5.3 矩阵的压缩存储矩阵的压缩存储2022-3-2219算法思想：算法思想：对对A A中的每一列中的每一列col(1coln)col(1coln)，通过从头至尾扫描三元表，通过从头至尾扫描三元表a.dataa.data，找出所有列号等于，找出所有列号等于colcol的那些三元组，将其行号和列号互换后依的那些三元组，将其行号和列号互换后依次放入次放入b.datab.data中，即可得到中，即可得到B B的按行优先的压缩存储表示。的按行优先的压缩存储表示。5.3 矩阵的压缩存储ijv121213931-3361443245218611564-7ijv13-31615211

27、22518319342446-76314矩阵矩阵A A矩阵矩阵B B2022-3-2220void transmatrix( tripletable a, tripletable &b ) int p, q, col; b.m=a.n; b.n=a.m; b.t=a.t; if( b.t = 0 ) printf(“A=0n”); q=1; for( col=1; col=a.n; col+ ) for( p=1; p=a.t; p+ ) if( a.datap.j = col ) b.dataq.i = a.datap.j; b.dataq.j = a.datap.i; b.data

28、q.v = a.datap.v; q+; 5.3 5.3 矩阵的压缩存储矩阵的压缩存储演示2022-3-2221 分析这个算法，主要的工作是在分析这个算法，主要的工作是在p p和和colcol的两个循环中完成的两个循环中完成的，故算法的时间复杂度为的，故算法的时间复杂度为O(nO(n* *t)t)，即矩阵的列数和非零元的，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为：个数的乘积成正比。而一般传统矩阵的转置算法为： for(colfor(col=0;col=n-1;+col)=0;col=n-1;+col) for(rowfor(row=0;row=0;row=m;+row

29、m;+row) ) tcolrowtcolrow=mrowcolmrowcol; 其时间复杂度为其时间复杂度为O(nO(n* *m)m)。当非零元素的个数。当非零元素的个数t t和和m m* *n n同数量同数量级时，算法级时，算法transmatrixtransmatrix的时间复杂度为的时间复杂度为O(mO(m* *n n2 2) )。 三元组顺序表虽然节省了存储空间，但时间复杂度比一般三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。矩阵转置的算法还要复杂，同时还有可能增加算法的难度。 因此，此算法仅适用于因此，此算法仅适用于t mt

30、m* *n n的情况的情况( (稀疏矩阵稀疏矩阵) )。5.3 5.3 矩阵的压缩存储矩阵的压缩存储2022-3-2222快速转置的算法快速转置的算法： 对对A A扫描一次，按扫描一次，按A A的列号一次确定位置装入的列号一次确定位置装入B B的一个三元组。的一个三元组。具体实施如下：具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。三元组。可见，位置关系是此种算法的关键。 为了预先确定矩阵为了预先确定矩阵A A中的每一列的第一个非零元素在数组中的每一列的第一个非零元素在数组B B中

31、应有的位置，中应有的位置，需要先求得矩阵需要先求得矩阵A A中的每一列中非零元素的个数。中的每一列中非零元素的个数。 矩阵矩阵A A中每一列的第一个非零元素在数组中每一列的第一个非零元素在数组B B中应有的位置等于前一列第一个中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。非零元素的位置加上前列非零元素的个数。 为此，需要设置两个一维数组为此，需要设置两个一维数组num1.A.nnum1.A.n和和cpot1.A.ncpot1.A.n num1.A.n num1.A.n ：统计：统计A A中每列非零元素的个数，中每列非零元素的个数，numcolnumcol 的值可以由的值可以

32、由A A的非的非零元的列号求得。零元的列号求得。 cpot1.A.ncpot1.A.n：由递推关系得出：由递推关系得出A A中的每列第一个非零元素在中的每列第一个非零元素在B B中的位置。中的位置。5.3 5.3 矩阵的压缩存储矩阵的压缩存储2022-3-2223算法通过算法通过cpotcpot数组建立位置对应关系：数组建立位置对应关系： cpot1=1cpot1=1 cpotcolcpotcol=cpotcol-1+numcol-1 2=cpotcol-1+numcol-1 2=colcol=a.na.n 例如：前例中的矩阵例如：前例中的矩阵A A可以求得可以求得numcolnumcol 和

33、和cpotcolcpotcol 的值的值如下：如下：colcolnumcolnumcol cpotcolcpotcol 1 2 3 4 5 6 7 1 2 3 4 5 6 7 2 2 2 1 0 1 0 2 2 2 1 0 1 0 1 3 5 7 8 8 9 1 3 5 7 8 8 95.3 5.3 矩阵的压缩存储矩阵的压缩存储2022-3-2224Status fasttranstri(tritupletable b,tritupletable a) b.m=a.n; b.n=a.m; b.t=a.t; if(b.t) for(col=1;col=a.n;+col) numcol=0; fo

34、r(k=1;k=a.t;+k) +numa.datak.j; cpot1=1; for(col=2;col=a.n;+col) cpotcol=cpotcol-1+numcol-1; for(p=1;p=a.t;+p) col=a.datap.j; q=cpotcol; b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; +cpotcol; /for /if return OK;时间复杂度为时间复杂度为O(n+tO(n+t),),最坏情况最坏情况 O(mO(m* *n)n)。5.3 5.3 矩阵的压缩存储矩阵的压缩存储演

35、示2022-3-2225二、带行表的三元组二、带行表的三元组 有时为了方便某些矩阵运算，我们在按行优先存储的三元组有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。其类型描述如下：元组表。其类型描述如下： #define maxrow 100 typed

36、ef struct triple datamaxsize; int rposmaxrow; int n,m,t; rtripletable5.3 5.3 矩阵的压缩存储矩阵的压缩存储2022-3-2226 两个矩阵相乘的经典算法也是大家所熟悉的。若设两个矩阵相乘的经典算法也是大家所熟悉的。若设Q=MQ=M* *N N其中，其中，M M是是m m1 1* *n n1 1矩阵，矩阵，N N是是m m2 2* *n n2 2矩阵。当矩阵。当n n1 1=m=m2 2时有：时有： for(ifor(i=1;i=m1;+i)=1;i=m1;+i) for(jfor(j=1;j=n2;+j)=1;j=n2

37、;+j) qijqij=0=0 for(kfor(k=1;k=n1;+k)=1;k=n1;+k) qijqij+=+=mikmik * *nkjnkj; 此算法的复杂度为此算法的复杂度为O(mO(m1 1* *n n1 1* *n n2 2) )。 当当M M和和N N是稀疏矩阵并用三元组表存储结构时，就不能套用是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。上述算法。 5.3 5.3 矩阵的压缩存储矩阵的压缩存储2022-3-2227假设假设M M和和N N分别为：分别为： 3 0 0 50 -1 0 02 0 0 0Mm1*n1= 0 2 1 0-2 4 0 0Nn1*n2=则则Q=

38、MQ=M* *N N为：为： 0 6-1 0 0 4Qm1*n2=5.3 5.3 矩阵的压缩存储矩阵的压缩存储乘积矩阵乘积矩阵Q Q中元素中元素 Q(i,j)=11),(*),(nkjkNkiM（）（）2022-3-2228 它们的三元组分别为：它们的三元组分别为： i j v i j v i j v 1 1 3 1 2 2 1 2 6 1 4 5 2 1 1 2 1 -1 3 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 q.data m.data n.data 稀疏矩阵稀疏矩阵相乘的基本思想相乘的基本思想是：对于是：对于M M中每个元素中每个元素M.datapM.datap

39、，找到，找到N N中所中所有满足条件有满足条件M.datap.jM.datap.j= = N.dataq.iN.dataq.i的元素的元素N.dataqN.dataq ，求得，求得M.datap.vM.datap.v和和N.dataq.vN.dataq.v的乘积，而从式（的乘积，而从式（- -）得知，乘积矩阵）得知，乘积矩阵Q Q中中每个元素的值是个累加和，这个乘积只是其中的一部分。为了便于操作，应每个元素的值是个累加和，这个乘积只是其中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组对每个元素设一累加和的变量，其初值为零，然后扫描数组M M，求得相应元，求得相应

40、元素的乘积并累加到适当的求累计和的变量上。素的乘积并累加到适当的求累计和的变量上。 算法见算法见P102-103P102-103。5.3 5.3 矩阵的压缩存储矩阵的压缩存储2022-3-2229Status multsmatrix( rtripletable a, rtripletable b, rtripletable c) if(a.n!=b.m) return ERROR; c.m=a.m; c.n=b.n; c.t=0; if(a.t*b.t!=0) for(arow=1;arow=a.m;+arow) ctemparow=0; c.rposarow=c.t+1; for(p=a.r

41、opsarow;pa.rposarow+1;+p) brow=a.datap.j; if(browb.m) t=b.rposbrow+1 else t=b.t+1; for(q=b.rposbrow; qt;+q) ccol=n.dataq.j; ctempccol+=a.datap.v*b.dataq.v; for(ccol=1;ccolmaxsize) return ERROR; c.datac.t=arow,ccol,ctempccol; return OK;2022-3-22305.3 5.3 矩阵的压缩存储矩阵的压缩存储三、十字链表三、十字链表稀疏矩阵稀疏矩阵M的十字链表的十字链表t

42、ypedef struct OLNode int i; int j; ElemType e; struct OLNode *right; struct OLNode *down; *OLink;typedef struct OLink *rhead; OLink *chead; int mu; int nu; int tu; CrossList;11314522-1312M.cheadM.rhead2022-3-2231假设假设M M和和N N分别为：分别为： 3 0 0 50 -1 0 02 0 0 0M= 0 2 1 0-2 4 0 0N=则Q=M*N为： 0 6-1 0 0 4Q=5.3

43、 5.3 矩阵的压缩存储矩阵的压缩存储2022-3-22325.3 5.3 矩阵的压缩存储矩阵的压缩存储n n 当矩阵的非零元个数和位置在操作过程中变化较大当矩阵的非零元个数和位置在操作过程中变化较大时，采用链式存储结构表示三元组的线形表更为合时，采用链式存储结构表示三元组的线形表更为合适。适。n n 链表中的每个非零元可用一个含五个域的结点表链表中的每个非零元可用一个含五个域的结点表示，其中示，其中i，j和和e 分别表示该非零元所在的行、列和分别表示该非零元所在的行、列和值，指针值，指针right用以链接同一行中下一个非零元，指用以链接同一行中下一个非零元，指针针down用以链接同一列中下一

44、个非零元。用以链接同一列中下一个非零元。n n 同一行的非零元通过指针同一行的非零元通过指针right链接成一个链表。链接成一个链表。n n 同一列的非零元通过指针同一列的非零元通过指针down链接成一个链表。链接成一个链表。2022-3-22335.3 5.3 矩阵的压缩存储矩阵的压缩存储v每个非零元既是某个行链表中的一个结点，也每个非零元既是某个行链表中的一个结点，也是某个列链表中的一个结点，整个矩阵构成一是某个列链表中的一个结点，整个矩阵构成一个个十字链表十字链表。vn n 所有的行链表的头指针组成一个指针数组。所有的行链表的头指针组成一个指针数组。vn n 所有的列链表的头指针组成一个

45、指针数组。所有的列链表的头指针组成一个指针数组。vn n 稀疏矩阵的十字链表由行链表头指针数组、稀疏矩阵的十字链表由行链表头指针数组、列链表头指针数组、行数、列数和非零元个数列链表头指针数组、行数、列数和非零元个数组成。组成。v 建立十字链表算法见建立十字链表算法见 P104 算法算法5.4。2022-3-22345.4 5.4 广义表的定义广义表的定义n 广义表广义表的概念的概念: n( : n( 0 0 ) )个表元素组成的有限序列，个表元素组成的有限序列，记作：记作： LS = (aLS = (a0 0, a, a1 1, a, a2 2, , , a, an-1n-1) ) LS LS

46、是是表名表名，a ai i是是表元素表元素，它可以是表，它可以是表( (称为子表称为子表) )，可以是数据元素可以是数据元素( (称为原子称为原子) )。 a0为表头，为表头， ( a1, a2, , an-1)为表尾。为表尾。n n n为为表的长度表的长度。n = 0 n = 0 的广义表为空表。的广义表为空表。 n 例如：例如：A = ( ) B = ( 6, 2 )C = ( a, ( 5, 3, x ) )D = ( B, C, A )E = ( B, D )F = ( 4, F )2022-3-2235各种广义表的示意图各种广义表的示意图2022-3-2236 n n00时，时，广义表的第一个元素称为广义表的广义表的第一个元素称为广义表的表头表头( (headhead) )，除此之外，其它元素组成的表称为广义表的除此之外，其它元素组成的表称为广义表的表尾表尾( (tailtail) )。例如：例如：A =A =（）（） B =B =（6,26