精品數(shù)據(jù)結(jié)構(gòu)哈夫曼樹(shù)及其應(yīng)用

1、1065865姓名姓名 學(xué)號(hào)學(xué)號(hào) 成績(jī)成績(jī) 班級(jí)班級(jí) 李紅李紅 9761059 95 機(jī)機(jī)97.6 abcdefg2021-11-322.5.3哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用1、哈夫曼樹(shù)、哈夫曼樹(shù) 樹(shù)的路徑長(zhǎng)度的概念：樹(shù)的路徑長(zhǎng)度的概念： 從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支數(shù)從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支數(shù)目稱(chēng)為這對(duì)結(jié)點(diǎn)之間的路徑長(zhǎng)度。目稱(chēng)為這對(duì)結(jié)點(diǎn)之間的路徑長(zhǎng)度。 樹(shù)的路徑長(zhǎng)度是從樹(shù)的根到每一結(jié)點(diǎn)的樹(shù)的路徑長(zhǎng)度是從樹(shù)的根到每一結(jié)點(diǎn)的路徑長(zhǎng)度之和。路徑長(zhǎng)度之和。2021-11-331 12 2453 367pl=0+1+1+2+2+2+2=10樹(shù)的路徑長(zhǎng)度用樹(shù)的路徑長(zhǎng)度用plpl表示。表示。

2、2021-11-341 12 2453 367pl=0+1+1+2+2+2+2=101 12 245c67pl=0+1+1+2+2+3+3=12樹(shù)的路徑長(zhǎng)度用樹(shù)的路徑長(zhǎng)度用plpl表示。表示。2021-11-35 結(jié)點(diǎn)帶權(quán)的路徑長(zhǎng)度：結(jié)點(diǎn)帶權(quán)的路徑長(zhǎng)度： 從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。從該結(jié)點(diǎn)到樹(shù)根之間的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)的帶權(quán)路徑長(zhǎng)度： 樹(shù)中葉子結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度之和。樹(shù)中葉子結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度之和。 abcd7524wpl=7*2+5*2+2*2+4*2=362021-11-36樹(shù)的帶權(quán)路徑長(zhǎng)度記作：樹(shù)的帶權(quán)路徑長(zhǎng)度記作： 其中：其中：wk為樹(shù)中每個(gè)

3、葉子結(jié)點(diǎn)的權(quán)；為樹(shù)中每個(gè)葉子結(jié)點(diǎn)的權(quán)； l k為每個(gè)葉子結(jié)點(diǎn)到根的路徑長(zhǎng)度。為每個(gè)葉子結(jié)點(diǎn)到根的路徑長(zhǎng)度。nkklkwwpl1abcd7524wpl=7*2+5*2+2*2+4*2=36wpl最小的二叉樹(shù)就稱(chēng)作最優(yōu)二叉樹(shù)或哈夫曼樹(shù)最小的二叉樹(shù)就稱(chēng)作最優(yōu)二叉樹(shù)或哈夫曼樹(shù) 。2021-11-37abcd7524wpl=7*2+5*2+2*2+4*2=36dcab2475wpl=7*3+5*3+2*1+4*2=46abcd7524wpl=7*1+5*2+2*3+4*3=35 哈夫曼樹(shù)哈夫曼樹(shù) （最優(yōu)樹(shù)）（最優(yōu)樹(shù)）加權(quán)路徑長(zhǎng)度最小的二叉樹(shù)就加權(quán)路徑長(zhǎng)度最小的二叉樹(shù)就是哈夫曼樹(shù)。是哈夫曼樹(shù)。公式：公式：

4、nkklkwwpl12021-11-38675cd(b)11b57cd(c)18a711cdb5624(d)abcd7524(a)2、哈夫曼樹(shù)的構(gòu)造、哈夫曼樹(shù)的構(gòu)造例：給定權(quán)值例：給定權(quán)值7，5，2，4，構(gòu)造哈夫曼樹(shù)。，構(gòu)造哈夫曼樹(shù)。方法：方法：（1）由原始數(shù)據(jù)生成森林；）由原始數(shù)據(jù)生成森林；(2) 在森林中選取兩棵根結(jié)點(diǎn)權(quán)值在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的和次小的最小的和次小的二二叉樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，其根結(jié)點(diǎn)的叉樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，其根結(jié)點(diǎn)的權(quán)值為左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。規(guī)定左子樹(shù)根結(jié)點(diǎn)權(quán)值為左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。規(guī)定左子樹(shù)根結(jié)點(diǎn)的權(quán)值小于右子樹(shù)根結(jié)點(diǎn)的權(quán)值。

5、的權(quán)值小于右子樹(shù)根結(jié)點(diǎn)的權(quán)值。（3）將新的二叉樹(shù)加入到森林）將新的二叉樹(shù)加入到森林f中，去除原兩棵權(quán)值中，去除原兩棵權(quán)值最小的樹(shù)；最小的樹(shù)；（4）重復(fù)）重復(fù)2、3步驟，直至步驟，直至f中只剩一棵樹(shù)為止。中只剩一棵樹(shù)為止。注意：參看書(shū)中注意：參看書(shū)中p53的例子。的例子。2021-11-393、哈夫曼樹(shù)的應(yīng)用、哈夫曼樹(shù)的應(yīng)用（1）判定樹(shù)）判定樹(shù)在解決某些判定問(wèn)題時(shí)，利用哈夫曼樹(shù)可以得到最在解決某些判定問(wèn)題時(shí)，利用哈夫曼樹(shù)可以得到最佳判定算法。佳判定算法。例例1 將學(xué)生百分成績(jī)按分?jǐn)?shù)段分級(jí)的程序。將學(xué)生百分成績(jī)按分?jǐn)?shù)段分級(jí)的程序。若學(xué)生成績(jī)分布是均勻的，可用圖（若學(xué)生成績(jī)分布是均勻的，可用圖（a)

6、二叉樹(shù)結(jié)構(gòu)二叉樹(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。來(lái)實(shí)現(xiàn)。 a60 a70 a80 a90 不及格不及格中等中等良好良好優(yōu)秀優(yōu)秀及格及格ynynynyn(a)輸入輸入10000個(gè)個(gè)數(shù)據(jù)，則需進(jìn)數(shù)據(jù)，則需進(jìn)行行31500次比次比較。較。2021-11-310分?jǐn)?shù)分?jǐn)?shù)0596069707980899099比例比例0.050.150.40.30.10 70a 80 a60 及格及格中等中等良好良好 80a90 60a70 不及格不及格優(yōu)秀優(yōu)秀ynyyynnn(b) 不及格不及格y a90 a80 a70 a60 優(yōu)秀優(yōu)秀中等中等及格及格良好良好ynnn(c)yyy 學(xué)生成績(jī)分布不是均勻的情況：學(xué)生成績(jī)分布不是均勻的情況：

7、以比例數(shù)為權(quán)構(gòu)造一棵哈夫曼樹(shù)，以比例數(shù)為權(quán)構(gòu)造一棵哈夫曼樹(shù)，如（如（b)判斷樹(shù)所示。判斷樹(shù)所示。再將每一比較框的兩次比較改為一再將每一比較框的兩次比較改為一次，可得到（次，可得到（c)判定樹(shù)。判定樹(shù)。輸入輸入10000個(gè)個(gè)數(shù)據(jù)，僅需進(jìn)數(shù)據(jù)，僅需進(jìn)行行22000次比次比較。較。2021-11-311146833442200001111t;acs各字符編碼是各字符編碼是 t ； a c s 00 01 10 110 111上述電文編碼：上述電文編碼：11010111011101000011111000011000方法：方法：（1）用）用 2，4， 2，3， 3 作為葉子結(jié)點(diǎn)的權(quán)值生成一棵哈作為葉子

8、結(jié)點(diǎn)的權(quán)值生成一棵哈夫曼樹(shù)，并將對(duì)應(yīng)權(quán)值夫曼樹(shù)，并將對(duì)應(yīng)權(quán)值wi的葉子結(jié)點(diǎn)注明對(duì)應(yīng)的字符；的葉子結(jié)點(diǎn)注明對(duì)應(yīng)的字符；（2）約定左分支表示字符）約定左分支表示字符“0”，右分支表示字符，右分支表示字符1（3）從葉子結(jié)點(diǎn)開(kāi)始，順著雙親反推上去，直到根結(jié)點(diǎn)，路）從葉子結(jié)點(diǎn)開(kāi)始，順著雙親反推上去，直到根結(jié)點(diǎn)，路徑上的徑上的0或或1連接的序列就是結(jié)點(diǎn)對(duì)應(yīng)的字符的二進(jìn)制連接的序列就是結(jié)點(diǎn)對(duì)應(yīng)的字符的二進(jìn)制編碼的編碼的逆序逆序。（2）哈夫曼編碼哈夫曼編碼-利用哈夫曼樹(shù)構(gòu)造通訊中電文編碼（前綴碼）利用哈夫曼樹(shù)構(gòu)造通訊中電文編碼（前綴碼）例例2：要傳輸?shù)碾娢氖且獋鬏數(shù)碾娢氖莄as；cat；sat；at要傳輸?shù)淖?/p>

9、符集是要傳輸?shù)淖址?d=c，a，s，t， ；每個(gè)字符出現(xiàn)的頻率是每個(gè)字符出現(xiàn)的頻率是w= 2，4， 2，3， 3 注意：編碼的總長(zhǎng)度恰好為哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)。注意：編碼的總長(zhǎng)度恰好為哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)。2021-11-31211月月1日上機(jī)作業(yè)：日上機(jī)作業(yè)：1. 折半查找折半查找2. 順序查找順序查找3. 選擇排序選擇排序4. 快速排序快速排序2021-11-3132.6.1 圖的基本概念圖的基本概念2.6 圖圖bacd63215頂點(diǎn)頂點(diǎn): :圖中的數(shù)據(jù)元素圖中的數(shù)據(jù)元素v v表示表示頂頂點(diǎn)的非空有限集合。點(diǎn)的非空有限集合。vrvr表示兩個(gè)表示兩個(gè)頂頂點(diǎn)之間關(guān)系的集合。點(diǎn)之間關(guān)系的集合

10、。2021-11-314圖圖有向圖有向圖無(wú)向圖無(wú)向圖在有向圖中，在有向圖中， 表示從表示從v v1 1到到v v3 3的一條弧。的一條弧。 v v1 1為弧尾或初始點(diǎn)，為弧尾或初始點(diǎn)，v v3 3為弧頭或終端點(diǎn)。為弧頭或終端點(diǎn)。在無(wú)向圖中，在無(wú)向圖中，( (v v1 1，v v3 3) )表示表示v v1 1和和v v3 3之間的一條邊之間的一條邊。v1v3v2v4v1v3v2v42021-11-315v1v3v2v4v1v3v2v4頂點(diǎn)集合v=v1 ， v2 ， v3 ， v4 弧的集合g=, , , 頂點(diǎn)集合v=v1 ， v2 ， v3 ， v4 邊的集合e=(v1, v3), (v1,

11、v2), (v1, v4),(v2, v4)g=( v, e )頂點(diǎn)(v1, v3)與 (v3, v1)表示同一條邊2021-11-316bacd63215權(quán)：與圖的邊或弧相關(guān)的數(shù)。權(quán)：與圖的邊或弧相關(guān)的數(shù)。網(wǎng)：帶權(quán)的圖。網(wǎng)：帶權(quán)的圖。頂點(diǎn)的度：依附于該頂點(diǎn)的邊數(shù)或弧數(shù)。頂點(diǎn)的度：依附于該頂點(diǎn)的邊數(shù)或弧數(shù)。出度：（僅對(duì)有向圖）以該頂點(diǎn)為尾的弧數(shù)。出度：（僅對(duì)有向圖）以該頂點(diǎn)為尾的弧數(shù)。入度：（僅對(duì)有向圖）以該頂點(diǎn)為頭的弧數(shù)。入度：（僅對(duì)有向圖）以該頂點(diǎn)為頭的弧數(shù)。路徑：頂點(diǎn)路徑：頂點(diǎn)a a與頂點(diǎn)與頂點(diǎn)c c之間存在一條路徑。路之間存在一條路徑。路徑上邊或弧的數(shù)目稱(chēng)為該路徑的路徑長(zhǎng)度。徑上邊或弧

12、的數(shù)目稱(chēng)為該路徑的路徑長(zhǎng)度。2021-11-317 （1）圖的連接矩陣表示法）圖的連接矩陣表示法 （2）圖的鄰接表示法）圖的鄰接表示法2.6.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)2021-11-318v1v3v2v4v1v3v2v4 v1 v2 v3 v4 v1 0 0 1 0 v2 0 0 0 1 v3 0 0 0 1 v4 1 0 0 0 v1 v2 v3 v4 v1 0 1 1 1 v2 1 0 0 1 v3 1 0 0 0 v4 1 1 0 0圖的連接矩陣表示法圖的連接矩陣表示法2021-11-319鄰接矩陣表示法對(duì)求頂點(diǎn)的度很方便。鄰接矩陣表示法對(duì)求頂點(diǎn)的度很方便。在無(wú)向圖中：在無(wú)向圖中：頂

13、點(diǎn)的度數(shù)頂點(diǎn)的度數(shù)= =矩陣中對(duì)應(yīng)該頂點(diǎn)的行矩陣中對(duì)應(yīng)該頂點(diǎn)的行或或列中非列中非零元素的個(gè)數(shù)。零元素的個(gè)數(shù)。在有向圖中：在有向圖中：頂點(diǎn)的出度頂點(diǎn)的出度= =矩陣中對(duì)應(yīng)該頂點(diǎn)的矩陣中對(duì)應(yīng)該頂點(diǎn)的行行中非零元中非零元素的個(gè)數(shù)。素的個(gè)數(shù)。頂點(diǎn)的入度頂點(diǎn)的入度= =矩陣中對(duì)應(yīng)該頂點(diǎn)的矩陣中對(duì)應(yīng)該頂點(diǎn)的列列中非零元中非零元素的個(gè)數(shù)。素的個(gè)數(shù)。2021-11-320v1v3v2v4v1v3v2v4 v1 v2 v3 v4 v1 0 0 1 0 v2 0 0 0 1 v3 0 0 0 1 v4 1 0 0 0 v1 v2 v3 v4 v1 0 1 1 1 v2 1 0 0 1 v3 1 0 0 0 v4

14、1 1 0 0入度入度 出度出度1 11 11 11 12 12 10 10 1度數(shù)度數(shù)3 3 2 2 1 1 2 2 2021-11-321v1v3v2v4 1 2 3 4 211134 42134 1 2 3 4 v1v3v2v44圖的鄰接表表示法：圖的鄰接表表示法：即對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第即對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)個(gè)單鏈表中的結(jié)點(diǎn)表示依附于該頂點(diǎn)單鏈表中的結(jié)點(diǎn)表示依附于該頂點(diǎn)vi的邊（或?。┑倪叄ɑ蚧。?021-11-3222.6.3 圖的應(yīng)用圖的應(yīng)用圖的應(yīng)用非常廣泛，例如：圖的應(yīng)用非常廣泛，例如：用圖可以表示一座城市的交通聯(lián)系的情況；用圖可以表示一座城市的交通聯(lián)系的情況；用有值圖可以表示兩座城市之間的距離、車(chē)費(fèi)、或用有值圖可以表示兩座城市之間的距離、車(chē)費(fèi)、或班次數(shù)目。班次數(shù)目。表示城市之間建立的通訊網(wǎng)絡(luò)表示城市之間建立的通訊網(wǎng)絡(luò)可以描述化學(xué)結(jié)構(gòu)式。可以描述化學(xué)結(jié)構(gòu)式。圖中兩點(diǎn)之間的最短距離問(wèn)題。圖中兩點(diǎn)之間的最短距離問(wèn)題。2021-11-323作業(yè)：作業(yè)：p77 第第26題、第題、第28題題第第30題（題（1）、（）、（2）、）、(3)第第31題（題（1）、（）、（2）、