数据结构课件：第5章 数组和广义表1数组

1、广义表的定义第5章 数组和广义表数组的定义数组的顺序表示和实现矩阵的压缩存储广义表的存储结构数组的处理比其它数据结构要简单？数组中各元素具有统一的类型；数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。5.1 数组的定义 数组的特点二维数组的特点：一维数组的特点：1个下标，ai 是ai+1的直接前驱2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：5.1 数组的定义 数组的特点5.1 数组的定义 数组的特点5.1 数组的定义 数组的特点5.1 数组的定义 N维数组

2、的特点：n个下标，每个元素aj1,j2,jn受到n个关系约束一个n维数组可以看成是由若干个n1维数组组成的线性表。数组的抽象数据类型定义5.1 数组的定义 ADT Array 数据对象：Daj1j2jn | ji=0,bi-1, i=1,2,n，n（0）称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，aj1jnElemSet 数据关系：RR1, R2, Rn Ri | 0jkbk-1, 1kn 且ki, 0jibi-2, aj1jijn , aj1ji jnD, i=1,2,n 基本操作：ADT Array+1+1数组的抽象数据类型定义5.1 数组的定义 数组一旦被定义，它

3、的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取和修改元素值操作。数组的常用操作5.1 数组的定义 InitArray(&A, n, bound1, ., boundn) 结果：若维数n和各维长度合法，则构造相应的数组A, 并返回OKDestroyArray(&A) 结果：销毁数组AValue(A, &e, index1, ., indexn) 条件：A是n维数组，e为元素变量，随后是n个下标值 结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OKAssign(&A, e, index1, ., indexn) 条件：同3） 结果：若下标不超界，则将e的值赋给所

4、指定的A的元素，并返回OK思考(如何设计数组)5.2 数组的顺序表示和实现问题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？解决办法：事先约定按某种次序将数组元素排成一列序列， 然后将这个线性序列存入存储器中。例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。注意：若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；C和PASCAL中一般采用行优先顺序；FORTRAN采用列优先。按行优先顺序存放5.2 数组的顺序表示和实现 .a11 a12 . a1n a21 a22 . a2n am1 am

5、2 . amn amn am2 am1 a2n a22 a21 a1n a12 a11按列优先顺序存放5.2 数组的顺序表示和实现 .a11 a12 . a1n a21 a22 . a2n am1 am2 . amn amn a2n a1n am2 a22 a12 am1 a21 a11数组寻址公式5.2 数组的顺序表示和实现无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！）开始结点的存放地址（即基地址）维数和每维的上、下界；每个数组元素所占用的单元数数组寻址公式可用下标值随机访问该数组的任意一个元素。计算数组元素存储地址的公式称为寻址

6、公式。设数组为A，每个数组元素占L个存储单元，一旦定义了它的维数和各维的上、下界，就可以得到计算数组元素地址的寻址公式。5.2 数组的顺序表示和实现一维数组寻址公式若一维数组的下标下界为LB，上界为UB，每个单元占用L个存储单元，第一元素(其下标为LB)的地址为Loc(LB)，下标为i的数组元素Ai的地址为Loc(i)，则计算Loc(i)的寻址公式为： Loc(i)=Loc(LB)+(i-LB)L LBiUB在C语言中，数组下标的下界为0，则数组中任意一元素Ai的寻址公式为： Loc(i)=Loc(0)+iL 0iUB-1 5.2 数组的顺序表示和实现二维数组寻址公式若设二维数组Amn，m、n

7、分别表示数组的行和列，用Loc(i,j)表示数组元素Aij的地址，按行优先顺序存放则寻址公式为： Loc(i,j) = Loc(0,0) + (nij)L 按列优先存储时的寻址方式为: Loc(i,j) = Loc(0,0) + (mji)L5.2 数组的顺序表示和实现例：行序为主序的存储映象5.2 数组的顺序表示和实现称为基地址或基址LOC(i, j) = LOC(0,0) + (b2ij)L2维数组的长度a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L三维数组寻址公式5.2 数组的顺序表示和实现n维数组的寻址计算公式5.2 数组的顺序表示和

8、实现LOCj1,j2,jn = LOC0,0,0 + (b2bnj1 + b3bnj2 + + bnjn-1 + jn ) L = LOC0,0,0 + ( + jn ) LLOCj1,j2,jn = LOC0,0,0 +其中 cn = L ， ci-1 = bi ci , ci = bi+1bi+2 bnL上式称为n维数组的映象函数。n维数组的寻址计算公式5.2 数组的顺序表示和实现LOCj1,j2,jn = LOC0,0,0 + 其中 cn = L ， ci-1 = bi ci , ci = bi+1bi+2 bnL一个元素长度数组基址前面若干元素占用的地址字节总数第i维长度与所存元素个数

9、有关的系数，可用递推法求出n维数组的寻址计算公式5.2 数组的顺序表示和实现 数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，ci 就是常数。由于计算各元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。则称具有这一特点的存储结构为随机存储结构。例2：已知二维数组Am,m按行存储的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K , 按列存储的公式是？ Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （尽管是方阵，但公式仍不同）例1软考题：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素

10、用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。 288例3：00年计算机系考研题设数组a160, 170的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a32,58的存储地址为 。8950LOC(aij)=LOC(a1,1)+(j-1)*m+i-1)*L得：LOC(a32,58)=2048+(58-1)*60+32-1)*28950答：请注意审题！利用列优先通式：答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288数组基本操作的实现(顺序存储表示)5.2 数组的顺序表示和实现# include /标准头文件

11、/提供宏va_start、va_arg和va_end，用于存取变长参数表# define MAX_ARRAY_DIM 8 /数组维数的最大值typedef struct ElemType * base; /数组元素基址，由InitArray分配 int dim; /数组维数 int *bounds; /数组维界基址，由InitArray分配 int *constants; /数组映像函数常量基址，由InitArray分配Array；即Ci信息保存区构造数组5.2 数组的顺序表示和实现Status InitArray(Array &A, int dim, )/若维数dim和各维长度合法，则构造相

12、应的数组A if( dimMAX_ARRAY_DIM ) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim *sizeof(int); if (!A.bounds) exit(OVERFLOW)； /若各维长度合法,存入A.bounds,求元素总数elemtotal elemtotal=1; va_start(ap,dim); /ap为va_list类型，是存放变长参数表信息的数组 for( i=0; idim; +i ) A.boundsi=va_arg(ap,int); if(A.boundsi=0;-i) A.constantsi=A

13、.boundsi+1*A.constantsi+1; return OK;销毁数组5.2 数组的顺序表示和实现Status DestroyArray(Array &A) /销毁数组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.constants=NULL;数组基址指针各维长度保存区指针映像函数ci保存区

14、指针计算元素在数组中相对地址5.2 数组的顺序表示和实现Status Locate(Array A, va_list ap, int &off)/若ap指示的各下标值合法，求出该元素在A中相对地址off 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;A的元素值赋给变量e5.2 数组的顺序表示和实现Status Value(Array A, ElemType &e,)/A是n维数组，e为元素变

15、量，随后是n下标值。/若各下标不超界，则e赋值为所指定的A的元素值 Va_start(ap,e); if( (result=Locate(A, ap, off) = 0 ) return result; e = *(A.base+off); return OK;变量e的值赋给所指定的A的元素5.2 数组的顺序表示和实现Status Assign(Array &A, ElemType e, )/A是n维数组，e为元素变量，随后是n个下标值。/若下标不超界，则将e的值赋给所指定的A的元素 Va_start(ap,e); if( (result=Locate(A,ap,off) = 0 ) retu

16、rn result; *( A.base + off ) = e; return OK;变参函数 (实现多维数组的重要技术)5.2 数组的顺序表示和实现 ：利用宏va_start、va_arg和va_end提供遍历未知数目和类型的函数参数表的功能。Va_start ( va_list ap, x )：初始化ap，使其指向所在函数的参数x之后的第一个参数。Va_arg ( va_list ap , 类型)：返回ap当前指向的参数的值，并修改ap，使得ap指向下一个参数（“类型”为参数类型）。Va_end ( va_list ap)：用在所有的参数处理完毕之后，表示ap使用完毕。矩阵压缩5.3 矩

17、阵的压缩存储 矩阵应用广泛，但对于某些阶数较高的矩阵，其中有很多值相同的元素或者是零元素。为了节省存储空间，提出了矩阵压缩概念。 矩阵压缩： 指为多值相同的元素只分配一个存储空间 对零元素不分配空间 若值相同的元素或者零元素在矩阵中的分布有一定规律，则称这类矩阵为特殊矩阵；反之称稀疏矩阵。特殊矩阵对称矩阵三角矩阵对角矩阵5.3 矩阵的压缩存储对称矩阵5.3 矩阵的压缩存储a11, a21, a22, a31, a32, , an1, an2, , ann a11 a12 a13 a1n a21 a22 a23 a2nan1 an2 an3 ann A=行优先存放aij = ajin2个元素压缩

18、存储到n(n+1)/2个元素的空间中 对称矩阵5.3 矩阵的压缩存储a11, a21, a22, a31, a32, , an1, an2, , ann a11 a12 a13 a1n a21 a22 a23 a2nan1 an2 an3 ann 前i-1行非零元素个数Loc(aij)=Loc(a11)+ ( +j-1)L ij Loc(aij)=Loc(a11)+ ( +i-1)L i j 对称矩阵5.3 矩阵的压缩存储 a11 a21 a22 a31 an,nk是对称矩阵位于(i, j)位置的元素在一维数组中的存放位置S0123k = 对任意给定的一组下标(i, j) ，均可在一维数组 S

19、 中找到矩阵元aij；反之，对k=0,1, ，都能确定Sk 中的元素在矩阵中的位置(i, j)。 称 S 为 n 阶对称矩阵 A 的压缩存储。对称矩阵(取值操作算法的实现)5.3 矩阵的压缩存储int Value(int A,Elemtype *elem,int i,int j) if(iMAX_ROW_INDEX|jMAX_COL_INDEX) return FALSE; if (i=j) k=i*(i-1)/2+j-1; else k=j*(j-1)/2+i-1; *elem=Ak; return TRUE;下三角矩阵5.3 矩阵的压缩存储a11, a21, a22, a31, a32,

20、, an1, an2, , ann a11 0 0 0 a21 a22 0 0an1 an2 an3 ann A=行优先存放下三角矩阵5.3 矩阵的压缩存储a11, a21, a22, a31, a32, , an1, an2, , ann 前i-1行非零元素个数Loc(aij)=Loc(a11)+ ( +j-1)L ij Loc(aij)=0 i j a11 0 0 0 a21 a22 0 0an1 an2 an3 ann 下三角矩阵5.3 矩阵的压缩存储 0 a11 a21 a22 an,nk是对称矩阵位于(i, j)位置的元素在一维数组中的存放位置S0123k = 下三角矩阵的压缩存储与

21、对称矩阵的压缩存储类似，只是将上三角部分的常量值存储在0单元，下三角和主对角上的元素从1号单元开始存放。 下三角矩阵(取值操作算法的实现)5.3 矩阵的压缩存储int Value(int A,Elemtype *elem,int i,int j) if(iMAX_ROW_INDEX|jMAX_COL_INDEX) return FALSE; if (i=j) k=i*(i-1)/2+j; else k=0; *elem=Ak; return TRUE;三对角矩阵5.3 矩阵的压缩存储a11 a12 0 0a21 a22 a23 0 00 0 an-1,n-2 an-1,n-1 an-1,nA=

22、0 a32 a33 a34 0 0 0 0 an,n-1 ann行优先存放三对角矩阵5.3 矩阵的压缩存储a11, a12, a21, a22, a23, a32, a34, , an,n-1, ann Loc( aij ) = Loc( a11 )+ (i-1)3-1+(j-i+1) L = Loc( a11 )+( 2i+j-3 ) L其中 i-1ji+1稀疏矩阵5.3 矩阵的压缩存储 假设 m 行 n 列的矩阵含 t 个非零元素，则称 d= t/(mn)为稀疏因子，通常认为d0.05的矩阵为稀疏矩阵。 以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题：（1）零值元素占的空间很大（2

23、）计算中进行了很多和零值的运算稀疏矩阵5.3 矩阵的压缩存储问题： 如果只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？解决思路： 对每个非零元素增开若干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。实现方法： 将每个非零元素用一个三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个三元组表来表示。稀疏矩阵的表示方法线性表表示顺序存储结构 三元组表示法行逻辑链接的顺序表数组的链接存储结构 十字链表表示法5.3 矩阵的压缩存储线性表表示例1 ：三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。 5.3 矩阵的压缩

24、存储行下标列下标元素值线性表表示5.3 矩阵的压缩存储例2：写出右图所示稀疏矩阵的压缩存储形式。( 1,1,7) ，(1,5,15)， (2,2,-4)，(3,4,-1)， (4,1,-2)， (4,6,21)7 0 0 0 15 0 0 -4 0 0 0 00 0 0 -1 0 0-2 0 0 0 0 21三元组矩阵表示5.3 矩阵的压缩存储7 0 0 0 15 0 0 -4 0 0 0 00 0 0 -1 0 0-2 0 0 0 0 21M= 21 6 4 -2 1 4 -1 4 3 -4 2 2 15 5 1 7 1 1列行值行数mu, 列数nu, 非零元个数tu 三元组顺序表存储表示5

25、.3 矩阵的压缩存储#define MAXSIZE 12500 / 假设非零元个数的最大值为12500typedef struct int i, j; / 该非零元的行下标和列下标 ElemType e; Triple; typedef struct Triple dataMAXSIZE + 1; / 非零元三元组表，data0未用 int mu,nu,tu; / 矩阵的行数、列数和非零元个数 TSMatrix; 稀疏矩阵的操作（以转置运算为例） 5.3 矩阵的压缩存储 转置运算是一种简单的矩阵运算。对于一个 mn 的矩阵 M，它的转置矩阵 T 是个nm的矩阵，且T(i, j) = M(j,

26、i)，1in，1jm。稀疏矩阵的操作（以转置运算为例） 5.3 矩阵的压缩存储用常规的二维数组表示时的算法其时间复杂度为: O(munu) for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol; 7 0 0 0 15 0 0 -4 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0 21 6 4 -1 4 3 -4 2 2 15 5 1 7 1 1 -2 1 4 7 0 0 -2 0 -4 0 0 0 0 -1 0 0 0 0 0 15 0 0 0 0 0 0 21 -1 3 4 7 1 1

27、 -2 4 1 -4 2 2 15 1 5 21 4 6？MT稀疏矩阵的转置5.3 矩阵的压缩存储答：不正确！除了： （1）每个元素的行下标和列下标互换（即三元组中的i和j互换）；还应该：（2）T的总行数mu和总列数nu与M的不同（互换）； （3）重排三元组内元素顺序，使转置后的三元组也按行（或列）为主序有规律的排列。 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？ 提问：稀疏矩阵的转置5.3 矩阵的压缩存储上述（1）和（2）容易实现，难点在（3）。有两种实现方法压缩转置(压缩)快速转置稀疏矩阵的转置（压缩转置）5.3 矩阵的

28、压缩存储三元组表a.data三元组表b.data(1, 3, -3)(1, 6, 15)(2, 1, 12) (2, 5, 18)(3, 1, 9) (3, 4, 24) (4, 6, -7) (5, 3, 14)(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)11 22SMatrix MSMatrix Tp12345678q12345678压缩转置算法描述5.3 矩阵的压缩存储Status TransPoseSMatrix(TSMatrix M, TSMatrix &T)T.mu=

29、M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) q=1; for(col=1; col=M.nu; col+) for(p=1; p=M.tu; p+) if (M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.value=M.datap.value; q+; return OK; /TranposeSMatrix;压缩转置算法的效率分析5.3 矩阵的压缩存储算法主要时间消耗在查找M.datap.j=col的元素，由两重循环完成 for(col=1; col=M.nu; col+) 循环

30、次数nu for(p=1; p=M.tu; p+) 循环次数tu所以该算法的时间复杂度为O(nu*tu) -即M的列数与M中非零元素的个数之积最恶劣情况：M中全是非零元素，此时tu=mu*nu， 时间复杂度为 O(nu2*mu)注：若M中基本上是非零元素时，即使用非压缩传统转置算法的时间复杂度也不过是O(nu*mu)结论：压缩转置算法不能滥用。前提：仅适用于非零元素个数很少（即tumu*nu）的情况。思考5.3 矩阵的压缩存储 期望依次把a.data中的元素直接送入b.data的恰当位置上（即M三元组的p指针不回溯）。思考5.3 矩阵的压缩存储三元组表a.data三元组表b.data(1, 3

31、, -3)(1, 6, 15)(2, 1, 12) (2, 5, 18)(3, 1, 9) (3, 4, 24) (4, 6, -7) (5, 3, 14)(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)SMatrix MSMatrix Tp12345678q12345678思考5.3 矩阵的压缩存储关键：怎样寻找b.data的“恰当”位置？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

32、0Mcol 1 2 3 4 5 6三元组表b.data (1, 3, -3) (1, 6, 15) (2, 1, 12) (2, 5, 18) (3, 1, 9) (3, 4, 24) (4, 6, -7) (5, 3, 14)SMatrix T每一列首元素位置，依赖于上一列首元素+元素个数快速压缩转置算法5.3 矩阵的压缩存储令： M中的列变量用col表示； num col ：存放M中第col 列中非0元素个数， cpot col ：存放M中第col 列的第一个非0元素的位置， （即b.data中待计算的“恰当”位置所需参考点）col123456numcol222110cpotcol1规律：

33、 cpot(1)1cpotcol cpotcol-1 + numcol-10 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 0M 3 5 7 8 8col 1 2 3 4 5 6col123456cpotcol 9 2 7 8 6三元组表a.data三元组表b.data(1, 3, -3)(1, 6, 15)(2, 1, 12) (2, 5, 18)(3, 1, 9) (3, 4, 24) (4, 6, -7) (5, 3, 14)(1, 2, 12)(1, 3, 9 )(3, 1, -3)(3, 5

34、, 14)(4, 3, 24)(5, 2, 18)(6, 1, 15)(6, 4, -7)SMatrix MSMatrix Tp12345678q12345678 3 4 5 8 0 1 7 5 3快速压缩转置算法5.3 矩阵的压缩存储Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; cpot1

35、 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) col= M.datap.j; q = cpotcol; T.dataq.i= m.datap.j; T.dataq.j= m.datap.i; T.dataq.e=m.datap.e; +cpotcol; / if return OK; / FastTransposeSMatrix快速转置算法的效率分析5.3 矩阵的压缩存储1. 与常规算法相比，附加了生成辅助向量表的工作。增开了2个长度为列长的数组(num 和cpos

36、 ）。2. 从时间上，此算法用了4个并列的单循环，而且其中前3个单循环都是用来产生辅助向量表的。 for(col = 1; col =M.nu; col+) 循环次数nu; for( i = 1; i =M.tu; i +) 循环次数tu; for(col = 2; col =M.nu; col+) 循环次数nu; for( p =1; p =M.tu ; p + ) 循环次数tu; 该算法的时间复杂度(nu*2)+(tu*2)=O(nu+tu）快速转置算法的效率分析5.3 矩阵的压缩存储 传统转置：O(mu*nu) 压缩转置：O(mu*tu) 压缩快速转置：O(nu+tu)空间效率换时间效率

37、讨论：最恶劣情况是tu=nu*mu(即矩阵中全部是非零元素），而此时的时间复杂度也只是O(mu*nu)，并未超过传统转置算法的时间复杂度。小结：行逻辑链接的顺序表5.3 矩阵的压缩存储 为便于随机存取任意一行的非零元，需知道每一行的第一个非零元在三元组表中的位置。为此，可将快速转置矩阵算法中创建的指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。称这种“带行链接信息”的三元组为行逻辑链接的顺序表。行逻辑链接的顺序表的类型描述5.3 矩阵的压缩存储typedef struct Triple dataMAXSIZE + 1; / 非零元三元组表，data0未用 int rpotMAXRC

38、 + 1; / 指示各行第一个非零元的位置 int mu, nu, tu; / 矩阵的行数、列数和非零元个数 RLSMatrix;行逻辑链接的顺序表的类型描述5.3 矩阵的压缩存储两个稀疏矩阵相乘： Q = M N其中：M是 m1n1 的矩阵，N是 m2n2 的矩阵，n1=m2行逻辑链接的顺序表的类型描述5.3 矩阵的压缩存储矩阵乘法的经典算法: for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 算法时间复杂度为：O(m1 n1 n2)行逻辑链接的顺序表的类型描述5.3

39、矩阵的压缩存储存储：占用大量值为零的空间；运算：不论M(i, k)和N(k, j)的值是否为零，都要进行一次乘法运算，而实际上，这两者有一个值为零时，其乘积也为零。 000200-105003004-20120400-160=MNQ行逻辑链接的顺序表的类型描述5.3 矩阵的压缩存储000200-105003004-20120400-160=MNQijv1123142135-12ijv1233211221-24ijv1232126-14M.dataN.dataQ.data行逻辑链接的顺序表的类型描述5.3 矩阵的压缩存储 显然，当 M 和 N 是稀疏矩阵并用三元组表存储结构时，不能套用上述算法。

40、如何从M和N求得Q？如何从M和N求得Q5.3 矩阵的压缩存储(1) 乘积矩阵 Q 中元素 稀疏矩阵运算时，求Q的值，只需在 M.data 和 N.data 中找到相应的各对元素（即 M.data 中的 j 值和N.data 中的 i 值相等的各对元素）相乘即可。 由此，为得到非零乘积，只要对 M.data1.M.tu 中的每个元(i, k, M(i, k) (1im1,1kn1)，找到 N.data中所有相应的元(k, j,N(k, j) (1km2,1jn2)相乘即可。为此需在 N.data 中找矩阵 N 第 k 行所有非零元。如何从M和N求得Q5.3 矩阵的压缩存储 在稀疏矩阵的行逻辑链接

41、的顺序表中，N.rpos 提供了有关信息。例：矩阵 N 的 rpos 值如下表所示。 Row1234Rposrow1235rposrow指示矩阵N的第row行中第一个非零元在N.data中的序号 rposrow+1-1指示矩阵N的第row行中最后一个非零元在N.data中的序号 最后一行中最后一个非零元在N.data中的位置显然就是N.tu 如何从M和N求得Q5.3 矩阵的压缩存储(2)稀疏矩阵相乘基本操作： 对M中每个元素 M.datap (p=1,2,，M.tu)，找到N中所有满足条件 M.datap.j = N.dataq.i 的元素 N.dataq，求得 M.datap.v 和 N.d

42、ataq.v 的乘积，而乘积矩阵Q中每个元素的值是个累计和，这个乘积 M.datap.vN.dataq.v 只是 Qij 中的一部分。为便于操作，应对每个元素设一累计和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到求和变量上。 如何从M和N求得Q5.3 矩阵的压缩存储(3) 2个稀疏矩阵相乘的乘积不一定是稀疏矩阵。反之，即使每个分量值 M(i, k)N(k, j) 不为零，其累加值Qij也可能为零。因此乘积矩阵 Q 中的元素是否为非零元，只有求得其累加和后才能得知。 由于 Q 中元素的行号和 M 中元素的行号一致，又 M 中元素排列是以 M 的行序为主序的，由此可对Q进行逐行处

43、理，先求得累计求和的中间结果(Q的一行)，然后再压缩存储到 Q.data 中去。 如何从M和N求得Q5.3 矩阵的压缩存储如何从M和N求得Q5.3 矩阵的压缩存储M.dataN.datapqQ.dataijv12215322-123531434735643-3ijv12321222431152-2ijvctemp 行逻辑链接的顺序表的实现5.3 矩阵的压缩存储Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) /求矩阵乘积Q=M * N，采用行逻辑链接存储表示 if (M.nu != N.mu) return ERROR; Q.mu=M.mu; Q.nu=N.nu; Q.tu=0