數(shù)據(jù)結(jié)構(gòu)經(jīng)典課件

1、第5章 數(shù)組和廣義表1教學(xué)目的：掌握數(shù)組和廣義表的定義、特點及典型算法。2教學(xué)要求： 掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法。 掌握矩陣實現(xiàn)壓縮存儲時的下標變換。 理解稀疏矩陣的兩種存儲方式的特點和適用范圍，領(lǐng)會以三元組表示稀疏矩陣時進行運算采用的處理方法。 掌握廣義表的定義及其存儲結(jié)構(gòu)，學(xué)會將廣義表分解為表頭，表尾的方法。3教學(xué)重點： 掌握特殊矩陣的壓縮存儲。 掌握稀疏矩陣采用三元組存儲時典型算法的實現(xiàn)。 廣義表的定義、運算。4教學(xué)難點：數(shù)組的十字鏈表存儲結(jié)構(gòu)。圖5.1 Amn的二維數(shù)組5.1 數(shù)組5.1.1 數(shù)組的邏輯結(jié)構(gòu) 是線性表的推廣 數(shù)組特點：元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，

2、但屬于同一數(shù)據(jù)類型。 比如：一維數(shù)組可以看作一個線性表，二維數(shù)組可以看作“數(shù)據(jù)元素是一維數(shù)組”的一維數(shù)組，依此類推。圖5.1是一個m行n列的二維數(shù)組。圖5.2 矩陣Amn看成n個列向量的線性表 圖5.3 矩陣Amn看成m個行向量的線性表 推廣： n維數(shù)組每個數(shù)據(jù)元素受n個關(guān)系的約束，任一單個關(guān)系，仍是線性關(guān)系。通過以上分析可總結(jié)出數(shù)組具有以下性質(zhì)： 數(shù)組中數(shù)據(jù)元素數(shù)目固定。 數(shù)組中數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。 數(shù)組中每一個數(shù)據(jù)元素由唯一的一組下標來標識。 數(shù)組是隨機存取的存儲結(jié)構(gòu)。 在數(shù)組上不能做插入、刪除數(shù)據(jù)元素的操作。 通常在各種高級語言中數(shù)組一旦被定義，每一維的大小及上下界都不能改變。兩

3、種操作： 取值操作：給定一組下標，讀其對應(yīng)的數(shù)據(jù)元素。 賦值操作：給定一組下標，存儲或修改其相對應(yīng)的數(shù)據(jù)元素。 二維數(shù)組形式化表示為： 數(shù)組的順序存儲結(jié)構(gòu)有兩種： 2Array（D,R） D=aij | i =c1,c1+1,d1, j=c2,c2+1,d2, aijD0 R=Row,Col Row| c1 i d1 ,c2 j d2-1, aij, ai(j+1) D0 Col | c1 i d1-1 ,c2 j d2, aij, a(i+1)j D0 5.1.2 數(shù)組的存儲結(jié)構(gòu) 數(shù)組的順序存儲結(jié)構(gòu)有兩種： 1. 按行序存儲。如：BASIC、 COBOL和PASCAL語言。 2. 按列序存儲

4、。如：FORTRAN語言。 二維數(shù)組Amn以行為主的存儲序列為： a11, a12, ，a1n, a21, a22, , a2n, , am1, am2, , amn 而以列為主的存儲序列為： a11, a21, ，am1，a12, a22, , am2, , a1n, a2n, , amn設(shè)有二維數(shù)組Amn，按元素的下標求其地址的計算：以“以行為主序”的分配為例：設(shè)數(shù)組的基址為LOC(a11)，每個數(shù)組元素占據(jù)l個地址單元，那么aij的物理地址計算為： LOC(aij)=LOC(a11)+(i-1)*n+j-1)*l 在C語言中，數(shù)組中每一維的下界定義為0，則： LOC(aij)=LOC(a

5、00)+(i*n+j)*l 推廣到一般二維數(shù)組：Ac1.d1c2.d2，aij地址計算函數(shù)為： LOC(aij)=LOC(a c1 c2)+(i-c1)*(d2-c2+1)+(j-c2)*l 同理對于三維數(shù)組Amnp，即mnp數(shù)組，aijk其物理地址為： LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+k-1)*l 推廣到一般的三維數(shù)組：Ac1.d1c2.d2c3.d3，則aijk物理地址為： LOC(i,j,k)=LOC(a c1 c2 c3)+(i-c1)*(d2 -c2+1)*(d3-c3+1) +(j-c2) *(d3-c3+1)+(k-c3)*l 容易看出

6、，數(shù)組元素的存儲位置是其下標的線性函數(shù)，一旦數(shù)組下標的界偶確定之后，數(shù)組中的元素可隨機存取。我們稱具有這一特點的存儲結(jié)構(gòu)為隨機存儲結(jié)構(gòu)。 對于維數(shù)組A(c1.d1, c2.d2，, cn.dn)，元素aj1j2jn的存儲地址的計算公式: 例5.1 若矩陣Amn 中存在某個元素aij滿足：aij是第i行中最小值且是第j列中的最大值，則稱該元素為矩陣A的一個鞍點。試編寫一個算法，找出A中的所有鞍點。 基本思想：在矩陣A中求出每一行的最小值元素，然后判斷該元素是不是它所在列中的最大值，是則打印輸出，接著處理下一行。矩陣A用一個二維數(shù)組表示。void saddle(int A,int m, int n

7、) int i, j, min; for (i=0; im; i+) /*按行處理*/ min=Ai0; for (j=1; jn; j+) if(Aijmin ) min=Aij; /*找第i行最小值*/ for(j=0; jn; j+) /*檢測該行中的每一個最小值是不是鞍點*/ if(Aij=min ) k=j; p=0; while(pm&Apj=m) printf(%d, %d, %dn, i , k, min); /* if */ /*for i*/ 算法的時間性能為O(m*(n+m*n)。5.2 特殊矩陣的壓縮存儲特殊矩陣：1.非零元素非常少； 2.矩陣元素的分布有一定規(guī)律所謂壓

8、縮存儲是指：為多個值相同的元素只分配一個存儲空間，值為零的元素不分配空間。5.2.1 對稱矩陣 特點：在一個n階方陣中，有aij=aji ，其中1i,jn，如圖5.3所示是一個5階對稱矩陣。 對于元素aij，特點是：ij且1in，下標k與i、j的關(guān)系為： k=i*(i-1)/2+j-1 (kn*(n+1)/2 ) 若ij，則aij是上三角中的元素，因為aij=aji，這樣，訪問上三角中的元素aij時則去訪問和它對應(yīng)的下三角中的aji即可，因此將上式中的行列下標交換就是上三角中的元素在SA中的對應(yīng)關(guān)系： k=j*(j-1)/2+i-1 (kj)在一維數(shù)組A中的位置為： Loci, j=Loc1,

9、 1+前i-1行非零元個數(shù)+第i行中aij前非零元個數(shù) 即：Loci, j=Loc1, 1+i(i-1)/2+j-1設(shè)存入向量：SAn*(n+1)/2+1中，SA k與aij的對應(yīng)關(guān)系為：k=i*(i-1)/2+j-1 當ijn*(n+1)/2 當ij（2）上三角矩陣，也可以將其壓縮存儲到一個大小為n(n+1)/2的一維數(shù)組C中。其中元素aij(ij圖5.8 帶狀矩陣A 三對角帶狀矩陣有如下特點： i=1, j=1, 2; 1in, j=i-1, i, i+1; i=n, j=n-1, n;時，aij非零，其它元素均為零。 當5.2.3 帶狀矩陣 1.確定存儲該矩陣所需的一維向量空間的大小 假

10、設(shè)每個非零元素所占空間的大小為1個單元。 所需一維向量空間的大小為2+2+3（n-2）=3n-2，如圖5.9所示。 圖5.9 帶狀矩陣的壓縮形式 2.確定非零元素在一維數(shù)組空間中的位置 Loci,j = Loc1,1+前i-1行非零元個數(shù)+第i行中aij前非零元個數(shù)； 前i-1行元素個數(shù)=3(i-1)-1（因為第1行只有2個非零元素）； 第i行中aij前非零元素個數(shù)=j-i+1，其中 -1 (ji) j-i=由此得到 Loci, j=Loc1, 1+3(i-1)-1+j-i+1 =Loc1, 1+2(i-1)+j-1 5.3 稀疏矩陣的壓縮存儲 設(shè)mn矩陣中有t個非零元素且tmn，這樣的矩陣稱

11、為稀疏矩陣。5.3.1 稀疏矩陣 非零元個數(shù)遠遠小于零元個數(shù)。圖5.10 稀疏矩陣 三元組表的類型說明如下：define SMAX 1024 typedef struct int i, j; datatype v; SPNode; typedef struct int mu, nu, tu; SPNode dataSMAX; SPMatrix; 1) 用三元組表實現(xiàn)稀疏矩陣的轉(zhuǎn)置運算如圖所示的67矩陣M，它的轉(zhuǎn)置矩陣就是76的矩陣N，并且N（row，col）=M（col， row），其中，1row7 ，1col6。 采用矩陣的正常存儲方式時， 實現(xiàn)矩陣轉(zhuǎn)置的經(jīng)典算法如下：void TransM

12、atrix（ datatype sourcenm, datatype destmn） int i, j; for(i=0; im; i+) for (j=0; jmu= A.nu ; B-nu= A.mu ; B-tu= A.tu ; if (B-tu0) j=1; for(k=1; k=A.nu; k+) for(i=1; idataj.row=A.datai.col B-dataj.col=A.datai.row; B-dataj.e=A.datai.e; j+; 【算法5.1 基于稀疏矩陣的三元組表示矩陣的轉(zhuǎn)置算法】 時間復(fù)雜度為O（A.nA.len）, 最壞情況當A.len=A.mA.

13、n時，時間復(fù)雜度為O（A.mA.n2）。采用正常方式實現(xiàn)矩陣轉(zhuǎn)置的算法時間復(fù)雜度為O（A.mA.n）。 方法二： 依次按三元組表A的次序進行轉(zhuǎn)置，轉(zhuǎn)置后直接放到三元組表B的正確位置上。這種轉(zhuǎn)置算法稱為快速轉(zhuǎn)置算法。 為了能將待轉(zhuǎn)置三元組表A中元素一次定位到三元組表B的正確位置上，需要預(yù)先計算以下數(shù)據(jù)： (1) 待轉(zhuǎn)置矩陣每一列中非零元素的個數(shù)。 (2) 待轉(zhuǎn)置矩陣每一列中第一個非零元素在三元組表B中的正確位置。 為此， 需要設(shè)兩個數(shù)組 numcol用來存放A中第col列非零元素個數(shù) positioncol用來存放A中第col列中第一個非零元素在三元組表B中的正確位置。 其中：（1）numcol

14、的計算方法： 將三元組表A掃描一遍，對于其中列號為k的元素，給相應(yīng)的numk加1。 （2）positioncol的計算方法： position1=1， positioncol=position col-1+numcol-1，其中2colA.nu。 具體算法如下： FastTransposeTSMatrix (TSMatrix *A) /*基于矩陣的三元組表示， 采用快速轉(zhuǎn)置法， 將矩陣A轉(zhuǎn)置為B所指的矩陣*/ int col, t, p， q; int numMAXSIZE, positionMAXSIZE; B-tu=A-tu; B-nu=A-mu; B-mu=A-nu; if (B-tu)

15、 for (col=1; colnu; col+) numcol=0; for(t=1; ttu; t+) numA-datat.col+; /*計算每一列的非零元素的個數(shù)*/ position1=1; for(col=2; colnu; col+) /*求col列第一個非零元素在B.data的位置 */ positioncol=positioncol-1+numcol-1; for(p=1; pdataq.row=A.datap.col; B-dataq.col=A.datap.row; B-dataq.e=A.datap.e positioncol+; 【算法5.2 快速稀疏矩陣轉(zhuǎn)置算法】

16、 快速轉(zhuǎn)置算法時間耗費在四個并列的單循環(huán)上，這四個并列的單循環(huán)分別執(zhí)行了A.nu，A.tu，A.nu，A.tu次，因而總的時間復(fù)雜度為O(A.nu)+O(A.tu)+O(A.nu)+O(A.tu)。 當待轉(zhuǎn)置矩陣M中非零元素個數(shù)接近于A.muA.nu 時，其時間復(fù)雜度接近于經(jīng)典算法的時間復(fù)雜度O(A.muA.nu)。 空間耗費上除了三元組表所占用的空間外，還需要兩個輔助向量空間，即num1.A-nu，position1.A-nu?？梢?，算法在時間上的節(jié)省，是以更多的存儲空間為代價的。 2) 用三元組表實現(xiàn)稀疏矩陣的乘法運算 兩個矩陣相乘也是矩陣的一種常用的運算。設(shè)矩陣M是m1n1矩陣，N是m2

17、n2矩陣；若可以相乘，則必須滿足矩陣M的列數(shù)n1與矩陣N的行數(shù)m2相等，才能得到結(jié)果矩陣Q=MN（一個m1n2的矩陣）。 數(shù)學(xué)中矩陣Q中的元素的計算方法如下： 其中： 1im1, 1jn2。 圖5.17 Q=MN 圖5.17給出了一個矩陣相乘的例子。當矩陣M、N是稀疏矩陣時，我們可以采用三元組表的表示形式來實現(xiàn)矩陣的相乘。圖5.18 矩陣M、N、Q的三元組表 因為三元組表只對矩陣的非零元素做存儲。所以可以采用固定三元組表a中的元素（i，k，Mik）（1im1，1kn1），在三元組表b中找所有行號為k的對應(yīng)元素（k，j， Nkj）（1km2，1jn2）進行相乘、 累加，從而得到Qij，即以三元組

18、表a中的元素為基準， 依次求出其與三元組表b的有效乘積。 算法中附設(shè)兩個向量num 、first ，其中numrow表示三元組表b中第row行非零元素個數(shù)（1rowm2）， firstrow表示三元組表b中第row行第一個非零元素所在的位置。顯然，firstrow+1-1指向三元組表b中第row行最后一個非零元素的位置。 5.3.2 稀疏矩陣的十字鏈表存儲* 與用二維數(shù)組存儲稀疏矩陣比較，用三元組表表示的稀疏矩陣不僅節(jié)約了空間，而且使得矩陣某些運算的運算時間比經(jīng)典算法還少。 但是在進行矩陣加法、減法和乘法等運算時，有時矩陣中的非零元素的位置和個數(shù)會發(fā)生很大的變化。如A=A+B， 將矩陣B加到矩

19、陣A上，此時若還用三元組表表示法，勢必會為了保持三元組表“以行序為主序”而大量移動元素。 在十字鏈表中，矩陣的每一個非零元素用一個結(jié)點表示， 該結(jié)點除了（row，col，value）以外，還要有以下兩個鏈域： right：用于鏈接同一行中的下一個非零元素； down：用于鏈接同一列中的下一個非零元素。 再附設(shè)一個存放所有行鏈表的頭指針的一維數(shù)組和一個存放所有列鏈表的頭指針的一維數(shù)組。圖5.15(b)給出了稀疏矩陣圖5.15(a)的十字鏈表。十字鏈表的結(jié)構(gòu)類型說明如下： typedef struct OLNode int row, col; /* 非零元素的行和列下標 */ datatype v

20、alue; struct OLNode * right, *down; /* 非零元所在行、列表的后繼鏈域 */ OLNode; *OLink; typedef struct OLink * row-head, *col-head; /* 行、 列鏈表的頭指針向量 */ int m, n, len; /* 稀疏矩陣的行數(shù)、 列數(shù)、 非零元素的個數(shù) */ CrossList; CreateCrossList (CrossList * M) /* 采用十字鏈表存儲結(jié)構(gòu)， 創(chuàng)建稀疏矩陣M */ if(M!=NULL) free(M); scanf(&m, &n, &t); /* 輸入M的行數(shù), 列數(shù)

21、和非零元素的個數(shù) */ 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 *) m

22、alloc(sizeof(OLNode) exit(OVERFLOW); p-row=i; p-col=j; p-value=e; /* 生成結(jié)點 */ if(M-row-headi= =NULL) M-row-headi=p; else /* 尋找行表中的插入位置 */ for(q=M-row-headi; q-right&q-right-colright) p-right=q-right; q-right=p; /* 完成插入 */ if(M-col-headj=NULL) M-col-headj=p; else /*尋找列表中的插入位置*/ for(q=M-col-headj; q-do

23、wn&q-down-rowdown) p-down=q-down; q-down=p; /* 完成插入 */ 【算法5.4 建立稀疏矩陣的十字鏈表】 建十字鏈表的算法的時間復(fù)雜度為O（ts），s=MAX（m，n)。5.4 廣 義 表 * 廣義表的定義 廣義表是n個數(shù)據(jù)元素a1，a2，ai，an的有序序列。 一般記為： ls=（a1，a2，a3， ，an） 廣義表廣泛地應(yīng)用于人工智能等領(lǐng)域的表處理語言LISP語言中。 List(D,R)D=ai| ai Atomset 或 ai Lists R=|ai,ai+1 D 1=i=n-1其中 （1）ai是單個元素或是一個廣義表，稱為ls的原子或子表 （

24、2）長度：n是廣義表的長度。 （3）表頭：a1是廣義表ls的表頭 （4）表尾：其余元素組成的表是表尾。 （5）廣義表示一個遞歸定義的表。下面給出一些廣義表的例子，以加深對廣義表概念的理解。 D=（）空表；其長度為零。 A=(a，(b， c) 表長度為2的廣義表，其中第一個元素是單個數(shù)據(jù)a，第二個元素是一個子表(b，c)。 B=(A， A， D) 長度為3的廣義表， 其前兩個元素為表A， 第三個元素為空表D。 C=(a，C) 長度為2遞歸定義的廣義表，C相當于無窮表(a，(a,(a，()。 下面以廣義表A為例， 說明求表頭、 表尾的操作： head（A）=a 表A的表頭是a。 tail（A）=（

25、b， c） 表A的表尾是（b， c）。 廣義表的表尾一定是一個表。 廣義表的性質(zhì)從上述廣義表的定義和例子可以得到廣義表的重要性質(zhì)： 廣義表是一種多層次的數(shù)據(jù)結(jié)構(gòu)。廣義表的元素可以是單元素，也可以是子表，而子表的元素還可以是子表，。 廣義表可以是遞歸的表。例如表C 就是一個遞歸的表。 廣義表可以為其它表所共享。如廣義表B就共享表A。 在表B中不必列出表A的內(nèi)容，只要通過子表的名稱就可以引用該表。 廣義表基本運算 基本操作，取頭操作（Head）和取尾操作（Tail）。 根據(jù)廣義表的表頭、表尾的定義可知，對于任意一個非空的廣義表，其表頭可能是單元素也可能是廣義表，而表尾必為廣義表。例如：A（）B（e）C（a，（b，c，d）D（A，B，C）E（a，E）F（）那么：head（B）e tail（B）（）head（C）a tail（C）（b，c，d）head（D）A tail（D）（B，C）head（E）a tail（E）（E）head（F）（） tail（F）（）例如：L=(a，(b，(c，d)，e)，f) 如何訪問到d？ 在廣義表上可以定義與線性表類似的一些操作，如建立、插入、刪除、拆開、連接、復(fù)制、遍歷等。Crea