《第5章數組和廣義表》習題解答要點

1、第5章 數組和廣義表本章學習要點掌握多維數組在行優(yōu)先順序存儲結構中地址的計算方法了解特殊矩陣壓縮存儲時的下標轉換方法掌握稀疏矩陣常用的兩種壓縮存儲表示方法（三元組表和十字鏈表表示法）的特點和存儲結構掌握稀疏矩陣在三元組表表示下的基本運算（矩陣加法、減法、轉置和乘法等）方法了解廣義表的有關概念、廣義表的各種表示方法和存儲結構掌握廣義表的基本操作（求廣義表的表頭、表尾、表的深度以及廣義表的復制等）數組是最常用的數據結構之一，幾乎所有的高級程序設計語言都把數組類型設定為內部類型。在前面討論的線性結構中，其數據元素都是非結構的原子類型，元素的值是不可再分解的。本章所討論的數組可以看成是線性表的一種擴展

2、，即線性表中的每個數據元素本身也是一個線性表。稀疏矩陣是一種特殊的二維數組，因其在壓縮存儲方面的特點而被廣泛使用。廣義表是一種較為復雜的數據結構，它是線性結構和樹型結構的拓廣。廣義表被廣泛應用于人工智能等領域。5.1數組的概念如果一個向量的所有元素又都是向量（或稱子向量），且這些子向量具有相同的上限和下限標號，那么這種特殊形式的向量稱為數組。一維數組是一個向量，它的每一個元素都是該結構中不可分割的最小單位。n(n>1)維數組是一個向量，它的每個元素都是n-1維數組，且具有相同的上限和下限。從邏輯結構上看，n維數組Array中各元素的位置由該元素的下標唯一確定，一旦給定一組下標(j0,j1

3、,j2,jn-1)，都存在唯一的一個與其相對應的元素值a稱為數組元素，記為a(j0,j1,j2,jn-1)。其中，0<=ji<bi，bi稱為第i維的長度(i=0,1,2,n-1)。數組一旦被定義，它的元素類型（即數組類型）、維數、各維的界（長度）就不再改變。所以數組的基本操作主要有：（1）初始化InitArray(Array &A,int dim,int* bounds)：該操作根據數組元素類型、維數dim和長度bounds定義一個數組（初始化數組）A。（2）讀取操作Value(Array A,int* script,EType &e)：該操作根據下script標讀

4、取數組A中的元素到e中。（3）修改操作Assign(Array& A,int* script,EType e)：該操作根據下標script修改數組A中的元素為e的值。（4）銷毀操作：該操作回收一個數組所占的資源（銷毀數組）。5.2數組的順序存儲表示和實現由于數組不作插入和刪除操作，也就是說，一旦建立了數組，則該數組結構中的數據元素個數和元素之間的關系就不再發(fā)生變動。因此，采用順序存儲結構表示數組是最合理的方式。但是，由于內存地址是一維結構，而數組可以是多維結構，所以，必須有一個從多維下標到一維地址的對應關系。1數組的兩種順序存儲方法（1）以行（左下標）為主序的存儲結構該存儲結構以最左面

5、的下標為主序，右下標優(yōu)先變化，即下標變化順序是從右到左。以二維數組為例，其內存結構如圖5.1（a）所示。對于三維數組：（有2頁、2行、3列），按左下標為主序的內存結構如圖5.1（b）所示。（2）以列（右下標）為主序的存儲結構該存儲結構以最右面的下標為主序，左下標優(yōu)先變化，即下標變化順序是從左到右。以二維數組：為例，其內存結構如圖5.2（a）所示。對于三維數組：（有2頁、2行、3列），按右下標為主序的內存結構如圖5.2（b）所示。2左下標為主序存儲的n維數組中的元素a(j0,j1,.,jn-1)的地址計算公式對于一個已經被定義的二維數組Ab0×b1=(aij)b0×b1，只要

6、給出該數組存放的起始地址LOC(a00)、數組元素的行下標i和列下標j，以及每個元素所占用的存儲單元（字節(jié)）數L，便可以求得元素aij在內存中的首地址LOC(aij)。地址計算公式為： 其中b1為數組第2維的長度（界）。對于以行為主序的n維數組，數組元素a(j0,j1,.,jn-1)的地址計算公式為：其中為數組元素a00.0的地址，L為每個元素所占內存的字節(jié)數，b0,b1,.,bn-1為每一維的長度。如果記：,即可得到映像常數向量：，相應的n維數組元素的地址計算公式可簡寫為：完全類似地，讀者可以自行給出以右下標為主序的n維數組元素a(j0,j1,.,jn-1)的地址計算公式?！纠?.1】二維數

7、組M5×6的元素是4個字符（每個字符占1個存儲單元）組成的串，那么M按行優(yōu)先（以左下標為主序）存儲時元素M35的起始地址與M按列優(yōu)先（以右下標為主序）存儲時的哪個元素的起始地址相同？解：按行優(yōu)先存儲時元素M35的起始地址為：LOC(M35) =LOC(M00)+(i×6+j)×4=LOC(M00)+(3×6+5)×4=LOC(M00)+23×4按列優(yōu)先存儲時元素Mij的起始地址為：LOC(Mij)=LOC(M00)+(j×5+i)×4=LOC(M00)+23×4=LOC(M00)+(4×5+3)

8、×4所以，要求的元素Mij即為M34?！纠?.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+(3×5×6+2×6+0)×4=1408LOC(A135

9、)=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)×2=238LOC(A320)=100+(0×5×4+2×4+3)&

10、#215;2=122LOC(A135)=100+(5×5×4+3×4+1)×2=3261數組的順序存儲結構表示在C+語言環(huán)境中，順序數組的存儲表示如下#include"iostream.h" /標準輸入輸出頭文件typedef int EType; /便于上機操作定義數組類型為整型（int）struct ArrayEType *base; /數組的基地址int dim; /數組的維數int *bounds; /數組維界向量基地址int *constent; /數組元素的映像常數向量;2數組的初始化操作操作int InitArray(A

11、rray &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.bounds=new intdim; /分配維界向量的存儲空間A.constent=new intdim; /分配映像向量

12、的存儲空間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)提取數組元素的操作操作int Value(Array A,int* script,EType &e)的功能是，根據下標向量scr

13、ipt提取數組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;簡化的提取數組元素操作函數EType Value(Array A,int* script)，該操作對下標越界不做檢查。EType V

14、alue(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 Assign(Array& A,int* script,EType e)int i,off=0;for(i=0;i<A

15、.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=0;i<A.dim;i+)length*=A.boundsi;cout<<"以行為主序的順序輸入

16、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)的功能是，按左下標為主序，輸出一維、二維、三維和多維數組A中的元素。void Arrayoutput(Array A)int

17、 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)<<" "cout<<endl;break;case 3: /按三維數組格式輸出f

18、or(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: /三維以上按左下標優(yōu)先的一維數組格式輸出cout<<"維數為"<<A.dim<<"大于3n按

19、左下標為主序輸出所有元素的值: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(Array& A,Array B)if(B.dim!=2)return 0;int dim=2,s2,s12;int b

20、ounds=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矩陣操作的演示主程序在演示程序中，首先按左下標（行）優(yōu)先的順序分別建立一維、二維、三維和四維數組，以及二維數組的轉置，然后顯示輸出各個數組的值。void main()Array A1,A2,A22,A3,A4;int b1=5,b2=4,5,b22=5,4,b3=3,4,5

21、,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<<"A2的轉置矩陣為:n"Arrayoutput(A22);InitArray(A3,3,b3); /定義A3為三維

22、數組大小為3*4*5ArrayInput(A3);cout<<"A3結果為:n"Arrayoutput(A3);InitArray(A4,4,b4); /定義A4為四維數組大小為2*3*2*5ArrayInput(A4);cout<<"A4結果為:n"Arrayoutput(A4);程序運行結構為：以行為主序的順序輸入A5中的5個元素的值。1 2 3 4 5A1結果為:1 2 3 4 5以行為主序的順序輸入A4*5中的20個元素的值。1 2 3 4 53 4 5 6 75 6 7 8 97 8 9 0 1A2結果為:1 2 3 4

23、 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 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

24、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 40 41 42 43 44 45A4結果為:維數為4大于3按左下標為主序輸出所有元素的值:10 11 12 13 14 15 16 17

25、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) 是很多科學與工程計算問題中研究的數學對象。在數據結構中，主要關心的不是矩陣本身，而是如何存儲矩陣元素，使矩陣的各種運算能有效地進行。在高級語言程序設計中，通常是用二維數組來存儲矩陣元素的。然而，在數值分析中經常出現一些階數很高的矩陣，同時在矩陣中又有許多值相同元素或者是零元素。為了節(jié)省存儲空間，可以對這類矩陣進行壓縮存儲。即，對多個值相同的元素只分配一個存儲空間；對零元素不分配存儲空間。若

26、矩陣中值相同的元素或零元素的分布有一定的規(guī)律，則稱此類的矩陣為特殊矩陣。1對稱矩陣的壓縮存儲若n階方陣An×n中的元素aij滿足性質：，則稱A為n階對稱矩陣。n階對稱矩陣An×n用二維數組存儲時所占的存儲空間為n2個元素的存儲空間?？梢詫2個元素壓縮存儲到只有n(n+1)/2個元素空間的一維數組M中。A中元素Aij與M中元素Mk的對應關系是：二維數組A與一維數組M的存儲結構如圖5.3(a)和圖5.3(b)所示。2下三角矩陣的壓縮存儲若n階方陣An×n中的元素aij滿足性質：當i<j時aij=0(0i,j<n),則稱A為n階下三角矩陣。用二維數組存儲的

27、下三角矩陣Ann中的元素可以壓縮存儲到一維數組Bn(n+1)/2中。數組A中的元素aij與數組B中的元素bk的對應關系是：矩陣A與數組B的存儲結構如圖5.3(a)和圖5.3(b)所示。3帶狀矩陣的壓縮存儲如果矩陣中的所有非零元素都集中在以主對角線為中心的帶狀區(qū)域內，則稱該矩陣為帶狀陣。帶狀區(qū)域若包含主對角線上下各b條對角線上的元素，那么b稱為該帶狀陣的半帶寬，該帶狀陣的帶寬為m=(2b+1)。在半帶寬為b的帶狀陣中，當ij>b時，aij=0，帶狀區(qū)域的元素個數為：(2b+1)n-(b+1)b。例如，圖5.4所示的5階矩陣D5×5就是一個半帶寬為b=2，帶寬為m=5的帶狀陣。可將

28、帶寬為m的n階方陣An×n中的非零元素壓縮存儲到一維數組B(n-1)m+1中。壓縮存儲過程是，對所有帶狀區(qū)域中的元素按行優(yōu)先的順序存儲，并且除了第一行和最后一行外，每行都按照m（即2b+1）個非零元素計算，如果該行中的區(qū)域元素不夠m個時要采用左、右零補齊的方法。這樣，A中元素aij與B中元素Bk的對應關系是：圖5.5是帶狀矩陣D的壓縮存儲示意圖。1稀疏矩陣的概念當用矩陣表示某個數學模型時，經常出現這樣一些特殊矩陣，它的階數很高且非零元素的個數遠遠小于矩陣中零元素的個數，我們稱這樣的矩陣為稀疏矩陣(sparse matrix)。假設矩陣Am×n中有t個非零元素，令=t/(m&

29、#215;n)，則稱為矩陣A的稀疏因子。通常認為，當0.05時稱矩陣Am×n為稀疏矩陣。圖5.6給出兩個稀疏矩陣A5×5和B5×5的通常表示形式，顯然矩陣B為矩陣A的裝置。對于稀疏矩陣，若按通常辦法將零元素與非零元素一起存儲起來，顯然浪費了大量的存儲空間，本節(jié)討論有關稀疏矩陣的三元組壓縮存儲問題以及三元組存儲矩陣的基本運算方法。2稀疏矩陣的三元組表示在稀疏矩陣的壓縮存儲過程中，可以只考慮非零元素的存儲以達到壓縮矩陣存儲空間的目的。但是，稀疏矩陣中非零元素的出現是沒有規(guī)律的，如果只是簡單地將它們一個挨一個存放起來，將來就很難按行、列號找到它們。所以在存儲一個非零元素

30、Aij的值aij時，必須同時將它的行下標i和列下標j一起存儲起來，即組成一個三元組(i,j,aij)。將一個稀疏矩陣的所有非零元素都用三元組來表示，若用順序存儲結構，就構成一個向量，該向量的每個分量是一個三元組。對于圖5.6中的稀疏矩陣A，可按行優(yōu)先的順序用三元組順序表示成向量：(0,2,-9),(0,4,5),(1,0,-7),(1,2,7),(3,1,8),(4,2,9)同理，稀疏矩陣B可用三元組順序表示為向量：(0,1,-7),(1,3,8),(2,0,-9),(2,1,7),(2,4,9),(4,0,5)3稀疏矩陣的基本操作由于稀疏矩陣是一種特殊的矩陣，所以有關稀疏矩陣的基本運算即為矩

31、陣的基本運算。其主要操作有：（1）創(chuàng)建CreatSMatrix(&M) 該操作創(chuàng)建稀疏矩陣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) 其功能是求稀疏矩陣M的轉置T；（6）乘法MulMatrix(A,B,&C) 其功能是求稀疏矩陣A、B的積C。1稀疏矩陣的順序存儲結構在C+語言程序設計環(huán)境中，可定義稀疏矩陣的順序

32、存儲結構為#include"iostream.h"#define MAXSIZE 2000 /定義非零元素的最大總數即三元組的最大容量typedef int Etype; /此處定義數組元素的類型為整型以便于上機操作struct Triple /定義三元組結構類型int i,j; Etype e;struct TSMatrixTriple dataMAXSIZE+1;int mu,nu,tu; /mu-行數,nu-列數,tu-非零元素總數;說明：在用三元組的順序存儲來表示一個稀疏矩陣時，還必須同時確定該矩陣的行數(mu)和列數(nu)，只有這樣才能保證矩陣的三元組表示與原矩

33、陣的一一對應。2稀疏矩陣的輸入操作操作void Create_TSM(TSMatrix &T)的功能是，根據行優(yōu)先的順序創(chuàng)建一個三元組順序表示的稀疏矩陣T。void Create_TSM(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

34、.i<T.mu&&T.datak.j<T.nu&&T.datak.e);T.tu-;3稀疏矩陣的輸出操作（1）操作void Print_TSM(TSMatrix T)的作用是，以行優(yōu)先的順序輸出三元組表示的稀疏矩陣T。void Print_TSM(TSMatrix T)int i;cout<<"行="<<T.mu<<",列="<<T.nu<<endl;for(i=1;i<=T.tu;i+)cout<<"("<

35、<T.datai.i<<","cout<<T.datai.j<<","cout<<T.datai.e<<")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(

36、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;for(i=0;i<m;i+) /以矩陣的形式輸出A的值for(j=0;j<n;j+)cout<<Ai*n+j<<' 'cout<<endl;deleteA;4稀疏矩陣的轉置操作對于用通常形式存儲的矩陣，其轉置操作過程是，只要將元素的行下標和列下標互換即可。對于用三元組順序存儲算法思想對A.data中每個三元組的列下標進行掃描，先找其值為j

37、=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,7)à(2,1,7)，(4,2,9)à(2,4,9)，以此類推，直到所有三元組都處理完為止。算法實

38、現操作函數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.datan.e=S.datap.e;T.datan.i=j;T.datan.j=S.datap.i;n+;算法分析在轉置操作函數

39、Trans_TSM()的算法中，其時間復雜度為O(nu×tu)，當矩陣中非零元素的個數tu與元素總數mu×nu同數量級時，其時間復雜度就成了O(mu×nu2)。顯然，雖然節(jié)省了存儲空間，但是時間復雜度卻大于通常矩陣轉置算法的時間復雜度?？梢娫撍惴▋H適用于tu遠遠小于mu×nu的情況。5三元組矩陣的快速轉置算法思想快速轉置的算法思想是，在求M的轉置矩陣T時，先通過對M.data的第一次掃描求出M中每一列非零元素的個數到向量num中，再通過num求出T中每一行非零元素的起始下標向量cpot，最后再通過對M.data的第二次掃描便可求得其轉置矩陣T。例如，對圖

40、5.7中三元組A.data中每個元素的列下標進行掃描，統(tǒng)計出每列元素的個數如表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=6(2),7算法實現void FTrans_TSM(TSMatrix M,TSMatrix &T)T.tu=M

41、.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<M.nu;col+)cpotcol=cpotcol-1+numcol-1; /求第col行的起始位置cpotco

42、lfor(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)，顯然比前者快了很多。6三元組矩陣的加法運算假定矩陣M、N均為三元組表示的稀疏矩陣且具有相同的行數和列數，可對稀疏矩陣進行求和

43、操作：A=M+N。算法思想(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&&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

44、.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.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.t

45、u+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.datap.e*=-1;Add_TSM(M,N,A);8三元組矩陣的乘法（1）函數void Frpot(int rpot,TSMatrix M)完成的操作是，求稀疏矩陣M中每行起始位置的向量rpot。voi

46、d 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+)rpotraw=rpotraw-1+numraw-1; /求第raw行的起始位置rpotrawdeletenum;（2）函數int Ffand(Etype &e,int i,int j,int rpot,TSMa

47、trix 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 if(M.datak.j>j) break;return 0;（3）函數void Mult_TSM(TSMatrix A,TSMatrix B,TSMatrix& C)的功能是，實現三元組矩陣的乘

48、法運算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=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,

49、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。并以矩陣形式顯示輸出每個矩陣的值。void main()TSMatrix A,B,C,D,E,F,G;while(1)cout<<"輸入兩個行、列相同的矩陣："cout<<"1-求轉置與快

50、速轉置，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<<"維數不符合要求請重新輸入!n"continue; Trans_TSM(A,C);FTrans_TSM(A,D);cout<<"A的轉置矩陣為:n"Print1_TSM(C);cout<

51、<"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<<"A*B的積為:n"Print1_TSM(G);cout<<"矩陣A為:n"Print1_TSM(A);cout<<"矩陣B為:n"P

52、rint1_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 0

53、A+B的和為:0 -7 -9 0 0-7 0 7 8 0-9 7 0 0 90 8 0 0 05 0 9 0 0A-B的差為:0 7 -9 0 0-7 0 7 -8 09 -7 0 0 -90 8 0 0 0-5 0 9 0 0A*B的積為:81 -63 0 0 -81-63 98 0 0 630 0 0 0 00 0 0 64 0-81 63 0 0 81矩陣A為:0 0 -9 0 0-7 0 7 0 00 0 0 0 00 8 0 0 00 0 9 0 0矩陣B為:0 -7 0 0 00 0 0 8 0-9 7 0 0 90 0 0 0 05 0 0 0 0當稀疏矩陣中非零元素的個數和位置在操作過程中變化比較大時，就不易采用順序存儲結構來表示三元組。例如，在稀疏矩陣A中隨機增加或刪除一個非零元素，都會引起A.data中元素的移動。為此，下面給出三元組的另一種存儲表示法，即十字鏈表示法。1十字鏈表的存儲結構十字鏈表的結點結構如圖5.8所示，其中的i,j,e分別表示非零元素所在的行、列下標以及元素的值（三元組），指針down指向同列的下一個非零元素，指針right指向同行右邊的非零元素。由