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