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

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

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

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

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時i＞j時下三角矩陣：

k=

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

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

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

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

其中,data域中表示的非零元素通常以行序為主序順序排列,它是一種下標(biāo)按行有序的存儲結(jié)構(gòu)。這種有序存儲結(jié)構(gòu)可簡化大多數(shù)矩陣運算算法。下面的討論假設(shè)data域按行有序存儲。ijaij021112203335446557564(1)從一個二維矩陣創(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)//只存儲非零元素{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個元素后移一位,將指定元素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//不存在這樣的元素時插入一個元素{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)置對于一個m×n的矩陣Am×n,其轉(zhuǎn)置矩陣是一個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++;}}}以上算法的時間復(fù)雜度為O(t.cols*t.nums),而將二維數(shù)組存儲在一個m行n列矩陣中時,其轉(zhuǎn)置算法的時間復(fù)雜度為O(m*n)。最壞情況是當(dāng)稀疏矩陣中的非零元素個數(shù)t.nums和m*n同數(shù)量級時,上述轉(zhuǎn)置算法的時間復(fù)雜度就為O(m*n2)。對其他幾種矩陣運算也是如此?？梢?常規(guī)的非稀疏矩陣應(yīng)采用二維數(shù)組存儲,只有當(dāng)矩陣中非零元素個數(shù)s滿足s<<m*n時,方可采用三元組順序表存儲結(jié)構(gòu)。這個結(jié)論也同樣適用于下面要討論的十字鏈表。5.2.2稀疏矩陣的十字鏈表表示

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

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

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

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

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