第5章數(shù)據(jù)結(jié)構(gòu)-數(shù)組與廣義表(天津大學(xué))

第五章數(shù)組和

廣義表數(shù)組稀疏矩陣廣義表數(shù)組定義相同類型的數(shù)據(jù)元素的集合。一維數(shù)組的示例352749186054778341020123456789一維數(shù)組數(shù)組的定義和初始化main(){inta1[3]={3,5,7},*elem;for(inti=0;i<3;i++)printf(“%d”,a1[i],“\n”);//靜態(tài)數(shù)組

elem=a1; for(inti=0;i<3;i++){printf(“%d”,*elem,“\n”);//動(dòng)態(tài)數(shù)組

elem++;}}一維數(shù)組存儲(chǔ)方式352749186054778341020123456789llllllllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=

LOC(i-1)+l=a+i*l,i>0

a,i=0

a+i*la類似于線性表，一個(gè)二維數(shù)組的邏輯結(jié)構(gòu)可形式地表示為：2_Array=(D,R)其中D={aij(i=0,1,…,m-1,j=0,1,…,n-1)},aij是同類型數(shù)據(jù)元素的集合。R={ROW,COL}是數(shù)據(jù)元素上關(guān)系的集合。ROW={<aij,ai(j+1)>|0<=i<=m-1,0<=j<=n-2}每一行上的列關(guān)系。COL={<aij,a(i+1)j>|0<=i<=m-2,0<=j<=n-1}每一列上的行關(guān)系。

二維數(shù)組

行優(yōu)先存放：設(shè)數(shù)組開(kāi)始存放位置LOC(0,0)=a,每個(gè)元素占用l個(gè)存儲(chǔ)單元

LOC(i,j)=a+(i*m+j)*l三維數(shù)組

各維元素個(gè)數(shù)為m1,m2,m3

下標(biāo)為i1,i2,i3的數(shù)組元素的存儲(chǔ)地址：（按頁(yè)/行/列存放）LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3

)*l

前i1頁(yè)總元素個(gè)數(shù)第i1頁(yè)的前i2行總元素個(gè)數(shù)

n維數(shù)組

各維元素個(gè)數(shù)為m1,m2,m3,…,mn

下標(biāo)為i1,i2,i3,…,in

的數(shù)組元素的存儲(chǔ)地址：LOC(i1,i2,…,in)=a+(i1*m2*m3*…*mn+i2*m3*m4*…*mn++……+in-1*mn+in

)*l

二維數(shù)組三維數(shù)組行向量下標(biāo)i頁(yè)向量下標(biāo)i列向量下標(biāo)j行向量下標(biāo)j

列向量下標(biāo)k特殊矩陣的壓縮存儲(chǔ)特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。特殊矩陣的壓縮存儲(chǔ)主要是針對(duì)階數(shù)很高的特殊矩陣。為節(jié)省存儲(chǔ)空間，對(duì)可以不存儲(chǔ)的元素，如零元素或?qū)ΨQ元素，不再存儲(chǔ)。對(duì)稱矩陣三對(duì)角矩陣對(duì)稱矩陣的壓縮存儲(chǔ)設(shè)有一個(gè)nn的對(duì)稱矩陣A。在矩陣中，aij=aji為節(jié)約存儲(chǔ)空間，只存對(duì)角線及對(duì)角線以上的元素，或者只存對(duì)角線及對(duì)角線以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。把它們按行存放于一個(gè)一維數(shù)組B中，稱之為對(duì)稱矩陣A的壓縮存儲(chǔ)方式。數(shù)組B共有n+(n-1)++1=n*(n+1)/2個(gè)元素。上三角矩陣下三角矩陣下三角矩陣Ba00a10a11a20a21a22a30a31a32……

an-1n-1

012345678n(n+1)/2-1若ij,數(shù)組元素A[i][j]在數(shù)組B中的存放位置為1+2++i+j=(i+1)*i/2+j前i行元素總數(shù)第i行第j個(gè)元素前元素個(gè)數(shù)

若i<j，數(shù)組元素A[i][j]在矩陣的上三角部分,在數(shù)組B中沒(méi)有存放，可以找它的對(duì)稱元素A[j][i]：=j*(j+1)/2+i若已知某矩陣元素位于數(shù)組B的第k個(gè)位置，可尋找滿足

i(i+1)/2k<(i+1)*(i+2)/2的i,此即為該元素的行號(hào)。

j=k-i*(i+1)/2此即為該元素的列號(hào)。

例，當(dāng)

k=8,3*4/2=6k<4*5/2=10,取

i=3。則

j=8-3*4/2=2。

上三角矩陣Ba00a01a02a03a11a12a13a22a23

a33

0123456789若i

j，數(shù)組元素A[i][j]在數(shù)組B中的存放位置為 n+(n-1)+(n-2)++(n-i+1)+j-i前i行元素總數(shù)第i行第j個(gè)元素前元素個(gè)數(shù)n=4

若i

j，數(shù)組元素A[i][j]在數(shù)組B中的存放位置為

n+(n-1)+(n-2)++(n-i+1)+j-i==(2*n-i+1)*i/2+j-i==(2*n-i-1)*i/2+j

若i>j，數(shù)組元素A[i][j]在矩陣的下三角部分，在數(shù)組B中沒(méi)有存放。因此，找它的對(duì)稱元素A[j][i]。

A[j][i]在數(shù)組B的第(2*n-j-1)*j/2+i

的位置中找到。三對(duì)角矩陣的壓縮存儲(chǔ)Ba00a01a10a11a12a21a22a23…

an-1n-2an-1n-1

012345678910三對(duì)角矩陣中除主對(duì)角線及在主對(duì)角線上下最臨近的兩條對(duì)角線上的元素外，所有其它元素均為0。總共有3n-2個(gè)非零元素。將三對(duì)角矩陣A中三條對(duì)角線上的元素按行存放在一維數(shù)組B中，且a00存放于B[0]。在三條對(duì)角線上的元素aij

滿足

0in-1,i-1ji+1在一維數(shù)組B中A[i][j]在第i行，它前面有3*i-1個(gè)非零元素,在本行中第j列前面有j-i+1個(gè)，所以元素A[i][j]在B中位置為k=

2*i+j。若已知三對(duì)角矩陣中某元素

A[i][j]

在數(shù)組

B[]存放于第

k

個(gè)位置，則有

i=(k+1)/3

j=k

-2*i例如，當(dāng)

k=8時(shí)，

i=(8+1)/3=3,j=8-2*3=2

當(dāng)

k=10時(shí)，

i=(10+1)/3=3,j=10-2*3=4稀疏矩陣(SparseMatrix)非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于矩陣元素個(gè)數(shù)在上圖中,矩陣A是6*7的矩陣,它有42個(gè)元素,但只有8個(gè)非零元素,且分布無(wú)規(guī)律可循,所以可以稱之為稀疏矩陣。稀疏矩陣的抽象數(shù)據(jù)類型(三元組順序表）#defineMAXSIZE12500typedefstruct{ inti,j;

//非零元素行號(hào)/列號(hào)

ElemTypee;//非零元素的值}Triple;//三元組typedefunion{ Tripledata[MAXSIZE+1]; intmu,nu,tu;//矩陣行數(shù)、列數(shù)、非零元個(gè)數(shù)}TSMatrix;//稀疏矩陣類定義稀疏矩陣轉(zhuǎn)置矩陣用三元組表表示的稀疏矩陣及其轉(zhuǎn)置稀疏矩陣轉(zhuǎn)置算法思想顯然，一個(gè)稀疏矩陣的轉(zhuǎn)置仍然是一個(gè)稀疏矩陣，方法是：設(shè)將矩陣M轉(zhuǎn)置為矩陣T（1）將矩陣的行列值交換（2）將每一個(gè)三元組的i和j相互調(diào)換（3）重排三元組之間的次序可以有兩種處理方法：方法一：按照M(m*n)的列序來(lái)進(jìn)行轉(zhuǎn)置設(shè)矩陣列數(shù)為nu，對(duì)矩陣三元組表掃描nu次。第k次檢測(cè)列號(hào)為k的項(xiàng)。第k次掃描找尋所有列號(hào)為k的項(xiàng)，將其行號(hào)變列號(hào)、列號(hào)變行號(hào)，順次存于轉(zhuǎn)置矩陣三元組表。稀疏矩陣的轉(zhuǎn)置StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){ T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; //轉(zhuǎn)置矩陣的列數(shù),行數(shù)和非零元素個(gè)數(shù)

if(T.tu){ q=1;//矩陣T的指針

for(col=1;col<=M.nu;++col) for(p=1;p<=M.tu;++p)//矩陣M的指針

if(M.data[p].j==col){ T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ++q; } } returnOK;}//TransposeSMatrix該算法主要工作是在p*col的兩重循環(huán)中做的，所以時(shí)間復(fù)雜度是O(nu*tu)。而一般矩陣的轉(zhuǎn)置算法是在nu*mu的兩重循環(huán)中做的，時(shí)間復(fù)雜度是O(nu*mu)。當(dāng)稀疏矩陣的非零元個(gè)數(shù)tu=nu*mu時(shí)，其時(shí)間復(fù)雜度O(nu*tu)=O(nu*nu*mu)=O(nu2*mu)大大高于一般矩陣的時(shí)間復(fù)雜度，所以該算法僅適用于tu<<nu*mu的稀疏矩陣。方法二：快速轉(zhuǎn)置運(yùn)算在對(duì)M矩陣轉(zhuǎn)置時(shí)，M矩陣的三元組中元素按行序排列，T矩陣中的元素按M矩陣的列序排列，前面的轉(zhuǎn)置算法的特點(diǎn)是以T矩陣的三元組為中心，在M矩陣的三元組中通盤(pán)查找合適的結(jié)點(diǎn)置入T中。如果能預(yù)先確定M的每一列第一個(gè)非零元在T中應(yīng)有的位置，則在轉(zhuǎn)置時(shí)就可直接放到T中去，所以在轉(zhuǎn)置前，應(yīng)先求得M的每一列中非零元的個(gè)數(shù)和每一列的第一個(gè)非零元在T中的位置。為此，需要兩個(gè)輔助數(shù)組num和cpot,num表示M中第col列非零元素的個(gè)數(shù)。cpot表示M中第col列第一個(gè)非零元素在T中的位置。顯然有：cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]矩陣M的輔助數(shù)組的值Col012356num[col]111221cpot[col]123468轉(zhuǎn)置矩陣StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){ T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; if(T.tu){ for(col=1;col<=M.nu;++col)num[col]=0;//初始化num for(t=1;t<=M.tu;++t)++num[M.data[t].j];//求M中每列非零元個(gè)數(shù)

cpot[1]=1; for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];

//求第col列中第一個(gè)非零元在T中的序號(hào)

for(p=1;p<=M.tu;++p){ col=M.data[p].j;q=cpot[col]; T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e;++cpot[col];//該列下一元素位置

}//for }//if returnOK;}//FastTransposeSMatrix行邏輯鏈接的順序表為便于隨機(jī)存取任意一行的非零元，將快速轉(zhuǎn)置矩陣的算法中的輔助數(shù)組cpot固定在稀疏矩陣的存儲(chǔ)結(jié)構(gòu)中。typedefstruct{ Tripledata[MAXSIZE+1]; intrpos[MAXRC+1]; intmu,nu,tu;}RLSMatrix;該存儲(chǔ)方法便于某些運(yùn)算如稀疏矩陣的相乘。十字鏈表以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示三元組的線性表。廣義表(GeneralLists)

廣義表的概念

n(0)個(gè)表元素組成的有限序列，記作

LS=(a0,a1,a2,…,an-1)LS是表名，ai是表元素，它可以是表(稱為子表)，可以是數(shù)據(jù)元素(稱為原子)。

n為表的長(zhǎng)度。n=0的廣義表為空表。

n>0時(shí)，表的第一個(gè)表元素稱為廣義表的表頭(head)，除此之外，其它表元素組成的表稱為廣義表的表尾(tail)。

A=(); //A是一個(gè)空表B=(e); //表B有一個(gè)原子C=(a,(b,c,d)); //兩個(gè)元素為原子a和子表 (b,c,d)D=(A,B,C); //有三個(gè)元素均為列表E=(a,E); //遞歸的列表,包含兩個(gè)元素,一個(gè)是單元素a,另一個(gè)是子表,但該子表是其自身.所以,E相當(dāng)于一個(gè)無(wú)限的廣義表(a,(a,(a,…))).例如表結(jié)點(diǎn)Tag=1hptp廣義表存儲(chǔ)結(jié)構(gòu)原子結(jié)點(diǎn)Tag=0atomtypedefstructGLNode{ inttag; union{ charatom; struct{structGLNode*hp,*tp;}ptr; };}*GList;方法一方法一A=NILE111D11BC10e0a1110b0c0d110a表結(jié)點(diǎn)Tag=1hptp廣義表存儲(chǔ)結(jié)構(gòu)原子結(jié)點(diǎn)typedefstructGLNode{ inttag; union{ charatom; structGLNode*hp; }; s