第5章　數(shù)組和廣義表ppt課件

1、第五章第五章數(shù)組和廣義表數(shù)組和廣義表5.1 數(shù)組的類型定義數(shù)組的類型定義5.3 稀疏矩陣的緊縮存儲稀疏矩陣的緊縮存儲 5.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)5.4 廣義表的類型定義廣義表的類型定義5.5 廣義表的表示方法廣義表的表示方法5.6 廣義表操作的遞歸函數(shù)廣義表操作的遞歸函數(shù)5.1 數(shù)組的類型定義數(shù)組的類型定義ADT Array 數(shù)據(jù)對象：數(shù)據(jù)對象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,.,n 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且且k i, 0 ji bi -2, i=2

2、,.,n ADT Array 根本操作根本操作:二維數(shù)組的定義二維數(shù)組的定義:數(shù)據(jù)對象數(shù)據(jù)對象: : D = aij | 0ib1-1, 0 D = aij | 0ib1-1, 0 jb2-1jb2-1數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系: : 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

3、)Value(A, &e, index1, ., indexn)Assign(&A, e, index1, ., indexn) InitArray(&A, n, bound1, ., boundn) 操作結(jié)果：假設(shè)維數(shù) n 和各維長度合法， 那么構(gòu)造相應(yīng)的數(shù)組A，并 前往OK。 DestroyArray(&A) 操作結(jié)果：銷毀數(shù)組A。 Value(A, &e, index1, ., indexn) 初始條件：A是n維數(shù)組，e為元素變量， 隨后是n 個下標值。 操作結(jié)果：假設(shè)各下標不超界，那么e賦值為 所指定的A 的元素值，并返 回OK。 Assign(

4、&A, e, index1, ., indexn) 初始條件：A是n維數(shù)組，e為元素變量， 隨后是n 個下標值。 操作結(jié)果：假設(shè)下標不超界，那么將e的值賦 給所指定的A的元素，并前往 OK。5.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn) 類型特點類型特點:1) 只需援用型操作，沒有加工型操作；只需援用型操作，沒有加工型操作；2) 數(shù)組是多維的構(gòu)造，而存儲空間是數(shù)組是多維的構(gòu)造，而存儲空間是 一個一維的構(gòu)造。一個一維的構(gòu)造。 有兩種順序映象的方式有兩種順序映象的方式:1)以行序為主序以行序為主序(低下標優(yōu)先低下標優(yōu)先)；2)以列序為主序以列序為主序(高下標優(yōu)先高下標優(yōu)先)。例如：例如：

5、 稱為基地址或基址。以以“行序為主序行序為主序的存儲映象的存儲映象二維數(shù)組A中任一元素ai,j 的存儲位置 LOC(i,j) = LOC(0,0) + (b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 推行到普通情況，可得到 n 維數(shù)組數(shù)據(jù)元素存儲位置的映象關(guān)系 稱為 n 維數(shù)組的映象函數(shù)。數(shù)組元素的存儲位置是其下標的線性函數(shù)。其中 cn = L，ci-1 = bi ci , 1 i n。LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji i=1n假設(shè) m 行 n 列的矩陣含 t 個非零元素，那

6、么稱 為稀疏因子。通常以為 0.05 的矩陣為稀疏矩陣。nmt5.3 稀疏矩陣的緊縮存儲稀疏矩陣的緊縮存儲何謂稀疏矩陣？ 以常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時產(chǎn)生的問題:1) 零值元素占了很大空間零值元素占了很大空間;2) 計算中進展了很多和零值的運算，計算中進展了很多和零值的運算， 遇除法，還需判別除數(shù)能否為零。遇除法，還需判別除數(shù)能否為零。1) 盡能夠少存或不存零值元素；處理問題的原那么處理問題的原那么:2) 盡能夠減少沒有實踐意義的運算；3) 操作方便。 即： 能盡能夠快地找到與 下標值(i，j)對應(yīng)的元素， 能盡能夠快地找到同 一行或同一列的非零值元。1) 特殊矩陣特殊矩陣 非

7、零元在矩陣中的分布有一定規(guī)那么非零元在矩陣中的分布有一定規(guī)那么 例如例如: 三角矩陣三角矩陣 對角矩陣對角矩陣2) 隨機稀疏矩陣隨機稀疏矩陣 非零元在矩陣中隨機出現(xiàn)非零元在矩陣中隨機出現(xiàn)有兩類稀疏矩陣：有兩類稀疏矩陣：隨機稀疏矩陣的緊縮存儲方法隨機稀疏矩陣的緊縮存儲方法:一、三元組順序表一、三元組順序表二、行邏輯聯(lián)接的順序表二、行邏輯聯(lián)接的順序表三、三、 十字鏈表十字鏈表 #define MAXSIZE 12500 typedef struct int i, j; /該非零元的行下標和列下標 ElemType e; / 該非零元的值 Triple; / 三元組類型一、三元組順序表一、三元組順序

8、表typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩陣類型稀疏矩陣類型如何求轉(zhuǎn)置矩陣？如何求轉(zhuǎn)置矩陣？028003600070500140005280000007143600用常規(guī)的二維數(shù)組表示時的算法 其時間復(fù)雜度為其時間復(fù)雜度為: O(munu) for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;用“三元組表示時如何實現(xiàn)？1 2 141 5 -52 2 -73 1 363 4 282 1 145 1 -52 2 -

9、71 3 364 3 28 首先應(yīng)該確定每一行的第一個非零元在三元組中的位置。1 2 151 5 -52 2 -73 1 363 4 28 col12345Numpos12011Cpotcol12445 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;

10、+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) / if return OK; / FastTransposeSMatrix 轉(zhuǎn)置矩陣元素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 分析算法

11、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) for (col=2; col=M.nu; +col) for (p=1; p=M.tu; +p) 三元組順序表又稱有序的雙下標法，它的特點是，非零元在表中按行序有序存儲，因此便于進展依行順序處置的矩陣運算。然而，假設(shè)需隨機存取某一行中的非零元，那么需從頭開場進展查找。二、行邏輯聯(lián)接的順序表二、行邏輯聯(lián)接的順序表 #define MAXMN 500 typedef

12、 struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; int mu, nu, tu; RLSMatrix; / 行邏輯鏈接順序表類行邏輯鏈接順序表類型型 修正前述的稀疏矩陣的構(gòu)造定義，添加一個數(shù)據(jù)成員rpos，其值在稀疏矩陣的初始化函數(shù)中確定。例如：給定一組下標，求矩陣的元素值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

13、 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初始化； if Q是非零矩陣 / 逐行求積 for (arow=1; arow=M.mu; +arow) / 處置M的每一行 ctemp = 0; / 累加器清零 計算Q中第arow行的積并存入ctemp 中； 將ctemp 中非零元緊縮存儲到Q.data； /

14、for arow / if 兩個稀疏矩陣相乘兩個稀疏矩陣相乘QMN 的過程可大致描畫如下：的過程可大致描畫如下： Status MultSMatrix (RLSMatrix M, RLSMatrix 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; / M

15、ultSMatrix ctemp = 0; / 當(dāng)前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; pM.rposarow+1;+p) /對當(dāng)前行中每一個非零元 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)行的非零元

16、for (ccol=1; ccol MAXSIZE) return ERROR; Q.dataQ.tu = arow, ccol, ctempccol; / if處置 的每一行M分析上述算法的時間復(fù)雜度分析上述算法的時間復(fù)雜度累加器ctemp初始化的時間復(fù)雜度為(M.muN.nu)，求Q的一切非零元的時間復(fù)雜度為(M.tuN.tu/N.mu)，進展緊縮存儲的時間復(fù)雜度為(M.muN.nu)，總的時間復(fù)雜度就是(M.muN.nu+M.tuN.tu/N.mu)。假設(shè)M是m行n列的稀疏矩陣，N是n行p列的稀疏矩陣，那么M中非零元的個數(shù) M.tu = Mmn， N中非零元的個數(shù) N.tu = Nnp，

17、相乘算法的時間復(fù)雜度就是 (mp(1+nMN) ，當(dāng)M0.05 和N0.05及 n 1000時，相乘算法的時間復(fù)雜度就相當(dāng)于 (mp)。三、三、 十字鏈表十字鏈表M.cheadM.rhead3 0 0 50 -1 0 02 0 0 01 1 31 4 52 2-13 1 2 5.4 廣義表的類型定義廣義表的類型定義ADT Glist 數(shù)據(jù)對象：數(shù)據(jù)對象：Dei | i=1,2,.,n; n0; eiAtomSet 或或 eiGList, AtomSet為某個數(shù)據(jù)對象為某個數(shù)據(jù)對象 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： LR| ei-1 ,eiD, 2in ADT Glist根本操作根本操作:廣義表是遞歸定義的

18、線性構(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)造例如：例如：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( ) d( )bce廣義表廣義表 LS = ( 1, 2, , n )的構(gòu)造的構(gòu)造特點特點:1) 廣義表中的數(shù)據(jù)元素有相對次序；2) 廣義表的長度定義為最外層包含元素個數(shù)；3) 廣義表的深度定義為所含括弧的重數(shù)； 留意：“原子

19、的深度為 0 “空表的深度為 1 4) 廣義表可以共享；5) 廣義表可以是一個遞歸的表。 遞歸表的深度是無窮值，長度是有限值。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) Tail( ( b, c) ) = ( )Head

20、( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( ) 構(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, e)

21、; DeleteFirst_GL(&L, &e); 遍歷遍歷 Traverse_GL(L, Visit();5.5 廣義表的表示方法廣義表的表示方法通常采用頭、尾指針的鏈表構(gòu)造表結(jié)點表結(jié)點: :原子結(jié)點：原子結(jié)點：tag=1 hp tptag=0 data1) 表頭、表尾分析法：構(gòu)造存儲構(gòu)造的兩種分析方法構(gòu)造存儲構(gòu)造的兩種分析方法: :假設(shè)表頭為原子，那么為假設(shè)表頭為原子，那么為空表空表 ls=NIL非空表非空表 lstag=1 指向表頭的指針指向表尾的指針tag=0 data否那么，依次類推。否那么，依次類推。例如例如:L=(a, (x, y), (x) ) a (x, y)

22、, (x) ) (x, y) ( (x) ) x (y) (x) ( ) y ( ) (x) ( ) x ( )L = ( a, ( x, y ), ( ( x ) ) )a ( x, y ) ( ) 1 LL = ( )0 a 1 1 1 1 1 0 a ( )x2) 子表分析法：假設(shè)子表為原子，那么為假設(shè)子表為原子，那么為空表空表 ls=NIL非空表非空表 1 指向子表1 的指針tag=0 data否那么，依次類推。否那么，依次類推。 1 指向子表2 的指針 1 指向子表n 的指針ls 例如例如: a (x, y) (x) LS=( a, (x,y), (x) )ls5.6 廣義表操作的遞

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

24、 y); move(x, n, z); hanoi(n-1, y, x, z); 二叉樹的遍歷二叉樹的遍歷 void PreOrderTraverse( BiTree T,void (Visit)(BiTree P) if (T) Visit(T-data); (PreOrderTraverse(T-lchild, Visit); (PreOrderTraverse(T-rchild, Visit); / PreOrderTraverse一、分治法一、分治法 (Divide and Conquer) (又稱分割求解法又稱分割求解法)如何設(shè)計遞歸函數(shù)？如何設(shè)計遞歸函數(shù)？二、后置遞歸法二、后置遞歸

25、法(Postponing the work)三、回溯法三、回溯法(Backtracking) 對于一個輸入規(guī)模為 n 的函數(shù)或問題，用某種方法把輸入分割成 k(1ptr.tp) dep = GlistDepth(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

26、) max = dep; 例如例如:pppp-ptr.hppppppp-ptr.hppp-ptr.hp例二例二 復(fù)制廣義表復(fù)制廣義表新的廣義表由新的表頭和表尾構(gòu)成。新的廣義表由新的表頭和表尾構(gòu)成?？梢灾苯忧蠼獾膬煞N簡單情況為： 空表復(fù)制求得的新表自然也是空表; 原子結(jié)點可以直接復(fù)制求得。 將廣義表分解成表頭和表尾兩部分，分別(遞歸)復(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 并使并使 new

27、ls-ptr.hp = newhp, newls-ptr.tp = newtp復(fù)制求廣義表的算法描畫如下復(fù)制求廣義表的算法描畫如下:Status CopyGList(Glist &T, Glist L) if (!L) T = NULL; / 復(fù)制空表復(fù)制空表 else if ( !(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; /

28、 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ù)制求得表尾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)地有

29、不同的創(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)造中首先分析廣義表和子表在存儲構(gòu)造中的關(guān)系。的關(guān)系。先看第一個子表和廣義表的關(guān)系先看第一個子表和廣義表的關(guān)系: 1 L指向廣義表指向廣義表的頭指針的頭指針指向第一

30、個指向第一個子表的頭指針子表的頭指針再看相鄰兩個子表之間的關(guān)系再看相鄰兩個子表之間的關(guān)系: 1 1 指向第指向第i+1個個子表的頭指針子表的頭指針指向第指向第i個個子表的頭指針子表的頭指針可見，兩者之間經(jīng)過表結(jié)點相鏈接?？梢姡瑑烧咧g經(jīng)過表結(jié)點相鏈接。假設(shè)假設(shè) S = ( ) 那么那么 L = NIL；否那么，構(gòu)造第一個表結(jié)點否那么，構(gòu)造第一個表結(jié)點 *L， 并從串并從串S中分解出第一個子串中分解出第一個子串1，對，對應(yīng)創(chuàng)建第一個子廣義表應(yīng)創(chuàng)建第一個子廣義表 L-ptr.hp； 假設(shè)剩余串非空，那么構(gòu)造第二個表假設(shè)剩余串非空，那么構(gòu)造第二個表結(jié)點結(jié)點 L-ptr.tp，并從串，并從串S中分解出

31、第二中分解出第二個子串個子串 2，對應(yīng)創(chuàng)建第二個子廣義，對應(yīng)創(chuàng)建第二個子廣義表表 ； 依次類推，直至剩余串為空串止。依次類推，直至剩余串為空串止。void CreateGList(Glist &L, String S) if (空串空串) L = NULL; / 創(chuàng)建空表創(chuàng)建空表 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(

32、sub, hsub); / 分別出子表串分別出子表串hsub=i if (!StrEmpty(sub) p-ptr.tp=(Glist)malloc(sizeof(GLNode); / 建下一個子表的表結(jié)點建下一個子表的表結(jié)點*(p-ptr.tp) p=p-ptr.tp; while (!StrEmpty(sub);p-ptr.tp = NULL; / 表尾為空表表尾為空表創(chuàng)建由串創(chuàng)建由串hsub定義的廣義表定義的廣義表p-ptr.hp;if (StrLength(hsub)=1) p-ptr.hp=(GList)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM

33、; p-ptr.hp-atom=hsub; / 創(chuàng)建單原子結(jié)點創(chuàng)建單原子結(jié)點else CreateGList(p-ptr.hp, hsub); /遞歸建廣義表遞歸建廣義表 假如某個問題的求解過程可以分成若干步進行，并且當(dāng)前這一步的解可以直接求得，則先先求求出出當(dāng)當(dāng)前前這這一一步步的的解解，對于余余下下的的問問題題，若問題的性質(zhì)和原問題類似，則又可遞遞歸歸求求解解。后置遞歸的設(shè)計思想為后置遞歸的設(shè)計思想為: 遞歸的終結(jié)形狀是，當(dāng)前的問題可以直接求解，對原問題而言，那么是已走到了求解的最后一步。鏈表是可以如此求解的一個典型例子。例如：編寫“刪除單鏈表中一切值為x 的數(shù)據(jù)元素的算法。1) 單鏈表是一

34、種順序構(gòu)造，必需從第一個結(jié)點起，逐個檢查每個結(jié)點的數(shù)據(jù)元素；分析分析:2) 從另一角度看，鏈表又是一個遞歸構(gòu)造，假設(shè) L 是線性鏈表 (a1, a2, , an) 的頭指針，那么 L-next是線性鏈表 (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

35、) / 刪除以刪除以L為頭指針的帶頭結(jié)點的單鏈表中為頭指針的帶頭結(jié)點的單鏈表中 / 一切值為一切值為x的數(shù)據(jù)元素的數(shù)據(jù)元素 if (L-next) if (L-next-data=x) p=L-next; L-next=p-next; free(p); delete(L, x); else delete(L-next, x); / delete刪除廣義表中一切元素為刪除廣義表中一切元素為x x的原子結(jié)點的原子結(jié)點分析分析: : 比較廣義表和線性表的構(gòu)造特點：比較廣義表和線性表的構(gòu)造特點：類似處：都是鏈表構(gòu)造。類似處：都是鏈表構(gòu)造。不同處：不同處：1)1)廣義表的數(shù)據(jù)元素能夠還是個廣義表的數(shù)據(jù)元

36、素能夠還是個 廣義表；廣義表； 2)2)刪除時，不僅要刪除原子結(jié)點，刪除時，不僅要刪除原子結(jié)點， 還需求刪除相應(yīng)的表結(jié)點。還需求刪除相應(yīng)的表結(jié)點。void Delete_GL(Glist&L, AtomType x) /刪除廣義表刪除廣義表L中一切值為中一切值為x的原子結(jié)點的原子結(jié)點 if (L) head = L-ptr.hp; / 調(diào)查第一個子表調(diào)查第一個子表 if (head-tag = Atom) & (head-atom = x) / 刪除原子項刪除原子項 x的情況的情況 else / 第一項沒有被刪除的情況第一項沒有被刪除的情況 / Delete_GL p=L; L

37、 = L-ptr.tp; / 修正指針free(head); / 釋放原子結(jié)點free(p); / 釋放表結(jié)點Delete_GL(L, x); / 遞歸處置剩余表項 1 L0 x 1 pL headif (head-tag = LIST) /該項為廣義該項為廣義表表 Delete_GL(head, x);Delete_GL(L-ptr.tp, x); / 遞歸處置剩余表項遞歸處置剩余表項 1 L0 a 1 1 headL-ptr.tp回溯法是一種回溯法是一種“窮舉窮舉方法。其根本思想為：方法。其根本思想為： 假設(shè)問題的解為 n 元組 (x1, x2, , xn)，其中 xi 取值于集合 Si。

38、 n 元組的子組 (x1, x2, , xi) (in)的一的一個合法規(guī)劃個合法規(guī)劃 / 時，輸出之。時，輸出之。 if (in) 輸出棋盤的當(dāng)前規(guī)劃輸出棋盤的當(dāng)前規(guī)劃; else for (j=1; jn) else while ( ! Empty(Si) 從從 Si 中取中取 xi 的一個值的一個值 viSi; if (x1, x2, , xi) 滿足約束條件滿足約束條件 B( i+1, n); / 繼續(xù)求下一個部分解繼續(xù)求下一個部分解 從從 Si 中刪除值中刪除值 vi; / B綜合幾點：綜合幾點：1. 對于含有遞歸特性的問題，最好設(shè)計對于含有遞歸特性的問題，最好設(shè)計遞歸方式的算法。但也

39、不要單純追求方遞歸方式的算法。但也不要單純追求方式，應(yīng)在算法設(shè)計的分析過程中式，應(yīng)在算法設(shè)計的分析過程中“就事就事論事論事。例如，在利用分割求解設(shè)計算。例如，在利用分割求解設(shè)計算法時，子問題和原問題的性質(zhì)一樣；或法時，子問題和原問題的性質(zhì)一樣；或者，問題的當(dāng)前一步處理之后，余下的者，問題的當(dāng)前一步處理之后，余下的問題和原問題性質(zhì)一樣，那么自然導(dǎo)致問題和原問題性質(zhì)一樣，那么自然導(dǎo)致遞歸求解。遞歸求解。2. 實現(xiàn)遞歸函數(shù)，目前必需利用實現(xiàn)遞歸函數(shù)，目前必需利用“棧棧。一個遞歸函數(shù)必定能改寫。一個遞歸函數(shù)必定能改寫為利用棧實現(xiàn)的非遞歸函數(shù)；反之，為利用棧實現(xiàn)的非遞歸函數(shù)；反之，一個用棧實現(xiàn)的非遞歸函

40、數(shù)可以改一個用棧實現(xiàn)的非遞歸函數(shù)可以改寫為遞歸函數(shù)。需求留意的是遞歸寫為遞歸函數(shù)。需求留意的是遞歸函數(shù)遞歸層次的深度決議所需存儲函數(shù)遞歸層次的深度決議所需存儲量的大小。量的大小。3. 分析遞歸算法的工具是遞歸樹，從分析遞歸算法的工具是遞歸樹，從遞歸樹上可以得到遞歸函數(shù)的各種相遞歸樹上可以得到遞歸函數(shù)的各種相關(guān)信息。例如：遞歸樹的深度即為遞關(guān)信息。例如：遞歸樹的深度即為遞歸函數(shù)的遞歸深度；遞歸樹上的結(jié)點歸函數(shù)的遞歸深度；遞歸樹上的結(jié)點數(shù)目恰為函數(shù)中的主要操作反復(fù)進展數(shù)目恰為函數(shù)中的主要操作反復(fù)進展的次數(shù)；假設(shè)遞歸樹蛻化為單支樹或的次數(shù)；假設(shè)遞歸樹蛻化為單支樹或者遞歸樹中含有很多一樣的結(jié)點，那者遞歸樹中含有很多一樣的結(jié)點，那么闡明該遞歸函數(shù)不適用。么闡明該遞歸函數(shù)不適用。 例如: n=3的梵塔算法中主要操作move的執(zhí)行次數(shù)可以利用以下遞歸樹進展分析:move(3, a, b, c)move(2, a, c, b)move(2, b, a, c)move(1, a, b, c)move(1, c, a, b)move(1, b, c,