【正文】 的遞歸算法int GListDepth(GList GL)該操作的算法的思想是，先用遞歸算法算出廣義表GL中所有子表的深度的最大值max，再返回該廣義表GL的深度max+1。 //定義廣義表的表頭 (hp)、表尾 (tp)指針域ptr的類型為無名結(jié)構(gòu)體 }Data。typedef struct GLNode //定義結(jié)點(diǎn)的結(jié)構(gòu)類型GLNode{ ElemTag tag。在C++語言中用以下結(jié)構(gòu)類型來表示廣義表。（4）D=((),(e),(a,(b,c,d)))。對(duì)于子表結(jié)點(diǎn)，設(shè)置指向頭表的指針域hp和指向表尾的指針域tp；而對(duì)于原子結(jié)則設(shè)置數(shù)據(jù)域atom。e) 該操作的結(jié)果是，刪除廣義表L的第一個(gè)元素，并用e返回其值；（10）遍歷操作Traverse_GL(L) 該操作的功能是依次輸出L中的每個(gè)數(shù)據(jù)元素。L,S) 其操作結(jié)果為，由廣義表串S創(chuàng)建廣義表L；（3）復(fù)制CopyGList(amp。注意：廣義表（）和（（））是兩個(gè)不同的廣義表。如[]中的廣義表D。（5）E=(a,E)E=(a,(a,(a,…)))是一個(gè)廣義表，長(zhǎng)度為2，深度為無限大，表頭為a，表尾為(E)。（1）A=()A是一個(gè)空表，長(zhǎng)度為0，深度為1，不存在表頭和表尾。廣義表中括號(hào)的最大重?cái)?shù)稱為該廣義表的深度。 ciny。 while(y==1) { Create_OL(MM)。 39。(39。i。 }}5．十字鏈的遍歷操作函數(shù)void Print_OL(CrossList M)的作用是，以三元組形式輸出用十字鏈表表示的稀疏矩陣M的所有非零元素及其所在的行、列下標(biāo)。 Init_OL(M,m,n)。 M){ int m,n,i,j。 } return(1)。qdownii。[j]=p。q=qright)。} else { for(q=[i]。 p=new OLNode。int Insert_OL(CrossListamp。i++)[i]=NULL。im。=0。void Init_OL(CrossListamp。 int mu,nu,tu。 Etype e。1．十字鏈表的存儲(chǔ)結(jié)構(gòu)，其中的i,j,e分別表示非零元素所在的行、列下標(biāo)以及元素的值（三元組），指針down指向同列的下一個(gè)非零元素，指針right指向同行右邊的非零元素。 Print1_TSM(B)。 Print1_TSM(G)。 coutAB的差為:\n。 Add_TSM(A,B,E)。 coutA的轉(zhuǎn)置矩陣為:\n。 if((!=)||(!=)||(!=)) { cout維數(shù)不符合要求請(qǐng)重新輸入!\n。 cout輸入三元組矩陣A：\n。并以矩陣形式顯示輸出每個(gè)矩陣的值。 [k].j=j。Ffand(e2,k,j,Bnum,B)) s+=e1*e2。 for(k=0。i。 =。 int *Anum=new int[]。 C)的功能是，實(shí)現(xiàn)三元組矩陣的乘法運(yùn)算C=AB。 return 1。k=amp。e,int i,int j,int rpot[],TSMatrix M)完成的操作是，求數(shù)組M中的元素a(i,j)到e，操作成功返回1，否則返回0。raw。t=。 for(raw=0。 Add_TSM(M,N,A)。 A){ int p。}算法分析本算法的時(shí)間復(fù)雜度為O(+)，通過加法運(yùn)算的函數(shù)調(diào)用可以實(shí)現(xiàn)稀疏矩陣的減法運(yùn)算。 else [r++]=[q++]。 [r++].e=e。amp。算法實(shí)現(xiàn)void Add_TSM(TSMatrix M,TSMatrix N,TSMatrixamp。 delete[]cpot。 [q].i=[p].j。 //求第col行的起始位置cpot[col] for(p=1。 //求每列中非零元素的個(gè)數(shù) cpot[0]=1。col++)num[col]=0。 //為向量cpot分配空間 int col,p,q,t。 快速轉(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 amp。5．三元組矩陣的快速轉(zhuǎn)置算法思想快速轉(zhuǎn)置的算法思想是，在求M的轉(zhuǎn)置矩陣T時(shí)，再通過num求出T中每一行非零元素的起始下標(biāo)向量cpot。 n++。p=。 n=1。 =。算法實(shí)現(xiàn)操作函數(shù)void Trans_TSM(TSMatrix S,TSMatrix amp。(1,3,8)；，查找其值為j=2的，若有，則將其行、比如(0,2,9)224。例如。}4．稀疏矩陣的轉(zhuǎn)置操作對(duì)于用通常形式存儲(chǔ)的矩陣，其轉(zhuǎn)置操作過程是，只要將元素的行下標(biāo)和列下標(biāo)互換即可。j++) coutA[i*n+j]39。 } for(i=0。p=。i++) //對(duì)A進(jìn)行零初始化 for(j=0。void Print1_TSM(TSMatrix T){ int i,j,p,m=,n=。i++) { cout([i].i,。void Print_TSM(TSMatrix T){ int i。amp。cin[k].i[k].j[k].e。cin。T)的功能是，根據(jù)行優(yōu)先的順序創(chuàng)建一個(gè)三元組順序表示的稀疏矩陣T。說明：在用三元組的順序存儲(chǔ)來表示一個(gè)稀疏矩陣時(shí)，還必須同時(shí)確定該矩陣的行數(shù)(mu)和列數(shù)(nu)，只有這樣才能保證矩陣的三元組表示與原矩陣的一一對(duì)應(yīng)。}。C) 其功能是求稀疏矩陣A、B的積C。T) 該操作由稀疏矩陣M復(fù)制到T；（3）加法AddSMatrix(A,B,amp。將一個(gè)稀疏矩陣的所有非零元素都用三元組來表示，若用順序存儲(chǔ)結(jié)構(gòu)，就構(gòu)成一個(gè)向量，該向量的每個(gè)分量是一個(gè)三元組。對(duì)于稀疏矩陣，若按通常辦法將零元素與非零元素一起存儲(chǔ)起來，顯然浪費(fèi)了大量的存儲(chǔ)空間，本節(jié)討論有關(guān)稀疏矩陣的三元組壓縮存儲(chǔ)問題以及三元組存儲(chǔ)矩陣的基本運(yùn)算方法。1．稀疏矩陣的概念當(dāng)用矩陣表示某個(gè)數(shù)學(xué)模型時(shí)，經(jīng)常出現(xiàn)這樣一些特殊矩陣，它的階數(shù)很高且非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣中零元素的個(gè)數(shù)，我們稱這樣的矩陣為稀疏矩陣(sparse matrix)。例如，5就是一個(gè)半帶寬為b=2，帶寬為m=5的帶狀陣。數(shù)組A中的元素a[i][j]與數(shù)組B中的元素b[k]的對(duì)應(yīng)關(guān)系是：(a)(b)所示?？梢詫2個(gè)元素壓縮存儲(chǔ)到只有n(n+1)/2個(gè)元素空間的一維數(shù)組M中。即，對(duì)多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配存儲(chǔ)空間。在數(shù)據(jù)結(jié)構(gòu)中，主要關(guān)心的不是矩陣本身，而是如何存儲(chǔ)矩陣元素，使矩陣的各種運(yùn)算能有效地進(jìn)行。1 2 3 4 5↙A1結(jié)果為:1 2 3 4 5以行為主序的順序輸入A[4*5]中的20個(gè)元素的值。 //定義A4為四維數(shù)組大小為2*3*2*5 ArrayInput(A4)。 //定義A3為三維數(shù)組大小為3*4*5 ArrayInput(A3)。 Trans(A22,A2)。 InitArray(A2,2,b2)。 InitArray(A1,1,b1)。 } return 1。s[0]++) for(s[1]=0。 int bounds[]={[1],[0]}。如果B的維數(shù)不等于2返回0表示操作失敗，否則返回1表示操作成功。i++)cout[i] 。i。 coutendl。s[1][1]。 case 3: //按三維數(shù)組格式輸出 for(s[0]=0。s[1][1]。 break。 switch() { case 1: //按一維數(shù)組格式輸出 for(s[0]=0。ilength。)[i]。i++) coutchar((i)?39。i++)length*=[i]。void ArrayInput(Arrayamp。 //計(jì)算對(duì)應(yīng)元素的偏移量off } [off]=e。 for(i=0。 A,int* script,EType e)的作用是，根據(jù)下標(biāo)向量script修改數(shù)組A中相應(yīng)元素的值為e。i。 return 1。i。如果下標(biāo)合理返回1表示提取成功，否則返回0表示操作失敗。i) //計(jì)算數(shù)組元素的映像常數(shù)向量[i]=[i+1]*[i+1]。 =new EType[length]。idim。 if(dim1)return 0。A,int dim,int* bounds)的功能是，、。 //數(shù)組的維數(shù) int *bounds。解：按右下標(biāo)為主序的地址計(jì)算公式為：LOC(A[i][j][k])= LOC(A[0][0][0])+(kb0b1+jb0+i)L?！尽慷S數(shù)組M56的元素是4個(gè)字符（每個(gè)字符占1個(gè)存儲(chǔ)單元）組成的串，那么M按行優(yōu)先（以左下標(biāo)為主序）存儲(chǔ)時(shí)元素M[3][5]的起始地址與M按列優(yōu)先（以右下標(biāo)為主序）存儲(chǔ)時(shí)的哪個(gè)元素的起始地址相同？解：按行優(yōu)先存儲(chǔ)時(shí)元素M[3][5]的起始地址為：LOC(M[3][5]) =LOC(M[0][0])+(i6+j)4=LOC(M[0][0])+(36+5)4=LOC(M[0][0])+234按列優(yōu)先存儲(chǔ)時(shí)元素M[i][j]的起始地址為：LOC(M[i][j])=LOC(M[0][0])+(j5+i)4=LOC(M[0][0])+234=LOC(M[0][0])+(45+3)4所以，要求的元素M[i][j]即為M[3][4]。2．左下標(biāo)為主序存儲(chǔ)的n維數(shù)組中的元素a(j0,j1,...,jn1)的地址計(jì)算公式對(duì)于一個(gè)已經(jīng)被定義的二維數(shù)組Ab0b1=(a[i][j])b0b1，只要給出該數(shù)組存放的起始地址LOC(a[0][0])、數(shù)組元素的行下標(biāo)i和列下標(biāo)j，以及每個(gè)元素所占用的存儲(chǔ)單元（字節(jié)）數(shù)L，便可以求得元素a[i][j]在內(nèi)存中的首地址LOC(a[i][j])。對(duì)于三維數(shù)組：（有2頁、2行、3列），（b）所示。因此，采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組是最合理的方式。（3）修改操作Assign(Arrayamp。所以數(shù)組的基本操作主要有：（1）初始化InitArray(Array amp。n(n1)維數(shù)組是一個(gè)向量，它的每個(gè)元素都是n1維數(shù)組，且具有相同的上限和下限。廣義表是一種較為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，它是線性結(jié)構(gòu)和樹型結(jié)構(gòu)的拓廣。第5章 數(shù)組和廣義表第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)部類型。稀疏矩陣是一種特殊的二維數(shù)組，因其在壓縮存儲(chǔ)方面的特點(diǎn)而被廣泛使用。一維數(shù)組是一個(gè)向量，它的每一個(gè)元素都是該結(jié)構(gòu)中不可分割的最小單位。數(shù)組一旦被定義，它的元素類型（即數(shù)組類型）、維數(shù)、各維的界（長(zhǎng)度）就不再改變。e)：該操作根據(jù)下script標(biāo)讀取數(shù)組A中的元素到e中。由于數(shù)組不作插入和刪除操作，也就是說，一旦建立了數(shù)組，則該數(shù)組結(jié)構(gòu)中的數(shù)據(jù)元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變動(dòng)。以二維數(shù)組為例，（a）所示。對(duì)于三維數(shù)組：（有2頁、2行、3列），（b）所示。如果記：,即可得到映像常數(shù)向量：，相應(yīng)的n維數(shù)組元素的地址計(jì)算公式可簡(jiǎn)寫為：完全類似地，讀者可以自行給出以右下標(biāo)為主序的n維數(shù)組元素a(j0,j1,...,jn1)的地址計(jì)算公式。所以：LOC(A[1][2][3])=1000+(156+26+3)4=1180LOC(A[3][2][0])=1000+(356+26+0)4=1408LOC(A[1][3][5])=1000+(156+36+5)4=1212【】已知A456為按右下標(biāo)為主序存儲(chǔ)的3維數(shù)組，每個(gè)元素占2個(gè)存儲(chǔ)單元，并且元素A[0][0][0]的首地址為100，分別計(jì)算元素A[1][2][3]、A[3][2][0]和A[1][3][5]的首地址。 //數(shù)組的基地址 int dim。2．?dāng)?shù)組的初始化操作操作int InitArray(Array amp。A,int dim,int* bounds){ int length=1,i。 //分配映像向量的存儲(chǔ)空間 for(i=0。 } =dim。i=0。e)的功能是，根據(jù)下標(biāo)向量script提取數(shù)組A中相應(yīng)元素的值到e中。 for(i=0。 //計(jì)算對(duì)應(yīng)元素的偏移