【正文】 ee(p)。 // 釋放表結點 Delete_GL(L, x)。 // 遞歸處理剩余表項 1 L 0 x 1 p L head if (headtag == LIST) //該項為廣義表 Delete_GL(head, x)。 Delete_GL(L, x)。 // 遞歸 處理剩余表項 1 L 0 a 1 1 head L 回溯法 是一種“ 窮舉 ”方法。其基本思想為 : 假設問題的解為 n 元組 (x1, x2, …, x n)， 其中 xi 取值于集合 Si。 n 元組的子組 (x1, x2, …, x i) (in) 稱為部分解，應滿足一定的約束條件。 對于已求得的部分解 (x1, x2, …, x i) ， 若在 添加 xi+1?Si+1 之后 仍然滿足約束條件 ， 則得到一個新的部分解 (x1, x2, …, x i+1) , 之后 繼續(xù) 添加 xi+2?Si+2 并檢查 之 。 若對于 所有 取值于集合 Si+ 1的 xi+1都不能得到新的滿足約束條件的部分解 (x1,x2, ? ??， xi + 1 ) ，則從當前子組中 刪去 xi, 回溯到前一個部分解 (x1,x2, ? ? ? , xi 1 ) ， 重新添加 那些值集 Si中尚未考察過的 xi，看是否滿足約束條件。如此反復進行，直至求得滿足約束條件的問題的解，或者證明問題無解。例一、皇后問題求解 設四皇后 問題的解 為 (x1, x2, x3, x4), 其中 : xi (i=1,2,3,4) ? Si={1, 2, 3, 4} 約束條件 為 : 其中 任意兩個 xi 和 xj不能位于棋盤的同行、同列及同對角線。 按回溯法的定義，皇后問題 求解過程 為 : 解的初 始 值為空 ； 首先添加 x1=1, 之后添加 滿足條件的 x2=3， 由于對所有的 x3?{1,2, 3, 4}都不能找到滿足約束條件的部分解 (x1, x2, x3), 則 回溯到部分解 (x1), 重新添加滿足約束條件的 x2=4, 依次類推。 void Trial(int i, int n) { // 進入本函數(shù)時，在 n n棋盤前 i1行已放置了互不攻 // 擊的 i1個棋子?，F(xiàn)從第 i 行起繼續(xù)為后續(xù)棋子選擇 // 滿足約束條件的位置。當求得 (in)的一個合法布局 // 時，輸出之。 if (in) 輸出棋盤的當前布局 。 else for (j=1。 j=n。 ++j) { 在第 i 行第 j 列放置一個棋子 。 if (當前布局合法 ) Trial(i+1, n)。 移去第 i 行第 j 列的棋子 。 } } // trial 回溯法求解的算法一般形式 : void B(int i, int n) { // 假設已求得滿足約束條件的部分解 (x1,..., xi1)， 本函 //數(shù)從 xi 起繼續(xù)搜索，直到求得整個解 (x1, x2, … x n)。 if (in) else while ( ! Empty(Si)) { 從 Si 中取 xi 的一個值 vi?Si。 if (x1, x2, …, x i) 滿足約束條件 B( i+1, n)。 // 繼續(xù)求下一個部分解 從 Si 中刪除值 vi。 } } // B 綜合幾點： 1. 對于 含有遞歸特性 的問題，最好設計遞歸形式的算法。 但也 不要單純追求形式 ，應在算法設計的分析過程中“就事論事”。例如，在利用分割求解設計算法時，子問題和原問題的性質相同；或者，問題的當前一步解決之后，余下的問題和原問題性質相同，則自然導致遞歸求解。 2. 實現(xiàn) 遞歸函數(shù)，目前必須利用“ 棧 ”。 一個遞歸函數(shù)必定能改寫為利用棧實現(xiàn)的非遞歸函數(shù)；反之，一個用棧實現(xiàn)的非遞歸函數(shù)可以改寫為遞歸函數(shù)。需要注意的是遞歸函數(shù)遞歸層次的深度決定所需存儲量的大小。 3. 分析 遞歸算法的工具是 遞歸樹 ，從遞歸樹上可以得到遞歸函數(shù)的各種相關信息。例如： 遞歸樹的深度即為遞歸函數(shù)的 遞歸深度 ；遞歸樹上的結點數(shù)目恰為函數(shù)中的主要操作 重復進行的次數(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, a) move(1, a, b, c) 上圖遞歸樹的中序序列即為圓盤的移動操作序列。 如 : 求 n!的遞歸函數(shù)的遞歸樹已退化為一個單枝樹 。 n n1 1 0 。 F5 F4 F3 F3 F2 F2 F1 F1 F0 F1 F0 。 而計算斐波那契遞歸函數(shù)的遞歸樹中有很多重復出現(xiàn)的結點。 4. 遞歸函數(shù)中的 尾遞歸 容易消除。 例如：先序遍歷二叉樹可以改寫為： void PreOrderTraverse( BiTree T) { While (T) { Visit(Tdata)。 PreOrderTraverse(Tlchild)。 T = Trchild。 } } // PreOrderTraverse void delete(LinkList amp。L, ElemType x) { // L為無頭結點的單鏈表的頭指針 if (L) { if (Ldata=x) { p=L。 L=Lnext。 free(p)。 delete(L, x)。 } else delete(Lnext, x)。 } } 又如 : void delete(LinkList amp。L, ElemType x) { // L為帶頭結點的單鏈表的頭指針 p=Lnext。 pre=L。 while (p) { if (pdata=x) { prenext=pnext。 free(p)。 p=prenext。 } else { pre=p。 p=pnext。 } } } 可改寫為 5. 可以用 遞歸方程 來表述遞歸函數(shù)的 時間性能 。 例如 : 假設解 n個圓盤的梵塔的執(zhí)行 時間為 T(n) 則遞歸方程為： T(n) = 2T(n1) + C， 初始條件為： T(0) = 0 1. 了解數(shù)組的兩種存儲表示方法 ，并掌握數(shù)組在以行為主的存儲結構中的地址計算方法 。 2. 掌握對特殊矩陣進行壓縮存儲時的下標變換公式 。 3. 了解稀疏矩陣的兩類壓縮存儲方法的特點和適用范圍 ， 領會以三元組表示稀疏矩陣時進行矩陣運算采用的處理方法 。 4. 掌握廣義表的結構特點及其存儲表示方法，讀者可根據自己的習慣熟練掌握任意一種結構的鏈表，學會對非空廣義表進行分解的兩種分析方法：即可將一個非空廣義表分解為表頭和表尾兩部分或者分解為 n個子表。 5. 學習利用分治法的算法設計思想編制遞歸算法的方法。