1、第五章第五章 數組和廣義表數組和廣義表 數組和廣義表可看成是數組和廣義表可看成是一種特殊的線性表，其特一種特殊的線性表，其特殊在于殊在于:表中的數據元素表中的數據元素本身也是一種線性表本身也是一種線性表 5.1 數組的定義 數組是我們最熟習的數據類型，在早期的高級言語中，數組是獨一可供運用的數據類型。由于數組中各元素具有一致的類型，并且數組元素的下標普通具有固定的上界和下界，因此，數組的處置比其它復雜的構造更為簡單。多維數組是向量的推行。例如，二維數組： a11 a12 a1n a21 a22 a2n am1 am2 amn Amn= 可以看成是m由個行向量組成的向量，也可以看成是n個列向量組

2、成的向量。 數組一旦被定義，它的維數和維界就不再改動。因此，除了構造的初始化和銷毀之外，數組只需存取元素和修正元素值的操作。 5.2 數組的順序表示和實現 由于計算機的內存儲構造是一維的，因此用一維內存來表示多維數組，就必需按某種次序將數組元素排成一列序列，然后將這個線性序列存放在存儲器中。 又由于對數組普通不做插入和刪除操作，也就是說，數組一旦建立，構造中的元素個數和元素間的關系就不再發生變化。因此，普通都是采用順序存儲的方法來表示數組。 5.1 數組的類型定義數組的類型定義5.3 稀疏矩陣的緊縮存儲稀疏矩陣的緊縮存儲 5.2 數組的順序表示和實現數組的順序表示和實現5.4 廣義表的類型定義

3、廣義表的類型定義5.5 廣義表的表示方法廣義表的表示方法5.6 廣義表操作的遞歸函數廣義表操作的遞歸函數5.1 數組的類型定義數組的類型定義ADT Array 數據對象：數據對象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,.,n 數據關系：數據關系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且且k i, 0 ji bi -2, i=2,.,n ADT Array 根本操作根本操作:二維數組的定義二維數組的定義:數據對象數據對象: : D = aij | 0ib1-1, 0 D = aij | 0ib1-1, 0 jb2-

4、1jb2-1數據關系數據關系: : R = ROW, COL R = ROW, COL ROW = | 0ib1- ROW = | 0ib1-2, 0jb2-12, 0jb2-1 COL = | 0ib1- COL = | 0ib1-1, 0 jb2-21, 0 jb2-2根本操作：根本操作：InitArray(&A, n, bound1, ., boundn)DestroyArray(&A)Value(A, &e, index1, ., indexn)Assign(&A, e, index1, ., indexn) InitArray(&A, n, b

5、ound1, ., boundn) 操作結果：假設維數 n 和各維長度合法， 那么構造相應的數組A，并 前往OK。 DestroyArray(&A) 操作結果：銷毀數組A。 Value(A, &e, index1, ., indexn) 初始條件：A是n維數組，e為元素變量， 隨后是n 個下標值。 操作結果：假設各下標不超界，那么e賦值為 所指定的A 的元素值，并返 回OK。 Assign(&A, e, index1, ., indexn) 初始條件：A是n維數組，e為元素變量， 隨后是n 個下標值。 操作結果：假設下標不超界，那么將e的值賦 給所指定的A的元素，并前往

6、 OK。5.2 數組的順序表示和實現數組的順序表示和實現 類型特點類型特點:1) 只需援用型操作，沒有加工型操作；只需援用型操作，沒有加工型操作；2) 數組是多維的構造，而存儲空間是數組是多維的構造，而存儲空間是 一個一維的構造。一個一維的構造。 有兩種順序映象的方式有兩種順序映象的方式:1)以行序為主序以行序為主序(低下標優先低下標優先)；2)以列序為主序以列序為主序(高下標優先高下標優先)。例如：例如： 稱為基地址或基址。以以“行序為主序的存儲映象行序為主序的存儲映象二維數組A中任一元素ai,j 的存儲位置 LOC(i,j) = LOC(0,0) + (b2ij)a0,1a0,0a0,2a

7、1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 推行到普通情況，可得到 n 維數組數據元素存儲位置的映象關系 稱為 n 維數組的映象函數。數組元素的存儲位置是其下標的線性函數。其中 cn = L，ci-1 = bi ci , 1 i n。LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji i=1n假設 m 行 n 列的矩陣含 t 個非零元素，那么稱 為稀疏因子。通常以為 0.05 的矩陣為稀疏矩陣。nmt5.3 稀疏矩陣的緊縮存儲稀疏矩陣的緊縮存儲何謂稀疏矩陣？ 以常規方法，即以二維數組表示高階的稀疏矩陣時產生的問題:1) 零值元

8、素占了很大空間零值元素占了很大空間;2) 計算中進展了很多和零值的運算，計算中進展了很多和零值的運算， 遇除法，還需判別除數能否為零。遇除法，還需判別除數能否為零。1) 盡能夠少存或不存零值元素；處理問題的原那么處理問題的原那么:2) 盡能夠減少沒有實踐意義的運算；3) 操作方便。 即： 能盡能夠快地找到與 下標值(i，j)對應的元素， 能盡能夠快地找到同 一行或同一列的非零值元。1) 特殊矩陣特殊矩陣 非零元在矩陣中的分布有一定規那么非零元在矩陣中的分布有一定規那么 例如例如: 三角矩陣三角矩陣 對角矩陣對角矩陣2) 隨機稀疏矩陣隨機稀疏矩陣 非零元在矩陣中隨機出現非零元在矩陣中隨機出現有兩

9、類稀疏矩陣：有兩類稀疏矩陣：5.3.1特殊矩陣 所謂特殊矩陣是指非零元素或零元素的分布有一定規律的矩陣，下面我們討論幾種特殊矩陣的緊縮存儲。1、對稱矩陣 在一個n階方陣A中，假設元素滿足下述性質： aij=aji 0i,jn-1那么稱A為對稱矩陣。如圖5.1便是一個5階對稱矩陣。 對稱矩陣中的元素關于主對角線對稱，故只需存儲矩陣中上三角或下三角中的元素，讓每兩個對稱的元素共享一個存儲空間，這樣，能節約近一半的存儲空間。不失普通性，我們按“行優先順序存儲主對角線包括對角線以下的元素，其存儲方式如下圖： 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20

10、a21 a23 3 0 2 5 1 . 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 圖 5.1 對稱矩陣 在這個下三角矩陣中，第i行恰有i+1個元素，元素總數為： n(n+1)/2 因此，我們可以按圖中箭頭所指的次序將這些元素存放在一個向量sa0.n(n+1)/2-1中。為了便于訪問對稱矩陣A中的元素，我們必需在aij和sak 之間找一個對應關系。 假設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

11、=i*(i+1)/2+j 0kn(n+1)/2 假設ij，那么aij是在上三角矩陣中。由于aij=aji，所以只需交換上述對應關系式中的i和j即可得到： k=j*(j+1)/2+i 0 kn(n+1)/2 令 I=max(i,j)， J=min(i,j)，那么k和 i, j的對應關系可一致為： k=I*(I+1)/2+J 0 kn(n+1)/2 因此，aij的地址可用以下式計算： LOC(aij)=LOC(sak) =LOC(sa0)+k*d=LOC(sa0+I*(I+1)/2+J*d 有了上述的下標交換關系，對于恣意給定一組下標(i，j)，均可在sak中找到矩陣元素aij，反之，對一切的k=

12、0,1,2,n(n-1)/2-1，都能確定sak中的元素在矩陣中的位置(i,j)。由此，稱san(n+1)/2為階對稱矩陣A的緊縮存儲，見以下圖：k=0 1 2 3 n(n-1)/2 n(n+1)/2-1例如a21和a12均存儲在 sa4中，這是由于 k=I*(I+1)/2+J=2*(2+1)/2+1=4a00a10a11a20an-1 0 an-1,n-12、三角矩陣 以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如下圖，它的下三角不包括主對角線中的元素均為常數。下三角矩陣正好相反，它的主對角線上方均為常數，如下圖。在大多數情況下，三角矩陣常數為零。 a00 a01 a 0 n-1

13、 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩陣 (b)下三角矩陣 圖5.2 三角矩陣 三角矩陣中的反復元素c可共享一個存儲空間，其他的元素正好有n(n+1)/2個，因此，三角矩陣可緊縮存儲到向量sa0.n(n+1)/2中，其中c存放在向量的最后一個分量中， 上三角矩陣中，主對角線之上的第p行(0pjk= 下三角矩陣的存儲和對稱矩陣類似，sak和aij對應關系是： i(i+1)/2+j ij n(n+1)/2 ij 3、對角矩陣 對角矩陣中，一切的非零元素集中在以主對角線為了中心

14、的帶狀區域中，即除了主對角線和主對角線相鄰兩側的假設干條對角線上的元素之外，其他元素皆為零。以下圖給出了一個三對角矩陣， a00 a01 a10 a11 a12 a21 a22 a23 . . . 圖5.3 對角矩陣 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1k=非零元素僅出如今主對角(aii,0in-1上，緊鄰主對角線上面的那條對角線上(aii+1,0in-2)和緊鄰主對角線下面的那條對角線上(ai+1 i,0in-2)。顯然，當 i-j 1時，元素aij=0。由此可知，一個k對角矩陣(k為奇數)A是滿足下述條件的矩陣：假設 i-j (k-1)/

15、2 ，那么元素 aij=0。 對角矩陣可按行優先順序或對角線的順序，將其緊縮存儲到一個向量中，并且也能找到每個非零元素和向量下標的對應關系。 在三對角矩陣里附滿足條件i=0，j=0、1，或i=n-1j=n-2、n-1或1in-1,j=i-1、i、i+1的元素aij外，其他元素都是零。 對這種矩陣，我們也可按行優序為主序來存儲。除第0行和第n-1行是2個元素外，每行的非零元素都要是3個，因此，需存儲的元素個數為3n-2。a00a01 a10a11a12a21 a n-1 n-2a n-1 n-1K=0 1 2 3 4 5 3n-2 3n-1 數組sa中的元素sak與三對角帶狀矩陣中的元素aij存

16、在一一對應關系，在aij之前有i行,共有3*i-1個非零元素，在第i行，有j-i+1個非零元素，這樣，非零元素aij的地址為： LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d 上例中，a34對應著sa10。 k=2*i+j=2*3+4=10 a21對應著sa5 k=2*2+1=5由此，我們稱sa0.3*n-2是階三對角帶狀矩陣A的緊縮存儲表示。上述的各種特殊矩陣，其非零元素的分布都是有規律的，因此總能找到一種方法將它們緊縮存儲到一個向量中，并且普通都能找到矩陣中的元素與該向量的對應關系，經過這個關系，仍能對矩陣的元素進展隨機存取。 5.

17、3.2 稀疏矩陣。隨機稀疏矩陣的緊縮存儲方法隨機稀疏矩陣的緊縮存儲方法:一、三元組順序表一、三元組順序表二、行邏輯聯接的順序表二、行邏輯聯接的順序表三、三、 十字鏈表十字鏈表 #define MAXSIZE 12500 typedef struct int i, j; /該非零元的行下標和列下標 ElemType e; / 該非零元的值 Triple; / 三元組類型一、三元組順序表一、三元組順序表typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩陣類型稀疏矩陣類型如何求轉置矩陣？如何求轉置矩陣？02800

18、3600070500140005280000007143600用常規的二維數組表示時的算法 其時間復雜度為其時間復雜度為: O(munu) for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;用“三元組表示時如何實現？1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28 首先應該確定每一行的第一個非零元在三元組中的位置。1 2 151 5 -52 2 -73 1 363 4 28 col12345Numpos12011Cpotcol1244

19、5 cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1;Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) 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) cpotco

20、l = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) / if return OK; / FastTransposeSMatrix 轉置矩陣元素Col = M.datap.j;q = cpotcol;T.dataq.i = M.datap.j;T.dataq.j = M.datap.i;T.dataq.e = M.datap.e;+cpotcol 分析算法FastTransposeSMatrix的時間復雜度：時間復雜度為時間復雜度為: O(M.nu+M.tu): O(M.nu+M.tu)for (col=1; col=M.nu; +col) for (

21、t=1; t=M.tu; +t) for (col=2; col=M.nu; +col) for (p=1; p=M.tu; +p) 三元組順序表又稱有序的雙下標法，它的特點是，非零元在表中按行序有序存儲，因此便于進展依行順序處置的矩陣運算。然而，假設需隨機存取某一行中的非零元，那么需從頭開場進展查找。二、行邏輯聯接的順序表二、行邏輯聯接的順序表 #define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; int mu, nu, tu; RLSMatrix; / 行邏輯鏈接順序表類行邏輯鏈接順序表類型型

22、 修正前述的稀疏矩陣的構造定義，添加一個數據成員rpos，其值在稀疏矩陣的初始化函數中確定。例如：給定一組下標，求矩陣的元素值ElemType value(RLSMatrix 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 =

23、0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 其時間復雜度為其時間復雜度為: O(m1n2n1) Q初始化； if Q是非零矩陣 / 逐行求積 for (arow=1; arow=M.mu; +arow) / 處置M的每一行 ctemp = 0; / 累加器清零 計算Q中第arow行的積并存入ctemp 中； 將ctemp 中非零元緊縮存儲到Q.data； / for arow / if 兩個稀疏矩陣相乘兩個稀疏矩陣相乘QMN 的過程可大致描畫如下：的過程可大致描畫如下： Status MultSMatrix (RLSMatrix M, RLSMatrix

24、N, RLSMatrix &Q) 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; / MultSMatrix ctemp = 0; / 當前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; pM.rposarow+1;+p) /對當前行中

25、每一個非零元 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 q / 求得Q中第crow( =arow)行的非零元 for (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if處置 的每一行M分析上述算法的時間復雜

26、度分析上述算法的時間復雜度累加器ctemp初始化的時間復雜度為(M.muN.nu)，求Q的一切非零元的時間復雜度為(M.tuN.tu/N.mu)，進展緊縮存儲的時間復雜度為(M.muN.nu)，總的時間復雜度就是(M.muN.nu+M.tuN.tu/N.mu)。假設M是m行n列的稀疏矩陣，N是n行p列的稀疏矩陣，那么M中非零元的個數 M.tu = Mmn， N中非零元的個數 N.tu = Nnp，相乘算法的時間復雜度就是 (mp(1+nMN) ，當M0.05 和N0.05及 n 1000時，相乘算法的時間復雜度就相當于 (mp)。三、三、 十字鏈表十字鏈表M.cheadM.rhead3 0 0

27、 50 -1 0 02 0 0 01 1 31 4 52 2-13 1 2 5.4 廣義表的類型定義廣義表的類型定義ADT Glist 數據對象：數據對象：Dei | i=1,2,.,n; n0; eiAtomSet 或或 eiGList, AtomSet為某個數據對象為某個數據對象 數據關系：數據關系： LR| ei-1 ,eiD, 2in ADT Glist根本操作根本操作:廣義表是遞歸定義的線性構造， LS = ( 1, 2, , n )其中：i 或為原子 或為廣義表例如例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B =

28、(a, B) = (a, (a, (a, , ) ) )廣義表是一個多層次的線性構造例如：例如：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( ) d( )bce廣義表廣義表 LS = ( 1, 2, , n )的構的構造特點造特點:1) 廣義表中的數據元素有相對次序；2) 廣義表的長度定義為最外層包含元素個數；3) 廣義表的深度定義為所含括弧的重數； 留意：“原子的深度為 0 “空表的深度為 1 4) 廣義表可以共享；5) 廣義表可以是一個遞歸的表。 遞歸表的深度是無窮值，長度是有限值。6) 任何一個非空廣義表 LS = ( 1, 2, , n) 均可分解為

29、表頭 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n) 兩部分。例如例如: D = ( E, F ) = (a, (b, c)，F )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( ) 構造的創建和銷毀 InitGList(&

30、;L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);根本操作根本操作 形狀函數形狀函數 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和刪除操作插入和刪除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); 遍歷遍歷 Traverse_GL(L, Visit();5.5 廣義表的表示方法廣義表的表示方法通常采用頭、尾指針的鏈表構造表結點表

31、結點: :原子結點：原子結點：tag=1 hp tptag=0 data1) 表頭、表尾分析法：構造存儲構造的兩種分析方法構造存儲構造的兩種分析方法: :假設表頭為原子，那么為假設表頭為原子，那么為空表空表 ls=NIL非空表非空表 lstag=1 指向表頭的指針指向表尾的指針tag=0 data否那么，依次類推。否那么，依次類推。例如例如:L=(a, (x, y), (x) ) a (x, y), (x) ) (x, y) ( (x) ) x (y) (x) ( ) y ( ) (x) ( ) x ( )L = ( a, ( x, y ), ( ( x ) ) )a ( x, y ) ( )

32、 1 LL = ( )0 a 1 1 1 1 1 0 x ( )x2) 子表分析法：假設子表為原子，那么為假設子表為原子，那么為空表空表 ls=NIL非空表非空表 1 指向子表1 的指針tag=0 data否那么，依次類推。否那么，依次類推。 1 指向子表2 的指針 1 指向子表n 的指針ls 例如例如: a (x, y) (x) LS=( a, (x,y), (x) )ls5.6 廣義表操作的遞歸函數廣義表操作的遞歸函數遞歸函數遞歸函數 一個含直接或間接調用本函數一個含直接或間接調用本函數語句的函數被稱之為遞歸函數，它語句的函數被稱之為遞歸函數，它必需滿足以下兩個條件：必需滿足以下兩個條件：

33、1)在每一次調用本人時，必需是在每一次調用本人時，必需是(在某在某 種意義上種意義上)更接近于解更接近于解;2)必需有一個終止處置或計算的準那么。必需有一個終止處置或計算的準那么。例如例如: : 梵塔的遞歸函數梵塔的遞歸函數void hanoi (int n, char x, char y, char z) if (n=1) move(x, 1, z); else hanoi(n-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); 二叉樹的遍歷二叉樹的遍歷 void PreOrderTraverse( BiTree T,void (Visit)(B

34、iTree P) if (T) Visit(T-data); (PreOrderTraverse(T-lchild, Visit); (PreOrderTraverse(T-rchild, Visit); / PreOrderTraverse一、分治法一、分治法 (Divide and Conquer) (又稱分割求解法又稱分割求解法)如何設計遞歸函數？如何設計遞歸函數？二、后置遞歸法二、后置遞歸法(Postponing the work)三、回溯法三、回溯法(Backtracking) 對于一個輸入規模為 n 的函數或問題，用某種方法把輸入分割成 k(1ptr.tp) dep = Glist

35、Depth(pp-ptr.hp); if (dep max) max = 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.hppp-ptr.hp例二例二 復制廣義表復制廣義表新的廣義表由新的表頭和表尾構成。新的廣義表由新的表頭和表尾構成。可以

36、直接求解的兩種簡單情況為： 空表復制求得的新表自然也是空表; 原子結點可以直接復制求得。 將廣義表分解成表頭和表尾兩部分，分別(遞歸)復制求得新的表頭和表尾，假設假設 ls= NIL 那么那么 newls = NIL否那么否那么 構造結點構造結點 newls, 由由 表頭表頭ls-ptr.hp 復制得復制得 newhp 由由 表尾表尾 ls-ptr.tp 復制得復制得 newtp 并使并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp復制求廣義表的算法描畫如下復制求廣義表的算法描畫如下:Status CopyGList(Glist &T, Gli

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

38、opyGList(T-ptr.tp, L-ptr.tp); / 復制求得表尾復制求得表尾T-ptr.tp 的一個副本的一個副本L-ptr.tp語句語句 CopyGList(T-ptr.hp, L-ptr.hp);等價于等價于 CopyGList(newhp, L-ptr.tp); T-ptr.hp = newhp;例三例三 創建廣義表的存儲構造創建廣義表的存儲構造 對應廣義表的不同定義方法相應地有不同的創建存儲構造的算法。 假設以字符串 S = (1, 2, , n ) 的方式定義廣義表 L，建立相應的存儲構造。 由于S中的每個子串i定義 L 的一個子表，從而產生 n 個子問題，即分別由這 n

39、個子串 (遞歸)建立 n 個子表，再組合成一個廣義表。 可以直接求解的兩種簡單情況為：由串( )建立的廣義表是空表；由單字符建立的子表只是一個原子結點。如何由子表組合成一個廣義表？如何由子表組合成一個廣義表？ 首先分析廣義表和子表在存儲構造中首先分析廣義表和子表在存儲構造中的關系。的關系。先看第一個子表和廣義表的關系先看第一個子表和廣義表的關系: 1 L指向廣義表指向廣義表的頭指針的頭指針指向第一個指向第一個子表的頭指針子表的頭指針再看相鄰兩個子表之間的關系再看相鄰兩個子表之間的關系: 1 1 指向第指向第i+1個個子表的頭指針子表的頭指針指向第指向第i個個子表的頭指針子表的頭指針可見，兩者之

40、間經過表結點相鏈接。可見，兩者之間經過表結點相鏈接。假設假設 S = ( ) 那么那么 L = NIL；否那么，構造第一個表結點否那么，構造第一個表結點 *L， 并從串并從串S中分解出第一個子串中分解出第一個子串1，對，對應創建第一個子廣義表應創建第一個子廣義表 L-ptr.hp； 假設剩余串非空，那么構造第二個表假設剩余串非空，那么構造第二個表結點結點 L-ptr.tp，并從串，并從串S中分解出第二中分解出第二個子串個子串 2，對應創建第二個子廣義，對應創建第二個子廣義表表 ； 依次類推，直至剩余串為空串止。依次類推，直至剩余串為空串止。void CreateGList(Glist &

41、;L, String S) if (空串空串) L = NULL; / 創建空表創建空表 else L=(Glist) malloc(sizeof(GLNode); L-tag=List; p=L; sub=SubString(S,2,StrLength(S)-1); /脫去串脫去串S的外層括弧的外層括弧 / else 由由sub中所含中所含n個子串建立個子串建立n個子表個子表;do sever(sub, hsub); / 分別出子表串分別出子表串hsub=i if (!StrEmpty(sub) p-ptr.tp=(Glist)malloc(sizeof(GLNode); / 建下一個子表的

42、表結點建下一個子表的表結點*(p-ptr.tp) p=p-ptr.tp; while (!StrEmpty(sub);p-ptr.tp = NULL; / 表尾為空表表尾為空表創建由串創建由串hsub定義的廣義表定義的廣義表p-ptr.hp;if (StrLength(hsub)=1) p-ptr.hp=(GList)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM; p-ptr.hp-atom=hsub; / 創建單原子結點創建單原子結點else CreateGList(p-ptr.hp, hsub); /遞歸建廣義表遞歸建廣義表 假如某個問題的求解過程可以分

43、成若干步進行，并且當前這一步的解可以直接求得，則先先求求出出當當前前這這一一步步的的解解，對于余余下下的的問問題題，若問題的性質和原問題類似，則又可遞遞歸歸求求解解。后置遞歸的設計思想為后置遞歸的設計思想為: 遞歸的終結形狀是，當前的問題可以直接求解，對原問題而言，那么是已走到了求解的最后一步。鏈表是可以如此求解的一個典型例子。例如：編寫“刪除單鏈表中一切值為x 的數據元素的算法。1) 單鏈表是一種順序構造，必需從第一個結點起，逐個檢查每個結點的數據元素；分析分析:2) 從另一角度看，鏈表又是一個遞歸構造，假設 L 是線性鏈表 (a1, a2, , an) 的頭指針，那么 L-next是線性鏈

44、表 (a2, , an)的頭指針。 a1 a2 a3 an L例如例如: a1 a2 a3 an L a1 a2 a3 an L知以下鏈表1) “a1=x，那么 L 仍為刪除 x 后的鏈表頭指針2) “a1x，那么余下問題是思索以 L-next 為頭指針的鏈表 a1 L-nextL-next=p-nextp=L-nextvoid delete(LinkList &L, ElemType x) / 刪除以刪除以L為頭指針的帶頭結點的單鏈表中為頭指針的帶頭結點的單鏈表中 / 一切值為一切值為x的數據元素的數據元素 if (L-next) if (L-next-data=x) p=L-nex

45、t; L-next=p-next; free(p); delete(L, x); else delete(L-next, x); / delete刪除廣義表中一切元素為刪除廣義表中一切元素為x x的原子結點的原子結點分析分析: : 比較廣義表和線性表的構造特點：比較廣義表和線性表的構造特點：類似處：都是鏈表構造。類似處：都是鏈表構造。不同處：不同處：1)1)廣義表的數據元素能夠還是個廣義表的數據元素能夠還是個 廣義表；廣義表； 2) 2)刪除時，不僅要刪除原子結點，刪除時，不僅要刪除原子結點， 還需求刪除相應的表結點。還需求刪除相應的表結點。void Delete_GL(Glist&L

46、, AtomType x) /刪除廣義表刪除廣義表L中一切值為中一切值為x的原子結點的原子結點 if (L) head = L-ptr.hp; / 調查第一個子表調查第一個子表 if (head-tag = Atom) & (head-atom = x) / 刪除原子項刪除原子項 x的情況的情況 else / 第一項沒有被刪除的情況第一項沒有被刪除的情況 / Delete_GL p=L; L = L-ptr.tp; / 修正指針free(head); / 釋放原子結點free(p); / 釋放表結點Delete_GL(L, x); / 遞歸處置剩余表項 1 L0 x 1 pL head

47、if (head-tag = LIST) /該項為廣義該項為廣義表表 Delete_GL(head, x);Delete_GL(L-ptr.tp, x); / 遞歸處置剩余表項遞歸處置剩余表項 1 L0 a 1 1 headL-ptr.tp回溯法是一種回溯法是一種“窮舉方法。其根本思想為：窮舉方法。其根本思想為： 假設問題的解為 n 元組 (x1, x2, , xn)，其中 xi 取值于集合 Si。 n 元組的子組 (x1, x2, , xi) (in)的一的一個合法規劃個合法規劃 / 時，輸出之。時，輸出之。 if (in) 輸出棋盤的當前規劃輸出棋盤的當前規劃; else for (j=1

48、; jn) else while ( ! Empty(Si) 從從 Si 中取中取 xi 的一個值的一個值 viSi; if (x1, x2, , xi) 滿足約束條件滿足約束條件 B( i+1, n); / 繼續求下一個部分解繼續求下一個部分解 從從 Si 中刪除值中刪除值 vi; / B綜合幾點：綜合幾點：1. 對于含有遞歸特性的問題，最好設計對于含有遞歸特性的問題，最好設計遞歸方式的算法。但也不要單純追求方遞歸方式的算法。但也不要單純追求方式，應在算法設計的分析過程中式，應在算法設計的分析過程中“就事就事論事。例如，在利用分割求解設計算論事。例如，在利用分割求解設計算法時，子問題和原問題

49、的性質一樣；或法時，子問題和原問題的性質一樣；或者，問題的當前一步處理之后，余下的者，問題的當前一步處理之后，余下的問題和原問題性質一樣，那么自然導致問題和原問題性質一樣，那么自然導致遞歸求解。遞歸求解。2. 實現遞歸函數，目前必需利用實現遞歸函數，目前必需利用“棧棧。一個遞歸函數必定能改寫為利。一個遞歸函數必定能改寫為利用棧實現的非遞歸函數；反之，一用棧實現的非遞歸函數；反之，一個用棧實現的非遞歸函數可以改寫個用棧實現的非遞歸函數可以改寫為遞歸函數。需求留意的是遞歸函為遞歸函數。需求留意的是遞歸函數遞歸層次的深度決議所需存儲量數遞歸層次的深度決議所需存儲量的大小。的大小。3. 分析遞歸算法的工具是遞歸樹，從分析遞歸算法的工具是遞歸樹，從遞歸樹上可以得到遞歸函數的各種相遞歸樹上可以得到遞歸函數的各種相關信息。例如：遞歸樹的深度即為遞關信息。例如：遞歸樹的深