數(shù)據(jù)結(jié)構(gòu)-第五章數(shù)組和廣義表

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

5.3.1三角矩陣

5.3.2帶狀矩陣

5.3.3稀疏矩陣5.4廣義表

5.1數(shù)組的定義和運(yùn)算數(shù)組是一種數(shù)據(jù)類型。從邏輯結(jié)構(gòu)上看，數(shù)組可以看成是一般線性表的擴(kuò)充。二維數(shù)組可以看成是線性表的線性表。例如：Am×n=a12

a12

┅a1j

┅a1na21a22┅a2j

┅a2n┇┇ai1ai2┅aij

┅ain┇┇am1am2┅amj

┅amnAm×n=a12

a12

┅a1j

┅a1na21a22┅a2j

┅a2n┇┇ai1ai2┅aij

┅ain┇┇am1am2┅amj

┅amnA=（

1

2┅

j

┅

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

1

2…

j…

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

a12

…a1j

…a1na21a22…a2j

…a2n┇┇ai1ai2…aij

…ain┇┇am1am2…amj

…amnB‖12┇i┇m我們還可以將數(shù)組Am×n看成另外一個(gè)線性表:B=(1，,2,，…，m)，其中i（1≤i≤m）本身也是一個(gè)線性表，稱為行向量，即：I=（ai1，ai2，…，aij

，…，ain）。上面二維數(shù)組的例子，介紹了數(shù)組的結(jié)構(gòu)特性，實(shí)際上數(shù)組是一組有固定個(gè)數(shù)的元素的集合。由于這個(gè)性質(zhì)，使得對(duì)數(shù)組的操作不象對(duì)線性表的操作那樣，可以在表中任意一個(gè)合法的位置插入或刪除一個(gè)元素。對(duì)于數(shù)組的操作一般只有兩類：（1）獲得特定位置的元素值；（2）修改特定位置的元素值。數(shù)組的抽象數(shù)據(jù)類型定義（ADTArray）數(shù)據(jù)對(duì)象：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返回?cái)?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ù)組的順序存儲(chǔ)和實(shí)現(xiàn)對(duì)于數(shù)組A，一旦給定其維數(shù)n及各維長度bi（1≤i≤n），則該數(shù)組中元素的個(gè)數(shù)是固定的，不可以對(duì)數(shù)組做插入和刪除操作，不涉及移動(dòng)元素操作，因此對(duì)于數(shù)組而言，采用順序存儲(chǔ)法比較合適。

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

…,

amn

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

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

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

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

三維數(shù)組A（1..r,1..m,1..n）可以看成是r個(gè)m×n的二維數(shù)組，如下圖所示：假定每個(gè)元素占一個(gè)存儲(chǔ)單元，采用以行為主序的方法存放，首元素a111的地址為Loc[1,1,1]，ai11的地址為Loc[i,1,1]=Loc[1,1,1]+(i-1)*m*n，那么求任意元素aijk的地址計(jì)算公式為：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，每個(gè)元素占一個(gè)存儲(chǔ)單元。則三維數(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)為每個(gè)元素所占存儲(chǔ)單元數(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)系。

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

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特殊矩陣的壓縮存儲(chǔ)特殊矩陣壓縮存儲(chǔ)的壓縮原則是：對(duì)有規(guī)律的元素和值相同的元素只分配一個(gè)存儲(chǔ)單元，對(duì)于零元素不分配空間。5.3.1三角矩陣三角矩陣大體分為：下三角矩陣、上三角矩陣和對(duì)稱矩陣。對(duì)于一個(gè)n階矩陣A來說：若當(dāng)i<j時(shí)，有aij=0，則稱此矩陣為下三角矩陣；若當(dāng)i>j時(shí)，有aij=0，則此矩陣稱為上三角矩陣；若矩陣中的所有元素均滿足aij=aji，則稱此矩陣為對(duì)稱矩陣。對(duì)于下三角矩陣，按“行序?yàn)橹餍颉边M(jìn)行存儲(chǔ)，得到的序列為：a11,a21,a22,a31,a32,a33…an1,an2…ann。由于下三角矩陣的元素個(gè)數(shù)為n(n+1)/2，所以可壓縮存儲(chǔ)到一個(gè)大小為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同樣，對(duì)于上三角矩陣，也可以將其壓縮存儲(chǔ)到一個(gè)大小為n(n+1)/2的一維數(shù)組C中。其中元素aij(i<j)在數(shù)組C中的存儲(chǔ)位置為：Loc[i,j]=Loc[1,1]+j(j-1)/2+i-1對(duì)于對(duì)稱矩陣，因其元素滿足aij=aji，我們可以為每一對(duì)相等的元素分配一個(gè)存儲(chǔ)空間，即只存下三角（或上三角）矩陣，從而將n2個(gè)元素壓縮到n(n+1)/2個(gè)空間中。5.3.2帶狀矩陣帶狀矩陣：在矩陣A中，所有的非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中。最常見的是三對(duì)角帶狀矩陣。An×n=a11a12a21a22a23a32a33a34a43a44a45

……………特點(diǎn):

i=1,j=1,2;當(dāng)

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

三對(duì)角帶狀矩陣的壓縮存儲(chǔ)，以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ)，并且只存儲(chǔ)非零元素。其方法為：1.確定存儲(chǔ)該矩陣所需的一維向量空間的大小

從三對(duì)角帶狀矩陣中可看出：除第一行和最后一行只有兩個(gè)元素外，其余各行均有3個(gè)非零元素。由此可得到一維向量所需的空間大小為：3n-2。2.確定非零元素在一維數(shù)組空間中的位置LOC[i,j]=LOC[1,1]+3×（i-1）-1+j-i+1=LOC[1,1]+2(i-1)+j-15.3.3稀疏矩陣稀疏矩陣：指矩陣中大多數(shù)元素為零的矩陣。一般地，當(dāng)非零元素個(gè)數(shù)只占矩陣元素總數(shù)的25%—30%,或低于這個(gè)百分?jǐn)?shù)時(shí)，我們稱這樣的矩陣為稀疏矩陣。003001512000180900240000000-70000000014000000000M6×7=012900000000000-3000014000240000018000001500-7000N6×7=1.稀疏矩陣的三元組表表示法

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

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

三元組表的類型說明：#defineMAXSIZE1000/*非零元素的個(gè)數(shù)最多為1000*/

typedef

struct {introw,col;/*該非零元素的行下標(biāo)和列下標(biāo)*/

ElementTypee；/*該非零元素的值*/ }Triple;

typedef

struct{Tripledata[MAXSIZE+1];

/*非零元素的三元組表。data[0]未用*/

intm,n,len;/*矩陣的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)*/}TSMatrix；1）用三元組表實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置運(yùn)算矩陣轉(zhuǎn)置：指變換元素的位置，把位于（row，col）位置上的元素?fù)Q到（col

，row）位置上，也就是說，把元素的行列互換。

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

VoidTransMatrix（ElementType

source[n][m],ElementType

dest[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];}實(shí)現(xiàn)轉(zhuǎn)置的簡單方法：①矩陣source的三元組表A的行、列互換就可以得到B中的元素，如圖：②為了保證轉(zhuǎn)置后的矩陣的三元組表B也是以“行序?yàn)橹餍颉边M(jìn)行存放，則需要對(duì)行、列互換后的三元組B，按B的行下標(biāo)（即A的列下標(biāo)）大小重新排序。

B（i，j，x）————（j，i，x）

A兩種處理轉(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=1;

for(k=1;k<=A.n;k++)

for(i=1;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++; } }}算法二、FastTransposeTSMatrix(TSMatrixA,TSMatrix*B){/*基于矩陣的三元組表示，采用快速轉(zhuǎn)置法，將矩陣A轉(zhuǎn)置為B所指的矩陣*/int

col,t,p，q;int

num[MAXSIZE],position[MAXSIZE];B->len=A.len;B->n=A.m;B->m=A.n;if(B->len){for(col=1;col<=A.n;col++)num[col]=0;

for(t=1;t<=A.len;t++)num[A.data[t].col]++;/*計(jì)算每一列的非零元素的個(gè)數(shù)*/ position[1]=1;

for(col=2;col<A.n;col++)/*求col列中第一個(gè)非零元素在B.data[]中的正確位置*/position[col]=position[col-1]+num[col-1];

for(p=1;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].e

position[col]++; }}}用三元組表實(shí)現(xiàn)稀疏矩陣的乘法運(yùn)算設(shè)矩陣M是m1×n1矩陣，N是m2×n2矩陣；若可以相乘，則必須滿足矩陣M的列數(shù)n1與矩陣N的行數(shù)m2相等，才能得到結(jié)果矩陣Q=M×N（一個(gè)m1×n2的矩陣）。數(shù)學(xué)中矩陣Q中的元素的計(jì)算方法如下：

Q[i][j]=

M[i][k]×N[k][j]

n1

k=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]是否為零，都要進(jìn)行一次乘法運(yùn)算，而實(shí)際上，這是沒有不必要的。采用三元組表的方法來實(shí)現(xiàn)時(shí)，因?yàn)槿M只對(duì)矩陣的非零元素做存儲(chǔ)，所以可以采用固定三元組a中元素（i，k，Mik）（1≤i≤m1，1≤k≤n1），在三元組b中找所有行號(hào)為k的的對(duì)應(yīng)元素（k，j，Nkj）（1≤k≤m2，1≤j≤n2）進(jìn)行相乘、累加從而得到Q[i][j]。即：以三元組a中的元素為基準(zhǔn)，依次求出其與三元組b的有效乘積。相乘基本操作：對(duì)于三元組a中每個(gè)元素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的乘積，而這個(gè)乘積只是Q[i，j]的一部分，應(yīng)對(duì)每個(gè)元素設(shè)一個(gè)累計(jì)和變量，其初值為0。掃描完三元組a，求得相應(yīng)元素的乘積并累加到適當(dāng)?shù)睦塾?jì)和的變量上。注意：兩個(gè)稀疏矩陣相乘的結(jié)果不一定是稀疏矩陣。反之，相乘的每個(gè)分量M[i，k]×N[k，j]不為零，但累加的結(jié)果Q[i，j]可能是零。例如：100100100×111000000=111111111#defineMAXSIZE1000/*非零元素的個(gè)數(shù)最多為1000*/#defineMAXROW1000/*矩陣最大行數(shù)為1000*/

typedef

struct {introw,col;/*該非零元素的行下標(biāo)和列下標(biāo)*/

ElementTypee；/*該非零元素的值*/ }Triple;

typedef

struct{Tripledata[MAXSIZE+1];/*非零元素的三元組表，data[0]未用*/

intfirst[MAXROW+1];/*三元組表中各行第一個(gè)非零元素所在的位置。*/

intm,n,len;/*矩陣的行數(shù)、列數(shù)和非零元素的個(gè)數(shù)*/}TriSparMatrix；為方便實(shí)現(xiàn)，將三元組表的類型說明修改如下：具體算法如下：int

MulSMatrix(TriSparMatrixM,TriSparMatrixN,TriSparMatrix*Q){/*采用改進(jìn)的三元組表表示法，求矩陣乘積Q＝M×N*/

int

arow,brow,p;int

ctemp[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)前行中每一個(gè)非零元素*/{brow=M.data[p].col;/*M中的列號(hào)應(yīng)與N中的行號(hào)相等*/

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中列號(hào)*/ctemp[ccol]+=M.data[p].e*N.data[q].e;}/*forq*/}/*求得Q中第crow行的非零元*/for(ccol=1;ccol<Q->n；col++)/*壓縮存儲(chǔ)該非零元*/

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)酱鎯?chǔ)結(jié)構(gòu)：十字鏈表優(yōu)點(diǎn)：它能夠靈活地插入因運(yùn)算而產(chǎn)生的新的非零元素，刪除因運(yùn)算而產(chǎn)生的新的零元素，實(shí)現(xiàn)矩陣的各種運(yùn)算。在十字鏈表中，矩陣的每一個(gè)非零元素用一個(gè)結(jié)點(diǎn)表示，該結(jié)點(diǎn)除了（row，col，value）以外，還要有兩個(gè)域：right：用于鏈接同一行中的下一個(gè)非零元素；down：用以鏈接同一列中的下一個(gè)非零元素。rowcolvaluedownright十字鏈表中結(jié)點(diǎn)的結(jié)構(gòu)示意圖：返回主目錄十字鏈表的結(jié)構(gòu)類型說明如下：typedef

struct

OLNode{introw,col;/*非零元素的行和列下標(biāo)*/

ElementTypevalue;

struct

OLNode*right,*down;/*非零元素所在行表列表的后繼鏈域*/}OLNode;*OLink;

typedef

struct

{OLink*row_head,*col_head;/*行、列鏈表的頭指針向量*/

intm,n,len;/*稀疏矩陣的行數(shù)、列數(shù)、非零元素的個(gè)數(shù)*/ }CrossList;建立稀疏矩陣的十字鏈表算法：CreateCrossList(CrossList*M){/*采用十字鏈表存儲(chǔ)結(jié)構(gòu)，創(chuàng)建稀疏矩陣M*/if(M!=NULL)free(M);scanf(&m,&n,&t);/*輸入M的行數(shù),列數(shù)和非零元素的個(gè)數(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;/*初始化行、列頭指針向量，各行、列鏈表為空的鏈表*/for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)){if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p->row=i;p->col=j;p->value=e;/*生成結(jié)點(diǎn)*/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;/*完成插入*/}}}5.4廣義表廣義表也是線性表的一種推廣。廣義表也是n個(gè)數(shù)據(jù)元素（d1，d2，d3，…，dn）的有限序列，但不同的是，廣義表中的di既可以是單個(gè)元素，還可以是一個(gè)廣義表，通常記作：GL=（d1，d2，d3，…，dn）。GL是廣義表的名字，通常用大寫字母表示。n是廣義表的長度。若

di是一個(gè)廣義表，則稱di是廣義表GL的子表。在GL中，d1是GL的表頭，其余部分組成的表（d2，d3，…，dn）稱為GL的表尾。由此可見，廣義表的定義是遞歸定義的。