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

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