數(shù)據(jù)結(jié)構(gòu)ppt課件chap(編輯修改稿)
2025-08-17 22:05 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 b, c)) ) = ( ) Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ) Head( ( c ) ) = c Tail( ( c ) ) = ( ) ? 結(jié)構(gòu)的創(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())。 廣義表的表示方法 通常采用頭、尾指針的鏈表結(jié)構(gòu) 表結(jié)點(diǎn) : 原子結(jié)點(diǎn)： tag=0 data tag=1 hp tp 1) 表頭、表尾分析法 : 構(gòu)造存儲(chǔ)結(jié)構(gòu)的兩種分析方法 : 若表頭為原子，則為 空表 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ù) 一個(gè) 含直接或間接調(diào)用本函數(shù)語(yǔ)句的函數(shù)被稱之為遞歸函數(shù)，它必須滿足以下兩個(gè)條件 : 1)在每一次調(diào)用自己時(shí)，必須是 (在某 種意義上 )更接近于解 。 2)必須有一個(gè) 終止 處理或計(jì)算的 準(zhǔn)則 。 例如 : 梵塔的遞歸函數(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è)計(jì)遞歸函數(shù) ？ 二、后置遞歸法 (Postponing the work) 三、回溯法 (Backtracking) 對(duì)于一個(gè) 輸入規(guī)模為 n 的函數(shù)或問題， 用某種方法把輸入 分割成 k(1k≤ n)個(gè)子集 ， 從而 產(chǎn)生 l 個(gè)子問題 ， 分別求解 這 l 個(gè)問題， 得出 l 個(gè)問題的子解 ，再用某種方法把它們 組合成原來問題的解 。若子問題還相當(dāng)大， 則可以反復(fù)使用分治法，直至最后所分得 的子問題足夠小，以至可以直接求解為止。 分治法 的設(shè)計(jì)思想為 : 在利用分治法求解時(shí)，所得子問題的類型常常和原問題相同，因而很自然地導(dǎo)致遞歸求解。 例如 : 焚塔問題 : Hanoi(n, x, y, z) 可遞歸求解 Hanoi(n1, x, z, y) 將 n 個(gè)盤分成兩個(gè)子集 (1至 n1 和 n )，從而產(chǎn)生下列三個(gè)子問題 : 1) 將 1至 n1號(hào)盤從 x 軸移動(dòng)至 y 軸 。 3) 將 1至 n1號(hào)盤從 y軸移動(dòng)至 z軸 。 2) 將 n號(hào)盤從 x 軸移動(dòng)至 z 軸 。 可遞歸求解 Hanoi(n1, x, z, y) 又如 : 遍歷二叉樹 : Traverse(BT) 可遞歸求解 Traverse(LBT) 將 n 個(gè)結(jié)點(diǎn)分成三個(gè)子集 (根結(jié)點(diǎn)、左子樹 和右子樹 )，從而產(chǎn)生下列三個(gè)子問題 : 1) 訪問根結(jié)點(diǎn) 。 3) 遍歷右子樹 。 2) 遍歷左子樹 。 可遞歸求解 Traverse(RBT) 廣義表從結(jié)構(gòu)上可以分解成 廣義表 = 表頭 + 表尾 或者 廣義表 = 子表 1 + 子表 2 + + 子表 n 因此常利用分治法求解之。 算法設(shè)計(jì)中的關(guān)鍵問題是， 如何將 l 個(gè)子問題的解組合成原問題的解。 廣義表的頭尾鏈表存儲(chǔ)表示： typedef enum {ATOM, LIST} ElemTag。 // ATOM==0:原子 , LIST==1:子表 typedef struct GLNode { ElemTag tag。 // 標(biāo)志域 union{ AtomType atom。 // 原子結(jié)點(diǎn)的數(shù)據(jù)域 struct {struct GLNode *hp, *tp。} ptr。 }。 } *GList tag=1 hp tp ptr 表結(jié)點(diǎn) 例一 求廣義表的深度 例二 復(fù)制廣義表 例三 創(chuàng)建廣義表的存儲(chǔ)結(jié)構(gòu) 廣義表的深度 =Max {子表的深度 } +1 例一 求廣義表的深度 可以直接求解的兩種簡(jiǎn)單情況為 : 空表的深度 = 1 原子的深度 = 0 將廣義表分解成 n 個(gè)子表，分別 (遞歸 )求得每個(gè)子表的深度 , 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 … ?例二 復(fù)制廣義表 新的
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1