算法與數(shù)據(jù)結(jié)構(gòu)數(shù)組和廣義表

第5章數(shù)組和廣義表

5.1數(shù)組5.2稀疏矩陣本章小結(jié)5.3廣義表5.1.1數(shù)組的根本概念數(shù)組是n(n＞1)個(gè)相同類型數(shù)據(jù)元素a1,a2,…,an構(gòu)成的有限序列,且該有限序列存儲(chǔ)在一塊地址連續(xù)的內(nèi)存單元中。由此可見,數(shù)組的定義類似于采用順序存儲(chǔ)結(jié)構(gòu)的線性表。數(shù)組具有以下性質(zhì)：(1)數(shù)組中的數(shù)據(jù)元素?cái)?shù)目固定。一旦定義了一個(gè)數(shù)組,其數(shù)據(jù)元素?cái)?shù)目不再有增減變化。(2)數(shù)組中的數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。(3)數(shù)組中的每個(gè)數(shù)據(jù)元素都和一組惟一的下標(biāo)值對(duì)應(yīng)。(4)數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)?？呻S機(jī)存取數(shù)組中的任意數(shù)據(jù)元素。5.1.2數(shù)組的存儲(chǔ)結(jié)構(gòu)在一維數(shù)組中,一旦a1的存儲(chǔ)地址LOC(a1)確定,并假設(shè)每個(gè)數(shù)據(jù)元素占用k個(gè)存儲(chǔ)單元,那么任一數(shù)據(jù)元素ai的存儲(chǔ)地址LOC(ai)就可由以下公式求出：LOC(ai)=LOC(a1)+(i-1)*k(0≤i≤n)上式說明,一維數(shù)組中任一數(shù)據(jù)元素的存儲(chǔ)地址可直接計(jì)算得到,即一維數(shù)組中任一數(shù)據(jù)元素可直接存取,因此,一維數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。同樣,二維及多維數(shù)組也滿足隨機(jī)存儲(chǔ)特性。對(duì)于一個(gè)m行n列的二維數(shù)組Am×n,有：將Am*n簡(jiǎn)記為A,A是這樣的一維數(shù)組：A=(a1,a2,…,ai…,am)其中，ai=(ai,1,ai,2,…,ai,n)(1≤i≤m)。二維數(shù)組同樣滿足數(shù)組的定義。一個(gè)二維數(shù)組可以看作是每個(gè)數(shù)據(jù)元素都是相同類型的一維數(shù)組的一維數(shù)組。以此類推,任何多維數(shù)組都可以看作一個(gè)線性表,這時(shí)線性表中的每個(gè)數(shù)據(jù)元素也是一個(gè)線性表。多維數(shù)組是線性表的推廣。對(duì)于二維數(shù)組來說,由于計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)是線性的,如何用線性的存儲(chǔ)結(jié)構(gòu)存放二維數(shù)組元素就有一個(gè)行／列次序排放問題。以行序?yàn)橹餍虻拇鎯?chǔ)方式：即先存儲(chǔ)第1行,然后緊接著存儲(chǔ)第2行,最后存儲(chǔ)第m行。此時(shí),二維數(shù)組的線性排列次序?yàn)椋篴1,1,a1,2,…,a1,n,a2,1,a2,2,…,a2,n,…,am,1,am,2,…am,n對(duì)一個(gè)以行序?yàn)橹餍虻挠?jì)算機(jī)系統(tǒng)中,當(dāng)二維數(shù)組第一個(gè)數(shù)據(jù)元素a1,1的存儲(chǔ)地址LOC(a1,1)和每個(gè)數(shù)據(jù)元素所占用的存儲(chǔ)單元k確定后,那么該二維數(shù)組中任一數(shù)據(jù)元素ai,j的存儲(chǔ)地址可由下式確定：LOC(ai,j)=LOC(a1,1)+[(i-1)*n+(j-1)]*k其中n為列數(shù)。同理可推出在以列序?yàn)橹餍虻挠?jì)算機(jī)系統(tǒng)中有：LOC(ai,j)=LOC(a1,1)+[(j-1)*m+(i-1)]*k其中m為行數(shù)。

例按行優(yōu)先順序和按列優(yōu)先順序列出四維數(shù)組A[2][2][2][2]所有元素在內(nèi)存中的存儲(chǔ)次序。

解：按行優(yōu)先的存儲(chǔ)次序:A[0][0][0][0],A[0][0][0][1],A[0][0][1][0],A[0][0][1][1],A[0][1][0][0],A[0][1][0][1],A[0][1][1][0],A[0][1][1][1],A[1][0][0][0],A[1][0][0][1],A[1][0][1][0],A[1][0][1][1],A[1][1][0][0],A[1][1][0][1],A[1][1][1][0],A[1][1][1][1]

按列優(yōu)先的存儲(chǔ)次序:A[0][0][0][0],A[1][0][0][0],A[0][1][0][0],A[1][1][0][0],A[0][0][1][0],A[1][0][1][0],A[0][1][1][0],A[1][1][1][0],A[0][0][0][1],A[1][0][0][1],A[0][1][0][1],A[1][1][0][1],A[0][0][1][1],A[1][0][1][1],A[0][1][1][1],A[1][1][1][1]例對(duì)二維數(shù)組floata[5][4]計(jì)算：(1)數(shù)組a中的數(shù)組元素?cái)?shù)目；(2)假設(shè)數(shù)組a的起始地址為2000,且每個(gè)數(shù)組元素長(zhǎng)度為32位(即4個(gè)字節(jié)),數(shù)組元素a[3][2]的內(nèi)存地址。解：由于C語言中數(shù)組的行、列下界均為0,該數(shù)組行上界為5-1=4,列上界為4-l=3,所以該數(shù)組的元素?cái)?shù)目共有(4-0+1)*(3-0+1)=5*4=20個(gè)。又由于C語言采用行序?yàn)橹餍虻拇鎯?chǔ)方式,那么有：LOC(a3,2)=LOC(a0,0)+(i*n+j)*k=2000+(3*4+2)*4=20565.1.3特殊矩陣的壓縮存儲(chǔ)特殊矩陣的主要形式有：〔1〕對(duì)稱矩陣〔2〕上三角矩陣／下三角矩陣〔3〕對(duì)角矩陣它們都是方陣,即行數(shù)和列數(shù)相同。1.對(duì)稱矩陣的壓縮存儲(chǔ)假設(shè)一個(gè)n階方陣A[n][n]中的元素滿足ai,j=aj,i(0≤i,j≤n-1),那么稱其為n階對(duì)稱矩陣。由于對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱,因此在存儲(chǔ)時(shí)可只存儲(chǔ)對(duì)稱矩陣中上三角或下三角中的元素,使得對(duì)稱的元素共享一個(gè)存儲(chǔ)空間。這樣,就可以將n2個(gè)元素壓縮存儲(chǔ)到個(gè)元素的空間中。不失一般性,我們以行序?yàn)橹餍虼鎯?chǔ)其下三角(包括對(duì)角線)的元素。n2個(gè)元素←→n(n+1)/2個(gè)元素

A[0..n-1,0..n-1]←→B[0..n(n+1)/2-1]

a[i][j]←→b[k]k=+ji≥j+ii＜j上三角矩陣：

k=+j–ii≤j時(shí)i＞j時(shí)下三角矩陣：

k=

i≥j時(shí)i＜j時(shí)2.對(duì)角矩陣的壓縮存儲(chǔ)假設(shè)一個(gè)n階方陣A滿足其所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中,那么稱其為n階對(duì)角矩陣。其主對(duì)角線上下方各有b條次對(duì)角線,稱b為矩陣半帶寬,(2b+1)為矩陣的帶寬。對(duì)于半帶寬為b(0≤b≤(n-1)/2)的對(duì)角矩陣,其|i-j|≤b的元素ai,j不為零,其余元素為零。以下圖所示是半帶寬為b的對(duì)角矩陣示意圖。半帶寬為b的對(duì)角矩陣

當(dāng)b＝1時(shí)稱為三對(duì)角矩陣。其壓縮地址計(jì)算公式如下：k=2i+j A←→B

a[i][j]←→b[k]思考題：為什么采用壓縮存儲(chǔ)，需要解決什么問題？5.2稀疏矩陣一個(gè)階數(shù)較大的矩陣中的非零元素個(gè)數(shù)s相對(duì)于矩陣元素的總個(gè)數(shù)t十分小時(shí),即s<<t時(shí),稱該矩陣為稀疏矩陣。例如一個(gè)100×100的矩陣,假設(shè)其中只有100個(gè)非零元素,就可稱其為稀疏矩陣。5.2.1稀疏矩陣的三元組表示

稀疏矩陣的壓縮存儲(chǔ)方法是只存儲(chǔ)非零元素。由于稀疏矩陣中非零元素的分布沒有任何規(guī)律,所以在存儲(chǔ)非零元素時(shí)還必須同時(shí)存儲(chǔ)該非零元素所對(duì)應(yīng)的行下標(biāo)和列下標(biāo)。稀疏矩陣中的每一個(gè)非零元素需由一個(gè)三元組：(i,j,ai,j)唯一確定,稀疏矩陣中的所有非零元素構(gòu)成三元組線性表。假設(shè)有一個(gè)6×7階稀疏矩陣A(為圖示方便,所取的行列數(shù)都很小),A中元素如以下圖所示。那么對(duì)應(yīng)的三元組線性表為：((0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4))一個(gè)稀疏矩陣A假設(shè)把稀疏矩陣的三元組線性表按順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ),那么稱為稀疏矩陣的三元組順序表。那么三元組順序表的數(shù)據(jù)結(jié)構(gòu)可定義如下：#defineMaxSize100//矩陣中非零元素最多個(gè)數(shù)typedefstruct{intr; //行號(hào)intc; //列號(hào)ElemTyped; //元素值}TupNode; //三元組定義typedefstruct{introws; //行數(shù)值intcols; //列數(shù)值intnums; //非零元素個(gè)數(shù)TupNodedata[MaxSize];}TSMatrix;//三元組順序表定義

其中,data域中表示的非零元素通常以行序?yàn)橹餍蝽樞蚺帕?它是一種下標(biāo)按行有序的存儲(chǔ)結(jié)構(gòu)。這種有序存儲(chǔ)結(jié)構(gòu)可簡(jiǎn)化大多數(shù)矩陣運(yùn)算算法。下面的討論假設(shè)data域按行有序存儲(chǔ)。ijaij021112203335446557564(1)從一個(gè)二維矩陣創(chuàng)立其三元組表示以行序方式掃描二維矩陣A,將其非零的元素插入到三元組t的后面。

voidCreatMat(TSMatrix&t,ElemTypeA[M][N]){ inti,j; t.rows=M;t.cols=N;t.nums=0; for(i=0;i<M;i++) {for(j=0;j<N;j++)if(A[i][j]!=0)//只存儲(chǔ)非零元素{t.data[t.nums].r=i;t.data[t.nums].c=j; t.data[t.nums].d=A[i][j];t.nums++;} }}(2)三元組元素賦值先在三元組t中找到適當(dāng)?shù)奈恢胟,將k～t.nums個(gè)元素后移一位,將指定元素x插入到t.data[k]處。ijaij0211122033354465575648ijaij021112203335446557568修改元素ijaij0211122033354465575648ijaij021112203335358446557568增加元素算法如下：intValue(TSMatrix&t,ElemTypex,intrs,intcs){inti,k=0;if(rs>=t.rows||cs>=t.cols)return0;while(k<t.nums&&rs>t.data[k].r)k++;//查找行while(k<t.nums&&rs==t.data[k].r&&cs>t.data[k].c)k++;//查找列上述藍(lán)色局部教材中有誤。if(t.data[k].r==rs&&t.data[k].c==cs) t.data[k].d=x;//存在這樣的元素else//不存在這樣的元素時(shí)插入一個(gè)元素{for(i=t.nums-1;i>=k;i--)//元素后移{t.data[i+1].r=t.data[i].r;t.data[i+1].c=t.data[i].c;t.data[i+1].d=t.data[i].d;} t.data[k].r=rs;t.data[k].c=cs;t.data[k].d=x;t.nums++;}return1;}(3)將指定位置的元素值賦給變量先在三元組t中找到指定的位置,將該處的元素值賦給x。算法如下：

intAssign(TSMatrixt,ElemType&x,intrs,intcs){intk=0;if(rs>=t.rows||cs>=t.cols)return0;while(k<t.nums&&rs>t.data[k].r)k++;//查找行while(k<t.nums&&rs==t.data[k].r&&cs>t.data[k].c)k++;//查找列if(t.data[k].r==rs&&t.data[k].c==cs){x=t.data[k].d;return1;}elsereturn0;}(4)輸出三元組從頭到尾掃描三元組t,依次輸出元素值。算法如下：

voidDispMat(TSMatrixt){inti;if(t.nums<=0)return;printf(“\t%d\t%d\t%d\n",t.rows,t.cols,t.nums);printf("------------------\n");for(i=0;i<t.nums;i++) printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d);}(5)矩陣轉(zhuǎn)置對(duì)于一個(gè)m×n的矩陣Am×n,其轉(zhuǎn)置矩陣是一個(gè)n×m的矩陣。設(shè)為Bn×m,滿足ai,j=bj,i,其中1≤i≤m,1≤j≤n。ijaij021112203335446557564ijaij023112201335446557654voidTranTat(TSMatrixt,TSMatrix&tb){intp,q=0,v; //q為tb.data的下標(biāo)tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;if(t.nums!=0){for(v=0;v<t.cols;v++) for(p=0;p<t.nums;p++) //p為t.data的下標(biāo)if(t.data[p].c==v){tb.data[q].r=t.data[p].c;tb.data[q].c=t.data[p].r;tb.data[q].d=t.data[p].d;q++;}}}以上算法的時(shí)間復(fù)雜度為O(t.cols*t.nums),而將二維數(shù)組存儲(chǔ)在一個(gè)m行n列矩陣中時(shí),其轉(zhuǎn)置算法的時(shí)間復(fù)雜度為O(m*n)。最壞情況是當(dāng)稀疏矩陣中的非零元素個(gè)數(shù)t.nums和m*n同數(shù)量級(jí)時(shí),上述轉(zhuǎn)置算法的時(shí)間復(fù)雜度就為O(m*n2)。對(duì)其他幾種矩陣運(yùn)算也是如此?？梢?常規(guī)的非稀疏矩陣應(yīng)采用二維數(shù)組存儲(chǔ),只有當(dāng)矩陣中非零元素個(gè)數(shù)s滿足s<<m*n時(shí),方可采用三元組順序表存儲(chǔ)結(jié)構(gòu)。這個(gè)結(jié)論也同樣適用于下面要討論的十字鏈表。5.2.2稀疏矩陣的十字鏈表表示

十字鏈表為稀疏矩陣的每一行設(shè)置一個(gè)單獨(dú)鏈表,同時(shí)也為每一列設(shè)置一個(gè)單獨(dú)鏈表。這樣稀疏矩陣的每一個(gè)非零元素就同時(shí)包含在兩個(gè)鏈表中,即每一個(gè)非零元素同時(shí)包含在所在行的行鏈表中和所在列的列鏈表中。這就大大降低了鏈表的長(zhǎng)度,方便了算法中行方向和列方向的搜索,因而大大降低了算法的時(shí)間復(fù)雜度。

(a)結(jié)點(diǎn)結(jié)構(gòu)(b)頭結(jié)點(diǎn)結(jié)構(gòu)對(duì)于一個(gè)m×n的稀疏矩陣,每個(gè)非零元素用一個(gè)結(jié)點(diǎn)表示,結(jié)點(diǎn)結(jié)構(gòu)可以設(shè)計(jì)成如以下圖(a)所示結(jié)構(gòu)。其中i,j,value分別代表非零元素所在的行號(hào)、列號(hào)和相應(yīng)的元素值；down和right分別稱為向下指針和向右指針,分別用來鏈接同列中和同行中的下一個(gè)非零元素結(jié)點(diǎn)。十字鏈表中設(shè)置行頭結(jié)點(diǎn)、列頭結(jié)點(diǎn)和鏈表頭結(jié)點(diǎn)。它們采用和非零元素結(jié)點(diǎn)類似的結(jié)點(diǎn)結(jié)構(gòu),具體如上圖(b)所示。其中行頭結(jié)點(diǎn)和列頭結(jié)點(diǎn)的i,j域值均為0；行頭結(jié)點(diǎn)的right指針指向該行鏈表的第一個(gè)結(jié)點(diǎn),它的down指針為空；列頭結(jié)點(diǎn)的down指針指向該列鏈表的第一個(gè)結(jié)點(diǎn),它的right指針為空。行頭結(jié)點(diǎn)和列頭結(jié)點(diǎn)必須順序鏈接,這樣當(dāng)需要逐行(列)搜索時(shí),才能一行(列)搜索完后順序搜索下一行(列),行頭結(jié)點(diǎn)和列頭結(jié)點(diǎn)均用link指針完成順序鏈接。一個(gè)稀疏矩陣十字鏈表結(jié)點(diǎn)結(jié)構(gòu)和頭結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)可定義如下：#defineM3 //矩陣行#defineN4 //矩陣列#defineMax((M)>(N)?(M):(N))//矩陣行列較大者typedefstructmtxn{introw; //行號(hào)intcol; //列號(hào)structmtxn*right,*down; //向右和向下的指針union{intvalue;structmtxn*link;}tag;}MatNode; //十字鏈表類型定義思考題：稀疏矩陣的十字鏈表表示給我們什么啟示？例如，要存放假設(shè)干班的學(xué)生信息，每個(gè)班的人數(shù)不定，如何設(shè)計(jì)其存儲(chǔ)結(jié)構(gòu)？5.3廣義表1.廣義表的定義廣義表簡(jiǎn)稱表,它是線性表的推廣。一個(gè)廣義表是n(n≥0)個(gè)元素的一個(gè)序列,假設(shè)n=0時(shí)那么稱為空表。設(shè)ai為廣義表的第i個(gè)元素,那么廣義表GL的一般表示與線性表相同：GL=(a1,a2,…,ai,…,an)其中n表示廣義表的長(zhǎng)度,即廣義表中所含元素的個(gè)數(shù),n≥0。如果ai是單個(gè)數(shù)據(jù)元素,那么ai是廣義表GL的原子；如果ai是一個(gè)廣義表,那么ai是廣義表GL的子表。廣義表具有如下重要的特性：(1)廣義表中的數(shù)據(jù)元素有相對(duì)次序；(2)廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù)；(3)廣義表的深度定義為所含括弧的重?cái)?shù)。其中,原子的深度為0,空表的深度為1；(4)廣義表可以共享；一個(gè)廣義表可以為其他廣義表共享；這種共享廣義表稱為再入表；(5)廣義表可以是一個(gè)遞歸的表。一個(gè)廣義表可以是自已的子表。這種廣義表稱為遞歸表。遞歸表的深度是無窮值,長(zhǎng)度是有限值；(6)任何一個(gè)非空廣義表GL均可分解為表頭head(GL)=a1和表尾tail(GL)=(a2,…,an)兩局部。

為了簡(jiǎn)單起見,下面討論的廣義表不包括前面定義的再入表和遞歸表,即只討論一般的廣義表。另外,我們規(guī)定用小寫字母表示原子,用大寫字母表示廣義表的表名。例如：A=()B=(e)C=(a,(b,c,d))D=(A,B,C)=((),(e),(a,(b,c,d)))E=((a,(a,b),((a,b),c)))如果把每個(gè)表的名字(假設(shè)有的話)寫在其表的前面,那么上面的5個(gè)廣義表可相應(yīng)地表示如下：A()B(e)C(a,(b,c,d))D(A(),B(e),C(a,(b,c,d)))E((a,(a,b),((a,b),c)))假設(shè)用圓圈和方框分別表示表和單元素,并用線段把表和它的元素(元素結(jié)點(diǎn)應(yīng)在其表結(jié)點(diǎn)的下方)連接起來,那么可得到一個(gè)廣義表的圖形表示。例如,上面五個(gè)廣義表的圖形表示如以下圖所示。A()B(e)C(a,(b,c,d))D(A(),B(e),C(a,(b,c,d)))E((a,(a,b),((a,b),c)))2.廣義表的存儲(chǔ)結(jié)構(gòu)廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu),因此很難為每個(gè)廣義表分配固定大小的存儲(chǔ)空間,所以其存儲(chǔ)結(jié)構(gòu)只好采用動(dòng)態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。廣義表的存儲(chǔ)結(jié)構(gòu)typedefstructlnode{inttag; //結(jié)點(diǎn)類型標(biāo)識(shí)union{ElemTypedata;structlnode*sublist;}val;structlnode*link; //指向下一個(gè)元素}GLNode; //廣義表結(jié)點(diǎn)類型定義廣義表的兩種根本情況：為原子的情況

：3.廣義表的運(yùn)算(1)求廣義表的長(zhǎng)度在廣義表中,同一層次的每個(gè)結(jié)點(diǎn)是通過link域鏈接起來的,所以可把它看做是由link域鏈接起來的單鏈表。這樣,求廣義表的長(zhǎng)度就是求單鏈表的長(zhǎng)度,可以采用以前介紹過的求單鏈表長(zhǎng)度的方法求其長(zhǎng)度。求廣義表長(zhǎng)度的非遞歸算法如下：intGLLength(GLNode*g)//g為一個(gè)廣義表頭結(jié)點(diǎn)的指針{intn=0;g=g->val.sublist;//g指向廣義表的第一個(gè)元素while(g!=NULL){n++;g=g->link;}returnn;}(2)求廣義表的深度對(duì)于帶頭結(jié)點(diǎn)的廣義表g,廣義表深度的遞歸定義是它等于所有子表中表的最大深度加1。假設(shè)g為原子,其深度為0。求廣義表深度的遞歸模型f()如下：f(g)=0假設(shè)g為原子1 假設(shè)g為空表MAX{f(subg)}+1其他情況,subg為g的子表

intGLDepth(GLNode*g)//求帶頭結(jié)點(diǎn)的廣義表g的深度{intmax=0,dep;if(g->tag==0)return0; //為原子時(shí)返回0g=g->val.sublist; //g指向第一個(gè)元素if(g==NULL)return1;//為空表時(shí)返回1w