8935教學(xué)目標(biāo)-資料下載頁(yè)
2025-09-21 09:26本頁(yè)面
【導(dǎo)讀】通過(guò)本單元學(xué)習(xí)，了解、掌握有關(guān)圖:. 有向圖、無(wú)向圖、連通圖、網(wǎng)。鄰接矩陣、鄰接表。深度優(yōu)先、廣度優(yōu)先遍歷。圖是一種較之線性表和樹形結(jié)構(gòu)更為復(fù)雜。的非線性數(shù)據(jù)結(jié)構(gòu)。圖是對(duì)結(jié)點(diǎn)的前趨和后繼個(gè)數(shù)不加限制的。有關(guān)圖的理論，在“離散數(shù)學(xué)”。的圖論中有詳細(xì)論述和證明。討論圖在計(jì)算機(jī)中的實(shí)現(xiàn)和操作?，F(xiàn)實(shí)生活中，圖的應(yīng)用范圍很廣泛，涉及：。其中：V={v1，v2，……,vn}是非空有窮的結(jié)。點(diǎn)集合;E是頂點(diǎn)偶對(duì)的集合。例，圖G1=（V，E）。向圖，其偶對(duì)用表示，如圖G1所示。頂點(diǎn)間的關(guān)系可描述為頂點(diǎn)的偶對(duì)，也稱為頂點(diǎn)的邊。Vy），也可以看成是?；∈怯行虻?，〈Vx，Vy〉表示從。弧的起始點(diǎn)稱為弧尾。如圖G1、G2中的Ｖ1、Ｖ2，1，2。則Ｖx、Ｖy互為鄰接點(diǎn)。例如，G1中V2的度為3，V4的度為1。以某頂點(diǎn)為弧尾的弧的數(shù)目稱為該頂點(diǎn)的。,Vn,Vy)稱為從Vx到Vy的路徑。中V1到V3的長(zhǎng)度為1或2；而G2中1到4的長(zhǎng)度為2。徑，則稱此圖是強(qiáng)連通圖。如果該子圖是樹，則稱為G的生成樹。
【正文】 需進(jìn)行一次 LL旋轉(zhuǎn) （ 順時(shí)針旋轉(zhuǎn) ） 操作 。 程序?qū)崿F(xiàn)為： b = a?.lc a?.lc = b?.rc b?.rc = a a?.bf = 0 b?.bf = 0 b為子樹的新根 A B C LL B C A 示例 示意為： RR平衡化處理 由于在 A的右子樹的右子樹上插入結(jié)點(diǎn) ， 使 A點(diǎn)失去平衡 ， 需進(jìn)行一次RR旋轉(zhuǎn) （ 逆時(shí)針旋轉(zhuǎn) ）操作 。 程序?qū)崿F(xiàn)為： b = a?.rc a?.rc = b?.lc b?.lc = a a?.bf = 0 b?.bf = 0 b為子樹新根 A B C RR B A C 示例 示意為： LR平衡化處理 程序?qū)崿F(xiàn)為： b = a?.lc、 c = b?.rc、 a?.lc = c?.rc b?.rc = c?.lc、 c?.lc = b、 c?.rc = a A B C C B A A C B 示例 由于在 A的左子樹的右子樹上插入結(jié)點(diǎn) ， 使 A點(diǎn)失去平衡 ， 需進(jìn)行一次 LR旋轉(zhuǎn) （ 兩次旋轉(zhuǎn) 。先逆時(shí)針 ,再順時(shí)針旋轉(zhuǎn) ） 操作 。 示意為： RL平衡化處理 由于在 A的右子樹的左子樹上插入結(jié)點(diǎn) ， 使 A點(diǎn)失去平衡 ，需進(jìn)行一次 RL旋轉(zhuǎn) （ 兩次旋轉(zhuǎn) 。先順時(shí)針 ,再逆時(shí)針旋轉(zhuǎn) ）操作 。 A B C C A B A C B 程序?qū)崿F(xiàn)為： b = a?.rc、 c = b?.lc、 a?.rc = c?.lc b?.lc = c?.rc、 c?.lc = a、 c?.rc = b 示意為： 示例 平衡化處理舉例 有數(shù)據(jù)序列 {13,24,37,90,53} ? 插入 13,樹是平衡的 。 ? 插入 24,樹仍為平衡 。 ? 插入 37,樹不再平衡 , 執(zhí)行 RR旋轉(zhuǎn) 。 ? 插入 90,樹仍平衡 。 ? 插入 53,失去平衡 , 執(zhí)行 RL旋轉(zhuǎn) . 13 (1) 13 24 (2) 13 24 37 37 13 24 (3) 24 13 37 90 (4) 24 13 37 90 53 24 13 37 53 90 24 13 53 37 90 (5) 示例 Huffman(哈夫曼）樹及應(yīng)用 ? Huffman樹的定義 ? 構(gòu)造 Huffman樹 ? Huffman編碼 ? Huffman編碼的譯碼 Huffman樹的定義 ? Huffman樹也稱為最優(yōu)樹，是一類帶權(quán)路徑最短的二叉樹。 ? 樹的帶權(quán)路徑長(zhǎng)度定義為： WPL = ∑ wklk k = 1 n 其中： n 是樹中葉結(jié)點(diǎn)的個(gè)數(shù) wi 是第 i個(gè)結(jié)點(diǎn)的權(quán)值 li 是第 i個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度 Huffman樹舉例 ? 以下有三棵樹： （ a） （ b） （ c） a b c d a b c d a c b d 7 7 7 5 5 5 2 2 2 4 4 4 WPLa =7x2+5x2+2x2+4x2 = 36 WPLb =7x3+5x3+2x1+4x2 = 46 WPLc = 7x1+5x2+2x3+4x3 = 35 √ ? 事實(shí)證明按哈夫曼樹構(gòu)造二叉樹，可得到很好的特性，應(yīng)用于實(shí)際問題，可提高處理效率。 應(yīng)用舉例 ? 由統(tǒng)計(jì)規(guī)律可知，考試成績(jī)的分布符合正態(tài)分布： 1 1 0 分?jǐn)?shù) 0～ 59 60 ～ 69 70 ～ 79 80 ～ 89 90 ～ 100 比例數(shù) ? 根據(jù)正態(tài)分布規(guī)律，在 60 ～ 90之間的分?jǐn)?shù)占 85%，而不及格和優(yōu)秀是少數(shù)。 將百分制轉(zhuǎn)換成五分制 ? 判定樹比較： a60? a70? a80? a90? 不及格 及格 中等 良好 優(yōu)秀 Y Y Y Y N N N N a80? a70? a90? a60? 不及格 優(yōu)秀 良好 中等 中等 及格 不及格 Y Y Y N N N N Y (A) (B) ? 若輸入 1萬(wàn)個(gè)數(shù)據(jù)，按 A的判定過(guò)程進(jìn)行操作，約需比較 萬(wàn)次，而按 B比較 ,則僅需 。 構(gòu)造 Huffman樹 ? 構(gòu)造 Huffman樹算法步驟： – 1）將 n個(gè)帶權(quán)值 wi（ i≤n）的結(jié)點(diǎn)構(gòu)成 n棵二叉樹的集合 T={T1， T2， …… ， Tn}，每棵二叉樹只有一個(gè)根結(jié)點(diǎn)。 – 2）在 T中選取兩個(gè)權(quán)值最小的結(jié)點(diǎn)作為左右子樹，構(gòu)成一個(gè)新的二叉樹，其根結(jié)點(diǎn)的權(quán)值取左右子樹權(quán)值之和； – 3）在 T中刪除這兩棵樹，將新構(gòu)成的樹加入到 T中； – 4）重復(fù) 2）、 3）步的操作，直到 T中只含一棵樹為止，該樹就是 Huffman樹。 構(gòu)造 Huffman樹舉例 ? 以權(quán)值分別為 7， 5， 2， 4的結(jié)點(diǎn) a、 b、 c、 d構(gòu)造 Huffman樹。T= { a b c d } c d T3 2 4 6 b T3 T2 6 5 11 b T2 6 5 11 c d 2 4 18 a T2 7 11 T1 6 18 a 7 T1 b T3 T2 5 11 18 a 7 T1 b 5 11 c d 2 6 4 （ d） T={ T1 } （ c） T= { a T2 } （ b） T= { a b T3 } （ a） T= { a b c d } 代入 T2 代入T3 示例 Huffman編碼 ? 編碼：用二進(jìn)制數(shù)的不同組合來(lái)表示字符的方法。 ? 前綴編碼：一種非等長(zhǎng)度的編碼 (任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴 )。 a 0 b 0 1 c d 0 1 1 編碼： A（ 0） B（ 01） C（ 011） D（ 111） 方法約定： 1）左分支為‘ 0’ 2）右分支為‘ 1’ 3）由葉到根路徑上字符組成的二進(jìn)制串就是該葉結(jié)點(diǎn)的編碼。 ? Huffman編碼：一種非等長(zhǎng)度的編碼。以給定權(quán)值的結(jié)點(diǎn)構(gòu)造 Huffman樹，按二進(jìn)制前綴編碼的方式構(gòu)成的編碼為 Huffman編碼。 Huffman編碼舉例 ? 在某系統(tǒng)的通信聯(lián)絡(luò)中可能出現(xiàn) 8種字符，其頻率分別為 、 、 、 、 、 、 ，設(shè)權(quán)值分別為 {5， 29， 7， 8， 14，23， 3， 11}， n=8，其 Huffman樹為： 0 0 0 0 0 0 0 1 1 1 1 1 1 1 5 3 7 8 14 29 11 23 42 58 100 Huffman編碼為： A 5 0110 B 29 01 C 7 0111 D 8 1111 E 14 011 F 23 00 G 3 1110 H 11 010 Huffman編碼存儲(chǔ)結(jié)構(gòu) ? 由于 Huffman樹中沒有度為 1的結(jié)點(diǎn)，則 n個(gè)葉結(jié)點(diǎn)的 Huffman樹共有 2n1個(gè)結(jié)點(diǎn)。例如， 4個(gè)結(jié)點(diǎn)的Huffman樹，共有 7個(gè)結(jié)點(diǎn)。因此可以用長(zhǎng)度為 2n1的一維數(shù)組存放。 ? 求 Huffman編碼： 從葉到根的編碼。因此要知道每個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)。 0 0 0 0 0 0 0 1 1 1 1 1 1 1 5 3 7 8 14 29 11 23 42 58 100 Huffman編碼為： A 5 0110 B 29 01 C 7 0111 D 8 1111 E 14 011 F 23 00 G 3 1110 H 11 010 Huffman編碼的譯碼 ? 從 Huffman編碼樹上不難看出，代碼全部在葉結(jié)點(diǎn)上，根據(jù) Huffman編碼，就能求出相應(yīng)的字符。該過(guò)程稱為“譯碼”。 ? 譯碼是根據(jù)從根到葉的 Huffman編碼求相應(yīng)的字符。因此要知道每個(gè)結(jié)點(diǎn)的左右子結(jié)點(diǎn)。 ? 例如，根據(jù)“ 1111”，就能求出對(duì)應(yīng)的字符是“ 8”。 0 0 0 0 0 0 0 1 1 1 1 1 1 1 5 3 7 8 14 29 11 23 42 58 100 作業(yè)題 P89 1 1 20
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1