哈夫曼樹(shù)畢業(yè)論文修改版.doc

本科畢業(yè)論文本科畢業(yè)論文 論文題目論文題目 哈哈夫夫曼曼樹(shù)樹(shù)及及其其應(yīng)應(yīng)用用 學(xué)生姓名學(xué)生姓名 專業(yè)班級(jí)專業(yè)班級(jí) 信息與計(jì)算科學(xué)專業(yè)信息與計(jì)算科學(xué)專業(yè) 20082008 級(jí)級(jí) 1 1 班班 指導(dǎo)教師指導(dǎo)教師 20122012 年年 5 5 月月 2020 日日 教學(xué)單位教學(xué)單位 數(shù)數(shù) 學(xué)學(xué) 系系 學(xué)生學(xué)號(hào)學(xué)生學(xué)號(hào) 編編 號(hào)號(hào) 目 錄 一 、論文正文 .(1) 1 哈夫曼樹(shù) .(1) 1.1 哈夫曼樹(shù)的基本概念.(1) 1.2 哈夫曼算法證明.(2) 2 哈夫曼算法構(gòu)造 .(4) 2.1 哈夫曼樹(shù)的構(gòu)造算法.(4) 2.2 舉例說(shuō)明其構(gòu)造過(guò)程.(5) 3 哈夫曼樹(shù)的應(yīng)用 .(6) 3.1 用于最佳判斷過(guò)程.(6) 3.2 用于通信編碼.(7) 4 C+程序?qū)崿F(xiàn)(8) 5 總結(jié) .(11) 參考文獻(xiàn) .(11) 二、附錄 1. 開(kāi)題報(bào)告(13) 2. 結(jié)題報(bào)告(14) 3. 答辯報(bào)告(15) 哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用 （寶雞文理學(xué)院 數(shù)學(xué)系,陜西 寶雞 721013） 摘摘 要要: :簡(jiǎn)要介紹了哈夫曼樹(shù)的相關(guān)概念,闡述了哈夫曼樹(shù)的基本原理,探討 了它在相關(guān)領(lǐng)域的實(shí)際應(yīng)用,并采用 C+對(duì)其進(jìn)行了算法實(shí)現(xiàn). 關(guān)鍵詞關(guān)鍵詞: :哈夫曼樹(shù);二叉樹(shù);帶權(quán)路徑長(zhǎng)度;根結(jié)點(diǎn);葉結(jié)點(diǎn) 哈夫曼樹(shù)是由哈夫曼于 1951 年所創(chuàng)立并改進(jìn)的,他本人也根據(jù)哈夫曼樹(shù)提 出了相應(yīng)的編碼.由于哈夫曼樹(shù)是具有最小加權(quán)路徑長(zhǎng)度的二叉樹(shù),故哈夫曼編 碼能產(chǎn)生較短的碼文.基于這個(gè)優(yōu)勢(shì),在信息化高度發(fā)達(dá)的當(dāng)今社會(huì),對(duì)信息的傳 遞也有著較高要求的我們,希望信息在傳遞過(guò)程中,能夠保持節(jié)省性和保密性,哈 夫曼編碼則很好的滿足了這方面的要求,因而對(duì)其的研究是相當(dāng)有必要的. 1 哈夫曼樹(shù)哈夫曼樹(shù) 1.1 哈夫曼樹(shù)的基本概念哈夫曼樹(shù)的基本概念 首先要了解樹(shù)的概念.樹(shù)是一種數(shù)據(jù)結(jié)構(gòu),是由一個(gè)或多個(gè)結(jié)點(diǎn)組成的有限 集合.因其存放方式頗像一棵樹(shù)又有樹(shù)杈,因而稱其為樹(shù).現(xiàn)簡(jiǎn)要介紹一下相關(guān)概 念. 定義定義 1.1 在一棵樹(shù)中,從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路, 稱為路徑. 定義定義 1.2 若將樹(shù)中結(jié)點(diǎn)都賦給一個(gè)具有某種含義的數(shù)值,則這個(gè)數(shù)值稱為該結(jié) 點(diǎn)的權(quán). 定義定義 1.3 由根結(jié)點(diǎn)到所有葉結(jié)點(diǎn)的路徑長(zhǎng)度之和稱為二叉樹(shù)的路徑長(zhǎng)度. 定義定義 1.4 從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值之積的和叫做二叉樹(shù)的 帶權(quán)路徑長(zhǎng)度. 定義定義 1.5 最優(yōu)二叉樹(shù),也稱哈夫曼樹(shù),實(shí)質(zhì)是對(duì)一組帶有確定權(quán)值的葉結(jié)點(diǎn),構(gòu) 造的具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù). 如果二叉樹(shù)中的葉結(jié)點(diǎn)都具有一定的權(quán)值,則可將這一概念推廣,設(shè)二叉樹(shù) 有個(gè)帶權(quán)值的葉結(jié)點(diǎn),那么,二叉樹(shù)的帶權(quán)路徑長(zhǎng)度應(yīng)記為:n , n k kk LWWPL 1 其中為第個(gè)葉結(jié)點(diǎn)的權(quán)值;為第個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度. k Wk k Lk 現(xiàn)用下圖解釋上述相關(guān)概念 1 . 1 . 1 圖1 . 1 . 1 2 在圖中,即為根結(jié)點(diǎn),而則為葉結(jié)點(diǎn),若的權(quán)值分別為則1 . 1 . 1ACB,CB,4 , 3 二叉樹(shù)路徑長(zhǎng)度為 2,二叉樹(shù)的帶權(quán)路徑長(zhǎng)度為 7,即.71413WPL 例例 下面我們結(jié)合實(shí)例來(lái)說(shuō)明哈夫曼樹(shù).如果我們給定葉子結(jié)點(diǎn)的個(gè)數(shù)及每個(gè)葉 子結(jié)點(diǎn)的權(quán)值構(gòu)造出若干棵形態(tài)各異的二叉樹(shù)如圖所示,其中根結(jié)點(diǎn)和葉結(jié)點(diǎn)之 間的數(shù)字表示各葉子結(jié)點(diǎn)的權(quán)值. )(a)(b)(c 2 . 2 . 1圖 ;4922351638 3 ;4132352618 2 ;4222252628 1 WPL WPL WPL 按照的計(jì)算方法,經(jīng)過(guò)計(jì)算比較后,我們發(fā)現(xiàn),圖的值最WPL2 . 2 . 1)(bWPL 小,它即為哈夫曼樹(shù). 由此可見(jiàn),由相同權(quán)值的一組葉子結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有不同的形態(tài)和不同 的帶權(quán)路徑長(zhǎng)度.那么如何找到帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)呢？根據(jù)哈夫曼樹(shù)的 定義,一棵二叉樹(shù)要使其值最小,必須使權(quán)值越大的葉結(jié)點(diǎn)越靠近根結(jié)點(diǎn),WPL 而權(quán)值越小的葉結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn),這樣計(jì)算樹(shù)的帶權(quán)路徑長(zhǎng)度時(shí),自然樹(shù)會(huì)具 有最小的帶權(quán)路徑長(zhǎng)度,這是生成算法的一種基本思想. 1.2 哈夫曼算法證明哈夫曼算法證明 定理定理 1 如果是帶權(quán)的哈夫曼樹(shù),其中我們有下述T n WW, 1 . 21n WWW 結(jié)論成立. (1)若和是兄弟,則; i W j W ji WLWL (2)和是兄弟,且在所有分支點(diǎn)中,的層數(shù)最大; 1 W 2 W 21 WW (3)將帶權(quán)的分支點(diǎn)改為帶權(quán)的樹(shù)葉,得帶權(quán)為 21 WW 21 WW 的樹(shù),則也是哈夫曼樹(shù). n WWWW, 321 T T 證明證明: :(1) 由頂點(diǎn)的層數(shù)定義即知結(jié)論顯然成立. 3 (2) 若只有 2 片樹(shù)葉,則,和是兄弟,是T 1 2 WLWL i1 W 2 W 21 WW 和的父親,也是根,是唯一的分支點(diǎn). 1 W 2 W 設(shè),在所有分支點(diǎn)中, 的層數(shù)最大, 的兩個(gè)兒子分別是和,3nvv i W j W 則 ,. 1 WLWL i 2 WLWL i 1 WLWL j 2 WLWL j 假如,將和互換,得到新的樹(shù),記為, 1 WLWL i i W 1 W T 則 1111 WWLWWLWWLWWLTWTW iiii 111 WWWLWWWL iii ii WWWLWL 11 因?yàn)?當(dāng)時(shí),此時(shí)顯然是兄弟,從 i WW 1i WW 1ii WWWW 132 21,W W 而只需考慮的情形,于是有 i WW 1 TWTWTWTW , 0 這與是哈夫曼樹(shù)矛盾,所以.T 1 WLWL i 同理可證明,因此.這樣分 2 WLWL j ji WLWLWLWL 2121,W W 別是和,否則將分別與互換,得到一棵樹(shù),但 i W j W 21,W W ji WW , jjii WLWWLWWLWWLW 2211 與是哈夫曼樹(shù)矛盾.T (3) 首先可知.假設(shè)不是哈夫曼樹(shù),是帶權(quán) 21 WWTWTW T 1 T 的哈夫曼樹(shù).在中以的兩個(gè)兒子和為樹(shù)葉, n WWWW, 321 T 21 WW 1 W 2 W 成為分支點(diǎn),得到一棵帶權(quán)的二叉樹(shù),則 21 WW n WWW, 212 T 2112 WWTWTW 因?yàn)楹投际菐?quán)的二叉樹(shù),而是哈夫曼樹(shù),所以 T 1 T n WWWW, 321 1 T . TWTW 1 4 假如,則 TWTW ) ( 1 . TWWWTWWWTWTW 212112 這與是帶權(quán)的哈夫曼樹(shù)矛盾,因此.即為帶權(quán)T n WWW, 21 TWTW 1 T 的哈夫曼樹(shù). n WWWW, 321 2 哈夫曼算法構(gòu)造哈夫曼算法構(gòu)造 哈夫曼樹(shù),實(shí)質(zhì)是對(duì)一組帶有確定權(quán)值的葉結(jié)點(diǎn),構(gòu)造的具有最小帶權(quán)路徑 長(zhǎng)度的二叉樹(shù).盡管哈夫曼樹(shù)可以通過(guò)比較后得出,可是在運(yùn)算過(guò)程中往往WPL 會(huì)出現(xiàn)一些問(wèn)題,使其實(shí)現(xiàn)起來(lái)并不容易,因而我們可以應(yīng)用編程來(lái)有效地解決 這個(gè)問(wèn)題. 2.1 哈夫曼樹(shù)的構(gòu)造算法哈夫曼樹(shù)的構(gòu)造算法 為了構(gòu)造權(quán)值為的哈夫曼樹(shù),哈夫曼提出了一種構(gòu)造算法,現(xiàn) n WWWW, 321 將其陳述如下: 步驟步驟 1 根據(jù)題目給定的個(gè)權(quán)值構(gòu)造有下列棵二叉樹(shù)的集合 n n WWWW, 321 n ,其中每棵二叉樹(shù)中只有一個(gè)帶權(quán)為的根結(jié)點(diǎn),其 n TTTTF, 321 i T i W 左右樹(shù)均為空; 步驟步驟 2 在中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二 F 叉樹(shù),且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之 和; 步驟步驟 3 在中刪除這兩棵樹(shù),同時(shí)將新得到的二叉樹(shù)加入中;FF 步驟步驟 4 重復(fù)步驟 2 和步驟 3,直到只含有一棵樹(shù)為止,這棵樹(shù)便是哈夫曼樹(shù).F 2.2 舉例說(shuō)明其構(gòu)造過(guò)程舉例說(shuō)明其構(gòu)造過(guò)程 假設(shè)葉結(jié)點(diǎn)權(quán)值集合為的哈夫曼樹(shù)的構(gòu)造4 , 3 , 2 , 1W 第一步 我們根據(jù)給定的 4 個(gè)權(quán)值來(lái)構(gòu)造 4 棵二叉樹(shù)的集合.F 第二步 在找出權(quán)值中最小的兩個(gè)作為新二叉樹(shù)的左右子樹(shù),且置新的二F 叉樹(shù)根結(jié)點(diǎn)權(quán)值是其左右結(jié)點(diǎn)權(quán)值之和. 5 第三步 將次小的樹(shù)與新生成的樹(shù)再作為左右子樹(shù)生成權(quán)值為 6 的新樹(shù); 第四步 再次將權(quán)值為 4 的樹(shù)在同上一個(gè)權(quán)值為 6 的樹(shù)再次生成新樹(shù)即可. 從以上過(guò)程可以計(jì)算出這棵二叉樹(shù)的帶權(quán)路徑長(zhǎng)度為 19. 3 哈夫曼樹(shù)的應(yīng)用哈夫曼樹(shù)的應(yīng)用 3.1 用于最佳判斷過(guò)程用于最佳判斷過(guò)程 在考查課記分時(shí)往往把百分制轉(zhuǎn)換成優(yōu)秀,良好 ,中90x9080 x 等 ,及格,不及格五個(gè)等級(jí).若不考慮學(xué)生考試8070 x7060 x60x 分?jǐn)?shù)的分布概率,程序判定過(guò)程很容易寫(xiě)成所示的方法.一般來(lái)講學(xué)生考1 . 1 . 3圖 分大多分布在 70 至 80 分之間,從可看出這種情況的值要比較 2 至 3 次1 . 1 . 3圖x 才能確定等級(jí).而學(xué)生中考試不及格的人數(shù)很少,值比較一次即可定等級(jí).能否x 使出現(xiàn)次數(shù)多的在 70 至 80 分之間的值比較次數(shù)減少,而使很少出現(xiàn)的低于 60x 分的值比較次數(shù)多一些,以便提高程序的運(yùn)行效率是一個(gè)問(wèn)題.x 6 YY Y Y Y Y Y Y N N N N N N N N Y Y YYN N N N 1 . 1 . 3圖2 . 1 . 3圖 假設(shè)學(xué)生成績(jī)對(duì)于不及格,及格,中等,良好和優(yōu)秀的分布概率分別為 5%,15%,40%, 30%,10%,以它們做為葉子的權(quán)值來(lái)構(gòu)造哈夫曼樹(shù),如圖所示.2 . 1 . 3 此時(shí)帶權(quán)路徑長(zhǎng)最短,其值 210%.它可以使大部分的分?jǐn)?shù)值經(jīng)過(guò)較少的比較次數(shù) 得到相應(yīng)的等級(jí).但是,事物往往不是絕對(duì)的,此時(shí)每個(gè)判斷的框內(nèi)條件都較為復(fù) 雜,需比較兩次,反而降低運(yùn)行效率.所以我們采用折中作法,調(diào)整后得圖判3 . 1 . 3 定樹(shù),更加切合實(shí)際. X #include #include #define Max 32767 /*int 型最大可取值*/ typedef struct Node int weight; /*定義權(quán)值*/ int parent,Lchild,Rchild; /*定義雙親結(jié)點(diǎn),左、右孩子結(jié)點(diǎn)*/ HTNode; typedef char *HuffmanCode; /*雙重指針存儲(chǔ)哈夫曼編碼*/ void select(int w,int n,int /*min1 最小,min2 次小*/ min1=w1;xb1=1; min2=w2;xb2=2; if(min1min2) min1=w2;xb1=2; min2=w1;xb2=1; /*安排第一和第二個(gè)數(shù)的顯示順序 */ for(int i=3;i2 的數(shù)組元素*/ if(wixb2) /*保證 下標(biāo)小 的做左孩子*/ hti.Lchild=xb2; hti.Rchild=xb1; wxb1=Max; wxb2=Max; /*修改選過(guò)的節(jié)點(diǎn)的權(quán)值,避免下次再 被選中 */ /*輸出所有節(jié)點(diǎn)的下標(biāo)、權(quán)值、雙親、左孩子、右孩子的下標(biāo)*/ cout #define N 14 /* N 代表數(shù)組長(zhǎng)度,要改變數(shù)組長(zhǎng)度時(shí) ,只需要將 14 改為 想要的數(shù)*/ 11 void main() int w7; /*w 中的數(shù)不是固定的可以根據(jù)需要改變*/ printf(“ please input number for w n“); for(int j = 1;j =7;+j) scanf(“%d“, int n=7; /*n 是可以修改的*/ int m=2*n-1; HTNode ht14;/*哈夫曼樹(shù)成員數(shù)組 從 1-13;0 下標(biāo)不用.用于 雙親表示法存儲(chǔ) Huffman 樹(shù)*/ HuffmanCode hc8;/*7 個(gè)葉子節(jié)點(diǎn)也就是 w14里面的,從 1-7;0 下 標(biāo)不用 其中 HuffmanCode 被自定義為 char 型指針數(shù)據(jù)類型*/ createHTree(ht,hc,w,n); coutendlendl“各葉子節(jié)點(diǎn)的編碼如下:“endl; for(int i=1;i=n;i+) couti“ :“hciendl; 5 總結(jié)總結(jié) 程序經(jīng)運(yùn)行得到很好的實(shí)現(xiàn),但程序中仍存在一些不足之處,需要再加以改 進(jìn).通過(guò)此次論文設(shè)計(jì)很好的增強(qiáng)了我對(duì)編程及二叉樹(shù)理論的認(rèn)識(shí)和對(duì) C+軟件 的應(yīng)用能力,也是將理論知識(shí)運(yùn)用于解決實(shí)際問(wèn)題的一次新嘗試. 致謝:本文在寫(xiě)作過(guò)程中得到安海龍老師的指導(dǎo). 參考文獻(xiàn)參考文獻(xiàn): : 1 (美)John A. Dossey.離散數(shù)學(xué) M.北京:清華大學(xué)出版社,2005:207-219. 2 方世昌.離散數(shù)學(xué) M .西安:西安電子科技大學(xué)出版社,2010:304-310. 3 陳火旺.數(shù)據(jù)結(jié)構(gòu)與算法 M.湖南:中南大學(xué)出版社,2005:125-127. 4 王宏生,宋繼紅.數(shù)據(jù)結(jié)構(gòu) M .北京:國(guó)防工業(yè)出版社,2006:183-187. 5 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu) M .北京:清華大學(xué)出版社,1995:145-147. 6 譚浩強(qiáng).C+面向?qū)ο蟪绦蛟O(shè)計(jì) M.北京:清華大學(xué)出版社,2007:134-231. 7 李俊峰,馮剛.離散數(shù)學(xué) M .北京:清華大學(xué)出版社,2006:341-345. Huffman tree and its application (Department of mathematics, Baoji University of Arts and Sciences, Baoji 721013,Shaanxi, China) Abstract: