【文章內容簡介】 b, c)) ) = ( ) Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ) Head( ( c ) ) = c Tail( ( c ) ) = ( ) ? 結構的創(chuàng)建和銷毀 InitGList(amp。L)。 DestroyGList(amp。L)。 CreateGList(amp。L, S)。 CopyGList(amp。T, L)。 基本操作 ? 狀態(tài)函數(shù) GListLength(L)。 GListDepth(L)。 GListEmpty(L)。 GetHead(L)。 GetTail(L)。 ? 插入和刪除操作 InsertFirst_GL(amp。L, e)。 DeleteFirst_GL(amp。L, amp。e)。 ? 遍歷 Traverse_GL(L, Visit())。 廣義表的表示方法 通常采用頭、尾指針的鏈表結構 表結點 : 原子結點： tag=0 data tag=1 hp tp 1) 表頭、表尾分析法 : 構造存儲結構的兩種分析方法 : 若表頭為原子，則為 空表 ls = NIL 非空表 ls tag=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 ) ( ) 1 L = ( )0 a 1 1 1 1 1 0 x ???( ) x 1 1 1 ls … ?2) 子表分析法 : 若子表為原子，則為 空表 ls=NIL 非空表 指向子表 1 的指針 tag=0 data 否則，依次類推。 指向子表 2 的指針 指向子表 n 的指針 例如 : ? ls ((x)) LS=( a, (x,y), ((x)) ) a (x, y) 廣義表操作的遞歸函數(shù) 遞歸函數(shù) 一個 含直接或間接調用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個條件 : 1)在每一次調用自己時，必須是 (在某 種意義上 )更接近于解 。 2)必須有一個 終止 處理或計算的 準則 。 例如 : 梵塔的遞歸函數(shù) void hanoi (int n, char x, char y, char z) { if (n==1) move(x, 1, z)。 else { hanoi(n1, x, z, y)。 move(x, n, z)。 hanoi(n1, y, x, z)。 } } 二叉樹的遍歷 void PreOrderTraverse( BiTree T,void (Visit)(BiTree P)) { if (T) { Visit(Tdata)。 (PreOrderTraverse(Tlchild, Visit)。 (PreOrderTraverse(Trchild, Visit)。 } } // PreOrderTraverse 一、分治法 (Divide and Conquer) (又稱分割求解法 ) 如何設計遞歸函數(shù) ？ 二、后置遞歸法 (Postponing the work) 三、回溯法 (Backtracking) 對于一個 輸入規(guī)模為 n 的函數(shù)或問題， 用某種方法把輸入 分割成 k(1k≤ n)個子集 ， 從而 產生 l 個子問題 ， 分別求解 這 l 個問題， 得出 l 個問題的子解 ，再用某種方法把它們 組合成原來問題的解 。若子問題還相當大， 則可以反復使用分治法，直至最后所分得 的子問題足夠小，以至可以直接求解為止。 分治法 的設計思想為 : 在利用分治法求解時，所得子問題的類型常常和原問題相同，因而很自然地導致遞歸求解。 例如 : 焚塔問題 : Hanoi(n, x, y, z) 可遞歸求解 Hanoi(n1, x, z, y) 將 n 個盤分成兩個子集 (1至 n1 和 n )，從而產生下列三個子問題 : 1) 將 1至 n1號盤從 x 軸移動至 y 軸 。 3) 將 1至 n1號盤從 y軸移動至 z軸 。 2) 將 n號盤從 x 軸移動至 z 軸 。 可遞歸求解 Hanoi(n1, x, z, y) 又如 : 遍歷二叉樹 : Traverse(BT) 可遞歸求解 Traverse(LBT) 將 n 個結點分成三個子集 (根結點、左子樹 和右子樹 )，從而產生下列三個子問題 : 1) 訪問根結點 。 3) 遍歷右子樹 。 2) 遍歷左子樹 。 可遞歸求解 Traverse(RBT) 廣義表從結構上可以分解成 廣義表 = 表頭 + 表尾 或者 廣義表 = 子表 1 + 子表 2 + + 子表 n 因此常利用分治法求解之。 算法設計中的關鍵問題是， 如何將 l 個子問題的解組合成原問題的解。 廣義表的頭尾鏈表存儲表示： typedef enum {ATOM, LIST} ElemTag。 // ATOM==0:原子 , LIST==1:子表 typedef struct GLNode { ElemTag tag。 // 標志域 union{ AtomType atom。 // 原子結點的數(shù)據(jù)域 struct {struct GLNode *hp, *tp。} ptr。 }。 } *GList tag=1 hp tp ptr 表結點 例一 求廣義表的深度 例二 復制廣義表 例三 創(chuàng)建廣義表的存儲結構 廣義表的深度 =Max {子表的深度 } +1 例一 求廣義表的深度 可以直接求解的兩種簡單情況為 : 空表的深度 = 1 原子的深度 = 0 將廣義表分解成 n 個子表，分別 (遞歸 )求得每個子表的深度 , int GlistDepth(Glist L) { // 返回指針 L所指的廣義表的深度 for (max=0, pp=L。 pp。 pp=pp){ dep = GlistDepth(pp)。 if (dep max) max = dep。 } return max + 1。 } // GlistDepth if (!L) return 1。 if (Ltag == ATOM) return 0。 for (max=0, pp=L。 pp。 pp=pp){ dep = GlistDepth(pp)。 if (dep max) max = dep。 } 例如 : pp pp pp pp pp pp 1 1 1 L … ?例二 復制廣義表 新的