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

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

6.1數(shù)組6.2稀疏矩陣6.3廣義表16.1.1數(shù)組的基本概念從邏輯結(jié)構(gòu)上看，數(shù)組A是n（n＞1）個相同類型數(shù)據(jù)元素a1、a2、…、an構(gòu)成的有限序列，其邏輯表示為：A=（a1，a2，…，an）其中，ai（1≤i≤n）表示數(shù)組A的第i個元素。一個二維數(shù)組可以看作是每個數(shù)據(jù)元素都是相同類型的一維數(shù)組的一維數(shù)組。以此類推，任何多維數(shù)組都可以看作一個線性表，這時線性表中的每個數(shù)據(jù)元素也是一個線性表。2多維數(shù)組是線性表的推廣。推廣到d（d≥3）維數(shù)組，不妨把它看作一個由d-1維數(shù)組作為數(shù)據(jù)元素的線性表；或者這樣理解，它是一種較復雜的線性表結(jié)構(gòu)，由簡單的數(shù)據(jù)結(jié)構(gòu)即線性表輾轉(zhuǎn)合成而得。3Value(A,index1,index2,…,indexd)：A是已存在的d維數(shù)組，index1，index2，…，indexd是指定的d個下標值，且這些下標均未越界。其運算結(jié)果是返回由上述下標指定的A中的對應(yīng)元素的值。如Value(A,2,3)就是A23的值A(chǔ)ssign(A,e,index1,index2,…,indexd)：A是已存在的d維數(shù)組，e為元素變量，index1，index2，…，indexd

是指定的d個下標值，且這些下標均未越界。其運算結(jié)果是將e的值賦給由上述下標指定的A中的對應(yīng)元素。如Assign(A,123,3,5)就是A35=123ADisp(A,b1,b2,…,bd)：輸出d維數(shù)組A的所有元素值。

其中，bi是第i維的長度，i=1,2,...,d數(shù)組的基本運算如下：46.1.2數(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ù)元素都和一組惟一的下標值對應(yīng)。

(4)數(shù)組是一種隨機存儲結(jié)構(gòu)。可隨機存取數(shù)組中的任意數(shù)據(jù)元素。5

在一維數(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ù)組也滿足隨機存儲特性。6對于一個m行n列的二維數(shù)組Am×n,有：

將Am*n簡記為A,A是這樣的一維數(shù)組：

A=(a1,a2,…,ai…,am)其中,ai=(ai,1,ai,2,…,ai,n)(1≤j≤m)。7

顯然,二維數(shù)組同樣滿足數(shù)組的定義。一個二維數(shù)組可以看作是每個數(shù)據(jù)元素都是相同類型的一維數(shù)組的一維數(shù)組。以此類推,任何多維數(shù)組都可以看作一個線性表,這時線性表中的每個數(shù)據(jù)元素也是一個線性表。多維數(shù)組是線性表的推廣。8

對于二維數(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,n9

對一個已知以行序為主序的計算機系統(tǒ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ù)。10

同理可推出在以列序為主序的計算機系統(tǒng)中有：

LOC(ai,j)=LOC(a1,1)+[(j-1)*m+(i-1)]*k

其中m為行數(shù)。11

例6.1對C語言的二維數(shù)組floata[5][4]計算：

(1)數(shù)組a中的數(shù)組元素數(shù)目；

(2)若數(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=205612例6.2

約瑟夫問題：設(shè)有n個人站成一圈，編號從1到n。從編號為1的人開始循環(huán)報數(shù)“1，2，3，4，…”，數(shù)到m的人出列，然后出列者的下個人重新從1開始報數(shù)，數(shù)到m的人又出列，如此反復進行，直到n個人都出列為止。輸出n個人的出列順序。voidjosephus(intn,intm){intp[MaxSize];inti,j,t;for(i=0;i<n;i++)p[i]=i+1;//n個人編號存入數(shù)組pt=0;//t是開始報數(shù)者的下標

cout<<“出列順序：”;13for(i=n;i>=1;i--)//i為圈中剩下的人數(shù){t=(t+m-1)%i;//t是出列者的下標

cout<<p[t]<<“”;for(j=t+1;j<i;j++)p[j-1]=p[j];//將出列者后面的每個元素前移}}14intmain(intargc,char*argv[]){ intn,m; cout<<"輸入人數(shù)n："; cin>>n; cout<<"輸入報數(shù)最大值m："; cin>>m;

josephus(n,m); cout<<endl; return0;}156.1.3特殊矩陣的壓縮存儲

特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣,為了節(jié)省存儲空間,特別是在高階矩陣的情況下,可以利用特殊矩陣的規(guī)律,對它們進行壓縮存儲,也就是說,使多個相同的非零元素共享同一個存儲單元,對零元素不分配存儲空間。

特殊矩陣的主要形式有對稱矩陣、對角矩陣，上三角矩陣，下三角矩陣等,它們都是方陣,即行數(shù)和列數(shù)相同。161.對稱矩陣的壓縮存儲

若一個n階方陣A[n][n]中的元素滿足ai,j=aj,i(0≤i,j≤n-1),則稱其為n階對稱矩陣。由于對稱矩陣中的元素關(guān)于主對角線對稱,因此在存儲時可只存儲對稱矩陣中上三角或下三角中的元素,使得對稱的元素共享一個存儲空間。這樣,就可以將n2個元素壓縮存儲到n(n+1)/2個元素的空間中。不失一般性,我們以行序為主序存儲其下三角(包括對角線)的元素。17

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＜j0][1][2]….…[9]18上三角矩陣：

b[k]=a[i][j]A[0..n-1,0..n-1]←→B[0..n(n+1)/2]k=+j–ii≤j時i＞j時[0][1][2]….…[9][10]19下三角矩陣：b[k]=a[i][j]A[0..n-1,0..n-1]←→B[0..n(n+1)/2]

k=

i≥j時i＜j時[0][1][2]….…[9][10]202.對角矩陣的壓縮存儲

若一個n階方陣A滿足其所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中,則稱其為n階對角矩陣。其主對角線上下方各有b條次對角線,稱b為矩陣半帶寬,(2b+1)為矩陣的帶寬。對于半帶寬為b(0≤b≤(n-1)/2)的對角矩陣,其|i-j|≤b的元素ai,j不為零,其余元素為零。下圖所示是半帶寬為b的對角矩陣示意圖。21

半帶寬為b的對角矩陣

22當b＝1時稱為三對角矩陣。其壓縮地址計算公式如下：

k=2i+j

A←→B

a[i][j]←→b[k]A[0..n-1,0..n-1]←→B[0..3n-3]236.2稀疏矩陣

一個階數(shù)較大的矩陣中的非零元素個數(shù)s相對于矩陣元素的總個數(shù)t十分小時,即s<<t時,稱該矩陣為稀疏矩陣。例如一個100×100的矩陣,若其中只有100個非零元素,就可稱其為稀疏矩陣。246.2.1稀疏矩陣的三元組表示稀疏矩陣的壓縮存儲方法是只存儲非零元素。

由于稀疏矩陣中非零元素的分布沒有任何規(guī)律,所以在存儲非零元素時還必須同時存儲該非零元素所對應(yīng)的行下標和列下標。這樣稀疏矩陣中的每一個非零元素需由一個三元組(i,j,ai,j)惟一確定,稀疏矩陣中的所有非零元素構(gòu)成三元組線性表。25

假設(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))一個稀疏矩陣A26

若把稀疏矩陣的三元組線性表按順序存儲結(jié)構(gòu)存儲,則稱為稀疏矩陣的三元組順序表。則三元組順序表的數(shù)據(jù)結(jié)構(gòu)可定義如下：27

#defineMaxSize100/*矩陣中非零元素最多個數(shù)*/typedefstruct{intr; /*行號*/intc; /*列號*/ElemTyped; /*元素值*/}TupNode; /*三元組定義*/typedefstruct{introws; /*行數(shù)值*/intcols; /*列數(shù)值*/intnums; /*非零元素個數(shù)*/TupNodedata[MaxSize];}TSMatrix;/*三元組順序表定義*/28

其中,data域中表示的非零元素通常以行序為主序順序排列,它是一種下標按行有序的存儲結(jié)構(gòu)。這種有序存儲結(jié)構(gòu)可簡化大多數(shù)矩陣運算算法。下面的討論假設(shè)data域按行有序存儲。29(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++; } }}30(2)三元組元素賦值:相當于A[i][j]=x

先在三元組t中找到適當?shù)奈恢胟,將k～t.nums個元素后移一位,將指定元素x插入到t.data[k]處。算法如下：

boolValue(TSMatrix&t,ElemTypex,inti,intj){intk=0,k1;if(i>=t.rows||j>=t.cols)returnfalse;while(k<t.nums&&i>t.data[k].r)k++; /*查找行*/while(k<t.nums&&i==t.data[k].r&&j>t.data[k].c)k++; /*查找列*/31

if(t.data[k].r==i&&t.data[k].c==j) t.data[k].d=x;/*存在這樣的元素,只須改變其值

else/*不存在這樣的元素時插入一個新元素*/{for(k1=t.nums-1;k1>k;i--)/*元素后移*/{t.data[k1+1].r=t.data[k1].r;t.data[k1+1].c=t.data[k1].c;t.data[k1+1].d=t.data[k1].d; } t.data[k].r=i;t.data[k].c=j;t.data[k].d=x; t.nums++;}returntrue;}32(3)將指定位置的元素值賦給變量:相當于x=A[i][j]

先在三元組t中找到指定的位置,將該處的元素值賦給x。算法如下：boolAssign(TSMatrixt,ElemType&x,inti,intj){intk=0;if(i>=t.rows||j>=t.cols)returnfalse;while(k<t.nums&&i>t.data[k].r)k++;while(k<t.nums&&i==t.data[k].r&&j>t.data[k].c)k++;if(t.data[k].r==i&&t.data[k].c==j){x=t.data[k].d;returntrue;}elsereturnfalse;}33(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);}34(5)矩陣轉(zhuǎn)置

對于一個m×n的矩陣Am×n,其轉(zhuǎn)置矩陣是一個n×m的矩陣。設(shè)為Bn×m,滿足ai,j=bj,i,其中1≤i≤m,1≤j≤n。其完整的轉(zhuǎn)置算法如下：voidTranTat(TSMatrixt,TSMatrix&tb){intp,q=0,v; /*q為tb.data的下標*/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的下標*/35

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++;}}}36

以上算法的時間復雜度為O(t.cols*t.nums),而將二維數(shù)組存儲在一個m行n列矩陣中時,其轉(zhuǎn)置算法的時間復雜度為O(m*n)。最壞情況是當稀疏矩陣中的非零元素個數(shù)t.nums和m*n同數(shù)量級時,上述轉(zhuǎn)置算法的時間復雜度就為O(m*n2)。對其他幾種矩陣運算也是如此?？梢?常規(guī)的非稀疏矩陣應(yīng)采用二維數(shù)組存儲,只有當矩陣中非零元素個數(shù)s滿足s<<m*n時,方可采用三元組順序表存儲結(jié)構(gòu)。這個結(jié)論也同樣適用于下面要討論的十字鏈表。376.2.2稀疏矩陣的十字鏈表表示

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

(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é)點。link39

十字鏈表中設(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é)點必須順序鏈接,這樣當需要逐行(列)搜索時,才能一行(列)搜索完后順序搜索下一行(列),行頭結(jié)點和列頭結(jié)點均用link指針完成順序鏈接。

40一個稀疏矩陣4142十字鏈表結(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; /*十字鏈表類型定義*/43輸出十字鏈表矩陣的算法VoidDispMat(MatNode*h){MatNode*p,*q;printf(“行數(shù)=%d,列數(shù)=%d\n”,h->row,h->col)；

p=h->tag.link;while(p!=h){q=p->right;//p指向某行的頭結(jié)點q指向該行的元素結(jié)點

while(q!=p){printf(“\t%d\t%d\t%d\n”,q->row,q->col,q->tag.value);q=q->right;//q指向該行的下個元素結(jié)點

}44p=p->tag.link;//當輸出完一行后，p指向下行的頭結(jié)點

}}456.3廣義表6.3.1廣義表的定義

廣義表簡稱表,它是線性表的推廣。一個廣義表是n(n≥0)個元素的一個序列,若n=0時則稱為空表。設(shè)ai為廣義表的第i個元素,則廣義表GL的一般表示與線性表相同：

GL=(a1,a2,…,ai,…,an)

其中n表示廣義表的長度,即廣義表中所含元素的個數(shù),n≥0。如果ai是單個數(shù)據(jù)元素,則ai是廣義表GL的原子；如果ai是一個廣義表,則ai是廣義表GL的子表。

46廣義表具有如下重要的特性：

(1)廣義表中的數(shù)據(jù)元素有相對次序；

(2)廣義表的長度定義為最外層包含元素個數(shù)；

(3)廣義表的深度定義為所含括弧的重數(shù)。其中,原子的深度為0,空表的深度為1；

上述D的深度為3(4)廣義表可以共享；一個廣義表可以為其他廣義表共享；這種共享廣義表稱為再入表；

L=(a,b,c)F=(d,L)=(d,(a,b,c))

D=((a,(b,c)),F)

長度=247

(5)廣義表可以是一個遞歸的表。一個廣義表可以是自已的子表。這種廣義表稱為遞歸表。遞歸表的深度是無窮值,長度是有限值；

B=(a,B)=(a,(a,(a,,)))(6)任何一個非空廣義表GL均可分解為表頭head(GL)=a1

表尾tail(GL)=(a2,…,an)兩部分。

例如:

D=(E,F)=((a,(b,c))，F(xiàn))head(D)=E

tail(D)=(F)head(E)=a

tail(E)=((b,c))48head(((b,c)))=tail(((b,c)))=head((b,c))=?

tail((b,c))=?head((c))=

tail((c))=練習：head(tail(head(((a,d),(c,d))

)))=tail(head(tail(((a,d),(c,d))

)))=head((b,c))=b

tail((b,c))=(c)head((c))=c

tail((c))=()head(((b,c)))=(b,c)

tail(((b,c)))=()head(tail(head(((a,d),(c,d))

)))=dtail(head(tail(((a,d),(c,d))

)))=(d)49我們規(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)))50

如果把每個表的名字(若有的話)寫在其表的前面,則上面的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)))

51若用圓圈和方框分別表示表和單元素,并用線段把表和它的元素(元素結(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)))526.3.2廣義表的存儲結(jié)構(gòu)

廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu),因此很難為每個廣義表分配固定大小的存儲空間,所以其存儲結(jié)構(gòu)只好采用動態(tài)鏈式結(jié)構(gòu)。為了使子表和原子兩類結(jié)點既能在形式上保持一致，又能進行區(qū)別，其結(jié)點定義如下：tagsublist/datalinkTag=0時，表示原子，用data域；Tag=1時，表示子表，用sublist域（指針）53廣義表的存儲結(jié)構(gòu)C=(a,(b,c,d))54

typedefstructlnode{ inttag; /*結(jié)點類型標識*/ union {ElemTypedata;structlnode*sublist; }val; structlnode*link; /*指向下一個元素*/}GLNode; /*廣義表結(jié)點類型定義*/55廣義表的兩種基本情況：為原子的情況

：566.3.3廣義表的運算1.求廣義表的長度

在廣義表中,同一層次的每個結(jié)點是通過link域鏈接起來的,所以可把它看做是由link域鏈接起來的單鏈表。這樣,求廣義表的長度就是求單鏈表的長度,可以采用以前介紹過的求單鏈表長度的方法求其長度。57求廣義表長度的非遞歸算法如下：

intGLLength(GLNode*g)/*g為一個廣義表頭結(jié)點的指針*/{intn=0;GLNode*gl;gl=g->val.sublist; /*gl指向廣義表的第一個元素*/while(gl!=NULL){n++;gl=gl->link;}returnn;}gl582.求廣義表的深度

對于帶頭結(jié)點的廣義表g,廣義表深度的遞歸定義是它等于所有子表中表的最大深度加1。若g為原子,其深度為0。求廣義表深度的遞歸模型f()如下：f(g)=0若g為原子

1 若g為空表MAX{f(subg)}+1其他情況,subg為g的子表

59intGLDepth(GLNode*g)/*求帶頭結(jié)點的廣義表g的深度*/{intmax=0,dep;GLNode*gl;if(g->tag==0)return0;/*為原子時返回0*/gl=g->val.sublist; /*gl指向第一個元素*/if(gl==NULL)return1;/*為空表時返回1*/while(gl!=NULL) /*遍歷表中的每一個元素*/{if(gl->tag==1) /*元素為子表的情況*/{dep=GLDepth(gl);/*遞歸調(diào)用求出子表的深度*/if(dep>max)max=dep; /*max為同一層所求過的子表中深度的最大值*/}gl=gl->link; /*使gl指向下一個元素*/}return(max+1);gl603.輸出廣義表

以g作為帶表頭附加結(jié)點的廣義表的表頭指針,打印輸出該廣義表時,需要對子表進行遞歸調(diào)用。輸出一個廣義表的算法如下：61voidDispGL(GLNode*g)/*g為一個廣義表的頭結(jié)點指針*/{if(g!=NULL)/*表不為空判斷*/{if(g->tag==0)//為原子結(jié)點時

printf(“%c”,g->val.data);else/*為表結(jié)點時*/ {printf("(");/*輸出'('*/if(g->val.sublist==NULL)printf(“#");//輸出空子表

elseDispGL(g->val.sublist);/*遞歸輸出子表*/