數(shù)據(jù)結(jié)構(gòu)課件：第五章矩陣與廣義表

第5章數(shù)組和廣義表5.1數(shù)組的定義和運算5.2數(shù)組的順序存儲和實現(xiàn)5.3特殊矩陣的壓縮存儲

5.3.1三角矩陣

5.3.2帶狀矩陣

5.3.3稀疏矩陣5.4廣義表5.5總結(jié)與提高5.1數(shù)組的定義和運算數(shù)組是一種數(shù)據(jù)類型。從邏輯結(jié)構(gòu)上看，數(shù)組可以看成是一般線性表的擴充。二維數(shù)組可以看成是線性表的線性表。例如：Am×n=a12a12┅a1j

┅a1na21a22┅a2j

┅a2n┇┇ai1ai2┅aij

┅ain┇┇am1am2┅amj

┅amnAm×n=a12a12┅a1j

┅a1na21a22┅a2j

┅a2n┇┇ai1ai2┅aij

┅ain┇┇am1am2┅amj

┅amnA=（12┅

j

┅n)我們可以把二維數(shù)組看成一個線性表：A=(12…

j…n)，其中j（1≤j≤n）本身也是一個線性表，稱為列向量。矩陣Am×n看成n個列向量的線性表,即j=(a1j,a2j,…,amj)Am×n=a12a12…a1j

…a1na21a22…a2j

…a2n┇┇ai1ai2…aij

…ain┇┇am1am2…amj

…amnB‖12┇i┇m我們還可以將數(shù)組Am×n看成另外一個線性表:B=(1，,2,，…，m)，其中i（1≤i≤m）本身也是一個線性表，稱為行向量，即：I=（ai1，ai2，…，aij，…，ain）。上面二維數(shù)組的例子，介紹了數(shù)組的結(jié)構(gòu)特性，實際上數(shù)組是一組有固定個數(shù)的元素的集合。由于這個性質(zhì)，使得對數(shù)組的操作不象對線性表的操作那樣，可以在表中任意一個合法的位置插入或刪除一個元素。對于數(shù)組的操作一般只有兩類：（1）獲得特定位置的元素值；（2）修改特定位置的元素值。數(shù)組的抽象數(shù)據(jù)類型定義（ADTArray）數(shù)據(jù)對象：D={aj1j2…jn|n>0，稱為數(shù)組的維數(shù)，ji是數(shù)組的第i維下標(biāo)，1≤ji≤bi，bi為數(shù)組第i維的長度，aj1j2…jn∈ElementSet}數(shù)據(jù)關(guān)系：R={R1,R2,…,Rn}Ri={<aj1…ji…jn

，aj1…ji+1…jn>|1≤jk≤bk，1≤k≤n且k≠i，1≤ji≤bi-1，aj1…ji…jn

，aj1…ji+1…jn∈D，i=1，…，n}基本操作：（1）InitArray(A,n,bound1,…,boundn)：若維數(shù)n和各維的長度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回TRUE；（2）DestroyArray（A）：銷毀數(shù)組A；（3）GetValue（A，e,index1,…,indexn）：若下標(biāo)合法，用e返回數(shù)組A中由index1,…,indexn所指定的元素的值。（4）SetValue（A，e，index1,…,indexn）：若下標(biāo)合法，則將數(shù)組A中由index1,…,indexn所指定的元素的值置為e。注意：這里定義的數(shù)組下標(biāo)是從1開始，與C語言的數(shù)組略有不同。5.2數(shù)組的順序存儲和實現(xiàn)

對于數(shù)組A，一旦給定其維數(shù)n及各維長度bi（1≤i≤n），則該數(shù)組中元素的個數(shù)是固定的，不可以對數(shù)組做插入和刪除操作，不涉及移動元素操作，因此對于數(shù)組而言，采用順序存儲法比較合適。

數(shù)組的順序存儲結(jié)構(gòu)有兩種：一種是按行序存儲，如：高級語言BASIC、COBOL和PASCAL語言都是以行序為主。另一種是按列序存儲，如：高級語言中的FORTRAN語言就是以列序為主。對于二維數(shù)組Amxn以行為主的存儲序列為：a11,a12,…a1n,a21,a22,…,a2n,……,am1,am2,

…,

amn以列為主存儲序列為：a11,a21,…am1,a12,a22,…,am2,……,a1n,a2n,…,amn

假設(shè)有一個3×4×2的三維數(shù)組A

，其邏輯結(jié)構(gòu)圖為：列行縱

以二維數(shù)組Amn為例，假設(shè)每個元素只占一個存儲單元，“以行為主”存放數(shù)組，下標(biāo)從1開始，首元素a11的地址為Loc[1,1]求任意元素aij的地址，可由如下計算公式得到：Loc[i,j]=Loc[1,1]+n×(i-1)+(j-1)其中n為第2維的長度

如果每個元素占size個存儲單元，則任意元素aij的地址計算公式為：Loc[i,j]=Loc[1,1]+(n×(i-1)+j-1)×size

若首元素的地址為Loc[0,0]，每個元素占size個存儲單元，則二維數(shù)組中元素aij的存儲位置可由如下計算公式得到：Loc[i,j]=Loc[0,0]+（n×i+j）*size其中n為第2維的長度三維數(shù)組A（1..r,1..m,1..n）可以看成是r個m×n的二維數(shù)組，如下圖所示：

假定每個元素占一個存儲單元，采用以行為主序的方法存放，首元素a111的地址為Loc[1,1,1]，ai11的地址為Loc[i,1,1]=Loc[1,1,1]+(i-1)*m*n，那么求任意元素aijk的地址計算公式為：Loc[i,j,k]=Loc[1,1,1]+(i-1)*m*n+(j-1)*n+(k-1)其中1≤i≤ｒ，1≤j≤ｍ，1≤k≤ｎ。

如果將三維數(shù)組推廣到一般情況，即：用j1，j2，j3代替數(shù)組下標(biāo)i，j，k；并且j1，j2，j3的下限為c1，c2，c3，上限分別為d1，d2，d3，每個元素占一個存儲單元。則三維數(shù)組中任意元素a(j1，j2，j3)的地址為：Loc[j1，j2，j3]=Loc[c1,c2,c3]+1*(d2-c2+1)*(d3-c3+1)*(j1-c1)

+1*(d3-c3+1)*(j2-c2)+1*(j3-c3)其中l(wèi)為每個元素所占存儲單元數(shù)。例令α1=1*(d2-c2+1)*(d3-c3+1),α2=1*(d3-c3+1),α3=1，則：Loc[j1,j2,j3]=Loc[c1,c2,c3]+α1*(j1-c1)+α2*(j2-c2)+α3(j3-c3)=Loc[c1,c2,c3]+Σαi*(ji-ci)（1≤i≤3）由公式可知Loc[j1,j2,j3]與j1,j2,j3呈線性關(guān)系。

對于ｎ維數(shù)組A(c1:d1,c2:d2，…,cn,dn)，我們只要把上式推廣，就可以容易地得到ｎ維數(shù)組中任意元素aj1j2…jn的存儲地址的計算公式。

Loc[j1，j2，…jn]=Loc[c1，c2，…，cn]+αi(ji-ci)i=1n其中αi=l(dk-ck+1)（1≤i≤n）k=i+1n5.3特殊矩陣的壓縮存儲

特殊矩陣壓縮存儲的壓縮原則是：對有規(guī)律的元素和值相同的元素只分配一個存儲單元，對于零元素不分配空間。5.3.1三角矩陣三角矩陣大體分為：下三角矩陣、上三角矩陣和對稱矩陣。對于一個n階矩陣A來說：若當(dāng)i<j時，有aij=常量或零，則稱此矩陣為下三角矩陣若當(dāng)i>j時，有aij=常量或零，則此矩陣稱為上三角矩陣若矩陣中的所有元素均滿足aij=aji，則稱此矩陣為對稱矩陣

對于下三角矩陣，按“行序為主序”進行存儲，得到的序列為：a11,a21,a22,a31,a32,a33…an1,an2…ann。由于下三角矩陣的元素個數(shù)為n(n+1)/2，所以可壓縮存儲到一個大小為n(n+1)/2的一維數(shù)組中。下三角矩陣中元素aij(i>j)，在一維數(shù)組A中的位置為：

LOC[i,j]=LOC[1,1]+i(i-1)/2+j-1

下三角矩陣：A=a11a21a22a31a32a33┆┆┆┆an1an2an3

…ann

同樣，對于上三角矩陣，也可以將其壓縮存儲到一個大小為n(n+1)/2的一維數(shù)組C中。其中元素aij(i<j)在數(shù)組C中的存儲位置為：

Loc[i,j]=Loc[1,1]+j(j-1)/2+i-1上三角矩陣：A=a11a12a13…………a1na22a23……...an2

a33…………..an3┆┆┆ann

對于對稱矩陣，因其元素滿足aij=aji，我們可以為每一對相等的元素分配一個存儲空間，即只存下三角（或上三角）矩陣，從而將n2個元素壓縮到n(n+1)/2個空間中。假設(shè)一維數(shù)組sa[n(n+1)/2]作為n階對稱矩陣A的存儲結(jié)構(gòu)，則sa[k]和矩陣元aij之間對應(yīng)的關(guān)系是：i(i-1)/2+j-1當(dāng)i>=jj(j-1)/2+i-1當(dāng)i<jk=5.3.2帶狀矩陣帶狀矩陣：在矩陣A中，所有的非零元素都集中在以主對角線為中心的帶狀區(qū)域中。最常見的是三對角帶狀矩陣。An×n=a11a12a21a22a23a32a33a34a43a44a45

……………特點:i=1,j=1,2;當(dāng)

1<i<n，j=i-1,i,i+1i=n,j=n-1,n;時，aij非零，其他元素均為零。

三對角帶狀矩陣的壓縮存儲，以行序為主序進行存儲，并且只存儲非零元素。其方法為：1.確定存儲該矩陣所需的一維向量空間的大小

從三對角帶狀矩陣中可看出：除第一行和最后一行只有兩個元素外，其余各行均有3個非零元素。由此可得到一維向量所需的空間大小為：3n-2。2.確定非零元素在一維數(shù)組空間中的位置假設(shè)每個非零元素所占的空間的大小為1個單元LOC[i,j]=LOC[1,1]+2(i-1)+j-15.3.3稀疏矩陣稀疏矩陣：指矩陣中大多數(shù)元素為零的矩陣。一般地，當(dāng)非零元素個數(shù)只占矩陣元素總數(shù)的25%—30%,或低于這個百分數(shù)時，我們稱這樣的矩陣為稀疏矩陣。003001512000180900240000000-70000000014000000000M6×7=012900000000000-3000014000240000018000001500-7000N6×7=隨機稀疏矩陣的壓縮存儲方法:一、三元組順序表二、行邏輯聯(lián)接的順序表三、十字鏈表1.稀疏矩陣的三元組表表示法

對于稀疏矩陣的壓縮存儲要求在存儲非零元素的同時，還必須存儲該非零元素在矩陣中所處的行號和列號。我們將這種存儲方法叫做稀疏矩陣的三元組表示法。

rowcolvalue該非零元素所在的行號該非零元素所在的列號該非零元素的值每個非零元素在一維數(shù)組中的表示形式如圖所示：

三元組表的類型說明：#defineMAXSIZE1000/*非零元素的個數(shù)最多為1000*/ typedefstruct {introw,col;/*該非零元素的行下標(biāo)和列下標(biāo)*/ElementTypee；/*該非零元素的值*/ }Triple; typedefstruct{Tripledata[MAXSIZE+1];

/*非零元素的三元組表。data[0]未用*/ intm,n,len;/*矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)*/}TSMatrix；A的三元組順序表圖示A=012900000000000-3000014000240000018000001500-7000rowcole0123456782

0-35

0150

1124

1180

293

2245

3-72

514A.data678A.mA.nA.len1）用三元組表實現(xiàn)稀疏矩陣的轉(zhuǎn)置運算矩陣轉(zhuǎn)置：指變換元素的位置，把位于（row，col）位置上的元素換到（col，row）位置上，也就是說，把元素的行列互換。

采用矩陣的正常存儲方式時，實現(xiàn)矩陣轉(zhuǎn)置的經(jīng)典算法如下：

voidTransMatrix（ElementTypesource[n][m],ElementTypedest[m][n]）{/*Source和dest分別為被轉(zhuǎn)置的矩陣和轉(zhuǎn)置后的矩陣（用二維數(shù)組表示）*/inti,j;for(i=0;i<m;i++)for(j=0;j<n;j++)dest[i][j]=source[j][i];}A

=012900000000000-3000014000240000018000001500-7000B

=00-3001512000180900240000000-70000000014000000000轉(zhuǎn)置實現(xiàn)轉(zhuǎn)置的簡單方法：①矩陣source的三元組表A的行、列互換就可以得到B中的元素，如圖：②為了保證轉(zhuǎn)置后的矩陣的三元組表B也是以“行序為主序”進行存放，則需要對行、列互換后的三元組B，按B的行下標(biāo)（即A的列下標(biāo)）大小重新排序。B（i，j，x）————（j，i，x）A兩種處理轉(zhuǎn)置算法如下：方法一轉(zhuǎn)置運算算法基本思想：

對A.data從頭至尾掃描：第一次掃描時，將A.data中列號為0的三元組賦值到B.data中，第二次掃描時，將A.data中列號為1的三元組賦值到B.data中，依此類推，直至將A.data所有三元組賦值到B.data中rowcole0123456782

0-35

01502124

1180

293

2245

3-72

514A.data678A.mA.nA.lenrowcole0123456781

0

123

5

-70

2

-32

3

240

5

152

0

95

2

141

4

18B.data768B.mB.nB.len矩陣A的三元組順序表A的轉(zhuǎn)置矩陣B的三元組順序表rowcole0

1120

292

0-32

5143

2244

1185

0155

3-7rowcole2

0-31

4180

2-35

0150

5150

1121

0124

1180

292

093

2242

3245

3-73

5-72

5145

214A.dataB.data對M六次掃描完成轉(zhuǎn)置運算第一次掃描查找第1列元素第一次掃描結(jié)束第二次掃描結(jié)束第二次掃描查找第2列元素第三次掃描查找第3列元素第四次掃描查找第4列元素第五次掃描查找第5列元素第六次掃描查找第6列元素轉(zhuǎn)置運算算法圖示voidTransposeTSMatrix(TSMatrixA,TSMatrix*B){/*把矩陣A轉(zhuǎn)置到B所指向的矩陣中去。矩陣用三元組表表示*/inti,j,k;B->m=A.n;B->n=A.m;B->len=A.len;if(B->len>0) {j=0; for(k=0;k<A.n;k++) for(i=0;i<A.len;i++) if(A.data[i].col==k) {B->data[j].row=A.data[i].col B->data[j].col=A.data[i].row;B->data[j].e=A.data[i].e;j++; } }}時間復(fù)雜度分析算法的基本操作為將M.data中的三元組賦值到N.data，是在兩個循環(huán)中完成的，故算法的時間復(fù)雜度為O(nlen)

我們知道，若用二維數(shù)組存儲矩陣，轉(zhuǎn)置算法1的時間復(fù)雜度為O（mn）。當(dāng)非零元的個數(shù)len和矩陣元素個數(shù)mn

同數(shù)量級時，轉(zhuǎn)置運算算法1的時間復(fù)雜度為O（mn

n）。由此可見：在這種情況下，用三元組順序表存儲矩陣，雖然可能節(jié)省了存儲空間，但時間復(fù)雜度提高了，因此算法僅適于len<<mn的情況。

該算法效率不高的原因是：對為實現(xiàn)M到N的轉(zhuǎn)置，該算法對M.data進行了多次掃描。能否在對M.data一次掃描的過程中，完成M到N的轉(zhuǎn)置？方法二：快速轉(zhuǎn)置算法

下面介紹轉(zhuǎn)置運算算法稱為快速轉(zhuǎn)置算法算法分析：在A.data中，A的各列非零元對應(yīng)的三元組是以行為主序存儲的，故M的各列非零元對應(yīng)的三元組存儲位置不是“連續(xù)”的。然而，A的各列非零元三元組的存儲順序卻與各列非零元在A中的順序一致。如：A的第一列非零元素是-3、15，它們對應(yīng)的三元組在A.data中的存儲順序也是（3，1，-3）在前（6，1，15）后。如果能先求得A各列第一個非零元三元組在B.data中的位置，就能在對A.data一次掃描的過程中，完成A到B的轉(zhuǎn)置：對A.data一次掃描時，首先遇到各列的第一個非零元三元組，可按先前求出的位置，將其放至B.data中，當(dāng)再次遇到各列的非零元三元組時，只須順序放到對應(yīng)列元素的后面。A

=012900000000000-3000014000240000018000001500-7000rowcole0123456782

0-35

0150

1124

1180

293

2245

3-72

514A.data678A.mA.nA.lenA的各列非零元三元組的存儲順序與各列非零元在A中的順序一致rowcole0123456782

0-35

0150

1124

1180

293

2245

3-72

514A.data678A.mA.nA.lenrowcole0123456781

0

123

5

-70

2

-32

3

240

5

152

0

95

2

141

4

18B.data768B.mB.nB.len各列第一個非零元三元組按先前求出的位置，放至T.data中各列后續(xù)的非零元三元組，順序放到對應(yīng)列元素的后面輔助向量num[]、cpot[]

為先求得M各列第一個非零元三元組在N.data中的位置。引入兩個輔助向量num[]、

position[]：

num[col]：存儲第col列非零元個數(shù)

position[col]：存儲第col列第一個非零元三元組在N.data中的位置

position[col]的計算方法：

position[0]=0

position[col]=position[col-1]+num[col-1]1<=col<a.n

例矩陣Acolnum[col]position[col]012345622711000352674428快速轉(zhuǎn)置算法主要步驟：1、求A中各列非零元個數(shù)num[];2、求A中各列第一個非零元在B.data中的下標(biāo)position[];3、對A.data進行一次掃描，遇到col列的第一個非零元三元組時，按position[col]的位置，將其放至B.data中，當(dāng)再次遇到col列的非零元三元組時，只須順序放到col列元素的后面;算法二:FastTransposeTSMatrix(TSMatrixA,TSMatrix*B){/*基于矩陣的三元組表示，采用快速轉(zhuǎn)置法，將矩陣A轉(zhuǎn)置為B所指的矩陣*/intcol,t,p，q;intnum[MAXSIZE],position[MAXSIZE];B->len=A.len;B->n=A.m;B->m=A.n;if(B->len){for(col=0;col<=A.n;col++)num[col]=0;for(t=0;t<=A.len;t++)num[A.data[t].col]++;/*計算每一列的非零元素的個數(shù)*/position[0]=0;for(col=1;col<A.n;col++)/*求col列中第一個非零元素在B.data[]中的正確位置*/position[col]=position[col-1]+num[col-1];for(p=0;p<A.len.p++){col=A.data[p].col;q=position[col];B->data[q].row=A.data[p].col;B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].eposition[col]++;}}}colnum[col]POSITION[col]0123456228110013526780

1120

292

0-32

5143

2244

1185

0155

3-7rowcolerowcoleM.dataT.data1012第2列第一個非零元在b中的位置第3列第一個非零元在b中的位置20902-3521423241418051535-74第2列第二個非零元在b中的位置62快速轉(zhuǎn)置算法圖示第3列第二個非零元在b中的位置第1列第一個非零元在b中的位置2470第4列第一個非零元在b中的位置求各列第1個非零元在b中位置求各列非零元個數(shù)掃描M.data實現(xiàn)M到T的轉(zhuǎn)置時間復(fù)雜度分析

該算法利用兩個輔助向量num[]、cpot[]，實現(xiàn)了對M.data一次掃描完成M到T的轉(zhuǎn)置。從時間上看，算法中有四個并列的單循環(huán)，循環(huán)次數(shù)分別為n、len、n和len，因而總的時間復(fù)雜度為O（n+len)，在A的非零元個數(shù)len和mn

同等數(shù)量級時，其時間復(fù)雜度為O(mn)

，和轉(zhuǎn)置算法1的時間復(fù)雜度相同。由此可見，只有當(dāng)len<<mn時，使用快速轉(zhuǎn)置算法才有意義。for(col=1;col<=A.n;++col)……for(t=1;t<=A.len;++t)……for(col=2;col<=A.n;++col)……for(p=1;p<=A.len;++p)……用三元組表實現(xiàn)稀疏矩陣的乘法運算

設(shè)矩陣M是m1×n1矩陣，N是m2×n2矩陣；若可以相乘，則必須滿足矩陣M的列數(shù)n1與矩陣N的行數(shù)m2相等，才能得到結(jié)果矩陣Q=M×N（一個m1×n2的矩陣）。數(shù)學(xué)中矩陣Q中的元素的計算方法如下：

Q[i][j]=M[i][k]×N[k][j]n1k=1其中：1≤i≤m1，1≤j≤n2

根據(jù)數(shù)學(xué)上矩陣相乘的原理，我們可以得到矩陣相乘的經(jīng)典算法：for(i=1;i<=m1;i++)for(j=1;j<=n2;j++){Q[i][j]=0;for(k=1;k<=n1;k++) Q[i][j]=Q[i][j]+M[i][k]*N[k][j];}

經(jīng)典算法中，不論M[i][k]，N[k][j]是否為零，都要進行一次乘法運算，實際是沒有必要的。采用三元組表的方法來實現(xiàn)時，因為三元組只對矩陣的非零元素做存儲，所以可以采用固定三元組a中元素（i，k，Mik）（1≤i≤m1，1≤k≤n1），在三元組b中找所有行號為k的的對應(yīng)元素（k，j，Nkj）（1≤k≤m2，1≤j≤n2）進行相乘、累加從而得到Q[i][j]。即：以三元組a中的元素為基準(zhǔn)，依次求出其與三元組b的有效乘積。相乘基本操作：對于三元組a中每個元素a.data[p]（p=1，2，3，…a.len），找出三元組b中所有滿足條件：a.data[p].col=b.data[q].row的元素b.data[q]，求得a.data[p].e與b.data[q].e的乘積，而這個乘積只是Q[i，j]的一部分，應(yīng)對每個元素設(shè)一個累計和變量，其初值為0。掃描完三元組a，求得相應(yīng)元素的乘積并累加到適當(dāng)?shù)睦塾嫼偷淖兞可稀Ｗ⒁猓簝蓚€稀疏矩陣相乘的結(jié)果不一定是稀疏矩陣。反之，相乘的每個分量M[i，k]×N[k，j]不為零，但累加的結(jié)果Q[i，j]可能是零。例如：100100100×111000000=111111111#defineMAXSIZE1000/*非零元素的個數(shù)最多為1000*/#defineMAXROW1000/*矩陣最大行數(shù)為1000*/ typedefstruct {introw,col;/*該非零元素的行下標(biāo)和列下標(biāo)*/ElementTypee；/*該非零元素的值*/ }Triple; typedefstruct{Tripledata[MAXSIZE+1];/*非零元素的三元組表，data[0]未用*/

intfirst[MAXROW+1];/*三元組表中各行第一個非零元素所在的位置。*/intm,n,len;/*矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)*/}TriSparMatrix；為方便實現(xiàn)，將三元組表的類型說明修改如下：具體算法如下：intMulSMatrix(TriSparMatrixM,TriSparMatrixN,TriSparMatrix*Q){/*采用改進的三元組表表示法，求矩陣乘積Q＝M×N*/intarow,brow,p;intctemp[MAXSIZE];if(M.n!=N.m)returnFALSE;/*返回FALSE表示求矩陣乘積失敗*/Q->m=M.m;Q->n=N.n;Q->len=0;if(M.len*N.len!=0){for(arow=1;arow<=M.m;arow++)/*逐行處理M*/ {for(p=1;p<=M.n;p++) ctemp[p]=0;/*當(dāng)前行各元素的累加器清零*/Q->first[arow]=Q->len+1;for(p=M.first[arow];p<M.first[arow+1];p++)/*p指向M當(dāng)前行中每一個非零元素*/{brow=M.data[p].col;/*M中的列號應(yīng)與N中的行號相等*/if(brow<N.n)t=N.first[brow+1];elset=N.len+1;for(q=N.first[brow];q<t;q++){ccol=N.data[q].col;/*乘積元素在Q中列號*/ctemp[ccol]+=M.data[p].e*N.data[q].e;}/*forq*/}/*求得Q中第crow行的非零元*/for(ccol=1;ccol<Q->n；col++)/*壓縮存儲該非零元*/ if(ctemp[ccol]) {if(++Q->len>MAXSIZE)return0;Q->data[Q->len]={arow,ccol,ctemp[ccol]}; }/*if*/}/*forarow*/}/*if*/return(TRUE);/*返回TRUE表示求矩陣乘積成功*/}2.稀疏矩陣的鏈?zhǔn)酱鎯Y(jié)構(gòu)：十字鏈表優(yōu)點：它能夠靈活地插入因運算而產(chǎn)生的新的非零元素，刪除因運算而產(chǎn)生的新的零元素，實現(xiàn)矩陣的各種運算。在十字鏈表中，矩陣的每一個非零元素用一個結(jié)點表示，該結(jié)點除了（row，col，value）以外，還要有兩個域：right：用于鏈接同一行中的下一個非零元素；down：用以鏈接同一列中的下一個非零元素。rowcolvaluedownright十字鏈表中結(jié)點的結(jié)構(gòu)示意圖：30050-100200011314522-1312^^^^^^^十字鏈表的結(jié)構(gòu)類型說明如下：typedefstructOLNode{introw,col;/*非零元素的行和列下標(biāo)*/ElementTypevalue;structOLNode*right,*down;/*非零元素所在行表列表的后繼鏈域*/}OLNode;*OLink;typedefstruct{OLink*row_head,*col_head;/*行、列鏈表的頭指針向量*/intm,n,len;/*稀疏矩陣的行數(shù)、列數(shù)、非零元素的個數(shù)*/}CrossList;建立稀疏矩陣的十字鏈表算法：CreateCrossList(CrossList*M){/*采用十字鏈表存儲結(jié)構(gòu)，創(chuàng)建稀疏矩陣M*/if(M!=NULL)free(M);scanf(“%d%d%d”&m,&n,&t);/*輸入M行數(shù)、列數(shù)和非零元的個數(shù)*/M->m=m;M->n=n;M->len=t;if(!(M->row_head=(Olink*)malloc((m+1)sizeof(OLink))))exit(OVERFLOW);if(!(M->col_head=(OLink*)malloc((n+1)sizeof(OLink))))exit(OVERFLOW);M->row_head[]=M->col_head[]=NULL;/*初始化行、列頭指針向量，各行、列鏈表為空的鏈表*/scanf(“%d%d%d”&i,&j,&e);while(i!=0){if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p->row=i;p->col=j;p->value=e;/*生成結(jié)點*/if(M->row_head[i]==NULL)M->row_head[i]=p;else{/*尋找行表中的插入位置*/for(q=M->row_head[i];q->right&&q->right->col<j;q=q->right)p->right=q->right;q->right=p;/*完成插入*/}if(M->col_head[j]==NULL)M->col_head[j]=p;else{/*尋找列表中的插入位置*/for(q=M->col_head[j];q->down&&q->down->row<i;q=q->down)p->down=q->down;q->down=p;/*完成插入*/}scanf(“%d%d%d”&i,&j,&e);}}5.4廣義表

廣義表也是線性表的一種推廣。廣義表也是n個數(shù)據(jù)元素（d1，d2，d3，…，dn）的有限序列，但不同的是，廣義表中的di既可以是單個元素，還可以是一個廣義表，通常記作：GL=（d1，d2，d3，…，dn）。GL是廣義表的名字，通常用大寫字母表示。n是廣義表的長度。若

di是一個廣義表，則稱di是廣義表GL的子表。在GL中，d1是GL的表頭，其余部分組成的表（d2，d3，…，dn）稱為GL的表尾。由此可見，廣義表的定義是遞歸定義的。廣義表LS=(1,2,…,n)的結(jié)構(gòu)特點:1)廣義表中的數(shù)據(jù)元素有相對次序；2)廣義表的長度定義為最外層包含元素個數(shù)；3)廣義表的深度定義為所含括弧的重數(shù)；注意：“原子”的深度為0

“空表”的深度為14)廣義表可以共享；5)廣義表可以是一個遞歸的表。遞歸表的深度是無窮值，長度是有限值。6)任何一個非空廣義表

LS=(1,2,…,n)

均可分解為

表頭

Head(LS)=1和

表尾

Tail(LS)=(2,…,n)兩部分。例如:D=(E,F)=((a,(b,c))，F(xiàn))Head(D)=ETail(D)=(F)Head(E)=aTail(E)=((b,c))Head(((b,c)))=(b,c)Tail(((b,c)))=()Head((b,c))=bTail((b,c))=(c)Head((c))=cTail((c))=()

l

D=（）空表；其長度為零。lA=(a，(b，c))表長度為2的廣義表，其中第一個元素是單個數(shù)據(jù)a，第二個元素是一個子表（b，c）。lB=（A，A，D）長度為3的廣義表，其前兩個元素為表A，第三個元素為空表D。lC=（a，C）長度為2遞歸定義的廣義表，C相當(dāng)于無窮表C=（a，（a，（a，（…））））。

例如：head(A)=a表A的表頭是a。tail(A)=((b，c))表A的表尾是((b，c))，廣義表的表尾一定是一個表。從上面的例子可以看出：（1）廣義表的元素可以是子表，而子表還可以是子表…，由此，廣義表是一個多層的結(jié)構(gòu)。（2）廣義表可以被其他廣義表共享。如：廣義表B就共享表A。在表B中不必列出表A的內(nèi)容，只要通過子表的名稱就可以引用該表。（3）廣義表具有遞歸性，如廣義表C。

廣義表中有兩類結(jié)點:一類是單個元素結(jié)點，一類是子表結(jié)點。任何一個非空的廣義表都可以將其分解成表頭和表尾兩部分，反之，一對確定的表頭和表尾可以唯一地確定一個廣義表。一個表結(jié)點可由三個域構(gòu)成：標(biāo)志域，指向表頭的指針域，指向表尾的指針域。而元素結(jié)點只需要兩個域：標(biāo)志域和值域。

通常采用頭、尾指針的鏈表結(jié)構(gòu)表結(jié)點:原子結(jié)點：tag=0datatag=1hptp1)表頭、表尾分析法：構(gòu)造存儲結(jié)構(gòu)的兩種分析方法:若表頭為原子，則為空表

ls=NIL非空表lstag=1指向表頭的指針指向表尾的指針tag=0data否則，依次類推。L=(a,(x,y),((x)))a(x,y)(

)

1LL=()0a

10x

1()x

0x

0y

1

1

1

12)子表分析法：若子表為原子，則為空表

ls=NIL非空表1指向子表1

的指針tag=0data否則，依次類推。1指向子表2

的指針1指向子表n

的指針ls…D111Ac0b0a011111BCa0廣義表A、B、C、D的存儲結(jié)構(gòu)圖

廣義表的頭尾鏈表存儲結(jié)構(gòu)：

typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{AtomTypeatom;struct{structGLNode*hp,*tp;}htp;}atom_htp;}GLNode，*GList；另外，還有一種廣義表存儲結(jié)構(gòu)，在這種結(jié)構(gòu)中，無論是單元素結(jié)點還是子表結(jié)點均由三個域構(gòu)成。其結(jié)點結(jié)構(gòu)圖為：tpatomtag=0tphptag=1表結(jié)點原子結(jié)點11a0b01c0111a0DABC111廣義表的第二種存儲結(jié)構(gòu)圖typedefenum{ATOM,LIST}ElemTag;/*ATOM＝0，表示原子；LIST＝1，表示子表*/typedefstructGLNode{ElemTagtag;union{AtomTypeatom;structGLNode*hp;}atom_hp;structGLNode*tp;}*GList;

廣義表的擴展線性鏈表存儲結(jié)構(gòu)：下面以廣義表的頭尾鏈表存儲結(jié)構(gòu)為例，介紹廣義表的幾個基本操作。

5.4.3廣義表的操作實現(xiàn)舉例

GListHead(GListL){if(L==NULL)return(NULL);/*空表無表頭*/if(L->tag==ATOM)exit(0);/*原子不是表*/elsereturn(L->atom_htp.htp.hp);}GListTail(GListL){if(L==NULL)return(NULL);/*空表無表尾*/if(L->tag==ATOM)exit(0);/*原子不是表*/elsereturn(L->atom_htp.htp.tp);}1、求廣義表的表頭和表尾intLength(GListL){intn=0;GLNode*s;if(L==NULL)return(0);/*空表長度為0*/if(L->tag==ATOM)exit(0);/*原子不是表*/s=L;while(s!=NULL)/*統(tǒng)計最上層表的長度*/{k++;s=s->atom_htp.htp.tp;}return(k);}2、求廣義表的長度

intDepth(GListL){intd,max;GLNode*s;if(L==NULL)return(1);/*空表深度為1*/if(L->tag==ATOM)return(0);/*原子深度為0*/s=L;while(s!=NULL)/*求每個子表的深度的最大值*/{d=Depth(s->atom_htp.htp.hp);if(d>max)max=d;s=s->atom_htp.htp.tp;}return(max+1);/*表的深度等于最深子表的深度加1*/}

2、求廣義表的深度

intCountAtom(GListL){intn1,n2;if(L==NULL)return(0);/*空表中沒有原子*/if(L->tag==ATOM)return(1);/*L指向單個原子*/n1=CountAtom(L->atom_htp.htp.hp);/*求表頭中的原子數(shù)*/n2=CountAtom(L->atom_htp.htp.tp);/*求表尾中的原子數(shù)*/return(n1+n2);}

3、統(tǒng)計廣義表中原子數(shù)目

intCopyGList(GListS,GList*T){if(S==NULL){*T=NULL;return(OK);}/*復(fù)制空表*/*T=(GLNode*)malloc(sizeof(GLNode));if(*T==NULL)return(ERROR);(*T)->tag=S->tag;if(S->tag==ATOM)(*T)->atom=S->atom;/*復(fù)制單個原子*/else{CopyGList(S->atom_htp.htp.hp,&((*T)->atom_htp.htp.hp));/*復(fù)制表頭*/CopyGList(S->atom_htp.htp.tp,&((*T)->atom_htp.htp.tp));/*復(fù)制表尾*/}return(OK);}4、復(fù)制廣義表

5.5.1主要知識點1、數(shù)組的基本概念

n維數(shù)組可以看成是這樣的一個線性表，其中每個數(shù)據(jù)元素均是一個n-1維數(shù)組。

n維數(shù)組中的每一個元素由一個值和n個下標(biāo)來描述?！爸怠贝碓氐臄?shù)據(jù)信息，n個下標(biāo)用來描述該元素在數(shù)組中的相對位置。一旦定義了數(shù)組的維數(shù)和每一維的上下限，數(shù)組中元素的的個數(shù)就固定了，因此，不能對數(shù)組進行插入或刪除操作。對于數(shù)組的操作一般只有兩類：（1）獲得特定位置的元素值；（2）修改特定位置的元素值。5.5總結(jié)與提高

2、數(shù)組的存儲結(jié)構(gòu)由于數(shù)組中元素的個數(shù)是固定的，因此采用順序存儲結(jié)構(gòu)。二維數(shù)組的順序存儲結(jié)構(gòu)有兩種：一種是按行序存儲，另一種是按列序存儲。給定數(shù)組的起始地址和每個元素的大小，則根據(jù)任意元素的下標(biāo)，可以計算出該元素在存儲器中的地址。因此，數(shù)組是一種隨機存取結(jié)構(gòu)。假設(shè)二維數(shù)組按行序存儲，每個元素占size個存儲單元，數(shù)組的行下標(biāo)是從1到m，列下標(biāo)是從1到n，首元素a11的地址為Loc[1,1]，則任意元素aij的地址計算公式為：Loc[i,j]=Loc[1,1]＋(n×(i－1)＋j－1)×size

假設(shè)二維數(shù)組按行序存儲，每個元素占size個存儲單元，數(shù)組的行下標(biāo)是從c1到d1，列下標(biāo)是從c2到d2，首元素a(c1,c2)的地址為Loc[c1,c2]，則任意元素aij的地址計算公式為：Loc[i,j]=Loc[c1,c2]＋((d2－c2＋1)×(i－c1)＋j－c2)×size

假設(shè)三維數(shù)組采用以行為主序的方法存放，即行下標(biāo)變化最慢，縱下標(biāo)變化最快，每個元素占size個存儲單元，數(shù)組的行下標(biāo)是從c1到d1，列下標(biāo)是從c2到d2，縱下標(biāo)是從c3到d3，首元素a(c1,c2,c3)的地址為Loc[c1,c2,c3]，則任意元素a(i，j，k)的地址計算公式為：

Loc[i,j,k]=Loc[c1,c2,c3]＋

((d2－c2＋1)×(d3－c3＋1)×(i－c1)＋

(d3－c3＋1)×(j－c2)＋

(k－c3))×size

3、特殊矩陣的壓縮存儲

非零元素的分布有一定規(guī)律的矩陣，叫做特殊矩陣（通常為高階矩陣）?？梢岳梅橇阍氐姆植家?guī)律，只存儲非零元素，從而實現(xiàn)有效的壓縮存儲。常見的特殊矩陣包括上三角矩陣、下三角矩陣、帶狀矩陣。4、稀疏矩陣非零元素個數(shù)只占元素總數(shù)的25%—30%或低于這個百分數(shù)，并且分布沒有規(guī)律的矩陣，稱為稀疏矩陣（通常為高階矩陣）。稀疏矩陣的順序存儲結(jié)構(gòu)：三元組表稀疏矩陣的鏈?zhǔn)酱鎯Y(jié)構(gòu)：十字鏈表5、廣義表

廣義表是n個數(shù)據(jù)元素（d1，d2，d3，…，dn）的有限序列，其中di既可以是單個元素，也可以是一個廣義表。在廣義表（d1，d2，d3，…，dn）中，d1是廣義表的表頭，而（d2，d3，…，dn）稱為廣義表的表尾。廣義表的頭尾鏈表存儲結(jié)構(gòu)廣義表的擴展線性鏈表存儲結(jié)構(gòu)廣義表的簡單操作

5.5.2典型題選解例1

已知數(shù)組M[1..10,－1..6,0..3]，求：（1）數(shù)組的元素總數(shù)；（2）若數(shù)組以下標(biāo)順序為主序存儲，起始地址為1000，且每個數(shù)據(jù)元素占用3個存儲單元，試分別計算M[2,4,2],M[5,－1,3]的地址。解：（1）數(shù)組的元素總數(shù)為：(10－1＋1)×(6－(－1)＋1)×(3－0＋1)=320（2）地址計算公式為：Loc[i,j,k]=Loc[c1,c2,c3]＋

((d2－c2＋1)×(d3－c3＋1)×(i－c1)＋

(d3－c3＋1)×(j－c2)＋

(k－c3))×size在此c1=1，d1=10，c2=－1，d2=6，c3=0，d3=3，所以：Loc[2,4,2]=1000＋

((6－(－1)＋1)×(3－0＋1)×(2－1)＋

(3－0＋1)×(4－(－1))＋

(2－0))×3=1162Loc[5,－1,3]=1000＋

((6－(－1)＋1)×(3－0＋1)×(5－1)＋

(3－0＋1)×(－1－(－1))＋

(3－0))×size=1393例2：已知上三角矩陣An×n，當(dāng)i>j時，aij=c，要求將其壓縮存儲到一維數(shù)組B[1..m]中。請說明壓縮存儲方法，并給出任意元素aij與B[k]的對應(yīng)關(guān)系：k=f(i,j)。解：顯然，上三角中共有n(n+1)/2個元素，下三角中所有相同元素c可以共享一個存儲單元，所以一維數(shù)組B[1..m]的上界m=n(n+1)/2+1。將上三角中n(n+1)/2個元素逐行存放到一維數(shù)組B的前m－1個單元中，相同元素c存放在最后一個單元B[m]中。

上三角中第t行共有n-t+1個元素，所以，對于上三角中任意元素aij而言，排在前面的i-1行中共有元素：在上三角的第i行中，排在aij前面的元素數(shù)目為：j-(i-1)-1=j-i。所以，對于上三角中任意元素aij而言，排在aij前面的元素數(shù)目為：因此，上三角中任意元素aij在一維數(shù)組B中的位置為：綜上所述，上三角矩陣An×n中任意元素aij與B[k]的對應(yīng)關(guān)系為：當(dāng)i>j時，當(dāng)i<=j時，[思考題]：如何編寫從一維數(shù)組B中取出任意元素aij的函數(shù)

GetValue(i,j)？例3已知廣義表L=((x,y,z),a,(u,t,w))，從L表中取出原子u的運算是：A)head(tail(tail(L)))B)tail(head(head(tail(L))))C)head(tail(head(tail(L))))D)head(head(tail(tail(L))))解：取出原子u的過程如下：1）用tail運算去掉表頭(x,y,z)，即：tail(L)=(a,(u,t,w))2）再用tail運算去掉表頭a，即：tail(tail(L))=((u,t,w))3）用head運算取出表頭(u,t,w)，即：head(tail(tail(L)))=(u,t,w)4）再用head運算取出表頭u，即：head(head(tail(tail(L))))=u1.設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（

B

）。A.13B.