【正文】 free(head)。 Delete_GL(L, x)。 對于已求得的部分解 (x1, x2, …, x i) ， 若在 添加 xi+1?Si+1 之后 仍然滿足約束條件 ， 則得到一個新的部分解 (x1, x2, …, x i+1) , 之后 繼續(xù) 添加 xi+2?Si+2 并檢查 之 。 按回溯法的定義，皇后問題 求解過程 為 : 解的初 始 值為空 ； 首先添加 x1=1, 之后添加 滿足條件的 x2=3， 由于對所有的 x3?{1,2, 3, 4}都不能找到滿足約束條件的部分解 (x1, x2, x3), 則 回溯到部分解 (x1), 重新添加滿足約束條件的 x2=4, 依次類推。 if (in) 輸出棋盤的當前布局 。 if (當前布局合法 ) Trial(i+1, n)。 if (x1, x2, …, x i) 滿足約束條件 B( i+1, n)。例如，在利用分割求解設計算法時，子問題和原問題的性質相同；或者，問題的當前一步解決之后，余下的問題和原問題性質相同，則自然導致遞歸求解。 3. 分析 遞歸算法的工具是 遞歸樹 ，從遞歸樹上可以得到遞歸函數(shù)的各種相關信息。 n n1 1 0 。 而計算斐波那契遞歸函數(shù)的遞歸樹中有很多重復出現(xiàn)的結點。 T = Trchild。 free(p)。L, ElemType x) { // L為帶頭結點的單鏈表的頭指針 p=Lnext。 p=prenext。 例如 : 假設解 n個圓盤的梵塔的執(zhí)行 時間為 T(n) 則遞歸方程為： T(n) = 2T(n1) + C， 初始條件為： T(0) = 0 1. 了解數(shù)組的兩種存儲表示方法 ，并掌握數(shù)組在以行為主的存儲結構中的地址計算方法 。 5. 學習利用分治法的算法設計思想編制遞歸算法的方法。 3. 了解稀疏矩陣的兩類壓縮存儲方法的特點和適用范圍 ， 領會以三元組表示稀疏矩陣時進行矩陣運算采用的處理方法 。 p=pnext。 while (p) { if (pdata=x) { prenext=pnext。 } else delete(Lnext, x)。L, ElemType x) { // L為無頭結點的單鏈表的頭指針 if (L) { if (Ldata=x) { p=L。 例如：先序遍歷二叉樹可以改寫為： void PreOrderTraverse( BiTree T) { While (T) { Visit(Tdata)。 例如 : 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) 上圖遞歸樹的中序序列即為圓盤的移動操作序列。 一個遞歸函數(shù)必定能改寫為利用棧實現(xiàn)的非遞歸函數(shù)；反之，一個用棧實現(xiàn)的非遞歸函數(shù)可以改寫為遞歸函數(shù)。 } } // B 綜合幾點： 1. 對于 含有遞歸特性 的問題，最好設計遞歸形式的算法。 } } // trial 回溯法求解的算法一般形式 : void B(int i, int n) { // 假設已求得滿足約束條件的部分解 (x1,..., xi1)， 本函 //數(shù)從 xi 起繼續(xù)搜索，直到求得整個解 (x1, x2, … x n)。 j=n。現(xiàn)從第 i 行起繼續(xù)為后續(xù)棋子選擇 // 滿足約束條件的位置。如此反復進行，直至求得滿足約束條件的問題的解，或者證明問題無解。其基本思想為 : 假設問題的解為 n 元組 (x1, x2, …, x n)， 其中 xi 取值于集合 Si。 // 釋放表結點 Delete_GL(L, x)。 (headatom == x)) { } // 刪除原子項 x的情況 else { }// 第一項沒有被刪除的情況 } } // Delete_GL … … … … p=L。 void Delete_GL(Glistamp。 } else delete(Lnext, x)。L, ElemType x) { // 刪除以 L為頭指針的帶頭結點的單鏈表中 // 所有值為 x的數(shù)據(jù)元素 if (Lnext) { if (Lnextdata==x) { p=Lnext。 例如 :編寫“ 刪除單鏈表中所有值為 x 的數(shù)據(jù)元素 ”的算法。 // 創(chuàng)建單原子結點 } else CreateGList(p, hsub)。 // 表尾為空表 創(chuàng)建由串 hsub定義的廣義表 p。 // 分離出子表串 hsub=?i if (!StrEmpty(sub) { p=new(sizeof(GLNode))。 p=L。 void CreateGList(Glist amp。 先看第一個子表和廣義表的關系 : 1 L 指向廣義表 的頭指針 指向第一個 子表的頭指針 再看相鄰兩個子表之間的關系 : 1 1 指向第 i+1個 子表的頭指針 指向第 i個 子表的頭指針 可見，兩者之間通過表結點相鏈接。 由于 S中的每個子串 ?i定義 L 的一個 子表 ，從而產(chǎn)生 n 個子問題，即分別由這 n個子串 (遞歸 )建立 n 個子表，再 組合 成一個廣義表。 等價于 CopyGList(newhp, L)。 // 復制單原子結點 else { } } // else return OK。T, Glist L) { if (!L) T = NULL。 } 例如 : pp pp pp pp pp pp 1 1 1 L … ?例二 復制廣義表 新的廣義表由新的表頭和表尾構成。 for (max=0, pp=L。 if (dep max) max = dep。 }。 // ATOM==0:原子 , LIST==1:子表 typedef struct GLNode { ElemTag tag。 3) 遍歷右子樹 。 例如 : 焚塔問題 : Hanoi(n, x, y, z) 可遞歸求解 Hanoi(n1, x, z, y) 將 n 個盤分成兩個子集 (1至 n1 和 n )，從而產(chǎn)生下列三個子問題 : 1) 將 1至 n1號盤從 x 軸移動至 y 軸 。 (PreOrderTraverse(Trchild, Visit)。 move(x, n, z)。 指向子表 2 的指針 指向子表 n 的指針 例如 : ? ls ((x)) LS=( a, (x,y), ((x)) ) a (x, y) 廣義表操作的遞歸函數(shù) 遞歸函數(shù) 一個 含直接或間接調用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個條件 : 1)在每一次調用自己時，必須是