第5單元非線性數(shù)據(jù)結(jié)構(gòu)圖主講：劉志強-資料下載頁

【導(dǎo)讀】描述和如何存放？任意兩點之間的路徑?學(xué)生和教師之間的關(guān)系?結(jié)構(gòu)的基礎(chǔ)上進行操作（增、刪、圖型數(shù)據(jù)結(jié)構(gòu)有哪些應(yīng)用？通過本單元學(xué)習(xí)，了解、掌握有關(guān)圖:. 有向圖、無向圖、連通圖、網(wǎng)。鄰接矩陣、鄰接表。深度優(yōu)先、廣度優(yōu)先遍歷。雜的非線性數(shù)據(jù)結(jié)構(gòu)。圖是對結(jié)點的前趨和后繼個數(shù)不加限制的數(shù)。圖論中有詳細論述和證明。現(xiàn)實生活中，圖的應(yīng)用范圍很廣泛，涉及：。其中：V={v1，v2，…,vn}是非空有窮的結(jié)點。集合;E是頂點偶對的集合。向圖，其偶對用表示，如圖G1所示。邊是無序的，可以看成是（Vx，弧是有序的，〈Vx，Vy〉表示從。弧的起始點稱為弧尾。則Ｖx、Ｖy互為鄰接點。則Ｖy是Ｖx的鄰接點，反之，不是。例如，G1中V2的度為3，V4的度為1。以某頂點為弧尾的弧的數(shù)目稱為該。中V1到V3的長度為1或2；而G2中1到4的長度為2。間都存在Vx到Vy，及從Vy到Vx的路徑，則稱G1是G的子圖。G=（V，E），G1=. 權(quán)通常用來表示從一個。頂點到另一個頂點的距離或費用。

　　

【正文】 LL、 RR、 LR和 RL 四種 。 3 5 7 9 20 下一頁 上一頁 停止放映 第 74 頁 LL平衡化處理 由于在 A的左子樹的左子樹上插入結(jié)點 ， 使A點失去平衡 ， 需進行一次 LL旋轉(zhuǎn) （ 順時針旋轉(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 示例 示意為： 下一頁 上一頁 停止放映 第 75 頁 RR平衡化處理 由于在 A的右子樹的右子樹上插入結(jié)點 ， 使 A點失去平衡 ， 需進行一次RR旋轉(zhuǎn) （ 逆時針旋轉(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 示例 示意為： 下一頁 上一頁 停止放映 第 76 頁 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é)點 ， 使 A點失去平衡 ， 需進行一次 LR旋轉(zhuǎn) （ 兩次旋轉(zhuǎn) 。先逆時針 ,再順時針旋轉(zhuǎn) ） 操作 。 示意為： 下一頁 上一頁 停止放映 第 77 頁 RL平衡化處理 由于在 A的右子樹的左子樹上插入結(jié)點 ， 使 A點失去平衡 ， 需進行一次 RL旋轉(zhuǎn) （ 兩次旋轉(zhuǎn) 。先順時針 ,再逆時針旋轉(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 示意為： 示例 下一頁 上一頁 停止放映 第 78 頁 平衡化處理舉例 有數(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) 示例 下一頁 上一頁 停止放映 第 79 頁 Huffman(哈夫曼）樹及應(yīng)用 Huffman樹的定義 構(gòu)造 Huffman樹 Huffman編碼 Huffman編碼的譯碼 下一頁 上一頁 停止放映 第 80 頁 Huffman樹的定義 Huffman樹也稱為最優(yōu)樹，是一類帶權(quán)路徑最短的二叉樹。 樹的帶權(quán)路徑長度定義為： WPL = ∑ wklk k = 1 n 其中： n 是樹中葉結(jié)點的個數(shù) wi 是第 i個結(jié)點的權(quán)值 li 是第 i個結(jié)點的路徑長度 下一頁 上一頁 停止放映 第 81 頁 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 √ 事實證明按哈夫曼樹構(gòu)造二叉樹，可得到很好的特性，應(yīng)用于實際問題，可提高處理效率。 下一頁 上一頁 停止放映 第 82 頁 應(yīng)用舉例 由統(tǒng)計規(guī)律可知，考試成績的分布符合正態(tài)分布： 1 1 0 分數(shù) 0～ 59 60 ～ 69 70 ～ 79 80 ～ 89 90 ～ 100 比例數(shù) 根據(jù)正態(tài)分布規(guī)律，在 60～ 90之間的分數(shù)占 85%，而不及格和優(yōu)秀是少數(shù)。 下一頁 上一頁 停止放映 第 83 頁 將百分制轉(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萬個數(shù)據(jù)，按 A的判定過程進行操作，約需比較 ，而按 B比較 ,則僅需 。 下一頁 上一頁 停止放映 第 84 頁 構(gòu)造 Huffman樹 構(gòu)造 Huffman樹算法步驟： Step1 將 n個帶權(quán)值 wi（ i≤n ）的結(jié)點構(gòu)成 n棵二叉樹的集合 T={T1， T2， …… ， Tn}，每棵二叉樹只有一個根結(jié)點。 Step2 在 T中選取兩個權(quán)值最小的結(jié)點作為左右子樹，構(gòu)成一個新的二叉樹，其根結(jié)點的權(quán)值取左右子樹權(quán)值之和； Step3 在 T中刪除這兩棵樹，將新構(gòu)成的樹加入到 T中； Step4 重復(fù) 2）、 3）步的操作，直到 T中只含一棵樹為止，該樹就是 Huffman樹。 下一頁 上一頁 停止放映 第 85 頁 構(gòu)造 Huffman樹舉例 以權(quán)值分別為 7， 5， 2， 4的結(jié)點 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 示例 下一頁 上一頁 停止放映 第 86 頁 Huffman編碼 編碼 ： 用二進制數(shù)的不同組合來表示字符的方法。 前綴編碼 ：一種非等長度的編碼 (任一個字符的編碼都不是另一個字符編碼的前綴 )。 a 0 b 0 1 c d 0 1 1 編碼： a（ 0） b（ 01） c（ 011） d（ 111） 方法約定： 1）左分支為‘ 0’ 2）右分支為‘ 1’ 3） 由葉到根 路徑上字符組成的二進制串就是該葉結(jié)點的編碼。 Huffman編碼 ：一種非等長度的編碼。以給定權(quán)值的結(jié)點構(gòu)造 Huffman樹，按二進制前綴編碼的方式構(gòu)成的編碼為 Huffman編碼。 下一頁 上一頁 停止放映 第 87 頁 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 下一頁 上一頁 停止放映 第 88 頁 Huffman編碼存儲結(jié)構(gòu) 由于 Huffman樹中沒有度為 1的結(jié)點，則 n個葉結(jié)點的 Huffman樹共有 2n1個結(jié)點。例如， 4個結(jié)點的 Huffman樹，共有 7個結(jié)點。因此可以用長度為 2n1的一維數(shù)組存放。 求 Huffman編碼： 從葉到根的編碼。因此要知道每個結(jié)點的父結(jié)點。 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 下一頁 上一頁 停止放映 第 89 頁 Huffman編碼的譯碼 從 Huffman編碼樹上不難看出，代碼全部在葉結(jié)點上，根據(jù) Huffman編碼，就能求出相應(yīng)的字符。該過程稱為?譯碼?。 譯碼是根據(jù) 從根到葉 的 Huffman編碼求相應(yīng)的字符。因此要知道每個結(jié)點的左右子結(jié)點。 例如，根據(jù)? 1111”，就能求出對應(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 下一頁 上一頁 停止放映 第 90 頁 作業(yè)、思考題 第 2章思考題： 18 第 2章作業(yè) 5～ 13 作業(yè)要求： – 作業(yè)命名方式為： 學(xué)號 .章數(shù) _序號 下一頁 上一頁 停止放映 第 91 頁 結(jié)束語 歡迎參加網(wǎng)上討論，網(wǎng)站的地址： ： // 我的 Email地址： 答疑安排： 星期 四 下午 4： 00～ 6： 00 謝謝，再見！