第5章數組和廣義表5.1數組的定義和運算5.2數組的順序存儲和實現5.3特殊矩陣的壓縮存儲

5.3.1三角矩陣

5.3.2帶狀矩陣

5.3.3稀疏矩陣5.4廣義表

5.1數組的定義和運算數組是一種數據類型。從邏輯結構上看，數組可以看成是一般線性表的擴充。二維數組可以看成是線性表的線性表。例如：Am×n=a12

a12

┅a1j

┅a1na21a22┅a2j

┅a2n┇┇ai1ai2┅aij

┅ain┇┇am1am2┅amj

┅amnAm×n=a12

a12

┅a1j

┅a1na21a22┅a2j

┅a2n┇┇ai1ai2┅aij

┅ain┇┇am1am2┅amj

┅amnA=（

1

2┅

j

┅

n)我們可以把二維數組看成一個線性表：A=(

1

2…

j…

n)，其中j（1≤j≤n）本身也是一個線性表，稱為列向量。矩陣Am×n看成n個列向量的線性表,即j=(a1j,a2j,…,amj)Am×n=a12

a12

…a1j

…a1na21a22…a2j

…a2n┇┇ai1ai2…aij

…ain┇┇am1am2…amj

…amnB‖12┇i┇m我們還可以將數組Am×n看成另外一個線性表:B=(1，,2,，…，m)，其中i（1≤i≤m）本身也是一個線性表，稱為行向量，即：I=（ai1，ai2，…，aij

，…，ain）。上面二維數組的例子，介紹了數組的結構特性，實際上數組是一組有固定個數的元素的集合。由于這個性質，使得對數組的操作不象對線性表的操作那樣，可以在表中任意一個合法的位置插入或刪除一個元素。對于數組的操作一般只有兩類：（1）獲得特定位置的元素值；（2）修改特定位置的元素值。數組的抽象數據類型定義（ADTArray）數據對象：D={aj1j2…jn|n>0，稱為數組的維數，ji是數組的第i維下標，1≤ji≤bi，bi為數組第i維的長度，aj1j2…jn∈ElementSet}數據關系：R={R1,R2,…,Rn}Ri={<aj1…ji…jn

，aj1…ji+1…jn>|1≤jk≤bk，1≤k≤n且k≠i，1≤ji≤bi-1，aj1…ji…jn

，aj1…ji+1…jn∈D，i=1，…，n}基本操作：（1）InitArray(A,n,bound1,…,boundn)：若維數n和各維的長度合法，則構造相應的數組A，并返回TRUE；（2）DestroyArray（A）：銷毀數組A；（3）GetValue（A，e,index1,…,indexn）：若下標合法，用e返回數組A中由index1,…,indexn所指定的元素的值。（4）SetValue（A，e，index1,…,indexn）：若下標合法，則將數組A中由index1,…,indexn所指定的元素的值置為e。注意：這里定義的數組下標是從1開始，與C語言的數組略有不同。5.2數組的順序存儲和實現對于數組A，一旦給定其維數n及各維長度bi（1≤i≤n），則該數組中元素的個數是固定的，不可以對數組做插入和刪除操作，不涉及移動元素操作，因此對于數組而言，采用順序存儲法比較合適。

數組的順序存儲結構有兩種：一種是按行序存儲，如高級語言BASIC、COBOL和PASCAL語言都是以行序為主。另一種是按列序存儲，如高級語言中的FORTRAN語言就是以列序為主。對于二維數組Amxn以行為主的存儲序列為：a11,a12,…a1n,a21,a22,…,a2n,……,am1,am2,

…,

amn

以列為主存儲序列為：a11,a21,…am1,a12,a22,…,am2,……,a1n,a2n,…,amn

假設有一個3×4×2的三維數組A

，其邏輯結構圖為：列行縱

以二維數組Amn為例，假設每個元素只占一個存儲單元，“以行為主”存放數組，下標從1開始，首元素a11的地址為Loc[1,1]求任意元素aij的地址，可由如下計算公式得到：Loc[i,j]=Loc[1,1]+n×(i-1)+(j-1)如果每個元素占size個存儲單元，則任意元素aij的地址計算公式為：Loc[i,j]=Loc[1,1]+(n×(i-1)+j-1)×size

三維數組A（1..r,1..m,1..n）可以看成是r個m×n的二維數組，如下圖所示：假定每個元素占一個存儲單元，采用以行為主序的方法存放，首元素a111的地址為Loc[1,1,1]，ai11的地址為Loc[i,1,1]=Loc[1,1,1]+(i-1)*m*n，那么求任意元素aijk的地址計算公式為：Loc[i,j,k]=Loc[1,1,1]+(i-1)*m*n+(j-1)*n+(k-1)其中1≤i≤ｒ，1≤j≤ｍ，1≤k≤ｎ。如果將三維數組推廣到一般情況，即：用j1，j2，j3代替數組下標i，j，k；并且j1，j2，j3的下限為c1，c2，c3，上限分別為d1，d2，d3，每個元素占一個存儲單元。則三維數組中任意元素a(j1，j2，j3)的地址為：Loc[j1，j2，j3]=Loc[c1,c2,c3]+1*(d2-c2+1)*(d3-c3+1)*(j1-c1)

+1*(d3-c3+1)*(j2-c2)+1*(j3-c3)其中l為每個元素所占存儲單元數。令α1=1*(d2-c2+1)*(d3-c3+1),α2=1*(d3-c3+1),α3=1，則：Loc[j1,j2,j3]=Loc[c1,c2,c3]+α1*(j1-c1)+α2*(j2-c2)+α3(j3-c3)=Loc[c1,c2,c3]+Σαi*(ji-ci)（1≤i≤3）由公式可知Loc[j1,j2,j3]與j1,j2,j3呈線性關系。

對于ｎ維數組A(c1:d1,c2:d2，…,cn,dn)，我們只要把上式推廣，就可以容易地得到ｎ維數組中任意元素aj1j2…jn的存儲地址的計算公式。

Loc[j1，j2，…jn]=Loc[c1，c2，…，cn]+

αi

(ji-ci)i=1n其中αi

=l(dk-ck+1)（1≤i≤n）k=i+1n5.3特殊矩陣的壓縮存儲特殊矩陣壓縮存儲的壓縮原則是：對有規律的元素和值相同的元素只分配一個存儲單元，對于零元素不分配空間。5.3.1三角矩陣三角矩陣大體分為：下三角矩陣、上三角矩陣和對稱矩陣。對于一個n階矩陣A來說：若當i<j時，有aij=0，則稱此矩陣為下三角矩陣；若當i>j時，有aij=0，則此矩陣稱為上三角矩陣；若矩陣中的所有元素均滿足aij=aji，則稱此矩陣為對稱矩陣。對于下三角矩陣，按“行序為主序”進行存儲，得到的序列為：a11,a21,a22,a31,a32,a33…an1,an2…ann。由于下三角矩陣的元素個數為n(n+1)/2，所以可壓縮存儲到一個大小為n(n+1)/2的一維數組中。下三角矩陣中元素aij(i>j)，在一維數組A中的位置為：

LOC[i,j]=LOC[1,1]+i(i-1)/2+j-1下三角矩陣：A=a11a21a22a31a32a33┆┆┆┆an1an2an3

…

ann同樣，對于上三角矩陣，也可以將其壓縮存儲到一個大小為n(n+1)/2的一維數組C中。其中元素aij(i<j)在數組C中的存儲位置為：Loc[i,j]=Loc[1,1]+j(j-1)/2+i-1對于對稱矩陣，因其元素滿足aij=aji，我們可以為每一對相等的元素分配一個存儲空間，即只存下三角（或上三角）矩陣，從而將n2個元素壓縮到n(n+1)/2個空間中。5.3.2帶狀矩陣帶狀矩陣：在矩陣A中，所有的非零元素都集中在以主對角線為中心的帶狀區域中。最常見的是三對角帶狀矩陣。An×n=a11a12a21a22a23a32a33a34a43a44a45

……………特點:

i=1,j=1,2;當

1<i<n，j=i-1,i,i+1i=n,j=n-1,n;時，aij非零，其他元素均為零。

三對角帶狀矩陣的壓縮存儲，以行序為主序進行存儲，并且只存儲非零元素。其方法為：1.確定存儲該矩陣所需的一維向量空間的大小

從三對角帶狀矩陣中可看出：除第一行和最后一行只有兩個元素外，其余各行均有3個非零元素。由此可得到一維向量所需的空間大小為：3n-2。2.確定非零元素在一維數組空間中的位置LOC[i,j]=LOC[1,1]+3×（i-1）-1+j-i+1=LOC[1,1]+2(i-1)+j-15.3.3稀疏矩陣稀疏矩陣：指矩陣中大多數元素為零的矩陣。一般地，當非零元素個數只占矩陣元素總數的25%—30%,或低于這個百分數時，我們稱這樣的矩陣為稀疏矩陣。003001512000180900240000000-70000000014000000000M6×7=012900000000000-3000014000240000018000001500-7000N6×7=1.稀疏矩陣的三元組表表示法

對于稀疏矩陣的壓縮存儲要求在存儲非零元素的同時，還必須存儲該非零元素在矩陣中所處的行號和列號。我們將這種存儲方法叫做稀疏矩陣的三元組表示法。

rowcolvalue該非零元素所在的行號該非零元素所在的列號該非零元素的值每個非零元素在一維數組中的表示形式如圖所示：

三元組表的類型說明：#defineMAXSIZE1000/*非零元素的個數最多為1000*/

typedef

struct {introw,col;/*該非零元素的行下標和列下標*/

ElementTypee；/*該非零元素的值*/ }Triple;

typedef

struct{Tripledata[MAXSIZE+1];

/*非零元素的三元組表。data[0]未用*/

intm,n,len;/*矩陣的行數、列數和非零元素的個數*/}TSMatrix；1）用三元組表實現稀疏矩陣的轉置運算矩陣轉置：指變換元素的位置，把位于（row，col）位置上的元素換到（col

，row）位置上，也就是說，把元素的行列互換。

采用矩陣的正常存儲方式時，實現矩陣轉置的經典算法如下：

VoidTransMatrix（ElementType

source[n][m],ElementType

dest[m][n]）{/*Source和dest分別為被轉置的矩陣和轉置后的矩陣（用二維數組表示）*/

inti,j;for(i=0;i<m;i++)for(j=0;j<n;j++)dest[i][j]=source[j][i];}實現轉置的簡單方法：①矩陣source的三元組表A的行、列互換就可以得到B中的元素，如圖：②為了保證轉置后的矩陣的三元組表B也是以“行序為主序”進行存放，則需要對行、列互換后的三元組B，按B的行下標（即A的列下標）大小重新排序。

B（i，j，x）————（j，i，x）

A兩種處理轉置算法如下：算法一、voidTransposeTSMatrix(TSMatrixA,TSMatrix*B){/*把矩陣A轉置到B所指向的矩陣中去。矩陣用三元組表表示*/

inti,j,k;B->m=A.n;B->n=A.m;B->len=A.len;

if(B->len>0) {j=1;

for(k=1;k<=A.n;k++)

for(i=1;i<=A.len;i++)

if(A.data[i].col==k) {B->data[j].row=A.data[i].col B->data[j].col=A.data[i].row;B->data[j].e=A.data[i].e;j++; } }}算法二、FastTransposeTSMatrix(TSMatrixA,TSMatrix*B){/*基于矩陣的三元組表示，采用快速轉置法，將矩陣A轉置為B所指的矩陣*/int

col,t,p，q;int

num[MAXSIZE],position[MAXSIZE];B->len=A.len;B->n=A.m;B->m=A.n;if(B->len){for(col=1;col<=A.n;col++)num[col]=0;

for(t=1;t<=A.len;t++)num[A.data[t].col]++;/*計算每一列的非零元素的個數*/ position[1]=1;

for(col=2;col<A.n;col++)/*求col列中第一個非零元素在B.data[]中的正確位置*/position[col]=position[col-1]+num[col-1];

for(p=1;p<A.len.p++) {col=A.data[p].col;q=position[col];B->data[q].row=A.data[p].col; B->data[q]..col=A.data[p].row;B->data[q].e=A.data[p].e

position[col]++; }}}用三元組表實現稀疏矩陣的乘法運算設矩陣M是m1×n1矩陣，N是m2×n2矩陣；若可以相乘，則必須滿足矩陣M的列數n1與矩陣N的行數m2相等，才能得到結果矩陣Q=M×N（一個m1×n2的矩陣）。數學中矩陣Q中的元素的計算方法如下：

Q[i][j]=

M[i][k]×N[k][j]

n1

k=1其中：1≤i≤m1，1≤j≤n2根據數學上矩陣相乘的原理，我們可以得到矩陣相乘的經典算法：for(i=1;i<=m1;i++)

for(j=1;j<=n2;j++){Q[i][j]=0;

for(k=1;k<=n1;k++)

Q[i][j]=Q[i][j]+M[i][k]*N[k][j];}經典算法中，不論M[i][k]，N[k][j]是否為零，都要進行一次乘法運算，而實際上，這是沒有不必要的。采用三元組表的方法來實現時，因為三元組只對矩陣的非零元素做存儲，所以可以采用固定三元組a中元素（i，k，Mik）（1≤i≤m1，1≤k≤n1），在三元組b中找所有行號為k的的對應元素（k，j，Nkj）（1≤k≤m2，1≤j≤n2）進行相乘、累加從而得到Q[i][j]。即：以三元組a中的元素為基準，依次求出其與三元組b的有效乘積。相乘基本操作：對于三元組a中每個元素a.data[p]（p=1，2，3，…a.len），找出三元組b中所有滿足條件a.data[p].col=b.data[q].row的元素b.data[q]，求得a.data[p].e與b.data[q].e的乘積，而這個乘積只是Q[i，j]的一部分，應對每個元素設一個累計和變量，其初值為0。掃描完三元組a，求得相應元素的乘積并累加到適當的累計和的變量上。注意：兩個稀疏矩陣相乘的結果不一定是稀疏矩陣。反之，相乘的每個分量M[i，k]×N[k，j]不為零，但累加的結果Q[i，j]可能是零。例如：100100100×111000000=111111111#defineMAXSIZE1000/*非零元素的個數最多為1000*/#defineMAXROW1000/*矩陣最大行數為1000*/

typedef

struct {introw,col;/*該非零元素的行下標和列下標*/

ElementTypee；/*該非零元素的值*/ }Triple;

typedef

struct{Tripledata[MAXSIZE+1];/*非零元素的三元組表，data[0]未用*/

intfirst[MAXROW+1];/*三元組表中各行第一個非零元素所在的位置。*/

intm,n,len;/*矩陣的行數、列數和非零元素的個數*/}TriSparMatrix；為方便實現，將三元組表的類型說明修改如下：具體算法如下：int

MulSMatrix(TriSparMatrixM,TriSparMatrixN,TriSparMatrix*Q){/*采用改進的三元組表表示法，求矩陣乘積Q＝M×N*/

int

arow,brow,p;int

ctemp[MAXSIZE];

if(M.n!=N.m)returnFALSE;/*返回FALSE表示求矩陣乘積失敗*/ Q->m=M.m;Q->n=N.n;Q->len=0;

if(M.len*N.len!=0) {for(arow=1;arow<=M.m;arow++)/*逐行處理M*/ {for(p=1;p<=M.n;p++)

ctemp[p]=0;/*當前行各元素的累加器清零*/ Q->first[arow]=Q->len+1;

for(p=M.first[arow];p<M.first[arow+1];p++)/*p指向M當前行中每一個非零元素*/{brow=M.data[p].col;/*M中的列號應與N中的行號相等*/

if(brow<N.n)t=N.first[brow+1];elset=N.len+1;

for(q=N.first[brow];q<t;q++){ccol=N.data[q].col;/*乘積元素在Q中列號*/ctemp[ccol]+=M.data[p].e*N.data[q].e;}/*forq*/}/*求得Q中第crow行的非零元*/for(ccol=1;ccol<Q->n；col++)/*壓縮存儲該非零元*/

if(ctemp[ccol]) {if(++Q->len>MAXSIZE)return0;Q->data[Q->len]={arow,ccol,ctemp[ccol]}; }/*if*/}/*forarow*/}/*if*/return(TRUE);/*返回TRUE表示求矩陣乘積成功*/}2.稀疏矩陣的鏈式存儲結構：十字鏈表優點：它能夠靈活地插入因運算而產生的新的非零元素，刪除因運算而產生的新的零元素，實現矩陣的各種運算。在十字鏈表中，矩陣的每一個非零元素用一個結點表示，該結點除了（row，col，value）以外，還要有兩個域：right：用于鏈接同一行中的下一個非零元素；down：用以鏈接同一列中的下一個非零元素。rowcolvaluedownright十字鏈表中結點的結構示意圖：返回主目錄十字鏈表的結構類型說明如下：typedef

struct

OLNode{introw,col;/*非零元素的行和列下標*/

ElementTypevalue;

struct

OLNode*right,*down;/*非零元素所在行表列表的后繼鏈域*/}OLNode;*OLink;

typedef

struct

{OLink*row_head,*col_head;/*行、列鏈表的頭指針向量*/

intm,n,len;/*稀疏矩陣的行數、列數、非零元素的個數*/ }CrossList;建立稀疏矩陣的十字鏈表算法：CreateCrossList(CrossList*M){/*采用十字鏈表存儲結構，創建稀疏矩陣M*/if(M!=NULL)free(M);scanf(&m,&n,&t);/*輸入M的行數,列數和非零元素的個數*/M->m=m;M->n=n;M->len=t;If(!(M->row_head=(Olink*)malloc((m+1)sizeof(OLink))))exit(OVERFLOW);If(!(M->col_head=(OLink*)malloc((n+1)sizeof(OLink))))exit(OVERFLOW);M->row_head[]=M->col_head[]=NULL;/*初始化行、列頭指針向量，各行、列鏈表為空的鏈表*/for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)){if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p->row=i;p->col=j;p->value=e;/*生成結點*/if(M->row_head[i]==NULL)M->row_head[i]=p;else{/*尋找行表中的插入位置*/

for(q=M->row_head[i];q->right&&q->right->col<j;q=q->right)p->right=q->right;q->right=p;/*完成插入*/}if(M->col_head[j]==NULL)M->col_head[j]=p;else{/*尋找列表中的插入位置*/

for(q=M->col_head[j];q->down&&q->down->row<i;q=q->down)p->down=q->down;q->down=p;/*完成插入*/}}}5.4廣義表廣義表也是線性表的一種推廣。廣義表也是n個數據元素（d1，d2，d3，…，dn）的有限序列，但不同的是，廣義表中的di既可以是單個元素，還可以是一個廣義表，通常記作：GL=（d1，d2，d3，…，dn）。GL是廣義表的名字，通常用大寫字母表示。n是廣義表的長度。若

di是一個廣義表，則稱di是廣義表GL的子表。在GL中，d1是GL的表頭，其余部分組成的表（d2，d3，…，dn）稱為GL的表尾。由此可見，廣義表的定義是遞歸定義的。