《第5章數(shù)組和廣義表》習(xí)題解答要點(diǎn)

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

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

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

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

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

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

7、組M5×6的元素是4個(gè)字符（每個(gè)字符占1個(gè)存儲(chǔ)單元）組成的串，那么M按行優(yōu)先（以左下標(biāo)為主序）存儲(chǔ)時(shí)元素M35的起始地址與M按列優(yōu)先（以右下標(biāo)為主序）存儲(chǔ)時(shí)的哪個(gè)元素的起始地址相同？解：按行優(yōu)先存儲(chǔ)時(shí)元素M35的起始地址為：LOC(M35) =LOC(M00)+(i×6+j)×4=LOC(M00)+(3×6+5)×4=LOC(M00)+23×4按列優(yōu)先存儲(chǔ)時(shí)元素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為按左下標(biāo)為主序存儲(chǔ)的3維數(shù)組，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且元素A000的首地址為1000，分別計(jì)算元素A123、A320和A135的首地址。解：按左下標(biāo)為主序的地址計(jì)算公式為：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為按右下標(biāo)為主序存儲(chǔ)的3維數(shù)組，每個(gè)元素占2個(gè)存儲(chǔ)單元，并且元素A000的首地址為100，分別計(jì)算元素A123、A320和A135的首地址。解：按右下標(biāo)為主序的地址計(jì)算公式為：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數(shù)組的順序存儲(chǔ)結(jié)構(gòu)表示在C+語言環(huán)境中，順序數(shù)組的存儲(chǔ)表示如下#include"iostream.h" /標(biāo)準(zhǔn)輸入輸出頭文件typedef int EType; /便于上機(jī)操作定義數(shù)組類型為整型（int）struct ArrayEType *base; /數(shù)組的基地址int dim; /數(shù)組的維數(shù)int *bounds; /數(shù)組維界向量基地址int *constent; /數(shù)組元素的映像常數(shù)向量;2數(shù)組的初始化操作操作int InitArray(A

11、rray &A,int dim,int* bounds)的功能是，根據(jù)維數(shù)dim和維界向量bounds設(shè)置數(shù)組A的維數(shù)A.dim、維界向量A.bounds、以及元素映像向量A.constent，并分配相應(yīng)大小的存儲(chǔ)空間A.base。如果輸入維數(shù)dim合理返回1，表示操作成功，否則返回0表示操作失敗。int InitArray(Array &A,int dim,int* bounds)int length=1,i;if(dim<1)return 0;A.bounds=new intdim; /分配維界向量的存儲(chǔ)空間A.constent=new intdim; /分配映像向量

12、的存儲(chǔ)空間for(i=0;i<dim;i+)length*=boundsi; /計(jì)算數(shù)組元素的總數(shù)A.boundsi=boundsi;A.dim=dim;A.base=new ETypelength; /分配數(shù)組元素的存儲(chǔ)空間A.constentdim-1=1;for(i=dim-2;i>=0;i-) /計(jì)算數(shù)組元素的映像常數(shù)向量A.constenti=A.constenti+1*A.boundsi+1;return 1;3根據(jù)下標(biāo)(script)提取數(shù)組元素的操作操作int Value(Array A,int* script,EType &e)的功能是，根據(jù)下標(biāo)向量scr

13、ipt提取數(shù)組A中相應(yīng)元素的值到e中。如果下標(biāo)合理返回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; /計(jì)算對(duì)應(yīng)元素的偏移量offe=A.baseoff;return 1;簡化的提取數(shù)組元素操作函數(shù)EType Value(Array A,int* script)，該操作對(duì)下標(biāo)越界不做檢查。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根據(jù)下標(biāo)(script)修改數(shù)組元素的操作操作int Assign(Array& A,int* script,EType e)的作用是，根據(jù)下標(biāo)向量script修改數(shù)組A中相應(yīng)元素的值為e。如果下標(biāo)合理返回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; /計(jì)算對(duì)應(yīng)元素的偏移量offA.baseoff=e;return 1;5數(shù)組的按行序輸入操作操作void ArrayInput(Array& A)的功能是，以左下標(biāo)為主序依次輸入多維數(shù)組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<<"個(gè)元素的值。n"for(i=0;i<length;i+)cin>>A.basei;6數(shù)組的按行序輸出操作操作void Arrayoutput(Array A)的功能是，按左下標(biāo)為主序，輸出一維、二維、三維和多維數(shù)組A中的元素。void Arrayoutput(Array A)int

17、 s3,i,len=1;switch(A.dim)case 1: /按一維數(shù)組格式輸出for(s0=0;s0<A.bounds0;s0+) cout<<Value(A,s)<<" "cout<<endl;break;case 2: /按二維數(shù)組格式輸出for(s0=0;s0<A.bounds0;s0+)for(s1=0;s1<A.bounds1;s1+)cout<<Value(A,s)<<" "cout<<endl;break;case 3: /按三維數(shù)組格式輸出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: /三維以上按左下標(biāo)優(yōu)先的一維數(shù)組格式輸出cout<<"維數(shù)為"<<A.dim<<"大于3n按

19、左下標(biāo)為主序輸出所有元素的值:n"for(i=0;i<A.dim;i+)len*=A.boundsi;for(i=0;i<len;i+)cout<<A.basei<<" "cout<<endl;7矩陣的轉(zhuǎn)置操作操作int Trans(Array & A,Array B)作用是，計(jì)算矩陣B的轉(zhuǎn)置矩陣A。如果B的維數(shù)不等于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); /初始化數(shù)組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矩陣操作的演示主程序在演示程序中，首先按左下標(biāo)（行）優(yōu)先的順序分別建立一維、二維、三維和四維數(shù)組，以及二維數(shù)組的轉(zhuǎn)置，然后顯示輸出各個(gè)數(shù)組的值。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為一維數(shù)組長度為5ArrayInput(A1);cout<<"A1結(jié)果為:n"Arrayoutput(A1);InitArray(A2,2,b2); /定義A2為二維數(shù)組大小為4*5ArrayInput(A2);cout<<"A2結(jié)果為:n"Arrayoutput(A2); Trans(A22,A2);cout<<"A2的轉(zhuǎn)置矩陣為:n"Arrayoutput(A22);InitArray(A3,3,b3); /定義A3為三維

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

23、 53 4 5 6 75 6 7 8 97 8 9 0 1A2的轉(zhuǎn)置矩陣為:1 3 5 72 4 6 83 5 7 94 6 8 05 7 9 1以行為主序的順序輸入A3*4*5中的60個(gè)元素的值。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結(jié)果為:第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個(gè)元素的值。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結(jié)果為:維數(shù)為4大于3按左下標(biāo)為主序輸出所有元素的值: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矩陣的壓縮存儲(chǔ)矩陣(matrix) 是很多科學(xué)與工程計(jì)算問題中研究的數(shù)學(xué)對(duì)象。在數(shù)據(jù)結(jié)構(gòu)中，主要關(guān)心的不是矩陣本身，而是如何存儲(chǔ)矩陣元素，使矩陣的各種運(yùn)算能有效地進(jìn)行。在高級(jí)語言程序設(shè)計(jì)中，通常是用二維數(shù)組來存儲(chǔ)矩陣元素的。然而，在數(shù)值分析中經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時(shí)在矩陣中又有許多值相同元素或者是零元素。為了節(jié)省存儲(chǔ)空間，可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)。即，對(duì)多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配存儲(chǔ)空間。若

26、矩陣中值相同的元素或零元素的分布有一定的規(guī)律，則稱此類的矩陣為特殊矩陣。1對(duì)稱矩陣的壓縮存儲(chǔ)若n階方陣An×n中的元素aij滿足性質(zhì)：，則稱A為n階對(duì)稱矩陣。n階對(duì)稱矩陣An×n用二維數(shù)組存儲(chǔ)時(shí)所占的存儲(chǔ)空間為n2個(gè)元素的存儲(chǔ)空間。可以將n2個(gè)元素壓縮存儲(chǔ)到只有n(n+1)/2個(gè)元素空間的一維數(shù)組M中。A中元素Aij與M中元素Mk的對(duì)應(yīng)關(guān)系是：二維數(shù)組A與一維數(shù)組M的存儲(chǔ)結(jié)構(gòu)如圖5.3(a)和圖5.3(b)所示。2下三角矩陣的壓縮存儲(chǔ)若n階方陣An×n中的元素aij滿足性質(zhì)：當(dāng)i<j時(shí)aij=0(0i,j<n),則稱A為n階下三角矩陣。用二維數(shù)組存儲(chǔ)的

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

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

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

30、Aij的值aij時(shí)，必須同時(shí)將它的行下標(biāo)i和列下標(biāo)j一起存儲(chǔ)起來，即組成一個(gè)三元組(i,j,aij)。將一個(gè)稀疏矩陣的所有非零元素都用三元組來表示，若用順序存儲(chǔ)結(jié)構(gòu)，就構(gòu)成一個(gè)向量，該向量的每個(gè)分量是一個(gè)三元組。對(duì)于圖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稀疏矩陣的基本操作由于稀疏矩陣是一種特殊的矩陣，所以有關(guān)稀疏矩陣的基本運(yùn)算即為矩

31、陣的基本運(yùn)算。其主要操作有：（1）創(chuàng)建CreatSMatrix(&M) 該操作創(chuàng)建稀疏矩陣M；（2）復(fù)制CopySMatrix(M,&T) 該操作由稀疏矩陣M復(fù)制到T；（3）加法AddSMatrix(A,B,&C) 其功能是求稀疏矩陣A、B的和C；（4）減法SubMatrix(A,B,&C) 其功能是求稀疏矩陣A減B的差C；（5）轉(zhuǎn)置TransSMatrix(M,&T) 其功能是求稀疏矩陣M的轉(zhuǎn)置T；（6）乘法MulMatrix(A,B,&C) 其功能是求稀疏矩陣A、B的積C。1稀疏矩陣的順序存儲(chǔ)結(jié)構(gòu)在C+語言程序設(shè)計(jì)環(huán)境中，可定義稀疏矩陣的順序

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

33、陣的一一對(duì)應(yīng)。2稀疏矩陣的輸入操作操作void Create_TSM(TSMatrix &T)的功能是，根據(jù)行優(yōu)先的順序創(chuàng)建一個(gè)三元組順序表示的稀疏矩陣T。void Create_TSM(TSMatrix &T)int k;cout<<"請(qǐng)輸入行數(shù)和列數(shù):"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; /根據(jù)T中的函數(shù)、列數(shù)定義矩陣Afor(i=0;i<m;i+) /對(duì)A進(jìn)行零初始化for(

36、j=0;j<n;j+)Ai*n+j=0;for(p=1;p<=T.tu;p+) /通過T計(jì)算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稀疏矩陣的轉(zhuǎn)置操作對(duì)于用通常形式存儲(chǔ)的矩陣，其轉(zhuǎn)置操作過程是，只要將元素的行下標(biāo)和列下標(biāo)互換即可。對(duì)于用三元組順序存儲(chǔ)算法思想對(duì)A.data中每個(gè)三元組的列下標(biāo)進(jìn)行掃描，先找其值為j

37、=0的，若有，則將其行、列下標(biāo)對(duì)換后移至B.data中依此存放，比如A.data中的(1,0,-7)à(0,1,-7)；再重新掃描A.data中每個(gè)三元組的列下標(biāo)，查找其值為j=1的，若有，則將其行、列下標(biāo)對(duì)換后移至B.data中依此存放，比如A.data中的(3,1,8)à(1,3,8)；再重新掃描A.data中的列下標(biāo)，查找其值為j=2的，若有，則將其行、列下標(biāo)對(duì)換后移至B.data中依此存放，比如(0,2,-9)à(2,0,-9)，(1,2,7)à(2,1,7)，(4,2,9)à(2,4,9)，以此類推，直到所有三元組都處理完為止。算法實(shí)

38、現(xiàn)操作函數(shù)void Trans_TSM(TSMatrix S,TSMatrix &T)計(jì)算稀疏矩陣S的轉(zhuǎn)置矩陣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+;算法分析在轉(zhuǎn)置操作函數(shù)

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

40、5.7中三元組A.data中每個(gè)元素的列下標(biāo)進(jìn)行掃描，統(tǒng)計(jì)出每列元素的個(gè)數(shù)如表5.1中num所示。由num可算出轉(zhuǎn)置矩陣B的每行元素中第一個(gè)元素的初始位置序列cpot。在對(duì)A.data進(jìn)行第二次掃描時(shí)，cpot中相應(yīng)元素將進(jìn)行調(diào)整，其變化過程如表5.1所示。表5.1 快速轉(zhuǎn)置算法的實(shí)現(xiàn)過程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算法實(shí)現(xiàn)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; /求每列中非零元素的個(gè)數(shù)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+) /通過一次性掃描求出轉(zhuǎn)置矩陣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;算法分析在快速轉(zhuǎn)置操作函數(shù)FTrans_TSM()的算法中，比算法Trans_TSM()多使用了兩個(gè)輔助數(shù)組（num和cpot）的存儲(chǔ)空間，但是該算法的時(shí)間復(fù)雜度僅為O(nu+tu)，顯然比前者快了很多。6三元組矩陣的加法運(yùn)算假定矩陣M、N均為三元組表示的稀疏矩陣且具有相同的行數(shù)和列數(shù)，可對(duì)稀疏矩陣進(jìn)行求和

43、操作：A=M+N。算法思想(1) 行不相等時(shí)取行小者到A.data(2) 行相等但是列不相等時(shí)取列小者到A.data(3) 行、列都相等時(shí)求對(duì)應(yīng)元素的和，和值非零時(shí)移至A.data。算法實(shí)現(xiàn)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) /如果和不為零則保存結(jié)果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;算法分析本算法的時(shí)間復(fù)雜度為O(M.t

45、u+N.tu)，通過加法運(yùn)算的函數(shù)調(diào)用可以實(shí)現(xiàn)稀疏矩陣的減法運(yùn)算。7三元組矩陣的減運(yùn)算操作函數(shù)void Sub_TSM(TSMatrix M,TSMatrix N,TSMatrix& A)實(shí)現(xiàn)三元組矩陣的減法運(yùn)算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）函數(shù)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; /求每行非零元素的個(gè)數(shù)rpot0=1; /第0行的起始位置為1for(raw=1;raw<M.mu;raw+)rpotraw=rpotraw-1+numraw-1; /求第raw行的起始位置rpotrawdeletenum;（2）函數(shù)int Ffand(Etype &e,int i,int j,int rpot,TSMa

47、trix M)完成的操作是，求數(shù)組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）函數(shù)void Mult_TSM(TSMatrix A,TSMatrix B,TSMatrix& C)的功能是，實(shí)現(xiàn)三元組矩陣的乘

48、法運(yùn)算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三元組矩陣運(yùn)算的演示主程序程序中，首先以三元組順序結(jié)構(gòu)分別建立稀疏矩陣A和B，然后求出A的轉(zhuǎn)置矩陣C和快速轉(zhuǎn)置矩陣D，再分別求出：A與B的和E、A與B的差F、A與B的積G。并以矩陣形式顯示輸出每個(gè)矩陣的值。void main()TSMatrix A,B,C,D,E,F,G;while(1)cout<<"輸入兩個(gè)行、列相同的矩陣："cout<<"1-求轉(zhuǎn)置與快

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

51、<"A的快速轉(zhuǎn)置矩陣為: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);運(yùn)行結(jié)果為：輸入兩個(gè)行、列相同的矩陣：1-求轉(zhuǎn)置與快速轉(zhuǎn)置，2-矩陣的和與差，3-矩陣的積.輸入三元組矩陣A：請(qǐng)輸入行數(shù)和列數(shù):5 5輸入 i j e:0 2 -91 0 -71 2 73 1 84 2 90 0 0輸入三元組矩陣B：請(qǐng)輸入行數(shù)和列數(shù):5 5輸入 i j e:0 1 -71 3 82 0 -92 1 72 4 94 0 50 0 0A的轉(zhuǎn)置矩陣為:0 -7 0 0 00 0 0 8 0-9 7 0 0 90 0 0 0 00 0 0 0 0A的快速轉(zhuǎn)置矩陣為: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當(dāng)稀疏矩陣中非零元素的個(gè)數(shù)和位置在操作過程中變化比較大時(shí)，就不易采用順序存儲(chǔ)結(jié)構(gòu)來表示三元組。例如，在稀疏矩陣A中隨機(jī)增加或刪除一個(gè)非零元素，都會(huì)引起A.data中元素的移動(dòng)。為此，下面給出三元組的另一種存儲(chǔ)表示法，即十字鏈表示法。1十字鏈表的存儲(chǔ)結(jié)構(gòu)十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)如圖5.8所示，其中的i,j,e分別表示非零元素所在的行、列下標(biāo)以及元素的值（三元組），指針down指向同列的下一個(gè)非零元素，指針right指向同行右邊的非零元素。由