《哈夫曼樹及其應(yīng)用》ppt課件

1、第六章續(xù)哈夫曼樹及其運(yùn)用 設(shè)有設(shè)有1000010000個學(xué)生某門課程的考試成果的分布如個學(xué)生某門課程的考試成果的分布如下表所示：下表所示： 一、問題的提出一、問題的提出分?jǐn)?shù)05960697079 808990100學(xué)生比例數(shù)0.050.150.400.300.10學(xué)生成果數(shù)據(jù)分布情況表*問題：如今要編寫程序依次根據(jù)每個學(xué)生的成果打印出該學(xué)生的成果等級。分?jǐn)?shù)05960697079 808990100學(xué)生比例數(shù)0.050.150.400.300.10學(xué)生成果數(shù)據(jù)分布情況表方法方法1：a60打印打印bad“yesa70no打印打印passyesa80no打印打印generalyesa90no打印打印

2、goodyes打印打印excellentno5%的學(xué)生的學(xué)生15%的學(xué)生的學(xué)生40%的學(xué)生的學(xué)生30%的學(xué)生的學(xué)生10%的學(xué)生的學(xué)生共做31500次比較讀取一個學(xué)生成果a循環(huán)一萬次 i=1i=10000N終了終了 i = i+1分?jǐn)?shù)05960697079 808990100學(xué)生比例數(shù)0.050.150.400.300.10學(xué)生成果數(shù)據(jù)分布情況表方法方法2：a80打印打印badyesa90noyesnoa70yesnoa60yesno打印打印“good打印打印excellent打印打印pass打印打印general5%的學(xué)生的學(xué)生15%的學(xué)生的學(xué)生40%的學(xué)生的學(xué)生30%的學(xué)生的學(xué)生10%的學(xué)生

3、的學(xué)生讀取一個學(xué)生成果a循環(huán)一萬次 i=1i=10000N終了終了分?jǐn)?shù)05960697079 808990100學(xué)生比例數(shù)0.050.150.400.300.10學(xué)生成果數(shù)據(jù)分布情況表方法方法2：a80打印打印badyesa90noyesnoa70yesnoa60yesno打印打印“good打印打印excellent打印打印pass打印打印general5%的學(xué)生的學(xué)生15%的學(xué)生的學(xué)生40%的學(xué)生的學(xué)生30%的學(xué)生的學(xué)生10%的學(xué)生的學(xué)生共做22000次比較讀取一個學(xué)生成果a循環(huán)一萬次 i=1i=10000N終了終了思索：如何找到一棵最優(yōu)的判別樹使得編寫出來的程序的運(yùn)轉(zhuǎn)時間是最高效的？1.

4、1.哈夫曼樹的有關(guān)概念哈夫曼樹的有關(guān)概念 結(jié)點(diǎn)的途徑長度：結(jié)點(diǎn)的途徑長度： 從根結(jié)點(diǎn)沿某條途徑到某結(jié)點(diǎn)途中所閱歷的弧的條數(shù)從根結(jié)點(diǎn)沿某條途徑到某結(jié)點(diǎn)途中所閱歷的弧的條數(shù)稱為該結(jié)點(diǎn)的途徑長度。稱為該結(jié)點(diǎn)的途徑長度。 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用 樹的途徑長度：樹的途徑長度： 從根結(jié)點(diǎn)到每一個葉子結(jié)點(diǎn)的途徑長度之和。從根結(jié)點(diǎn)到每一個葉子結(jié)點(diǎn)的途徑長度之和。 樹的帶權(quán)途徑長度樹的帶權(quán)途徑長度(WPL)(WPL)： 樹中一切葉子結(jié)點(diǎn)的帶權(quán)途徑長度之和稱為樹的帶權(quán)樹中一切葉子結(jié)點(diǎn)的帶權(quán)途徑長度之和稱為樹的帶權(quán)途徑長度。途徑長度。結(jié)點(diǎn)的帶權(quán)途徑長度：結(jié)點(diǎn)的帶權(quán)途徑長度： 某結(jié)點(diǎn)的途徑長度與該結(jié)

5、點(diǎn)上的權(quán)值的乘積稱為該結(jié)某結(jié)點(diǎn)的途徑長度與該結(jié)點(diǎn)上的權(quán)值的乘積稱為該結(jié)點(diǎn)的帶權(quán)途徑長度。點(diǎn)的帶權(quán)途徑長度。 1. 1.哈夫曼樹的有關(guān)概念哈夫曼樹的有關(guān)概念 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用實(shí)例：知某二叉樹的四個葉子結(jié)點(diǎn)實(shí)例：知某二叉樹的四個葉子結(jié)點(diǎn) a,b,c,d分分別帶權(quán)別帶權(quán)7，5，2，4，那么可構(gòu)造出有如下幾，那么可構(gòu)造出有如下幾種不同方式的二叉樹：種不同方式的二叉樹：aaa777b5b5c2d4c2d4b5c2d 4樹的帶權(quán)途徑長度為：WPL=2*7+2*5+2*2+2*4=36樹的帶權(quán)途徑長度為：WPL=2*4+3*7+3*5+1*2=46樹的帶權(quán)途徑長度為：WPL=1*7+

6、2*5+3*2+3*4=351. 1.哈夫曼樹的有關(guān)概念哈夫曼樹的有關(guān)概念 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用哈夫曼樹的定義： 設(shè)有n個葉子結(jié)點(diǎn)的二叉樹，其第i個葉子結(jié)點(diǎn)的權(quán)值為wi(i=1,2,3,.n),且第i個葉子結(jié)點(diǎn)的途徑長度為li ,那么使WPL=wi*li最小的二叉樹稱為“最優(yōu)二叉樹或稱為“哈夫曼樹。i=1n n2. 2.哈夫曼樹的求解過程哈夫曼樹的求解過程 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用問題： 知n個葉子的權(quán)值為w1,w2,.wn，構(gòu)造一棵最優(yōu)二叉樹。2. 2.哈夫曼樹的求解過程哈夫曼樹的求解過程 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用方法： 步驟步驟1:構(gòu)造一

7、個具有構(gòu)造一個具有n棵二叉樹的森林棵二叉樹的森林F=T1,T2,.,Tn，其中其中Ti是只需一個根結(jié)點(diǎn)且根結(jié)點(diǎn)的權(quán)值為是只需一個根結(jié)點(diǎn)且根結(jié)點(diǎn)的權(quán)值為wi的二叉樹。的二叉樹。步驟步驟2:在在F中選取兩棵其根結(jié)點(diǎn)的權(quán)值最小的二叉樹，從中選取兩棵其根結(jié)點(diǎn)的權(quán)值最小的二叉樹，從F中刪除這兩棵樹，并以這兩棵二叉樹為左右子樹構(gòu)造一中刪除這兩棵樹，并以這兩棵二叉樹為左右子樹構(gòu)造一棵新的二叉樹添加到棵新的二叉樹添加到F中，該新的二叉樹的根結(jié)點(diǎn)的權(quán)值中，該新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右孩子二叉樹的根結(jié)點(diǎn)的權(quán)值之和。為其左右孩子二叉樹的根結(jié)點(diǎn)的權(quán)值之和。步驟步驟3:判別判別F中能否只需獨(dú)一的一棵二叉樹。假設(shè)是

8、，那中能否只需獨(dú)一的一棵二叉樹。假設(shè)是，那么求解過程終了；否那么，轉(zhuǎn)步驟么求解過程終了；否那么，轉(zhuǎn)步驟2。2. 2.哈夫曼樹的求解過程哈夫曼樹的求解過程 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用實(shí)例：知有5個葉子結(jié)點(diǎn)的權(quán)值分別為：5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。 a40b30c5d10e15152. 2.哈夫曼樹的求解過程哈夫曼樹的求解過程 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用實(shí)例：知有5個葉子結(jié)點(diǎn)的權(quán)值分別為：5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。 a40b30c5d10e15152. 2.哈夫曼樹的求解過程哈夫曼

9、樹的求解過程 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用實(shí)例：知有5個葉子結(jié)點(diǎn)的權(quán)值分別為：5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。 a40b30c5d10e1515302. 2.哈夫曼樹的求解過程哈夫曼樹的求解過程 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用實(shí)例：知有5個葉子結(jié)點(diǎn)的權(quán)值分別為：5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。 a40b30c5d10e151530602. 2.哈夫曼樹的求解過程哈夫曼樹的求解過程 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用實(shí)例：知有5個葉子結(jié)點(diǎn)的權(quán)值分別為：5 , 15 , 40 , 30 ,

10、10 ；試畫出一棵相應(yīng)的哈夫曼樹。 a40b30c5d10e151530601003.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用等長編碼： 以英文字符編碼為例，普通英文字符編碼是采用7位二進(jìn)制數(shù)編碼ASCII碼。7位二進(jìn)制數(shù)可以為27個不同的英文字符編碼。 下面為討論問題簡單起見，假設(shè)被編碼的字符集中只需4個即22個不同字符，故只需兩位二進(jìn)制數(shù)即可完成編碼。 設(shè)這4個不同的字符為A，B，C，D，那么可進(jìn)展等長編碼如下：3.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用等長編碼： 設(shè)這4個不同的字符為A，B，C，D，那么可進(jìn)展等長編碼如下：3.3.哈夫

11、曼編碼哈夫曼編碼 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用等長編碼： 設(shè)這4個不同的字符為A，B，C，D，那么可進(jìn)展等長編碼如下： A: 00 B: 01 C: 10 D: 11 那么對于電文“ABACCDA的二進(jìn)制電碼為： 00010010101100 總長為14位 譯碼時，兩位一分進(jìn)展譯碼，可獨(dú)一得到電文：ABACCDA 。3.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用緊縮編碼： 即采用不等長的編碼方案，將“高頻字符的編碼設(shè)計(jì)得盡能夠短一些，把最長的編碼留給“低頻字符。例如：對于剛剛的4個字符的編碼問題，可以按如下不等長編碼方案進(jìn)展編碼： A: 0 B: 00 C:

12、 1 D: 01問題：譯碼時能夠出現(xiàn)多意性，即譯碼不獨(dú)一： 那么對于電文“ABACCDA的二進(jìn)制電碼為： 000011010 總長為9位3.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用緊縮編碼： 例如：對于剛剛的4個字符的編碼問題，可以按如下不等長編碼方案進(jìn)展編碼： A: 0 B: 00 C: 1 D: 01問題：譯碼時能夠出現(xiàn)多意性，即譯碼不獨(dú)一： 那么對于電文“ABACCDA的二進(jìn)制電碼為： 000011010 總長為9位3.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用緊縮編碼： 例如：對于剛剛的4個字符的編碼問題，可以按如下不等長編碼方案進(jìn)展編

13、碼： A: 0 B: 00 C: 1 D: 01問題：譯碼時能夠出現(xiàn)多意性，即譯碼不獨(dú)一。 那么對于電文“ABACCDA的二進(jìn)制電碼為： 000011010 總長為9位 如000011010中的前4個0的譯碼會有如下幾種不同譯碼： 0000AAAA；0000ABA；0000BB思索：如何處理這一問題？問題的關(guān)鍵在于編碼能否為無前綴編碼。3.3.哈夫曼編碼哈夫曼編碼 二、哈夫曼樹及其運(yùn)用二、哈夫曼樹及其運(yùn)用無前綴緊縮編碼既哈夫曼編碼： *思想：利用哈夫曼樹設(shè)計(jì)出來的不等長的編碼方案一定是無前綴的。*方法：步驟1：將各字符按照其“出現(xiàn)頻率的統(tǒng)計(jì)數(shù)字安排一個“權(quán)值并作為“葉子，然后求出相應(yīng)的哈夫曼樹

14、；步驟2：樹中各結(jié)點(diǎn)到其左孩子的邊上的權(quán)值設(shè)為0、到其右孩子的邊上的權(quán)值設(shè)為1即所謂左0右1； 步驟3：從根開場到“葉子所閱歷的邊上的數(shù)值的序列即為該“葉子所對應(yīng)的字符的編碼。三、實(shí)例三、實(shí)例 知某通訊譽(yù)電文僅由A、B、C、D這4個字符構(gòu)成，其出現(xiàn)的頻率分別為：8、4、6、2，請給出它們的哈夫曼編碼，要求寫出相應(yīng)的哈夫曼樹。解：根據(jù)哈夫曼算法，求得哈夫曼樹如下：208122664BDAC010101 從根開場到葉子得各字符的哈夫曼編碼如下：A :0 B:100 C:11 D:101 那么對于電文“ABACCDA的二進(jìn)制電碼為： 0100011111010 總長為13位三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：

15、用一維數(shù)組存放單鏈表靜態(tài)鏈表李趙孫周鄭吳王錢A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李趙孫周鄭吳王錢A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李趙 8 孫周鄭吳王錢A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李趙 8 孫周鄭吳王錢 3A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李趙 8 孫 1 周鄭吳王錢 3A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)

16、充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周鄭吳王錢 3A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭吳王錢 3A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭吳 5 王錢 3A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王錢 3A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一

17、維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 92 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 9在“孫的前面插入一個“史：三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 92 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3 史A 0 1 2 3 4 5 6 7 8 9在“孫的前面插入一個“史：三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)

18、組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 92 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3 史A 0 1 2 3 4 5 6 7 8 9在“孫的前面插入一個“史：三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 92 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3 史 3A 0 1 2 3 4 5 6 7 8 9在“孫的前面插入一個“史：三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一

19、維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 92 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3 史 3A 0 1 2 3 4 5 6 7 8 9在“孫的前面插入一個“史：三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 92 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3 史 3A 0 1 2 3 4 5 6 7 8 9在“孫的前面插入一個“史：三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)

20、容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 92 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9在“孫的前面插入一個“史：刪除“周時表的變化：2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 92 李 4 趙 8

21、孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9在“孫的前面插入一個“史：刪除“周時表的變化：2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 92 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9在“孫的前面插入一個“史：刪除“周時表的變化：2 李 4 趙 8

22、 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 92 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9在“孫的前面插入一個“史：刪除“周時表的變化：2 李 6 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李

23、4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 3A 0 1 2 3 4 5 6 7 8 92 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9在“孫的前面插入一個“史：刪除“周時表的變化：2 李 6 趙 8 孫 1 周 6 鄭 7 吳 5 王 0 錢 9 史 3A 0 1 2 3 4 5 6 7 8 9總結(jié)：靜態(tài)鏈表在插入和刪除時普通不需求挪動元素，僅需求修正指針即可。但在懇求存儲空間時需求一次性懇求足夠大的空間。三、實(shí)例三、實(shí)例補(bǔ)充內(nèi)容：用一維數(shù)組存放單鏈表靜態(tài)鏈表2 李 4 趙 8 孫 1 周 6 鄭 7 吳 5 王

24、 0 錢 3A 0 1 2 3 4 5 6 7 8 9靜態(tài)鏈表的構(gòu)造類型定義：#defined MAXSIZE 1000 / 鏈表的最大尺寸Typedef struct StaticListNode ElemType data ; /存放表中元素的值 int next ; /指示后繼元素的存放位置 StaticListNode, StaticLinkList MAXSIZE ; /定義一個數(shù)組四、構(gòu)造哈夫曼樹并求四、構(gòu)造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序1.哈夫曼樹的結(jié)點(diǎn)的物理構(gòu)造：weightparentlchildrchildTypedef struct HTN

25、ode unsigned int weight ; unsigned int parent, lchild, rchild ;HTNode , * HuffmanTree ; /該指針用以懇求數(shù)組時作為數(shù)組名2.結(jié)點(diǎn)物理構(gòu)造的C言語定義：例如：7 7 0 05 6 0 025 0045006 634a7b5c2d 4117256111818016 1 2 3 4 5 6 7HT哈夫曼樹HT的存儲構(gòu)造如下(HT為HuffmanTree類型)：HT是一個HTNode類型的一維數(shù)組，用以存放m個結(jié)點(diǎn)元素(m=2n-1,其中n為葉子個數(shù))；即采用靜態(tài)二叉鏈表存放哈夫曼樹；故HT可以用如下語句為其懇求空

26、間：HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); 其中 0號單元未用，從HT1開場存放樹的結(jié)點(diǎn)四、構(gòu)造哈夫曼樹并求四、構(gòu)造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序1.哈夫曼樹的結(jié)點(diǎn)的物理構(gòu)造：weightparentlchildrchildtypedef char * * HaffmanCode ; / HaffmanCode是指向一個 字符型數(shù)組的指針類型 3.用n個字符型數(shù)組存放n個葉子的哈夫曼編碼這n個字符數(shù)組的頭指針HCi(1in)分別指向一個字符型數(shù)組的首地址，又構(gòu)成一個指針類型的一維數(shù)組；“0“1“1“0“0“

27、1“0“0.“0“0“1“1“1“0HC1HC2HCn.那么n個字符串?dāng)?shù)組的頭指針HCi(1 in)可以如此定義： HC=(HuffmanCode)malloc(n+1)*sizeof(char *);HCi = (char *)malloc(編碼長度+1)*sizeof(char); 四、構(gòu)造哈夫曼樹并求四、構(gòu)造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序4.構(gòu)造哈夫曼樹的程序之實(shí)現(xiàn)：算法思想：例如：a7b5c2d 4611187 0 0 05 0 0 020 0040000 00000000000 1 2 3 4 5 6 7HT其哈夫曼樹HT的存儲構(gòu)造的初始情況如下：針對

28、第i個結(jié)點(diǎn)(n+1i2n-1,n=4為葉子結(jié)點(diǎn)的個數(shù))，在1i-1號結(jié)點(diǎn)中為第i個結(jié)點(diǎn)尋覓兩個兒子結(jié)點(diǎn)(該兩個兒子應(yīng)該是i-1個節(jié)點(diǎn)中無父親且權(quán)值最小的兩個結(jié)點(diǎn))四、構(gòu)造哈夫曼樹并求四、構(gòu)造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序4.構(gòu)造哈夫曼樹的程序之實(shí)現(xiàn)：算法思想：例如：a7b5c2d 4611187 0 0 05 0 0 025 0045006 03400000000 1 2 3 4 5 6 7HT其哈夫曼樹HT的存儲構(gòu)造的初始情況如下：針對第i個結(jié)點(diǎn)(n+1i2n-1,n=4為葉子結(jié)點(diǎn)的個數(shù))，在1i-1號結(jié)點(diǎn)中為第i個結(jié)點(diǎn)尋覓兩個兒子結(jié)點(diǎn)(該兩個兒子應(yīng)該是i-1

29、個節(jié)點(diǎn)中無父親且權(quán)值最小的兩個結(jié)點(diǎn))四、構(gòu)造哈夫曼樹并求四、構(gòu)造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序4.構(gòu)造哈夫曼樹的程序之實(shí)現(xiàn)：算法思想：例如：a7b5c2d 4611187 0 0 05 6 0 025 0045006 634110250000 1 2 3 4 5 6 7HT其哈夫曼樹HT的存儲構(gòu)造的初始情況如下：針對第i個結(jié)點(diǎn)(n+1i2n-1,n=4為葉子結(jié)點(diǎn)的個數(shù))，在1i-1號結(jié)點(diǎn)中為第i個結(jié)點(diǎn)尋覓兩個兒子結(jié)點(diǎn)(該兩個兒子應(yīng)該是i-1個節(jié)點(diǎn)中無父親且權(quán)值最小的兩個結(jié)點(diǎn))四、構(gòu)造哈夫曼樹并求四、構(gòu)造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程

30、序4.構(gòu)造哈夫曼樹的程序之實(shí)現(xiàn)：算法思想：例如：a7b5c2d 4611187 7 0 05 6 0 025 0045006 6341172518016 1 2 3 4 5 6 7HT其哈夫曼樹HT的存儲構(gòu)造的初始情況如下：針對第i個結(jié)點(diǎn)(n+1i2n-1,n=4為葉子結(jié)點(diǎn)的個數(shù))，在1i-1號結(jié)點(diǎn)中為第i個結(jié)點(diǎn)尋覓兩個兒子結(jié)點(diǎn)(該兩個兒子應(yīng)該是i-1個節(jié)點(diǎn)中無父親且權(quán)值最小的兩個結(jié)點(diǎn))四、構(gòu)造哈夫曼樹并求四、構(gòu)造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序4.構(gòu)造哈夫曼樹的程序之實(shí)現(xiàn)：void HuffmanCoding(HuffmanTree &HT, Huffm

31、anCode &HC, int *w, int n) /w是存放n個字符的權(quán)值的一維數(shù)組， n為葉子個數(shù)；構(gòu)造哈夫曼樹HT; if (n=1) return; m = 2 * n - 1; /n即為葉子數(shù)n0,由二叉樹性質(zhì)3,n0=n2+1,故樹中結(jié)點(diǎn)數(shù)為2*n-1 HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0號單元未用 for (i=1; i=n; i+) /n個葉子結(jié)點(diǎn)賦初值，n個葉子最初為n個根結(jié)點(diǎn) HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for

32、 (i=n+1; i=m; i+) /n-1個度為2的結(jié)點(diǎn)賦初值 HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for (i=n+1; i=m; i+) / 第i次循環(huán)時為第i個結(jié)點(diǎn)選擇兩個兒子結(jié)點(diǎn)s1與s2 Select(HT, i-1, &s1, &s2); / 在i-1棵子樹中也即HT1.i-1中選擇無父親(parent為0) /且權(quán)值最小的兩個結(jié)點(diǎn)(其序號分別為s1和s2)。該子程序是一個順序查找過程 HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; /建立父子關(guān)系 /哈夫曼樹HT構(gòu)造終了四、構(gòu)造哈夫曼樹并求四、構(gòu)造哈夫曼樹并求n個字符的哈夫曼編碼之程序個字符的哈夫曼編碼之程序5.從葉子到根逆向求每個字符的哈夫曼編碼的程序之實(shí)現(xiàn)：/從葉子到根逆向求每個字符的哈夫曼編碼從葉子到根逆向求每個字符的哈夫曼編碼; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /懇求懇求n個字符編碼的頭指針個字符編碼的頭指針數(shù)數(shù) 組的存儲空間組的存儲空間 cd = (char