第6章數組和廣義表

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

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

其中，bi是第i維的長度，i=1,2,...,d數組的基本運算如下：46.1.2數組的存儲結構數組具有以下性質：

(1)數組中的數據元素數目固定。一旦定義了一個數組,其數據元素數目不再有增減變化。

(2)數組中的數據元素具有相同的數據類型。

(3)數組中的每個數據元素都和一組惟一的下標值對應。

(4)數組是一種隨機存儲結構。可隨機存取數組中的任意數據元素。5

在一維數組中,一旦a1的存儲地址LOC(a1)確定,并假設每個數據元素占用k個存儲單元,則任一數據元素ai的存儲地址LOC(ai)就可由以下公式求出：

LOC(ai)=LOC(a1)+(i-1)*k(0≤i≤n)

上式說明,一維數組中任一數據元素的存儲地址可直接計算得到,即一維數組中任一數據元素可直接存取,因此,一維數組是一種隨機存儲結構。同樣,二維及多維數組也滿足隨機存儲特性。6對于一個m行n列的二維數組Am×n,有：

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

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

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

對于二維數組來說,由于計算機的存儲結構是線性的,如何用線性的存儲結構存放二維數組元素就有一個行／列次序排放問題。以行序為主序的存儲方式：即先存儲第1行,然后緊接著存儲第2行,最后存儲第m行。此時,二維數組的線性排列次序為：

a1,1,a1,2,…,a1,n,a2,1,a2,2,…,a2,n,…,am,1,am,2,…am,n9

對一個已知以行序為主序的計算機系統中,當二維數組第一個數據元素a1,1的存儲地址LOC(a1,1)和每個數據元素所占用的存儲單元k確定后,則該二維數組中任一數據元素ai,j的存儲地址可由下式確定：

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

其中n為列數。10

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

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

其中m為行數。11

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

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

(2)若數組a的起始地址為2000,且每個數組元素長度為32位(即4個字節),數組元素a[3][2]的內存地址。

解：由于C語言中數組的行、列下界均為0,該數組行上界為5-1=4,列上界為4-l=3,所以該數組的元素數目共有(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

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

cout<<“出列順序：”;13for(i=n;i>=1;i--)//i為圈中剩下的人數{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<<"輸入人數n："; cin>>n; cout<<"輸入報數最大值m："; cin>>m;

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

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

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

若一個n階方陣A[n][n]中的元素滿足ai,j=aj,i(0≤i,j≤n-1),則稱其為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滿足其所有非零元素都集中在以主對角線為中心的帶狀區域中,則稱其為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稀疏矩陣

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

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

假設有一個6×7階稀疏矩陣A(為圖示方便,我們所取的行列數都很小),A中元素如下圖所示。則對應的三元組線性表為：

((0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4))一個稀疏矩陣A26

若把稀疏矩陣的三元組線性表按順序存儲結構存儲,則稱為稀疏矩陣的三元組順序表。則三元組順序表的數據結構可定義如下：27

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

其中,data域中表示的非零元素通常以行序為主序順序排列,它是一種下標按行有序的存儲結構。這種有序存儲結構可簡化大多數矩陣運算算法。下面的討論假設data域按行有序存儲。29(1)從一個二維矩陣創建其三元組表示

以行序方式掃描二維矩陣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中找到適當的位置k,將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)矩陣轉置

對于一個m×n的矩陣Am×n,其轉置矩陣是一個n×m的矩陣。設為Bn×m,滿足ai,j=bj,i,其中1≤i≤m,1≤j≤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),而將二維數組存儲在一個m行n列矩陣中時,其轉置算法的時間復雜度為O(m*n)。最壞情況是當稀疏矩陣中的非零元素個數t.nums和m*n同數量級時,上述轉置算法的時間復雜度就為O(m*n2)。對其他幾種矩陣運算也是如此。可見,常規的非稀疏矩陣應采用二維數組存儲,只有當矩陣中非零元素個數s滿足s<<m*n時,方可采用三元組順序表存儲結構。這個結論也同樣適用于下面要討論的十字鏈表。376.2.2稀疏矩陣的十字鏈表表示

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

(a)結點結構(b)頭結點結構

對于一個m×n的稀疏矩陣,每個非零元素用一個結點表示,結點結構可以設計成如下圖(a)所示結構。其中i,j,value分別代表非零元素所在的行號、列號和相應的元素值；down和right分別稱為向下指針和向右指針,分別用來鏈接同列中和同行中的下一個非零元素結點。link39

十字鏈表中設置行頭結點、列頭結點和鏈表頭結點。它們采用和非零元素結點類似的結點結構,具體如上圖(b)所示。其中行頭結點和列頭結點的i,j域值均為0；行頭結點的right指針指向該行鏈表的第一個結點,它的down指針為空；列頭結點的down指針指向該列鏈表的第一個結點,它的right指針為空。行頭結點和列頭結點必須順序鏈接,這樣當需要逐行(列)搜索時,才能一行(列)搜索完后順序搜索下一行(列),行頭結點和列頭結點均用link指針完成順序鏈接。

40一個稀疏矩陣4142十字鏈表結點結構和頭結點的數據結構可定義如下：#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(“行數=%d,列數=%d\n”,h->row,h->col)；

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

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

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

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

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

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

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

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

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

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

(3)廣義表的深度定義為所含括弧的重數。其中,原子的深度為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)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我們規定用小寫字母表示原子,用大寫字母表示廣義表的表名。例如：

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個廣義表可相應地表示如下：

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若用圓圈和方框分別表示表和單元素,并用線段把表和它的元素(元素結點應在其表結點的下方)連接起來,則可得到一個廣義表的圖形表示。例如,上面五個廣義表的圖形表示如下圖所示。

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廣義表的存儲結構

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

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

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

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

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

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

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

59intGLDepth(GLNode*g)/*求帶頭結點的廣義表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);/*遞歸調用求出子表的深度*/if(dep>max)max=dep; /*max為同一層所求過的子表中深度的最大值*/}gl=gl->link; /*使gl指向下一個元素*/}return(max+1);gl603.輸出廣義表

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

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

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