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

1、武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2019年3月12日:广义表的定义第第5 5章章 数组和广义表数组和广义表数组的定义数组的顺序表示和实现矩阵的紧缩存储广义表的存储构造:v数组的处置比其它数据构造要简单？数组的处置比其它数据构造要简单？v数组中各元素具有一致的类型；数组中各元素具有一致的类型；v数组元素的下标普通具有固定的上界和数组元素的下标普通具有固定的上界和下界，即数组一旦被定义，它的维数和下界，即数组一旦被定义，它的维数和维界就不再改动。维界就不再改动。v数组的根本操作比较简单，除了构造的数组的根本

2、操作比较简单，除了构造的初始化和销毁之外，只需存取元素和修初始化和销毁之外，只需存取元素和修正元素值的操作。正元素值的操作。5.1 数组的定义数组的定义 :v数组的特点数组的特点二维数组的特点：一维数组的特点：1个下标，ai 是ai+1的直接前驱2个下标，每个元素ai,j遭到两个关系行关系和列关系的约束：5.1 数组的定义数组的定义 :v数组的特点数组的特点5.1 数组的定义数组的定义 0001020,11011121,21,01,11,21,1nnm nmmmmnaaaaaaaaAaaaa:v数组的特点数组的特点5.1 数组的定义数组的定义 :v数组的特点数组的特点5.1 数组的定义数组的定

3、义 N维数组的特点：n个下标，每个元素aj1,j2,jn遭到n个关系约束一个n维数组可以看成是由假设干个n1维数组组成的线性表。:v数组的笼统数据类型定义数组的笼统数据类型定义5.1 数组的定义数组的定义 ADT Array 数据对象：Daj1j2jn | ji=0,bi-1, i=1,2,n，n0称为数组的维数，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:v数组的笼统

4、数据类型定义数组的笼统数据类型定义5.1 数组的定义数组的定义 数组一旦被定义，它的维数和维界就不再改动。因此，除了构造的初始化和销毁之外，数组只需存取和修正元素值操作。:v数组的常用操作数组的常用操作5.1 数组的定义数组的定义 InitArray(&A, n, bound1, ., boundn) 结果：假设维数结果：假设维数n和各维长度合法，那么构造相应的数组和各维长度合法，那么构造相应的数组A, 并前往并前往OKDestroyArray(&A) 结果：销毁数组结果：销毁数组AValue(A, &e, index1, ., indexn) 条件：条件：A是是n维数

5、组，维数组，e为元素变量，随后是为元素变量，随后是n个下标值个下标值 结果：假设各下标不超界，那么结果：假设各下标不超界，那么e赋值为所指定的赋值为所指定的A的元素值，并前的元素值，并前往往OKAssign(&A, e, index1, ., indexn) 条件：同条件：同3 结果：假设下标不超界，那么将结果：假设下标不超界，那么将e的值赋给所指定的的值赋给所指定的A的元素，并前的元素，并前往往OK:v思索思索(如何设计数组如何设计数组)5.2 数组的顺序表示和实现数组的顺序表示和实现问题：计算机的存储构造是一维的，而数组普通是多维的，怎样存放？处理方法：事先商定按某种次序将数组元素

6、排成一列序列， 然后将这个线性序列存入存储器中。例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。留意：假设规定好了次序，那么数组中恣意一个元素的存放地址便有规律可寻，可构成地址计算公式；商定的次序不同，那么计算元素地址的公式也有所不同；C和PASCAL中普通采用行优先顺序；FORTRAN采用列优先。:v按行优先顺序存放按行优先顺序存放5.2 数组的顺序表示和实现数组的顺序表示和实现 .a11 a12 . a1n a21 a22 . a2n am1 am2 . amn amn am2 am1 a2n a22 a21 a1n a12 a11:v按列优先顺序存放按列优先顺序存放5.2

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

8、公计算数组元素存储地址的公式称为寻址公式。式。v设数组为设数组为A，每个数组元素占，每个数组元素占L个存储单元，个存储单元，一旦定义了它的维数和各维的上、下界，一旦定义了它的维数和各维的上、下界，就可以得到计算数组元素地址的寻址公式。就可以得到计算数组元素地址的寻址公式。5.2 数组的顺序表示和实现数组的顺序表示和实现:v一维数组寻址公式一维数组寻址公式v假设一维数组的下标下界为假设一维数组的下标下界为LB，上界为，上界为UB，每个单元占用每个单元占用L个存储单元，第一元素个存储单元，第一元素(其其下标为下标为LB)的地址为的地址为Loc(LB)，下标为，下标为i的数的数组元素组元素Ai的地址

9、为的地址为Loc(i)，那么计算，那么计算Loc(i)的寻址公式为：的寻址公式为： v Loc(i)=Loc(LB)+(i-LB)L LBiUBv在在C言语中，数组下标的下界为言语中，数组下标的下界为0，那么数，那么数组中恣意一元素组中恣意一元素Ai的寻址公式为：的寻址公式为：v Loc(i)=Loc(0)+iL 0iUB-1 5.2 数组的顺序表示和实现数组的顺序表示和实现:v二维数组寻址公式二维数组寻址公式v假设设二维数组假设设二维数组Amn，m、n分别表示分别表示数组的行和列，用数组的行和列，用Loc(i,j)表示数组元素表示数组元素Aij的地址，的地址，按行优先顺序存放那么寻址公式为：

10、按行优先顺序存放那么寻址公式为：v Loc(i,j) = Loc(0,0) + (nij)Lv 按列优先存储时的寻址方式为按列优先存储时的寻址方式为:v Loc(i,j) = Loc(0,0) + (mji)L5.2 数组的顺序表示和实现数组的顺序表示和实现:v例：行序为主序的存储映象例：行序为主序的存储映象5.2 数组的顺序表示和实现数组的顺序表示和实现称为基地址或基址LOC(i, j) = LOC(0,0) + (b2ij)L2维数组的长度a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L:v三维数组寻址公式三维数组寻址公式5.2 数组的顺序

11、表示和实现数组的顺序表示和实现:vn维数组的寻址计算公式维数组的寻址计算公式5.2 数组的顺序表示和实现数组的顺序表示和实现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维数组的映象函数。111nnikik ijb 1niiic j:vn维数组的寻址计算公式维数组的寻址计算公式5.2 数组的顺序表示和实现数组的顺序表示和实现LO

12、Cj1,j2,jn = LOC0,0,0 + 其中 cn = L ， ci-1 = bi ci , ci = bi+1bi+2 bnL1niiic j一个元素长度数组基址前面假设干元素占用的地址字节总数第i维长度与所存元素个数有关的系数，可用递推法求出:vn维数组的寻址计算公式维数组的寻址计算公式5.2 数组的顺序表示和实现数组的顺序表示和实现 数组元素的存储位置是其下标的线性函数，一旦确定了数组的各维的长度，ci 就是常数。由于计算各元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。那么称具有这一特点的存储构造为随机存储构造。:例2：知二维数组Am,m按行存储的元素地址公式是： L

13、oc(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，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。 288例3：00年计算机系考研题设数组a160, 170的基地址为2048，每个元素占2个存储单元，假设以列序为主序顺序存储，那么元素a32,58的存储地址为 。8950LOC(aij)=LOC(a1,1)+(j-1)*m+i-1)*L得：LOC(a32,5

14、8)=2048+(58-1)*60+32-1)*28950答：请留意审题！ 利用列优先通式：答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288:v数组根本操作的实现数组根本操作的实现(顺序存储表示顺序存储表示)5.2 数组的顺序表示和实现数组的顺序表示和实现# include /规范头文件/提供宏va_start、va_arg和va_end，用于存取变长参数表# define MAX_ARRAY_DIM 8 /数组维数的最大值typedef struct ElemType * base; /数组元素基址，由InitArray 分配 int dim; /数组

15、维数 int *bounds; /数组维界基址，由InitArray分配 int *constants; /数组映像函数常量基址，由InitArray分配Array；即Ci信息保管区:v构造数组构造数组5.2 数组的顺序表示和实现数组的顺序表示和实现Status InitArray(Array &A, int dim, )/假设维数假设维数dim和各维长度合法，那么构造相应的数组和各维长度合法，那么构造相应的数组A if( dimMAX_ARRAY_DIM ) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim *sizeof(int

16、); 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.boundsi+1*A.constantsi+1; return OK;:v销毁数组销毁数组5.2 数组的顺序表示和

17、实现数组的顺序表示和实现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保管区指针:v计算元素在数组中相对地址计算元素在数组中相对地址5.2 数组的

18、顺序表示和实现数组的顺序表示和实现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;:vA的元素值赋给变量的元素值赋给变量e5.2 数组的顺序表示和实现数组的顺序表示和实现Status Valu

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

20、Type e, )/A是是n维数组，维数组，e为元素变量，随后是为元素变量，随后是n个下标值。个下标值。/假设下标不超界，那么将假设下标不超界，那么将e的值赋给所指定的的值赋给所指定的A的元素的元素 Va_start(ap,e); if( (result=Locate(A,ap,off) = 0 ) return result; *( A.base + off ) = e; return OK;:v变参函数变参函数 (实现多维数组的重要技术实现多维数组的重要技术)5.2 数组的顺序表示和实现数组的顺序表示和实现 ：利用宏va_start、va_arg和va_end提供遍历未知数目和类型的函数参

21、数表的功能。Va_start ( va_list ap, x )：初始化ap，使其指向所在函数的参数x之后的第一个参数。Va_arg ( va_list ap , 类型)：前往ap当前指向的参数的值，并修正ap，使得ap指向下一个参数“类型为参数类型。Va_end ( va_list ap)：用在一切的参数处置终了之后，表示ap运用终了。:v矩阵紧缩矩阵紧缩5.3 矩阵的紧缩存储矩阵的紧缩存储 矩阵运用广泛，但对于某些阶数较高的矩阵，其中有很多值一样的元素或者是零元素。为了节省存储空间，提出了矩阵紧缩概念。 矩阵紧缩： 指为多值一样的元素只分配一个存储空间 对零元素不分配空间 假设值一样的元素

22、或者零元素在矩阵中的分布有一定规律，那么称这类矩阵为特殊矩阵；反之称稀疏矩阵。:v特殊矩阵特殊矩阵v对称矩阵对称矩阵v三角矩阵三角矩阵v对角矩阵对角矩阵5.3 矩阵的紧缩存储矩阵的紧缩存储:v对称矩阵对称矩阵5.3 矩阵的紧缩存储矩阵的紧缩存储a11, a21, a22, a31, a32, , an1, an2, , ann a11 a12 a13 a1n a21 a22 a23 a2nan1 an2 an3 ann A=行优先存放aij = ajin2个元素紧缩存储到n(n+1)/2个元素的空间中 :v对称矩阵对称矩阵5.3 矩阵的紧缩存储矩阵的紧缩存储a11, a21, a22, a31

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

24、找到矩阵元aij；反之，对k=0,1, ，都能确定Sk 中的元素在矩阵中的位置(i, j)。 称 S 为 n 阶对称矩阵 A 的紧缩存储。(1)2n n(1)12n n(1)2n n:v对称矩阵对称矩阵(取值操作算法的实现取值操作算法的实现)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

25、;:v下三角矩阵下三角矩阵5.3 矩阵的紧缩存储矩阵的紧缩存储a11, a21, a22, a31, a32, , an1, an2, , ann a11 0 0 0 a21 a22 0 0an1 an2 an3 ann A=行优先存放:v下三角矩阵下三角矩阵5.3 矩阵的紧缩存储矩阵的紧缩存储a11, a21, a22, a31, a32, , an1, an2, , ann 前i-1行非零元素个数1R 1(1)R2ii iLoc(aij)=Loc(a11)+ ( +j-1)L ij (1)2i i Loc(aij)=0 i j a11 0 0 0 a21 a22 0 0an1 an2 an

26、3 ann :v下三角矩阵下三角矩阵5.3 矩阵的紧缩存储矩阵的紧缩存储 0 a11 a21 a22 an,nk是对称矩阵位于(i, j)位置的元素在一维数组中的存放位置S0123k =(1)2n n 下三角矩阵的紧缩存储与对称矩阵的紧缩存储类似，只是将上三角部分的常量值存储在0单元，下三角和主对角上的元素从1号单元开场存放。 :v下三角矩阵下三角矩阵(取值操作算法的实现取值操作算法的实现)5.3 矩阵的紧缩存储矩阵的紧缩存储int Value(int A,Elemtype *elem,int i,int j) if(iMAX_ROW_INDEX|jMAX_COL_INDEX) return

27、FALSE; if (i=j) k=i*(i-1)/2+j; else k=0; *elem=Ak; return TRUE;:v三对角矩阵三对角矩阵5.3 矩阵的紧缩存储矩阵的紧缩存储a11 a12 0 0a21 a22 a23 0 00 0 an-1,n-2 an-1,n-1 an-1,nA=0 a32 a33 a34 0 0 0 0 an,n-1 ann行优先存放:v三对角矩阵三对角矩阵5.3 矩阵的紧缩存储矩阵的紧缩存储a11, a12, a21, a22, a23, a32, a34, , an,n-1, ann Loc( aij ) = Loc( a11 )+ (i-1)3-1+(

28、j-i+1) L = Loc( a11 )+( 2i+j-3 ) L其中 i-1ji+1:v稀疏矩阵稀疏矩阵5.3 矩阵的紧缩存储矩阵的紧缩存储 假设 m 行 n 列的矩阵含 t 个非零元素，那么称 d= t/(mn)为稀疏因子，通常以为d0.05的矩阵为稀疏矩阵。 以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题：1零值元素占的空间很大2计算中进展了很多和零值的运算:v稀疏矩阵稀疏矩阵5.3 矩阵的紧缩存储矩阵的紧缩存储问题： 假设只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？处理思绪： 对每个非零元素增开假设干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在

29、位置。实现方法： 将每个非零元素用一个三元组i，j，aij来表示，那么每个稀疏矩阵可用一个三元组表来表示。:v稀疏矩阵的表示方法稀疏矩阵的表示方法v线性表表示线性表表示v顺序存储构造顺序存储构造 三元组表示法三元组表示法v行逻辑链接的顺序表行逻辑链接的顺序表v数组的链接存储构造数组的链接存储构造 十字链表表示十字链表表示法法5.3 矩阵的紧缩存储矩阵的紧缩存储:v线性表表示线性表表示例1 ：三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。 5.3 矩阵的紧缩存储矩阵的紧缩存储行下标列下标元素值:v线性表表示线性表表示5.3 矩阵的紧缩存储矩阵

30、的紧缩存储例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:v三元组矩阵表示三元组矩阵表示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 :v三元组顺序表存储表示三元组顺序

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

32、，它的转置矩阵 T 是个nm的矩阵，且T(i, j) = M(j, i)，1in，1jm。:v稀疏矩阵的操作以转置运算为例稀疏矩阵的操作以转置运算为例 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

33、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 -2 4 1 -4 2 2 15 1 5 21 4 6？MT:v稀疏矩阵的转置稀疏矩阵的转置5.3 矩阵的紧缩存储矩阵的紧缩存储答：不正确！除了： 1每个元素的行下标和列下标互换即三元组中的i和j互换；还应该：2T的总行数mu和总列数nu与M的不同互换； 3重排三元组内元素顺序，使转置后的三元组也按行或列为主序有规律的陈列。 假设采用三元组紧缩技术存储稀疏矩阵，只需把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？ 提问：:v稀疏矩阵的转置稀疏矩阵的转置5

34、.3 矩阵的紧缩存储矩阵的紧缩存储上述1和2容易实现，难点在3。有两种实现方法紧缩转置(紧缩)快速转置:v稀疏矩阵的转置紧缩转置稀疏矩阵的转置紧缩转置5.3 矩阵的紧缩存储矩阵的紧缩存储三三元元组组表表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 MSM

35、atrix Tp12345678q12345678:v紧缩转置算法描画紧缩转置算法描画5.3 矩阵的紧缩存储矩阵的紧缩存储Status TransPoseSMatrix(TSMatrix M, TSMatrix &T)T.mu=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

36、+; return OK; /TranposeSMatrix;:v紧缩转置算法的效率分析紧缩转置算法的效率分析5.3 矩阵的紧缩存储矩阵的紧缩存储算法主要时间耗费在查找M.datap.j=col的元素，由两重循环完成 for(col=1; col=M.nu; col+) 循环次数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)结论

37、：紧缩转置算法不能滥用。前提：仅适用于非零元素个数很少即tumu*nu的情况。:v思索思索5.3 矩阵的紧缩存储矩阵的紧缩存储 期望依次把a.data中的元素直接送入b.data的恰当位置上即M三元组的p指针不回溯。:v思索思索5.3 矩阵的紧缩存储矩阵的紧缩存储三三元元组组表表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,

38、18)(6, 1, 15)(6, 4, -7)SMatrix MSMatrix Tp12345678q12345678:v思索思索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 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每一

39、列首元素位置，依赖于上一列首元素+元素个数:v快速紧缩转置算法快速紧缩转置算法5.3 矩阵的紧缩存储矩阵的紧缩存储令： M中的列变量用col表示； num col ：存放M中第col 列中非0元素个数， cpot col ：存放M中第col 列的第一个非0元素的位置， 即b.data中待计算的“恰当位置所需参考点col123456numcol222110cpotcol1规律： 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

40、 3 5 7 8 8col 1 2 3 4 5 6:col123456cpotcol 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, 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:v快

41、速紧缩转置算法快速紧缩转置算法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 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.t

42、u; +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:v快速转置算法的效率分析快速转置算法的效率分析5.3 矩阵的紧缩存储矩阵的紧缩存储1. 与常规算法相比，附加了生成辅助向量表的任务。增开了2个长度为列长的数组(num 和cpos 。2. 从时间上，此算法用了4个并列的单循环，而且其中前3个单循环都是用来产生辅助向量表的。 for(col = 1;

43、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:v快速转置算法的效率分析快速转置算法的效率分析5.3 矩阵的紧缩存储矩阵的紧缩存储 传统转置：O(mu*nu) 紧缩转置：O(mu*tu) 紧缩快速转置：O(nu+tu)空间效率换时间效率讨论：最恶劣情况是tu=nu*mu(即矩阵中全部是非零元素，而此时的时间复杂度也只是O

44、(mu*nu)，并未超越传统转置算法的时间复杂度。小结：:v行逻辑链接的顺序表行逻辑链接的顺序表5.3 矩阵的紧缩存储矩阵的紧缩存储 为便于随机存取恣意一行的非零元，需知道每一行的第一个非零元在三元组表中的位置。为此，可将快速转置矩阵算法中创建的指示“行信息的辅助数组cpot固定在稀疏矩阵的存储构造中。称这种“带行链接信息的三元组为行逻辑链接的顺序表。:v行逻辑链接的顺序表的类型描画行逻辑链接的顺序表的类型描画5.3 矩阵的紧缩存储矩阵的紧缩存储typedef struct Triple dataMAXSIZE + 1; / 非零元三元组表，data0未用 int rpotMAXRC + 1;

45、 / 指示各行第一个非零元的位置 int mu, nu, tu; / 矩阵的行数、列数和非零元个数 RLSMatrix;:v行逻辑链接的顺序表的类型描画行逻辑链接的顺序表的类型描画5.3 矩阵的紧缩存储矩阵的紧缩存储两个稀疏矩阵相乘： Q = M N其中：M是 m1n1 的矩阵，N是 m2n2 的矩阵，n1=m21121( ,)( ,)( ,), 1, 1nkQ i jM i kN kjimjn:v行逻辑链接的顺序表的类型描画行逻辑链接的顺序表的类型描画5.3 矩阵的紧缩存储矩阵的紧缩存储矩阵乘法的经典算法: for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qi

46、j = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 算法时间复杂度为：O(m1 n1 n2):v行逻辑链接的顺序表的类型描画行逻辑链接的顺序表的类型描画5.3 矩阵的紧缩存储矩阵的紧缩存储存储：占用大量值为零的空间；运算：不论M(i, k)和N(k, j)的值能否为零，都要进展一次乘法运算，而实践上，这两者有一个值为零时，其乘积也为零。 000200-105003004-20120400-160=MNQ:v行逻辑链接的顺序表的类型描画行逻辑链接的顺序表的类型描画5.3 矩阵的紧缩存储矩阵的紧缩存储000200-105003004-20120400-160=

47、MNQijv1123142135-12ijv1233211221-24ijv1232126-14M.dataN.dataQ.data:v行逻辑链接的顺序表的类型描画行逻辑链接的顺序表的类型描画5.3 矩阵的紧缩存储矩阵的紧缩存储 显然，当 M 和 N 是稀疏矩阵并用三元组表存储构造时，不能套用上述算法。如何从如何从M和和N求得求得Q？:v如何从如何从M和和N求得求得Q5.3 矩阵的紧缩存储矩阵的紧缩存储(1) 乘积矩阵 Q 中元素 稀疏矩阵运算时，求Q的值，只需在 M.data 和 N.data 中找到相应的各对元素即 M.data 中的 j 值和N.data 中的 i 值相等的各对元素相乘即

48、可。 由此，为得到非零乘积，只需对 M.data1.M.tu 中的每个元(i, k, M(i, k) (1im1,1kn1)，找到 N.data中一切相应的元(k, j,N(k, j) (1km2,1jn2)相乘即可。为此需在 N.data 中找矩阵 N 第 k 行一切非零元。:v如何从如何从M和和N求得求得Q5.3 矩阵的紧缩存储矩阵的紧缩存储 在稀疏矩阵的行逻辑链接的顺序表中，N.rpos 提供了有关信息。例：矩阵 N 的 rpos 值如下表所示。 Row1234Rposrow1235rposrow指示矩阵N的第row行中第一个非零元在N.data中的序号 rposrow+1-1指示矩阵N

49、的第row行中最后一个非零元在N.data中的序号 最后一行中最后一个非零元在N.data中的位置显然就是N.tu :v如何从如何从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.dataq.v 的乘积，而乘积矩阵Q中每个元素的值是个累计和，这个乘积 M.datap.vN.dataq.v 只是 Qij 中的一部分。为便于操作，应对每个元素设一累计和的变量，其初值为零，然后扫描数

50、组M，求得相应元素的乘积并累加到求和变量上。 :v如何从如何从M和和N求得求得Q5.3 矩阵的紧缩存储矩阵的紧缩存储(3) 2个稀疏矩阵相乘的乘积不一定是稀疏矩阵。反之，即使每个分量值 M(i, k)N(k, j) 不为零，其累加值Qij也能够为零。因此乘积矩阵 Q 中的元素能否为非零元，只需求得其累加和后才干得知。 由于 Q 中元素的行号和 M 中元素的行号一致，又 M 中元素陈列是以 M 的行序为主序的，由此可对Q进展逐行处置，先求得累计求和的中间结果(Q的一行)，然后再紧缩存储到 Q.data 中去。 :v如何从如何从M和和N求得求得Q5.3 矩阵的紧缩存储矩阵的紧缩存储:v如何从如何从M和和N求得求得Q5.3 矩阵的紧缩存储矩阵的紧缩存储M.dataN.datapqQ.dataijv12215322-123531434735643-3ijv12321222431152-2ijvctemp :v行逻辑链接的顺序表的实现行逻辑链接的顺序表的实现5.3 矩阵的紧缩存储矩阵的紧缩存储Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) /求矩阵乘积求矩阵乘积Q=M * N，采用行逻辑链接存储表示，采用行逻辑