《西北大學(xué)：數(shù)據(jù)結(jié)構(gòu)第5章數(shù)組和廣義表.ppt》由會員分享，可在線閱讀，更多相關(guān)《西北大學(xué)：數(shù)據(jù)結(jié)構(gòu)第5章數(shù)組和廣義表.ppt（44頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,第5章 數(shù)組和廣義表,5.1 數(shù)組的定義和運算 5.2 數(shù)組的順序存儲和實現(xiàn) 5.3 特殊矩陣的壓縮存儲 5.3.1 三角矩陣 5.3.2 帶狀矩陣 5.3.3 稀疏矩陣 5.4 廣義表,返回主目錄,5.1 數(shù)組的定義和運算,數(shù)組是一種數(shù)據(jù)類型。從邏輯結(jié)構(gòu)上看，數(shù)組可以看成是一般線性表的擴(kuò)充。二維數(shù)組可以看成是線性表的線性表。例如：,返回主目錄,我們可以把二維數(shù)組看成一個線性表： A=( 1 2 j n)，其中j（1j n）本身也是一個線性表，稱為列向量。,矩陣Amn看成n個列向量的線性表,即j=(a1j,a2j, ,amj),返回主目錄,我們還可以將數(shù)組Amn看成另外一個線性表: B=(1

2、，,2,， ，m)，其中i（1i m）本身也是一個線性表，稱為行向量，即： I= （ai1，ai2， ，aij ，ain）。,返回主目錄,上面二維數(shù)組的例子，介紹了數(shù)組的結(jié)構(gòu)特性，實際上數(shù)組是一組有固定個數(shù)的元素的集合。由于這個性質(zhì)，使得對數(shù)組的操作不象對線性表的操作那樣，可以在表中任意一個合法的位置插入或刪除一個元素。,對于數(shù)組的操作一般只有兩類： （1）獲得特定位置的元素值； （2）修改特定位置的元素值。,返回主目錄,數(shù)組的抽象數(shù)據(jù)類型定義（ADT Array）,數(shù)據(jù)對象：D= aj1j2jn| n0，稱為數(shù)組的維數(shù)，ji是數(shù)組的第i維下標(biāo)，1jibi，bi為數(shù)組第i維的長度， aj1j2

3、jn ElementSet,數(shù)據(jù)關(guān)系：R=R1,R2,Rn Ri= | 1jkbk，1kn 且ki，1jibi-1， aj1 jijn ，aj1 ji+1jn D，i=1，n,返回主目錄,基本操作：,（1）InitArray(A,n,bound1,boundn)： 若維數(shù)n和各維的長度合法，則構(gòu)造相應(yīng)的數(shù)組A，并返回TRUE；,（2）DestroyArray（A）： 銷毀數(shù)組A；,（3）GetValue（A，e, index1, ,indexn）： 若下標(biāo)合法，用e返回數(shù)組A中由index1, ,indexn所指定的元素的值。,（4）SetValue（A，e，index1, ,indexn）：

4、 若下標(biāo)合法，則將數(shù)組A中由index1, ,indexn所指定的元素的值置為e。,注意：這里定義的數(shù)組下標(biāo)是從1開始，與C語言的數(shù)組略有不同。,返回主目錄,5.2 數(shù)組的順序存儲和實現(xiàn),對于數(shù)組A，一旦給定其維數(shù)n及各維長度bi（1in），則該數(shù)組中元素的個數(shù)是固定的，不可以對數(shù)組做插入和刪除操作，不涉及移動元素操作，因此對于數(shù)組而言，采用順序存儲法比較合適。,數(shù)組的順序存儲結(jié)構(gòu)有兩種：一種是按行序存儲，如高級語言BASIC、COBOL和PASCAL語言都是以行序為主。另一種是按列序存儲，如高級語言中的FORTRAN語言就是以列序為主。,返回主目錄,對于二維數(shù)組Amxn 以行為主的存儲序列為

5、：a11 ,a12, a1n ,a21 ,a22 ,a2n , ,am1 ,am2 , , amn 以列為主存儲序列為：a11, a21, am1 ,a12 ,a22 , ,am2 , ,a1n ,a2n , ,amn,假設(shè)有一個342的三維數(shù)組A ，其邏輯結(jié)構(gòu)圖為：,返回主目錄,以二維數(shù)組Amn為例，假設(shè)每個元素只占一個存儲單元，“以行為主”存放數(shù)組，下標(biāo)從1開始，首元素a11的地址為Loc1,1 求任意元素aij的地址 ，可由如下計算公式得到： Loci,j=Loc1,1+n(i-1)+(j-1),如果每個元素占size個存儲單元 ，則任意元素aij的地址計算公式為： Loci,j=Loc

6、1,1 + (n(i-1)+j-1)size,返回主目錄,三維數(shù)組A（1.r , 1.m , 1.n）可以看成是r個mn的二維數(shù)組 ，如下圖所示：,返回主目錄,假定每個元素占一個存儲單元，采用以行為主序的方法存放 ，首元素a111的地址為Loc1,1,1，ai11的地址為Loci,1,1=Loc1,1,1+(i-1)*m*n ，那么求任意元素aijk的地址計算公式為：,Loci,j,k=Loc1,1,1+(i-1)*m*n+(j-1)*n+(k-1) 其中1i，1j，1k。,返回主目錄,如果將三維數(shù)組推廣到一般情況，即：用j1，j2，j3代替數(shù)組下標(biāo)i，j，k；并且j1，j2，j3的下限為c1

7、，c2，c3，上限分別為d1，d2，d3，每個元素占一個存儲單元。則三維數(shù)組中任意元素a(j1，j2，j3)的地址為： Locj1，j2，j3=Locc1,c2,c3+1*(d2-c2+1)*(d3-c3+1)*(j1-c1) +1*(d3-c3+1)*(j2-c2)+1*(j3-c3) 其中l(wèi)為每個元素所占存儲單元數(shù)。,返回主目錄,令1=1*(d2-c2+1)*(d3-c3+1), 2=1*(d3-c3+1), 3=1，則：,Locj1,j2,j3=Locc1,c2,c3+ 1*(j1-c1)+ 2*(j2-c2)+ 3(j3-c3) =Locc1,c2,c3+ i*(ji-ci) （1i3

8、）,由公式可知Locj1,j2,j3與j1,j2,j3呈線性關(guān)系。,對于維數(shù)組A(c1:d1,c2:d2，,cn,dn)，我們只要把上式推廣，就可以容易地得到維數(shù)組中任意元素aj1j2jn的存儲地址的計算公式。,返回主目錄,5.3 特殊矩陣的壓縮存儲,特殊矩陣壓縮存儲的壓縮原則是：對有規(guī)律的元素和值相同的元素只分配一個存儲單元，對于零元素不分配空間。,5.3.1 三角矩陣,三角矩陣大體分為：下三角矩陣、上三角矩陣和對稱矩陣。對于一個n階矩陣A來說：若當(dāng)ij時，有aij=0，則此矩陣稱為上三角矩陣；若矩陣中的所有元素均滿足aij=aji，則稱此矩陣為對稱矩陣。,返回主目錄,對于下三角矩陣，按“行

9、序為主序”進(jìn)行存儲，得到的序列為：a11,a21,a22,a31,a32,a33an1,an2ann。由于下三角矩陣的元素個數(shù)為n(n+1)/2，所以可壓縮存儲到一個大小為n(n+1)/2的一維數(shù)組中。下三角矩陣中元素aij(ij)，在一維數(shù)組A中的位置為： LOC i ,j= LOC1,1+ i (i -1)/2+ j-1,下三角矩陣：,返回主目錄,同樣，對于上三角矩陣，也可以將其壓縮存儲到一個大小為n(n+1)/2的一維數(shù)組C中。其中元素aij(ij)在數(shù)組C中的存儲位置為： Loci,j= Loc1,1+j(j -1)/2+ i-1,對于對稱矩陣，因其元素滿足aij=aji，我們可以為每

10、一對相等的元素分配一個存儲空間，即只存下三角（或上三角）矩陣，從而將n2個元素壓縮到n(n+1)/2個空間中。,返回主目錄,5.3.2 帶狀矩陣,帶狀矩陣：在矩陣A中，所有的非零元素都集中在以主對角線為中心的帶狀區(qū)域中。最常見的是三對角帶狀矩陣。,特點:,時，aij非零，其他元素均為零。,返回主目錄,三對角帶狀矩陣的壓縮存儲，以行序為主序進(jìn)行存儲，并且只存儲非零元素。其方法為：,1. 確定存儲該矩陣所需的一維向量空間的大小,從三對角帶狀矩陣中可看出：除第一行和最后一行只有兩個元素外，其余各行均有3個非零元素。由此可得到一維向量所需的空間大小為：3n-2。,2. 確定非零元素在一維數(shù)組空間中的位

11、置,LOCi , j = LOC1,1+3（i-1）-1+j-i+1 =LOC1,1+2(i-1)+j-1,返回主目錄,5.3.3 稀疏矩陣,稀疏矩陣：指矩陣中大多數(shù)元素為零的矩陣。一般地，當(dāng)非零元素個數(shù)只占矩陣元素總數(shù)的25%30%,或低于這個百分?jǐn)?shù)時，我們稱這樣的矩陣為稀疏矩陣。,0 0 3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0,返回主目錄,1. 稀疏矩陣的三元組表表示法,對于稀疏矩陣的壓縮存儲要求在存儲非零元素的同時，還必須存儲該非零元素在矩陣中所處的行號和列

12、號。我們將這種存儲方法叫做稀疏矩陣的三元組表示法。,每個非零元素在一維數(shù)組中的表示形式如圖所示：,返回主目錄,三元組表的類型說明：,#define MAXSIZE 1000 /*非零元素的個數(shù)最多為1000*/ typedef struct int row, col; /*該非零元素的行下標(biāo)和列下標(biāo)*/ ElementType e； /*該非零元素的值*/ Triple; typedef struct Triple dataMAXSIZE+1; /* 非零元素的三元組表 。data0未用*/ int m, n, len; /*矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)*/ TSMatrix；,返回主目錄

13、,1）用三元組表實現(xiàn)稀疏矩陣的轉(zhuǎn)置運算,矩陣轉(zhuǎn)置：指變換元素的位置，把位于（row，col）位置上的元素?fù)Q到（col ，row）位置上，也就是說，把元素的行列互換。,采用矩陣的正常存儲方式時，實現(xiàn)矩陣轉(zhuǎn)置的經(jīng)典算法如下：,Void TransMatrix（ElementType sourcenm, ElementType destmn） /*Source和dest分別為被轉(zhuǎn)置的矩陣和轉(zhuǎn)置后的矩陣（用二維數(shù)組表示）*/ int i, j; for(i=0;im;i+) for (j=0;j n;j+) desti j=sourcej i ; ,返回主目錄,實現(xiàn)轉(zhuǎn)置的簡單方法：,矩陣source的

14、三元組表A的行、列互換就可以得到B中的元素，如圖 ：,為了保證轉(zhuǎn)置后的矩陣的三元組表B也是以“行序為主序”進(jìn)行存放，則需要對行、列互換后的三元組B，按B的行下標(biāo)（即A的列下標(biāo)）大小重新排序。,兩種處理轉(zhuǎn)置算法如下：,返回主目錄,算法一、,void TransposeTSMatrix(TSMatrix A, TSMatrix * B) /*把矩陣A轉(zhuǎn)置到B所指向的矩陣中去。矩陣用三元組表表示*/ int i , j, k ; B-m= A.n ; B-n= A.m ; B-len= A.len ; if(B-len0) j=1; for(k=1; kdataj.row=A.datai.col B

15、-dataj.col=A.datai.row; B-dataj.e=A.datai.e; j+; ,返回主目錄,算法二、,FastTransposeTSMatrix (TSMatrix A, TSMatrix * B) /*基于矩陣的三元組表示，采用快速轉(zhuǎn)置法，將矩陣A轉(zhuǎn)置為B所指的矩陣*/ int col , t , p，q; int numMAXSIZE, positionMAXSIZE ; B-len= A.len ; B-n= A.m ; B-m= A.n ; if(B-len) for(col=1;coldataq.row=A.datap.col; B-dataq.col=A.dat

16、ap.row; B-dataq.e=A.datap.e positioncol+; ,返回主目錄,用三元組表實現(xiàn)稀疏矩陣的乘法運算,設(shè)矩陣M是m1n1矩陣，N是m2n2矩陣；若可以相乘，則必須滿足矩陣M的列數(shù)n1與矩陣N的行數(shù)m2相等，才能得到結(jié)果矩陣Q=MN（一個m1n2的矩陣）。,數(shù)學(xué)中矩陣Q中的元素的計算方法如下：,其中：1im1，1jn2,返回主目錄,根據(jù)數(shù)學(xué)上矩陣相乘的原理，我們可以得到矩陣相乘的經(jīng)典算法：,for(i=1;i=m1;i+) for(j=1;j=n2;j+) Qij=0; for(k=1;k=n1;k+) Qij= Qij+Mik*Nkj; ,返回主目錄,經(jīng)典算法中，

17、不論Mik，Nkj是否為零，都要進(jìn)行一次乘法運算，而實際上，這是沒有不必要的。采用三元組表的方法來實現(xiàn)時，因為三元組只對矩陣的非零元素做存儲，所以可以采用固定三元組a中元素（i，k，Mik）（1im1，1kn1），在三元組b中找所有行號為k的的對應(yīng)元素（k，j，Nkj）（1km2，1jn2）進(jìn)行相乘、累加從而得到Qij。即：以三元組a中的元素為基準(zhǔn)，依次求出其與三元組b的有效乘積。,相乘基本操作：對于三元組a中每個元素a.datap（p=1，2，3，a.len），找出三元組b中所有滿足條件a.datap.col=b.dataq.row的元素b.dataq，求得a.datap.e與b.dataq

18、.e的乘積，而這個乘積只是Qi，j的一部分，應(yīng)對每個元素設(shè)一個累計和變量，其初值為0。掃描完三元組a，求得相應(yīng)元素的乘積并累加到適當(dāng)?shù)睦塾嫼偷淖兞可稀?返回主目錄,注意：兩個稀疏矩陣相乘的結(jié)果不一定是稀疏矩陣。反之，相乘的每個分量Mi，kNk，j不為零，但累加的結(jié)果Qi，j可能是零。 例如：,返回主目錄,#define MAXSIZE 1000 /*非零元素的個數(shù)最多為1000*/ #define MAXROW 1000 /*矩陣最大行數(shù)為1000*/ typedef struct int row, col; /*該非零元素的行下標(biāo)和列下標(biāo)*/ ElementType e； /*該非零元素的值

19、*/ Triple; typedef struct Triple dataMAXSIZE+1; /* 非零元素的三元組表，data0未用*/ int firstMAXROW+1; /*三元組表中各行第一個非零元素所在的位置。*/ int m, n, len; /*矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)*/ TriSparMatrix；,為方便實現(xiàn)，將三元組表的類型說明修改如下：,返回主目錄,具體算法如下：,int MulSMatrix(TriSparMatrix M, TriSparMatrix N, TriSparMatrix *Q) /*采用改進(jìn)的三元組表表示法，求矩陣乘積QMN*/ int a

20、row , brow , p; int ctempMAXSIZE; if(M.n!=N.m) return FALSE; /*返回FALSE表示求矩陣乘積失敗*/ Q-m=M.m; Q-n=N.n; Q-len=0; if(M.len*N.len!=0) for(arow=1; arowfirstarow=Q-len+1; for(p=M.firstarow;pM.firstarow+1;p+) /*p指向M當(dāng)前行中每一個非零元素*/,返回主目錄,brow=M.datap.col; /* M中的列號應(yīng)與N中的行號相等*/ if(brown；col+) /*壓縮存儲該非零元*/ if(ctemp

21、ccol) if(+Q-lenMAXSIZE) return 0; Q-dataQ-len=arow, ccol, ctempccol; /* if */ /* for arow */ /*if*/ return(TRUE); /*返回TRUE表示求矩陣乘積成功*/ ,返回主目錄,2. 稀疏矩陣的鏈?zhǔn)酱鎯Y(jié)構(gòu)：十字鏈表,優(yōu)點：它能夠靈活地插入因運算而產(chǎn)生的新的非零元素，刪除因運算而產(chǎn)生的新的零元素，實現(xiàn)矩陣的各種運算。,在十字鏈表中，矩陣的每一個非零元素用一個結(jié)點表示，該結(jié)點除了（row，col，value）以外，還要有兩個域：,right： 用于鏈接同一行中的下一個非零元素； down：用以

22、鏈接同一列中的下一個非零元素。,十字鏈表中結(jié)點的結(jié)構(gòu)示意圖：,返回主目錄,十字鏈表的結(jié)構(gòu)類型說明如下：,typedef struct OLNode int row, col; /*非零元素的行和列下標(biāo)*/ ElementType value; struct OLNode * right,*down; /*非零元素所在行表列表的后繼鏈域*/ OLNode; *OLink; typedef struct OLink * row_head, *col_head; /*行、列鏈表的頭指針向量*/ int m, n, len; /*稀疏矩陣的行數(shù)、列數(shù)、非零元素的個數(shù)*/ CrossList;,返回主目

23、錄,建立稀疏矩陣的十字鏈表算法：,CreateCrossList (CrossList * M) /*采用十字鏈表存儲結(jié)構(gòu)，創(chuàng)建稀疏矩陣M*/ if(M!=NULL) free(M); scanf( /*生成結(jié)點*/,返回主目錄,if(M-row_headi=NULL) M-row_headi=p; else /*尋找行表中的插入位置*/ for(q=M-row_headi; q-right /*完成插入*/ ,返回主目錄,5.4 廣義表,廣義表也是線性表的一種推廣。廣義表也是n個數(shù)據(jù)元素（d1，d2，d3，dn）的有限序列，但不同的是，廣義表中的di既可以是單個元素，還可以是一個廣義表，通常

24、記作：GL=（d1，d2，d3，dn）。GL是廣義表的名字，通常用大寫字母表示。n是廣義表的長度。若 di是一個廣義表，則稱di是廣義表GL的子表。 在GL中， d1是GL的表頭，其余部分組成的表（d2，d3，dn）稱為GL的表尾。由此可見，廣義表的定義是遞歸定義的。,返回主目錄,l D=（） 空表；其長度為零。,lA=(a，(b，c)表長度為2的廣義表，其中第一個元素是單個數(shù)據(jù)a，第二個元素是一個子表（b，c）。,lB=（A，A，D）長度為3的廣義表，其前兩個元素為表A，第三個元素為空表D。,lC=（a，C） 長度為2遞歸定義的廣義表，C相當(dāng)于無窮表C=（a，（a，（a，（）。,例如：,he

25、ad(A)=a 表A的表頭是a。 tail(A)=(b，c) 表A的表尾是(b，c) ，廣義表的表尾一定是一個表。,返回主目錄,從上面的例子可以看出：,（1）廣義表的元素可以是子表，而子表還可以是子表，由此，廣義表是一個多層的結(jié)構(gòu)。,（2）廣義表可以被其他廣義表共享。如：廣義表B就共享表A。在表B中不必列出表A的內(nèi)容，只要通過子表的名稱就可以引用該表。,（3）廣義表具有遞歸性，如廣義表C。,返回主目錄,廣義表中有兩類結(jié)點，一類是單個元素結(jié)點，一類是子表結(jié)點。任何一個非空的廣義表都可以將其分解成表頭和表尾兩部分，反之，一對確定的表頭和表尾可以唯一地確定一個廣義表。由此，一個表結(jié)點可由三個域構(gòu)成：

26、標(biāo)志域，指向表頭的指針域，指向表尾的指針域。而元素結(jié)點只需要兩個域：標(biāo)志域和值域。,廣義表A、B、C、D的存儲結(jié)構(gòu)圖,返回主目錄,形式說明如下：,/*廣義表的頭尾鏈表存儲結(jié)構(gòu)*/ 0- 89typedef enum ATOM, LIST ElemTag; /* ATOM0，表示原子；LIST1，表示子表*/ typedef struct GLNode ElemTag tag; /*標(biāo)志位tag用來區(qū)別原子結(jié)點和表結(jié)點*/ union AtomType atom; /*原子結(jié)點的值域atom*/ struct struct GLNode * hp, *tp; htp; /*表結(jié)點的指針域htp，

27、 包括表頭指針域hp和表尾指針域tp*/ atom_htp; /* atom_htp 是原子結(jié)點的值域atom和表結(jié)點的指針域htp的聯(lián)合體域*/ *GList；,返回主目錄,另外，還有一種廣義表存儲結(jié)構(gòu)，在這種結(jié)構(gòu)中，無論是單元素結(jié)點還是子表結(jié)點均由三個域構(gòu)成。 其結(jié)點結(jié)構(gòu)圖為：,廣義表的第二種存儲結(jié)構(gòu)圖,返回主目錄,typedef enum ATOM,LIST ElemTag; /* ATOM0，表示原子；LIST1，表示子表*/ typedef struct GLNode ElemTag tag; union AtomType atom; struct GLNode * hp; atom_hp; /*atom_hp是原子結(jié)點的值域atom和表結(jié)點的表頭指針域hp的聯(lián)合體域*/ struct GLNode * tp; *GList;,第二種存儲結(jié)構(gòu)的形式說明如下：,返回主目錄,