第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”);//動態(tài)數(shù)組

elem++;}}一維數(shù)組存儲方式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類似于線性表，一個二維數(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ù)組開始存放位置LOC(0,0)=a,每個元素占用l個存儲單元

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

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

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

)*l

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

n維數(shù)組

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

下標為i1,i2,i3,…,in

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

)*l

二維數(shù)組三維數(shù)組行向量下標i頁向量下標i列向量下標j行向量下標j

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

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

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

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

例，當

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個元素前元素個數(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中沒有存放。因此，找它的對稱元素A[j][i]。

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

的位置中找到。三對角矩陣的壓縮存儲Ba00a01a10a11a12a21a22a23…

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

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

滿足

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

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

A[i][j]

在數(shù)組

B[]存放于第

k

個位置，則有

i=(k+1)/3

j=k

-2*i例如，當

k=8時，

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

當

k=10時，

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

//非零元素行號/列號

ElemTypee;//非零元素的值}Triple;//三元組typedefunion{ Tripledata[MAXSIZE+1]; intmu,nu,tu;//矩陣行數(shù)、列數(shù)、非零元個數(shù)}TSMatrix;//稀疏矩陣類定義稀疏矩陣轉(zhuǎn)置矩陣用三元組表表示的稀疏矩陣及其轉(zhuǎn)置稀疏矩陣轉(zhuǎn)置算法思想顯然，一個稀疏矩陣的轉(zhuǎn)置仍然是一個稀疏矩陣，方法是：設(shè)將矩陣M轉(zhuǎn)置為矩陣T（1）將矩陣的行列值交換（2）將每一個三元組的i和j相互調(diào)換（3）重排三元組之間的次序可以有兩種處理方法：方法一：按照M(m*n)的列序來進行轉(zhuǎn)置設(shè)矩陣列數(shù)為nu，對矩陣三元組表掃描nu次。第k次檢測列號為k的項。第k次掃描找尋所有列號為k的項，將其行號變列號、列號變行號，順次存于轉(zhuǎn)置矩陣三元組表。稀疏矩陣的轉(zhuǎn)置StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){ T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; //轉(zhuǎn)置矩陣的列數(shù),行數(shù)和非零元素個數(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)中做的，所以時間復(fù)雜度是O(nu*tu)。而一般矩陣的轉(zhuǎn)置算法是在nu*mu的兩重循環(huán)中做的，時間復(fù)雜度是O(nu*mu)。當稀疏矩陣的非零元個數(shù)tu=nu*mu時，其時間復(fù)雜度O(nu*tu)=O(nu*nu*mu)=O(nu2*mu)大大高于一般矩陣的時間復(fù)雜度，所以該算法僅適用于tu<<nu*mu的稀疏矩陣。方法二：快速轉(zhuǎn)置運算在對M矩陣轉(zhuǎn)置時，M矩陣的三元組中元素按行序排列，T矩陣中的元素按M矩陣的列序排列，前面的轉(zhuǎn)置算法的特點是以T矩陣的三元組為中心，在M矩陣的三元組中通盤查找合適的結(jié)點置入T中。如果能預(yù)先確定M的每一列第一個非零元在T中應(yīng)有的位置，則在轉(zhuǎn)置時就可直接放到T中去，所以在轉(zhuǎn)置前，應(yīng)先求得M的每一列中非零元的個數(shù)和每一列的第一個非零元在T中的位置。為此，需要兩個輔助數(shù)組num和cpot,num表示M中第col列非零元素的個數(shù)。cpot表示M中第col列第一個非零元素在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中每列非零元個數(shù)

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

//求第col列中第一個非零元在T中的序號

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

廣義表的概念

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

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

n為表的長度。n=0的廣義表為空表。

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

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