第五部分?jǐn)?shù)組和廣義表教學(xué)ppt課件

1、第五章第五章 數(shù)組和廣義表數(shù)組和廣義表 數(shù)組可以看成是一種特殊的線性表，即線性表中數(shù)據(jù)元素本身也是一個線性表第五章第五章 數(shù)組和廣義表數(shù)組和廣義表5.1 數(shù)組的定義數(shù)組的定義5.3 矩陣的緊縮存儲矩陣的緊縮存儲 5.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)5.4 廣義表的定義廣義表的定義5.5 廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造 5.6 m元多項式的表示元多項式的表示 5.7 廣義表的遞歸算法廣義表的遞歸算法第五章第五章 數(shù)組和廣義表數(shù)組和廣義表5.1 數(shù)組的定義數(shù)組特點數(shù)組特點數(shù)組構(gòu)造固定數(shù)組構(gòu)造固定數(shù)據(jù)元素同構(gòu)數(shù)據(jù)元素同構(gòu)數(shù)組運算數(shù)組運算給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素給定一組下標(biāo)，存取

2、相應(yīng)的數(shù)據(jù)元素給定一組下標(biāo)，修正數(shù)據(jù)元素的值給定一組下標(biāo)，修正數(shù)據(jù)元素的值( )( )( )( )( )aj = (a0j,a1j, , am-1j)( )( )( )( )ai = (ai0,ai1, , ain-1)數(shù)組的定義=m* nAm-1n-1m-1n-2n-1aaaaaa.1111001a00a10am-10籠統(tǒng)數(shù)據(jù)類型數(shù)組的定義如下：籠統(tǒng)數(shù)據(jù)類型數(shù)組的定義如下：ADT List ADT List 數(shù)據(jù)對象：數(shù)據(jù)對象：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：D D a | n(n0) a | n(n0)稱為數(shù)組的維數(shù)，稱為數(shù)組的維數(shù)，bibi是是 數(shù)組第數(shù)組第i i維的長度，維的長度，jiji是數(shù)組元

3、素的第是數(shù)組元素的第i i維維 下標(biāo)下標(biāo)a ElemSet a ElemSet ji =0,.,bi -1, ji =0,.,bi -1, i=1,2,.,n i=1,2,.,n j1j2jnj1j2jnR1R1 | | 0 0 jk jk bk -1, 1 bk -1, 1 k k n n 且且k k i, i, 0 0 ji ji bi -2, i=2,.,n, 0 bi -2, i=2,.,n, 0 ji ji bi -2, bi -2,j1 jijnj1 ji+1jn數(shù)組的定義數(shù)組的定義二維數(shù)組的定義二維數(shù)組的定義:數(shù)據(jù)對象數(shù)據(jù)對象: : D = aij | 0ib1-1, 0 jb2

4、-1 D = aij | 0ib1-1, 0 jb2-1數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系: : R = ROW, COL R = ROW, COL ROW = | 0ib1-2, ROW = | 0ib1-2, 0jb2-10jb2-1 COL = | 0ib1-1, 0 COL = | 0ib1-1, 0 jb2-2jb2-2InitArray(&A, n, bound1, ., boundn)DestroyArray(&A)Value(A, &e, index1, ., indexn)Assign(&A, e, index1, ., indexn)根本操作：根本操作：數(shù)組的

5、定義=m* nAm-1n-1m-1n-2n-1aaaaaa.1111001a00a10am-10數(shù)組的定義有兩種順序映象的方式有兩種順序映象的方式:以行序為主序以行序為主序(低下標(biāo)優(yōu)先低下標(biāo)優(yōu)先)以列序為主序以列序為主序(高下標(biāo)優(yōu)先高下標(biāo)優(yōu)先)數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)Loc( aij)=Loc(a00)+i*n+j*l 按行序為主序存放按行序為主序存放 am-10am-11 . am-1n-1 a00 a01 . a0n-1 a10 a11 . a0n-1 .n-1 am-1n-1 . am-10 am-10 . a1n-1 . a11 a10 a0n-1 . a01 a000

6、1m*n-1n數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn) 按列序為主序存放按列序為主序存放01m-1m*n-1m am-1n-1 . a1n-1 a0n-1 . am-11 . a11 a01 am-10 . a10 a00 a00 a01 . a0n-1 a10 a11 . a1n-1 am-10am-11 am-1n-1 .Loc(aij)=Loc(a00)+j*m+i*l 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)4.3 矩陣的緊縮存儲特殊矩陣特殊矩陣 所謂特殊矩陣是指非零元素或零元素的所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊分布有一定規(guī)律的矩陣，下面我們

7、討論幾種特殊矩陣的緊縮存儲。矩陣的緊縮存儲。1 1、對稱矩陣、對稱矩陣 在一個在一個n n階方陣階方陣A A中，假設(shè)元素滿足下中，假設(shè)元素滿足下述性質(zhì)：述性質(zhì)： aij=aji 0 aij=aji 0i,ji,jn-1n-1那么稱那么稱A A為對稱矩陣。為對稱矩陣。矩陣的緊縮存儲 a00 a01 . . a0n-1 a10 a11 . . a1n-1 an-10 an-11 . an-1n-1 . 元素總數(shù)為元素總數(shù)為: : n(n+1)/2n(n+1)/2將這些元素存放在一個向量將這些元素存放在一個向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中中矩陣的緊縮存儲aijaij和和

8、saksak之間對應(yīng)關(guān)系之間對應(yīng)關(guān)系 ij 那么那么ai j在下三角形中。在下三角形中。 ai j之前的之前的i行行從第從第0行到第行到第i-1行一共有行一共有1+2+i=i(i+1)/2個元素，在第個元素，在第i行上，行上， ai j之之前恰有前恰有j個元素即個元素即ai0,ai1,ai2,aij-1，因此，因此有：有： k=i*(i+1)/2+j 0kn(n+1)/2a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序為主序：按行序為主序：矩陣的緊縮存儲a11 a21 a22 a31 a32 an1 ann .k=

9、0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序為主序：按行序為主序：ij 那么那么aij是在上三角矩陣中。由于是在上三角矩陣中。由于aij=aji，所以只需交換上述對應(yīng)關(guān)系式中的所以只需交換上述對應(yīng)關(guān)系式中的i和和j即可得即可得到：到： k=j*(j+1)/2+i 0 k(k-1)/2 (k-1)/2 ，那么元素，那么元素 aij=0 aij=0。 對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其緊縮存儲到一個向量中，并且也能找到每個將其緊縮存儲到一個向量中，并且也能找到每個非零元素和向量下標(biāo)的對應(yīng)關(guān)系。非零元素和向量下標(biāo)的對應(yīng)關(guān)系。Loc(

10、aij)=Loc(a11)+2(i-1)+(j-1) a11 a12 a21 a22 a23 ann-1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序為主序：矩陣的緊縮存儲假設(shè) m 行 n 列的矩陣含 t 個非零元素，那么稱 為稀疏因子。通常以為 0.05 的矩陣為稀疏矩陣。nmt稀疏矩陣稀疏矩陣7600070015000001800000240001400003000000000009120M矩陣的緊縮存儲7600070015000001800000240001400003000000000009120MM由(1,2,12), (1,3,9), (3,1,

11、-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩陣維數(shù)6,7獨一確定定義：非零元較零元少，且分布沒有一定規(guī)律的矩陣定義：非零元較零元少，且分布沒有一定規(guī)律的矩陣緊縮存儲原那么：只存矩陣的行列維數(shù)和每個非零元的緊縮存儲原那么：只存矩陣的行列維數(shù)和每個非零元的行列下標(biāo)及其值行列下標(biāo)及其值矩陣的緊縮存儲稀疏矩陣的緊縮存儲方法稀疏矩陣的緊縮存儲方法:一、三元組順序表一、三元組順序表二、行邏輯聯(lián)接的順序表二、行邏輯聯(lián)接的順序表三、三、 十字鏈表十字鏈表矩陣的緊縮存儲三元組表所需存儲單元個數(shù)為三元組表所需存儲單元個數(shù)為3(t+1)其中其中t為

12、非零元個數(shù)為非零元個數(shù)6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 mai j v0 1 2 3 4 5 6 7 8ma0.i,ma0.j,ma0.v分別存放分別存放矩陣行列維數(shù)和非零元個數(shù)矩陣行列維數(shù)和非零元個數(shù)行列下標(biāo)行列下標(biāo)非零元值非零元值7600070015000001800000240001400003000000000009120M三元組順序表三元組順序表矩陣的緊縮存儲 #define MAXSIZE 12500 typedef struct int i, j; /該非零元的行下標(biāo)和列下標(biāo)該非零元的行下標(biāo)和

13、列下標(biāo) ElemType e; / 該非零元的值該非零元的值 Triple; / 三元組類型三元組類型typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩陣類型稀疏矩陣類型矩陣的緊縮存儲 求轉(zhuǎn)置矩陣求轉(zhuǎn)置矩陣 問題描畫：知一個稀疏矩陣的三元組表，問題描畫：知一個稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表求該矩陣轉(zhuǎn)置矩陣的三元組表 問題分析問題分析 普通矩陣轉(zhuǎn)置算法：普通矩陣轉(zhuǎn)置算法：for(col=0;coln;col+) for(row=0;rowm;row+) ncolrow=mrowcol;T(n)

14、=O(mn)矩陣的緊縮存儲 其時間復(fù)雜度為其時間復(fù)雜度為: O(munu)7600070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300N6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 0 1 2 3 4 5

15、6 7 8mb?矩陣的緊縮存儲處理思緒：只需做到處理思緒：只需做到 將矩陣行、列維數(shù)互換將矩陣行、列維數(shù)互換 將每個三元組中的將每個三元組中的i i和和j j互相互換互相互換 重排三元組次序，使重排三元組次序，使mbmb中元素以中元素以N N的行的行(M(M的的列列) )為主序為主序方法一：按方法一：按M的列序轉(zhuǎn)置的列序轉(zhuǎn)置 即按即按mb中三元組次序依次在中三元組次序依次在ma中找到相中找到相應(yīng)的三元組進(jìn)展轉(zhuǎn)置。應(yīng)的三元組進(jìn)展轉(zhuǎn)置。 為找到為找到M中每一列一切非零元素，需對其中每一列一切非零元素，需對其三元組表三元組表ma從第一行起掃描一遍。由于從第一行起掃描一遍。由于ma中中以以M行序為主序

16、行序為主序,所以由此得到的恰是所以由此得到的恰是mb中應(yīng)中應(yīng)有的順序有的順序矩陣的緊縮存儲)()(2nmOnT算法分析：T(n)=O(M的列數(shù)n非零元個數(shù)t) 假設(shè) t 與mn同數(shù)量級，那么矩陣的緊縮存儲6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8ma7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j v0 1 2 3 4 5 6 7 8mbkppppppppkkkkppppppppcol=1co

17、l=2矩陣的緊縮存儲方法二：快速轉(zhuǎn)置方法二：快速轉(zhuǎn)置 即按即按mama中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入b b中中恰當(dāng)位置恰當(dāng)位置 此法關(guān)鍵是要預(yù)先確定此法關(guān)鍵是要預(yù)先確定M M中每一列第一個非零中每一列第一個非零元在元在mbmb中位置，為確定這些位置，轉(zhuǎn)置前應(yīng)先求得中位置，為確定這些位置，轉(zhuǎn)置前應(yīng)先求得M M的每一列中非零元個數(shù)的每一列中非零元個數(shù) 實現(xiàn)：設(shè)兩個數(shù)組實現(xiàn)：設(shè)兩個數(shù)組numcolnumcol：表示矩陣：表示矩陣M M中第中第colcol列中非零元個數(shù)列中非零元個數(shù)cpotcolcpotcol：指示：指示M M中第中第colcol列第一個非零元在列第一個

18、非零元在mbmb中位置中位置顯然有：顯然有：cpot1=1;cpotcol=cpotcol-1+numcol-1; (2col a.nu)矩陣的緊縮存儲1357889colnumcolcpotcol122232415061707600070015000001800000240001400003000000000009120MStatus FastTransposeSMatrix(TSMatrix M, TSMatrix &T) / FastTransposeSMatrix矩陣的緊縮存儲T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) /

19、if return OK;for (col=1; col=M.nu; +col) numcol = 0;for (t=1; t=M.tu; +t) +numM.datat.j;cpot1 = 1;for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1;for (p=1; p=M.tu; +p) 分析算法FastTransposeSMatrix的時間復(fù)雜度：時間復(fù)雜度為時間復(fù)雜度為: O(M.nu+M.tu): O(M.nu+M.tu)for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t)

20、for (col=2; col=M.nu; +col) for (p=1; p=M.tu; +p) 矩陣的緊縮存儲6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v0 1 2 3 4 5 6 7 8mbcolnumcolcpotcol1122323524715806817907 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 pppppppp4629753矩陣的緊縮存儲 三元組順序表又稱有序的雙下

21、標(biāo)法，它的特點是，三元組順序表又稱有序的雙下標(biāo)法，它的特點是，非零元在表中按行序有序存儲，因此便于進(jìn)展依行順非零元在表中按行序有序存儲，因此便于進(jìn)展依行順序處置的矩陣運算。然而，假設(shè)需隨機(jī)存取某一行中序處置的矩陣運算。然而，假設(shè)需隨機(jī)存取某一行中的非零元，那么需從頭開場進(jìn)展查找。的非零元，那么需從頭開場進(jìn)展查找。行邏輯聯(lián)接的順序行邏輯聯(lián)接的順序表表鏈?zhǔn)酱鎯?gòu)造鏈?zhǔn)酱鎯?gòu)造帶行指針向量的單鏈表表示帶行指針向量的單鏈表表示每行的非零元用一個單鏈表存放每行的非零元用一個單鏈表存放 設(shè)置一個行指針數(shù)組，指向本行第一個非設(shè)置一個行指針數(shù)組，指向本行第一個非零元結(jié)點；假設(shè)本行無非零元，那么指針零元結(jié)點；假

22、設(shè)本行無非零元，那么指針為空為空表頭結(jié)點與單鏈表結(jié)點類型定義表頭結(jié)點與單鏈表結(jié)點類型定義矩陣的緊縮存儲 #define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; int mu, nu, tu; RLSMatrix; / 行邏輯鏈接順序表類型行邏輯鏈接順序表類型0200000000000210010070003A1 35 73 -11 -12 -24 2需存儲單元個數(shù)為3t+m矩陣的緊縮存儲例如：給定一組下標(biāo)，求矩陣的元素值例如：給定一組下標(biāo)，求矩陣的元素值ElemType value(RLSMatri

23、x M, int r, int c) p = M.rposr; while (M.datap.i=r &M.datap.j c) p+; if (M.datap.i=r & M.datap.j=c) return M.datap.e; else return 0; / value矩陣的緊縮存儲矩陣乘法的精典算法矩陣乘法的精典算法: for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 其時間復(fù)雜度為其時間復(fù)雜度為: O(m1n2n1)矩陣的緊縮存儲 Q Q初始

24、化；初始化； if Qif Q是非零矩陣是非零矩陣 / / 逐行求積逐行求積 for (arow=1; arow=M.mu; +arow) for (arow=1; arow=M.mu; +arow) / / 處置處置M M的每一行的每一行 ctemp = 0; / ctemp = 0; / 累加器清零累加器清零 計算計算Q Q中第中第arowarow行的積并存入行的積并存入ctemp ctemp 中；中； 將將ctemp ctemp 中非零元緊縮存儲到中非零元緊縮存儲到Q.dataQ.data； / for arow / for arow / if / if 兩個稀疏矩陣相乘兩個稀疏矩陣相乘

25、QMN 的過程可大致描畫如下：的過程可大致描畫如下：矩陣的緊縮存儲 Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix &Q) / MultSMatrix矩陣的緊縮存儲if (M.nu != N.mu) return ERROR; Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; if (M.tu*N.tu != 0) / Q是非零矩陣是非零矩陣 for (arow=1; arow=M.mu; +arow) / 處置處置M的每一行的每一行 / for arow / if return OK; ctemp

26、= 0; / 當(dāng)前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; pM.rposarow+1;+p) /對當(dāng)前行中每一個非零元 / 求得Q中第crow( =arow)行的非零元 處置 的每一行M矩陣的緊縮存儲brow=M.datap.j; if (brow N.nu ) t = N.rposbrow+1; else t = N.tu+1 for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘積元素在Q中列號 ctempccol += M.datap.e * N.dataq.e; / for qfor

27、 (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if矩陣的緊縮存儲分析上述算法的時間復(fù)雜度分析上述算法的時間復(fù)雜度累加器累加器ctempctemp初始化的時間復(fù)雜度為初始化的時間復(fù)雜度為 (M.mu(M.muN.nu)N.nu)求求Q Q的一切非零元的時間復(fù)雜度為的一切非零元的時間復(fù)雜度為 (M.tu(M.tuN.tu/N.mu) N.tu/N.mu) 進(jìn)展緊縮存儲的時間復(fù)雜度為進(jìn)展緊縮存儲的時間復(fù)雜度為 (M.mu(M.muN.nu)N.nu) 總的時間復(fù)雜度就是總的時間復(fù)雜度就是 (M.

28、mu(M.muN.nu+M.tuN.nu+M.tuN.tu/N.mu)N.tu/N.mu)。矩陣的緊縮存儲 假設(shè)假設(shè)M是是m行行n列的稀疏矩陣，列的稀疏矩陣，N是是n行行p列列的稀疏矩陣，那么的稀疏矩陣，那么M中非零元的個數(shù)中非零元的個數(shù) M.tu = Mmn N中非零元的個數(shù)中非零元的個數(shù) N.tu = Nnp 相乘算法的時間復(fù)雜度就是相乘算法的時間復(fù)雜度就是 (mp(1+nMN) 當(dāng)當(dāng)M0.05 和和N0.05及及 n p-col時，p和q右移2插入：a、假設(shè)p=NULL且q=NULL，即本行空，那么rhr-1=s;b、假設(shè)p=NULL,q!=NULL，即走到行末，那么q-right=sc

29、、假設(shè)c=p-col，那么修正p-vald、假設(shè)ccol且q=NULL，那么在p之前插入s，即s是行鏈表中 第一個結(jié)點，令rhr-1=s; s-right=p;e、假設(shè)ccol且q!=NULL，那么在p之前插入s， 即 s-right=p; q-right=s;從鍵盤接納信息建立十字鏈表算法從鍵盤接納信息建立十字鏈表算法矩陣的緊縮存儲418234m=4,n=31,1,32,2,52,3,44,1,82,1,7113217225矩陣的緊縮存儲5.4 5.4 廣義表的定義廣義表的定義 廣義表廣義表Lists，又稱列表是線性表的推行。，又稱列表是線性表的推行。 廣義表是廣義表是n(n=0)個元素個元

30、素a1,a2,a3,an的有限序的有限序列，其中列，其中ai或者是原子項，或者是一個廣義表。通?；蛘呤窃禹?，或者是一個廣義表。通常記作記作:廣義表的定義廣義表的定義LS=a1,a2,a3,an) LS是廣義表的名字，是廣義表的名字，n為它的長度。假設(shè)為它的長度。假設(shè)ai是廣義是廣義表，那么稱它為表，那么稱它為LS的子表。的子表。 假設(shè)廣義表假設(shè)廣義表LSn=1)非空，那么非空，那么a1是是LS的表頭，的表頭，其他元素組成的表其他元素組成的表(a1,a2,an)稱為稱為LS的表尾。表尾的表尾。表尾ADT Glist 數(shù)據(jù)對象：數(shù)據(jù)對象：Dei | i=1,2,.,n; n0; eiAtomSe

31、t 或或 eiGList, AtomSet為某個數(shù)據(jù)對象為某個數(shù)據(jù)對象 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： LR| ei-1 ,eiD, 2in廣義表的定義廣義表的定義 ADT Glist 構(gòu)造的創(chuàng)建和銷毀 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L); 形狀函數(shù)形狀函數(shù) GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和刪除操作插入和刪除操作 InsertFirst_GL(&L,

32、 e); DeleteFirst_GL(&L, &e); 遍歷遍歷 Traverse_GL(L, Visit();根本操作：根本操作：廣義表的定義廣義表的定義廣義表是遞歸定義的線性構(gòu)造，廣義表是遞歸定義的線性構(gòu)造， LS = ( 1, 2, , n )其中：其中：i 或為原子或為原子 或為廣義表或為廣義表例如例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) )廣義表的定義廣義表的定義廣義表是一個多層次的線性構(gòu)造廣義表是一個多層次的線性構(gòu)造例如：例如：D=(E

33、, F)其中其中: : E=(a, (b, c) E=(a, (b, c) F=(d, (e) F=(d, (e)DEFa( )d( )bce廣義表的定義廣義表的定義廣義表廣義表 LS = ( 1, 2, , n )的構(gòu)造特點的構(gòu)造特點:1) 廣義表中的數(shù)據(jù)元素有相對次序；廣義表中的數(shù)據(jù)元素有相對次序；2) 廣義表的長度定義為最外層包含元素個數(shù)；廣義表的長度定義為最外層包含元素個數(shù)；3) 廣義表的深度定義為所含括弧的重數(shù)；廣義表的深度定義為所含括弧的重數(shù)； 留意：留意：“原子的深度為原子的深度為 0 “空表的深度為空表的深度為 1 4) 廣義表可以共享；廣義表可以共享；5) 廣義表可以是一個遞

34、歸的表。廣義表可以是一個遞歸的表。 遞歸表的深度是無窮值，長度是有限值。遞歸表的深度是無窮值，長度是有限值。6) 任何一個非空廣義表任何一個非空廣義表 LS = ( 1, 2, , n) 均可分解為均可分解為 表頭表頭 Head(LS) = 1 和和 表尾表尾 Tail(LS) = ( 2, , n) 兩部分。兩部分。廣義表的定義廣義表的定義例如例如: D = ( E, F ) = (a, (b, c)，F(xiàn) )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c)

35、 Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )廣義表的定義廣義表的定義5.5 5.5 廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造通常采用頭、尾指針的鏈表構(gòu)造通常采用頭、尾指針的鏈表構(gòu)造表結(jié)點表結(jié)點: :原子結(jié)點：原子結(jié)點：tag=1 hp tptag=0 atom廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造typedef enum ATOM,LIST ElemTag; / ATOM = 0:原子，原子，LIST=1：子表：子表廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造t

36、ypedef struct GLNode ElemTag tag; union AtomType atom; struct struct GLNode *hp,*top ptr; ; *Glist; 1) 表頭、表尾分析法：表頭、表尾分析法：構(gòu)造存儲構(gòu)造的兩種分析方法構(gòu)造存儲構(gòu)造的兩種分析方法: :假設(shè)表頭為原子，那么為假設(shè)表頭為原子，那么為空表空表 ls=NIL非空表非空表 lstag=1 指向表頭的指針指向表尾的指針tag=0 atom否那么，依次類推。否那么，依次類推。廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造 L=(a, (x, y), (x) ) a (x, y), (x) ) (x, y)

37、( (x) ) x (y) (x) ( )y ( ) (x) ( )x ( )例如例如:L=(a, (x, y), (x) ) 1 L0 a 1 1 1 1 1 0 a 廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造2) 2) 子表分析法：子表分析法：假設(shè)子表為原子，那么為假設(shè)子表為原子，那么為空表空表 ls=NIL非空表非空表 1 指向子表1 的指針tag=0 data否那么，依次類推。否那么，依次類推。 1 指向子表2 的指針 1 指向子表n 的指針ls 廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造例如例如: a (x, y) (x) LS=( a, (x,y), (x) )ls廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造5.

38、7 5.7 廣義表的遞歸函數(shù)廣義表的遞歸函數(shù)遞歸函數(shù)遞歸函數(shù) 一個含直接或間接調(diào)用本函數(shù)語句的函數(shù)被一個含直接或間接調(diào)用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)，它必需滿足以下兩個條件：稱之為遞歸函數(shù)，它必需滿足以下兩個條件：1)在每一次調(diào)用本人時，必需是在每一次調(diào)用本人時，必需是(在某在某 種意義上種意義上)更接近于解更接近于解;2)必需有一個終止處置或計算的準(zhǔn)那么。必需有一個終止處置或計算的準(zhǔn)那么。例如例如: : 梵塔的遞歸函數(shù)梵塔的遞歸函數(shù)void hanoi (int n, char x, char y, char z) if (n=1) move(x, 1, z); else hanoi(n

39、-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); 如何設(shè)計遞歸函數(shù)？如何設(shè)計遞歸函數(shù)？二、后置遞歸法二、后置遞歸法(Postponing the work)三、回溯法三、回溯法(Backtracking)一、分治法一、分治法 (Divide and Conquer) (又稱分割求解法又稱分割求解法) 對于一個輸入規(guī)模為對于一個輸入規(guī)模為 n n 的函數(shù)或問題，的函數(shù)或問題，用某種方法把輸入分割成用某種方法把輸入分割成 k(1kn) k(1ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max

40、= dep; return max + 1; / GlistDepthif (!L) return 1; if (L-tag = ATOM) return 0; 1 1 1 L for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; 例如例如:pppp-ptr.hppppppp-ptr.hp例二例二 復(fù)制廣義表復(fù)制廣義表新的廣義表由新的表頭和表尾構(gòu)成。新的廣義表由新的表頭和表尾構(gòu)成?？梢灾苯忧蠼獾膬煞N簡單情況為： 空表復(fù)制求得的新表自然也是空表; 原子結(jié)點可以直接復(fù)制求得。

41、 將廣義表分解成表頭和表尾兩部分，分別(遞歸)復(fù)制求得新的表頭和表尾，假設(shè)假設(shè) ls= NIL 那么那么 newls = NIL否那么否那么 構(gòu)造結(jié)點構(gòu)造結(jié)點 newls, 由由 表頭表頭ls-ptr.hp 復(fù)制得復(fù)制得 newhp 由由 表尾表尾 ls-ptr.tp 復(fù)制得復(fù)制得 newtp 并使并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp復(fù)制求廣義表的算法描畫如下復(fù)制求廣義表的算法描畫如下:Status CopyGList(Glist &T, Glist L) if (!L) T = NULL; / 復(fù)制空表復(fù)制空表 else if (

42、 !(T = (Glist)malloc(sizeof(GLNode) ) exit(OVERFLOW); / 建表結(jié)點建表結(jié)點 T-tag = L-tag; if (L-tag = ATOM) T-atom = L-atom; / 復(fù)制單原子結(jié)點復(fù)制單原子結(jié)點 else / else return OK; / CopyGList分別復(fù)制表頭和表尾分別復(fù)制表頭和表尾CopyGList(T-ptr.hp, L-ptr.hp); / 復(fù)制求得表頭復(fù)制求得表頭T-ptr.hp的一個副本的一個副本L-ptr.hpCopyGList(T-ptr.tp, L-ptr.tp); / 復(fù)制求得表尾復(fù)制求得表尾

43、T-ptr.tp 的一個副本的一個副本L-ptr.tp語句語句 CopyGList(T-ptr.hp, L-ptr.hp);等價于等價于 CopyGList(newhp, L-ptr.tp); T-ptr.hp = newhp;例三例三 創(chuàng)建廣義表的存儲構(gòu)造創(chuàng)建廣義表的存儲構(gòu)造 對應(yīng)廣義表的不同定義方法相應(yīng)地有不同的創(chuàng)建存儲構(gòu)造的算法。 假設(shè)以字符串 S = (1, 2, , n ) 的方式定義廣義表 L，建立相應(yīng)的存儲構(gòu)造。 由于S中的每個子串i定義 L 的一個子表，從而產(chǎn)生 n 個子問題，即分別由這 n個子串 (遞歸)建立 n 個子表，再組合成一個廣義表。 可以直接求解的兩種簡單情況為：由串( )建立的廣義表是空表；由單字符建立的子表只是一個原子結(jié)點。如何由子表組合成一個廣義表？如何由子表組合成一個廣義表？ 首先分析廣義表和子表在存儲構(gòu)造中的關(guān)系。首先分析廣義表和子表在存儲構(gòu)造中的關(guān)系。先看第一個子表和廣義表的關(guān)系先看第一個子表和廣義表的關(guān)系: 1 L指向廣義表指向廣義表的頭指針的頭指針指向第一個指向第一個子表的頭指針子表的頭指針再看相鄰兩個子表之間的關(guān)