數(shù)據(jù)結(jié)構(gòu)ppt課件chap-預(yù)覽頁
【正文】 其中： ?i 或為原子 或為廣義表 例如 : A = ( ) F = (d, (e)) D = ((a,(b,c)), F) C = (A, D, F) B = (a, B) = (a, (a, (a, ??? , ) ) ) 廣義表是一個 多層次 的 線性結(jié)構(gòu) 例如： D=(E, F) 其中 : E=(a, (b, c)) F=(d, (e)) D E F a ( ) d ( ) b c e 廣義表 LS = ( ?1, ?2, …, ?n )的結(jié)構(gòu)特點 : 1) 廣義表中的數(shù)據(jù)元素有相對 次序 。 “空表”的深度為 1 。 6) 任何一個 非空廣義表 LS = ( ?1, ?2, …, ?n) 均可分解為 表頭 Head(LS) = ?1 和 表尾 Tail(LS) = ( ?2, …, ?n) 兩部分 例如 : D = ( E, F ) = ((a, (b, c))， F ) Head( D ) = E Tail( D ) = ( F ) Head( E ) = a Tail( E ) = ( ( b, c) ) Head( (( b, c)) ) = ( b, c) Tail( (( b, c)) ) = ( ) Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ) Head( ( c ) ) = c Tail( ( c ) ) = ( ) ? 結(jié)構(gòu)的創(chuàng)建和銷毀 InitGList(amp。 CreateGList(amp。 基本操作 ? 狀態(tài)函數(shù) GListLength(L)。 GetTail(L)。L, amp。 例如 :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 否則，依次類推。 else { hanoi(n1, x, z, y)。 (PreOrderTraverse(Tlchild, Visit)。 分治法 的設(shè)計思想為 : 在利用分治法求解時，所得子問題的類型常常和原問題相同，因而很自然地導(dǎo)致遞歸求解。 可遞歸求解 Hanoi(n1, x, z, y) 又如 : 遍歷二叉樹 : Traverse(BT) 可遞歸求解 Traverse(LBT) 將 n 個結(jié)點分成三個子集 (根結(jié)點、左子樹 和右子樹 )，從而產(chǎn)生下列三個子問題 : 1) 訪問根結(jié)點 。 廣義表的頭尾鏈表存儲表示： typedef enum {ATOM, LIST} ElemTag。} ptr。 pp=pp){ dep = GlistDepth(pp)。 if (Ltag == ATOM) return 0。 if (dep max) max = dep。 將廣義表分解成表頭和表尾兩部分，分別 (遞歸 )復(fù)制求得新的表頭和表尾， 若 ls= NIL 則 newls = NIL 否則 構(gòu)造結(jié)點 newls, 由 表頭 ls 復(fù)制得 newhp 由 表尾 ls 復(fù)制得 newtp 并使 newls = newhp, newls = newtp 復(fù)制求廣義表的算法描述如下 : Status CopyGList(Glist amp。 if (Ltag == ATOM) Tatom = Latom。 // 復(fù)制求得表尾 T 的一個副本 L 語句 CopyGList(T, L)。 假設(shè)以字符串 S = ?(?1, ?2, ???, ?n )? 的形式定義廣義表 L，建立相應(yīng)的存儲結(jié)構(gòu) 。 如何由子表組合成一個廣義表？ 首先分析廣義表和子表在存儲結(jié)構(gòu)中的關(guān)系。 依次類推，直至剩余串為空串止。 // 生成表結(jié)點 Ltag=List。 do { sever(sub, hsub)。 p = NULL。 patom=hsub。 鏈表是可以如此求解的一個典型例子。 a1 a2 a3 an … ? L 例如 : a1 a2 a3 an ? L a1 a2 a3 an ? L 已知下列鏈表 1) “a1=x”, 則 L 仍為刪除 x 后的鏈表頭指針 2) “a1≠x”, 則余下問題是考慮以 Lnext 為頭指針的鏈表 … … Lnext Lnext=pnext p=Lnext void delete(LinkList amp。 delete(L, x)。 2)刪除時，不僅要刪除原子結(jié)點， 還需要刪除相應(yīng)的表結(jié)點。amp。 // 釋放原子結(jié)點 free(p)。 // 遞歸 處理剩余表項 1 L 0 a 1 1 head L 回溯法 是一種“ 窮舉 ”方法。 若對于 所有 取值于集合 Si+ 1的 xi+1都不能得到新的滿足約束條件的部分解 (x1,x2, ? ??， xi + 1 ) ，則從當(dāng)前子組中 刪去 xi, 回溯到前一個部分解 (x1,x2, ? ? ? , xi 1 ) ， 重新添加 那些值集 Si中尚未考察過的 xi，看是否滿足約束條件。 void Trial(int i, int n) { // 進入本函數(shù)時，在 n n棋盤前 i1行已放置了互不攻 // 擊的 i1個棋子。 else for (j=1。 移去第 i 行第 j 列的棋子 。 // 繼續(xù)求下一個部分解 從 Si 中刪除值 vi。 2. 實現(xiàn) 遞歸函數(shù)，目前必須利用“ 棧 ”。例如： 遞歸樹的深度即為遞歸函數(shù)的 遞歸深度 ；遞歸樹上的結(jié)點數(shù)目恰為函數(shù)中的主要操作 重復(fù)進行的次數(shù) ； 若遞歸樹蛻化為 單支樹 或者遞歸樹中 含有很多相同的結(jié)點 ，則表明該遞歸函數(shù)不適用 。 4. 遞歸函數(shù)中的 尾遞歸 容易消除。 } } // PreOrderTraverse void delete(LinkList amp。 delete(L, x)。 pre=L。 } else { pre=p。 2. 掌握對特殊矩陣進行壓縮存儲時的下標(biāo)變換公式 。
電大資料相關(guān)推薦
鄂ICP備17016276號-1