《第5章 数组和广义表》习题解答

1、第5章 数组和广义表第5章 数组和广义表本章学习要点掌握多维数组在行优先顺序存储结构中地址的计算方法了解特殊矩阵压缩存储时的下标转换方法掌握稀疏矩阵常用的两种压缩存储表示方法（三元组表和十字链表表示法）的特点和存储结构掌握稀疏矩阵在三元组表表示下的基本运算（矩阵加法、减法、转置和乘法等）方法了解广义表的有关概念、广义表的各种表示方法和存储结构掌握广义表的基本操作（求广义表的表头、表尾、表的深度以及广义表的复制等）数组是最常用的数据结构之一，几乎所有的高级程序设计语言都把数组类型设定为内部类型。在前面讨论的线性结构中，其数据元素都是非结构的原子类型，元素的值是不可再分解的。本章所讨论的数组可以看

2、成是线性表的一种扩展，即线性表中的每个数据元素本身也是一个线性表。稀疏矩阵是一种特殊的二维数组，因其在压缩存储方面的特点而被广泛使用。广义表是一种较为复杂的数据结构，它是线性结构和树型结构的拓广。广义表被广泛应用于人工智能等领域。5.1数组的概念5.1.1数组的定义如果一个向量的所有元素又都是向量（或称子向量），且这些子向量具有相同的上限和下限标号，那么这种特殊形式的向量称为数组。一维数组是一个向量，它的每一个元素都是该结构中不可分割的最小单位。n(n>1)维数组是一个向量，它的每个元素都是n-1维数组，且具有相同的上限和下限。从逻辑结构上看，n维数组Array中各元素的位置由该元素的下

3、标唯一确定，一旦给定一组下标(j0,j1,j2,jn-1)，都存在唯一的一个与其相对应的元素值a称为数组元素，记为a(j0,j1,j2,jn-1)。其中，0<=ji<bi，bi称为第i维的长度(i=0,1,2,n-1)。5.1.2数组的基本操作数组一旦被定义，它的元素类型（即数组类型）、维数、各维的界（长度）就不再改变。所以数组的基本操作主要有：（1）初始化InitArray(Array &A,int dim,int* bounds)：该操作根据数组元素类型、维数dim和长度bounds定义一个数组（初始化数组）A。（2）读取操作Value(Array A,int* scr

4、ipt,EType &e)：该操作根据下script标读取数组A中的元素到e中。（3）修改操作Assign(Array& A,int* script,EType e)：该操作根据下标script修改数组A中的元素为e的值。（4）销毁操作：该操作回收一个数组所占的资源（销毁数组）。5.2数组的顺序存储表示和实现5.2.1数组顺序存储的物理结构由于数组不作插入和删除操作，也就是说，一旦建立了数组，则该数组结构中的数据元素个数和元素之间的关系就不再发生变动。因此，采用顺序存储结构表示数组是最合理的方式。但是，由于内存地址是一维结构，而数组可以是多维结构，所以，必须有一个从多维下标到一

5、维地址的对应关系。1数组的两种顺序存储方法（1）以行（左下标）为主序的存储结构该存储结构以最左面的下标为主序，右下标优先变化，即下标变化顺序是从右到左。以二维数组为例，其内存结构如图5.1（a）所示。对于三维数组：（有2页、2行、3列），按左下标为主序的内存结构如图5.1（b）所示。（2）以列（右下标）为主序的存储结构该存储结构以最右面的下标为主序，左下标优先变化，即下标变化顺序是从左到右。以二维数组：为例，其内存结构如图5.2（a）所示。对于三维数组：（有2页、2行、3列），按右下标为主序的内存结构如图5.2（b）所示。2左下标为主序存储的n维数组中的元素a(j0,j1,.,jn-1)的地址

6、计算公式对于一个已经被定义的二维数组Ab0×b1=(aij)b0×b1，只要给出该数组存放的起始地址LOC(a00)、数组元素的行下标i和列下标j，以及每个元素所占用的存储单元（字节）数L，便可以求得元素aij在内存中的首地址LOC(aij)。地址计算公式为： 其中b1为数组第2维的长度（界）。对于以行为主序的n维数组，数组元素a(j0,j1,.,jn-1)的地址计算公式为：其中为数组元素a00.0的地址，L为每个元素所占内存的字节数，b0,b1,.,bn-1为每一维的长度。如果记：,即可得到映像常数向量：，相应的n维数组元素的地址计算公式可简写为：完全类似地，读者可以自行

7、给出以右下标为主序的n维数组元素a(j0,j1,.,jn-1)的地址计算公式。【例5.1】二维数组M5×6的元素是4个字符（每个字符占1个存储单元）组成的串，那么M按行优先（以左下标为主序）存储时元素M35的起始地址与M按列优先（以右下标为主序）存储时的哪个元素的起始地址相同？解：按行优先存储时元素M35的起始地址为：LOC(M35) =LOC(M00)+(i×6+j)×4=LOC(M00)+(3×6+5)×4=LOC(M00)+23×4按列优先存储时元素Mij的起始地址为：LOC(Mij)=LOC(M00)+(j×5+i)

8、×4=LOC(M00)+23×4=LOC(M00)+(4×5+3)×4所以，要求的元素Mij即为M34。【例5.2】已知A4×5×6为按左下标为主序存储的3维数组，每个元素占4个存储单元，并且元素A000的首地址为1000，分别计算元素A123、A320和A135的首地址。解：按左下标为主序的地址计算公式为：LOC(Aijk)= LOC(A000)+(ib1b2+jb2+k)×L。所以：LOC(A123)=1000+(1×5×6+2×6+3)×4=1180LOC(A320)=1000+

9、(3×5×6+2×6+0)×4=1408LOC(A135)=1000+(1×5×6+3×6+5)×4=1212【例5.3】已知A4×5×6为按右下标为主序存储的3维数组，每个元素占2个存储单元，并且元素A000的首地址为100，分别计算元素A123、A320和A135的首地址。解：按右下标为主序的地址计算公式为：LOC(Aijk)= LOC(A000)+(kb0b1+jb0+i)×L。所以：LOC(A123)=100+(3×5×4+2×4+1)×

10、2=238LOC(A320)=100+(0×5×4+2×4+3)×2=122LOC(A135)=100+(5×5×4+3×4+1)×2=3265.2.2数组基本操作的实现1数组的顺序存储结构表示在C+语言环境中，顺序数组的存储表示如下#include"iostream.h" /标准输入输出头文件typedef int EType; /便于上机操作定义数组类型为整型（int）struct ArrayEType *base; /数组的基地址int dim; /数组的维数int *bounds; /数

11、组维界向量基地址int *constent; /数组元素的映像常数向量;2数组的初始化操作操作int InitArray(Array &A,int dim,int* bounds)的功能是，根据维数dim和维界向量bounds设置数组A的维数A.dim、维界向量A.bounds、以及元素映像向量A.constent，并分配相应大小的存储空间A.base。如果输入维数dim合理返回1，表示操作成功，否则返回0表示操作失败。int InitArray(Array &A,int dim,int* bounds)int length=1,i;if(dim<1)return 0;A

12、.bounds=new intdim; /分配维界向量的存储空间A.constent=new intdim; /分配映像向量的存储空间for(i=0;i<dim;i+)length*=boundsi; /计算数组元素的总数A.boundsi=boundsi;A.dim=dim;A.base=new ETypelength; /分配数组元素的存储空间A.constentdim-1=1;for(i=dim-2;i>=0;i-) /计算数组元素的映像常数向量A.constenti=A.constenti+1*A.boundsi+1;return 1;3根据下标(script)提取数组元素

13、的操作操作int Value(Array A,int* script,EType &e)的功能是，根据下标向量script提取数组A中相应元素的值到e中。如果下标合理返回1表示提取成功，否则返回0表示操作失败。int Value(Array A,int* script,EType &e)int i,off=0;for(i=0;i<A.dim;i+)if(scripti>=A.boundsi| scripti<0)return 0;off+= scripti*A.constenti; /计算对应元素的偏移量offe=A.baseoff;return 1;简化的提

14、取数组元素操作函数EType Value(Array A,int* script)，该操作对下标越界不做检查。EType Value(Array A,int* script) int i,off=0;for(i=0;i<A.dim;i+)off+= scripti*A.constenti;returnA.baseoff;4根据下标(script)修改数组元素的操作操作int Assign(Array& A,int* script,EType e)的作用是，根据下标向量script修改数组A中相应元素的值为e。如果下标合理返回1表示修改成功，否则返回0表示操作失败。int Assi

15、gn(Array& A,int* script,EType e)int i,off=0;for(i=0;i<A.dim;i+)if(scripti>=A.boundsi| scripti<0)return 0;off+= scripti*A.constenti; /计算对应元素的偏移量offA.baseoff=e;return 1;5数组的按行序输入操作操作void ArrayInput(Array& A)的功能是，以左下标为主序依次输入多维数组A中各元素的值。void ArrayInput(Array& A)int length=1,i;for(i=

16、0;i<A.dim;i+)length*=A.boundsi;cout<<"以行为主序的顺序输入A"for(i=0;i<A.dim;i+) cout<<char(i)?'*':'')<<A.boundsi;cout<<"中的"<<length<<"个元素的值。n"for(i=0;i<length;i+)cin>>A.basei;6数组的按行序输出操作操作void Arrayoutput(Array A)

17、的功能是，按左下标为主序，输出一维、二维、三维和多维数组A中的元素。void Arrayoutput(Array A)int s3,i,len=1;switch(A.dim)case 1: /按一维数组格式输出for(s0=0;s0<A.bounds0;s0+) cout<<Value(A,s)<<" "cout<<endl;break;case 2: /按二维数组格式输出for(s0=0;s0<A.bounds0;s0+)for(s1=0;s1<A.bounds1;s1+)cout<<Value(A,s)&

18、lt;<" "cout<<endl;break;case 3: /按三维数组格式输出for(s0=0;s0<A.bounds0;s0+)cout<<"第"<<s0+1<<"页:n"for(s1=0;s1<A.bounds1;s1+)for(s2=0;s2<A.bounds2;s2+)cout<<Value(A,s)<<" "cout<<endl;break;default: /三维以上按左下标优先的一维数组格

19、式输出cout<<"维数为"<<A.dim<<"大于3n按左下标为主序输出所有元素的值:n"for(i=0;i<A.dim;i+)len*=A.boundsi;for(i=0;i<len;i+)cout<<A.basei<<" "cout<<endl;7矩阵的转置操作操作int Trans(Array & A,Array B)作用是，计算矩阵B的转置矩阵A。如果B的维数不等于2返回0表示操作失败，否则返回1表示操作成功。int Trans(Ar

20、ray& A,Array B)if(B.dim!=2)return 0;int dim=2,s2,s12;int bounds=B.bounds1,B.bounds0;InitArray(A,dim,bounds); /初始化数组Afor(s0=0;s0<B.bounds0;s0+)for(s1=0;s1<B.bounds1;s1+)s10=s1,s11=s0;Assign(A,s1,Value(B,s);return 1;8矩阵操作的演示主程序在演示程序中，首先按左下标（行）优先的顺序分别建立一维、二维、三维和四维数组，以及二维数组的转置，然后显示输出各个数组的值。voi

21、d main()Array A1,A2,A22,A3,A4;int b1=5,b2=4,5,b22=5,4,b3=3,4,5,b4=2,3,2,3;InitArray(A1,1,b1); /定义A1为一维数组长度为5ArrayInput(A1);cout<<"A1结果为:n"Arrayoutput(A1);InitArray(A2,2,b2); /定义A2为二维数组大小为4*5ArrayInput(A2);cout<<"A2结果为:n"Arrayoutput(A2); Trans(A22,A2);cout<<"

22、;A2的转置矩阵为:n"Arrayoutput(A22);InitArray(A3,3,b3); /定义A3为三维数组大小为3*4*5ArrayInput(A3);cout<<"A3结果为:n"Arrayoutput(A3);InitArray(A4,4,b4); /定义A4为四维数组大小为2*3*2*5ArrayInput(A4);cout<<"A4结果为:n"Arrayoutput(A4);程序运行结构为：-.134.-以行为主序的顺序输入A5中的5个元素的值。1 2 3 4 5A1结果为:1 2 3 4 5以行为主

23、序的顺序输入A4*5中的20个元素的值。1 2 3 4 53 4 5 6 75 6 7 8 97 8 9 0 1A2结果为:1 2 3 4 53 4 5 6 75 6 7 8 97 8 9 0 1A2的转置矩阵为:1 3 5 72 4 6 83 5 7 94 6 8 05 7 9 1以行为主序的顺序输入A3*4*5中的60个元素的值。1 2 3 4 52 3 4 5 63 4 5 6 74 5 6 7 821 22 23 24 2522 23 24 25 2623 24 25 26 2724 25 26 27 2831 32 33 34 3532 33 34 35 3633 34 35 36

24、3734 35 36 37 38A3结果为:第1页:1 2 3 4 52 3 4 5 63 4 5 6 74 5 6 7 8第2页:21 22 23 24 2522 23 24 25 2623 24 25 26 2724 25 26 27 28第3页:31 32 33 34 3532 33 34 35 3633 34 35 36 3734 35 36 37 38以行为主序的顺序输入A2*3*2*3中的36个元素的值。10 11 12 13 14 1516 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 4

25、0 41 42 43 44 45A4结果为:维数为4大于3按左下标为主序输出所有元素的值:10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 455.3矩阵的压缩存储矩阵(matrix) 是很多科学与工程计算问题中研究的数学对象。在数据结构中，主要关心的不是矩阵本身，而是如何存储矩阵元素，使矩阵的各种运算能有效地进行。在高级语言程序设计中，通常是用二维数组来存储矩阵元素的。然而，在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中又有许多

26、值相同元素或者是零元素。为了节省存储空间，可以对这类矩阵进行压缩存储。即，对多个值相同的元素只分配一个存储空间；对零元素不分配存储空间。5.3.1特殊矩阵的压缩存储若矩阵中值相同的元素或零元素的分布有一定的规律，则称此类的矩阵为特殊矩阵。1对称矩阵的压缩存储若n阶方阵An×n中的元素aij满足性质：，则称A为n阶对称矩阵。n阶对称矩阵An×n用二维数组存储时所占的存储空间为n2个元素的存储空间。可以将n2个元素压缩存储到只有n(n+1)/2个元素空间的一维数组M中。A中元素Aij与M中元素Mk的对应关系是：二维数组A与一维数组M的存储结构如图5.3(a)和图5.3(b)所示

27、。2下三角矩阵的压缩存储若n阶方阵An×n中的元素aij满足性质：当i<j时aij=0(0i,j<n),则称A为n阶下三角矩阵。用二维数组存储的下三角矩阵Ann中的元素可以压缩存储到一维数组Bn(n+1)/2中。数组A中的元素aij与数组B中的元素bk的对应关系是：矩阵A与数组B的存储结构如图5.3(a)和图5.3(b)所示。3带状矩阵的压缩存储如果矩阵中的所有非零元素都集中在以主对角线为中心的带状区域内，则称该矩阵为带状阵。带状区域若包含主对角线上下各b条对角线上的元素，那么b称为该带状阵的半带宽，该带状阵的带宽为m=(2b+1)。在半带宽为b的带状阵中，当ij>

28、b时，aij=0，带状区域的元素个数为：(2b+1)n-(b+1)b。例如，图5.4所示的5阶矩阵D5×5就是一个半带宽为b=2，带宽为m=5的带状阵。可将带宽为m的n阶方阵An×n中的非零元素压缩存储到一维数组B(n-1)m+1中。压缩存储过程是，对所有带状区域中的元素按行优先的顺序存储，并且除了第一行和最后一行外，每行都按照m（即2b+1）个非零元素计算，如果该行中的区域元素不够m个时要采用左、右零补齐的方法。这样，A中元素aij与B中元素Bk的对应关系是：图5.5是带状矩阵D的压缩存储示意图。5.3.2稀疏矩阵1稀疏矩阵的概念当用矩阵表示某个数学模型时，经常出现这样一

29、些特殊矩阵，它的阶数很高且非零元素的个数远远小于矩阵中零元素的个数，我们称这样的矩阵为稀疏矩阵(sparse matrix)。假设矩阵Am×n中有t个非零元素，令=t/(m×n)，则称为矩阵A的稀疏因子。通常认为，当0.05时称矩阵Am×n为稀疏矩阵。图5.6给出两个稀疏矩阵A5×5和B5×5的通常表示形式，显然矩阵B为矩阵A的装置。对于稀疏矩阵，若按通常办法将零元素与非零元素一起存储起来，显然浪费了大量的存储空间，本节讨论有关稀疏矩阵的三元组压缩存储问题以及三元组存储矩阵的基本运算方法。2稀疏矩阵的三元组表示在稀疏矩阵的压缩存储过程中，可以只

30、考虑非零元素的存储以达到压缩矩阵存储空间的目的。但是，稀疏矩阵中非零元素的出现是没有规律的，如果只是简单地将它们一个挨一个存放起来，将来就很难按行、列号找到它们。所以在存储一个非零元素Aij的值aij时，必须同时将它的行下标i和列下标j一起存储起来，即组成一个三元组(i,j,aij)。将一个稀疏矩阵的所有非零元素都用三元组来表示，若用顺序存储结构，就构成一个向量，该向量的每个分量是一个三元组。对于图5.6中的稀疏矩阵A，可按行优先的顺序用三元组顺序表示成向量：(0,2,-9),(0,4,5),(1,0,-7),(1,2,7),(3,1,8),(4,2,9)同理，稀疏矩阵B可用三元组顺序表示为向

31、量：(0,1,-7),(1,3,8),(2,0,-9),(2,1,7),(2,4,9),(4,0,5)3稀疏矩阵的基本操作由于稀疏矩阵是一种特殊的矩阵，所以有关稀疏矩阵的基本运算即为矩阵的基本运算。其主要操作有：（1）创建CreatSMatrix(&M) 该操作创建稀疏矩阵M；（2）复制CopySMatrix(M,&T) 该操作由稀疏矩阵M复制到T；（3）加法AddSMatrix(A,B,&C) 其功能是求稀疏矩阵A、B的和C；（4）减法SubMatrix(A,B,&C) 其功能是求稀疏矩阵A减B的差C；（5）转置TransSMatrix(M,&T) 其

32、功能是求稀疏矩阵M的转置T；（6）乘法MulMatrix(A,B,&C) 其功能是求稀疏矩阵A、B的积C。5.3.3稀疏矩阵的顺序存储表示与实现1稀疏矩阵的顺序存储结构在C+语言程序设计环境中，可定义稀疏矩阵的顺序存储结构为#include"iostream.h"#define MAXSIZE 2000 /定义非零元素的最大总数即三元组的最大容量typedef int Etype; /此处定义数组元素的类型为整型以便于上机操作struct Triple /定义三元组结构类型int i,j; Etype e;struct TSMatrixTriple dataMAXS

33、IZE+1;int mu,nu,tu; /mu-行数,nu-列数,tu-非零元素总数;说明：在用三元组的顺序存储来表示一个稀疏矩阵时，还必须同时确定该矩阵的行数(mu)和列数(nu)，只有这样才能保证矩阵的三元组表示与原矩阵的一一对应。按行优先的顺序可将图5.6中的稀疏矩阵A、B顺序表示为图5.7中的三元组A.data和B.data。其中，A.mu、A.nu、B.mu、B.nu的值均为5，A.tu、B.tu的值为6。2稀疏矩阵的输入操作操作void Create_TSM(TSMatrix &T)的功能是，根据行优先的顺序创建一个三元组顺序表示的稀疏矩阵T。void Create_TSM

34、(TSMatrix &T)int k;cout<<"请输入行数和列数:"cin>>T.mu>>T.nu;T.tu=0;cout<<"输入 i j e:n"dok=+T.tu;cin>>T.datak.i>>T.datak.j>>T.datak.e;while(T.datak.i<T.mu&&T.datak.j<T.nu&&T.datak.e);T.tu-;3稀疏矩阵的输出操作（1）操作void Print_TSM(TSM

35、atrix T)的作用是，以行优先的顺序输出三元组表示的稀疏矩阵T。void Print_TSM(TSMatrix T)int i;cout<<"行="<<T.mu<<",列="<<T.nu<<endl;for(i=1;i<=T.tu;i+)cout<<"("<<T.datai.i<<","cout<<T.datai.j<<","cout<<T.datai.e

36、<<")n"（2）程序void Print1_TSM(TSMatrix T)的作用是，以矩阵的形式输出三元组顺序表示的稀疏矩阵T。void Print1_TSM(TSMatrix T)int i,j,p,m=T.mu,n=T.nu;Etype *A=new Etypem*n; /根据T中的函数、列数定义矩阵Afor(i=0;i<m;i+) /对A进行零初始化for(j=0;j<n;j+)Ai*n+j=0;for(p=1;p<=T.tu;p+) /通过T计算A的值i=T.datap.i; j=T.datap.j;Ai*n+j=T.datap.e;

37、for(i=0;i<m;i+) /以矩阵的形式输出A的值for(j=0;j<n;j+)cout<<Ai*n+j<<' 'cout<<endl;deleteA;4稀疏矩阵的转置操作对于用通常形式存储的矩阵，其转置操作过程是，只要将元素的行下标和列下标互换即可。对于用三元组顺序存储表示的稀疏矩阵，其转置操作似乎只在三元组表中将i,j两列数对调一下就可以了，但实际上并非那么简单。由于三元组表中的元素是按行号递增的顺序排列，在行号相同的情况下再按列号递增排列。那么转置后也应当保持这一规律才行。例如，图5.7中A.data与B.data互为

38、转置关系。下面以此为例来说明有关稀疏矩阵转置操作的算法。算法思想对A.data中每个三元组的列下标进行扫描，先找其值为j=0的，若有，则将其行、列下标对换后移至B.data中依此存放，比如A.data中的(1,0,-7)à(0,1,-7)；再重新扫描A.data中每个三元组的列下标，查找其值为j=1的，若有，则将其行、列下标对换后移至B.data中依此存放，比如A.data中的(3,1,8)à(1,3,8)；再重新扫描A.data中的列下标，查找其值为j=2的，若有，则将其行、列下标对换后移至B.data中依此存放，比如(0,2,-9)à(2,0,-9)，(1,2

39、,7)à(2,1,7)，(4,2,9)à(2,4,9)，以此类推，直到所有三元组都处理完为止。算法实现操作函数void Trans_TSM(TSMatrix S,TSMatrix &T)计算稀疏矩阵S的转置矩阵T。void Trans_TSM(TSMatrix S,TSMatrix &T)int j,n,p;T.mu=S.nu;T.nu=S.mu;T.tu=S.tu;if(!T.tu)return;n=1;for(j=0;j<S.nu;j+) /逐列按递增顺序查找元素for(p=1;p<=S.tu;p+)if(S.datap.j=j)T.data

40、n.e=S.datap.e;T.datan.i=j;T.datan.j=S.datap.i;n+;算法分析在转置操作函数Trans_TSM()的算法中，其时间复杂度为O(nu×tu)，当矩阵中非零元素的个数tu与元素总数mu×nu同数量级时，其时间复杂度就成了O(mu×nu2)。显然，虽然节省了存储空间，但是时间复杂度却大于通常矩阵转置算法的时间复杂度。可见该算法仅适用于tu远远小于mu×nu的情况。5三元组矩阵的快速转置算法思想快速转置的算法思想是，在求M的转置矩阵T时，先通过对M.data的第一次扫描求出M中每一列非零元素的个数到向量num中，再通过

41、num求出T中每一行非零元素的起始下标向量cpot，最后再通过对M.data的第二次扫描便可求得其转置矩阵T。例如，对图5.7中三元组A.data中每个元素的列下标进行扫描，统计出每列元素的个数如表5.1中num所示。由num可算出转置矩阵B的每行元素中第一个元素的初始位置序列cpot。在对A.data进行第二次扫描时，cpot中相应元素将进行调整，其变化过程如表5.1所示。表5.1 快速转置算法的实现过程num cpot行位置的变化过程0101p0=1(3),21111+1=2p1=2(5),32322+1=3p2=3(1),4(4),5(6),63033+3=6p3=64146+0=6p4

42、=6(2),7算法实现void FTrans_TSM(TSMatrix M,TSMatrix &T)T.tu=M.tu,T.mu=M.nu,T.nu=M.mu;int* num=new intM.nu; /为向量num分配空间int* cpot=new intM.nu; /为向量cpot分配空间int col,p,q,t;if(!T.tu)return;for(col=0;col<M.nu;col+)numcol=0;for(t=1;t<=M.tu;t+)+numM.datat.j; /求每列中非零元素的个数cpot0=1; /第0行的起始位置为1for(col=1;col

43、<M.nu;col+)cpotcol=cpotcol-1+numcol-1; /求第col行的起始位置cpotcolfor(p=1;p<=M.tu;p+) /通过一次性扫描求出转置矩阵Tcol=M.datap.j;q=cpotcol+;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;deletenum; deletecpot;算法分析在快速转置操作函数FTrans_TSM()的算法中，比算法Trans_TSM()多使用了两个辅助数组（num和cpot）的存储空间，但是该算法的时间复杂度仅为O(nu+tu)，显然

44、比前者快了很多。6三元组矩阵的加法运算假定矩阵M、N均为三元组表示的稀疏矩阵且具有相同的行数和列数，可对稀疏矩阵进行求和操作：A=M+N。算法思想从前往后逐个扫描M.data和N.data中的每个三元组M.datap,N.dataq：(1) 行不相等时取行小者到A.data(2) 行相等但是列不相等时取列小者到A.data(3) 行、列都相等时求对应元素的和，和值非零时移至A.data。算法实现void Add_TSM(TSMatrix M,TSMatrix N,TSMatrix& A)Etype e;int p=1,q=1,r=1;while(p<=M.tu&&

45、q<=N.tu) if(M.datap.i=N.dataq.i) if(M.datap.j<N.dataq.j) A.datar+=M.datap+; else if(M.datap.j>N.dataq.j) A.datar+=N.dataq+; else if(e=M.datap.e+N.dataq.e) /如果和不为零则保存结果A.datar=M.datap;A.datar+.e=e;p+;q+; else if(M.datap.i<N.dataq.i) A.datar+=M.datap+; else A.datar+=N.dataq+;while(p<=M.

46、tu)A.datar+=M.datap+;while(q<=N.tu)A.datar+=N.dataq+;A.mu=M.mu,A.nu=M.nu,A.tu=r-1;算法分析本算法的时间复杂度为O(M.tu+N.tu)，通过加法运算的函数调用可以实现稀疏矩阵的减法运算。7三元组矩阵的减运算操作函数void Sub_TSM(TSMatrix M,TSMatrix N,TSMatrix& A)实现三元组矩阵的减法运算A=M-N。void Sub_TSM(TSMatrix M,TSMatrix N,TSMatrix& A)int p;for(p=1;p<=N.tu;p+)N

47、.datap.e*=-1;Add_TSM(M,N,A);8三元组矩阵的乘法（1）函数void Frpot(int rpot,TSMatrix M)完成的操作是，求稀疏矩阵M中每行起始位置的向量rpot。void Frpot(int rpot,TSMatrix M)int* num=new intM.mu;int raw,t;for(raw=0;raw<M.mu;raw+)numraw=0;for(t=1;t<=M.tu;t+)+numM.datat.i; /求每行非零元素的个数rpot0=1; /第0行的起始位置为1for(raw=1;raw<M.mu;raw+)rpotra

48、w=rpotraw-1+numraw-1; /求第raw行的起始位置rpotrawdeletenum;（2）函数int Ffand(Etype &e,int i,int j,int rpot,TSMatrix M)完成的操作是，求数组M中的元素a(i,j)到e，操作成功返回1，否则返回0。int Ffand(Etype &e,int i,int j,int rpot,TSMatrix M)int k=rpoti;for(;k<=M.tu&&(M.datak.i=i);k+)if(M.datak.j=j)e=M.datak.e;return 1;else i

49、f(M.datak.j>j) break;return 0;（3）函数void Mult_TSM(TSMatrix A,TSMatrix B,TSMatrix& C)的功能是，实现三元组矩阵的乘法运算C=A×B。void Mult_TSM(TSMatrix A,TSMatrix B,TSMatrix& C)int i,j,k;Etype s,e1,e2;int *Anum=new intA.mu;int *Bnum=new intB.mu; Frpot(Anum,A);Frpot(Bnum,B);C.mu=A.mu;C.nu=B.nu;C.tu=0;for(i=

50、0;i<A.mu;i+)for(j=0;j<B.nu;j+)s=0;for(k=0;k<A.nu;k+) if(Ffand(e1,i,k,Anum,A)&&Ffand(e2,k,j,Bnum,B)s+=e1*e2;if(s)k=+C.tu;C.datak.e=s;C.datak.i=i;C.datak.j=j;deleteAnum; deleteBnum;9三元组矩阵运算的演示主程序程序中，首先以三元组顺序结构分别建立稀疏矩阵A和B，然后求出A的转置矩阵C和快速转置矩阵D，再分别求出：A与B的和E、A与B的差F、A与B的积G。并以矩阵形式显示输出每个矩阵的值。

51、void main()TSMatrix A,B,C,D,E,F,G;while(1)cout<<"输入两个行、列相同的矩阵："cout<<"1-求转置与快速转置，2-矩阵的和与差，3-矩阵的积.n"cout<<"输入三元组矩阵A：n" Create_TSM(A);cout<<"输入三元组矩阵B：n" Create_TSM(B);if(A.mu!=A.nu)|(A.mu!=B.mu)|(B.mu!=B.nu) cout<<"维数不符合要求请重新输入

52、!n"continue; Trans_TSM(A,C);FTrans_TSM(A,D);cout<<"A的转置矩阵为:n"Print1_TSM(C);cout<<"A的快速转置矩阵为:n"Print1_TSM(D);Add_TSM(A,B,E);Sub_TSM(A,B,F);cout<<"A+B的和为:n"Print1_TSM(E);cout<<"A-B的差为:n"Print1_TSM(F);Mult_TSM(A,B,G);cout<<"

53、;A*B的积为:n"Print1_TSM(G);cout<<"矩阵A为:n"Print1_TSM(A);cout<<"矩阵B为:n"Print1_TSM(B);运行结果为：输入两个行、列相同的矩阵：1-求转置与快速转置，2-矩阵的和与差，3-矩阵的积.输入三元组矩阵A：请输入行数和列数:5 5输入 i j e:0 2 -91 0 -71 2 73 1 84 2 90 0 0输入三元组矩阵B：请输入行数和列数:5 5输入 i j e:0 1 -71 3 82 0 -92 1 72 4 94 0 50 0 0A的转置矩阵为:0 -7 0 0 00 0 0 8 0-9 7 0 0 90 0 0 0 00 0 0 0 0A的快速转置矩阵为:0 -7 0 0 00 0 0 8 0-9 7 0 0 90 0 0 0 00 0 0 0 0A+B的和为:0 -7 -