哈夫曼樹及其應(yīng)用

1、EAST CHINA INSTITUTE OF TECHNOLOGY* * * *課程設(shè)計報告題目：哈夫曼樹及其應(yīng)用學(xué)生姓名:何昆學(xué) 號：201120180418班 級：1121804指導(dǎo)教師：張軍2013年1月10日目錄一、需求分析說明31課程設(shè)計目的32.課程設(shè)計題目 33 程序功能及需求說明3二、總體設(shè)計41. 哈夫曼樹建立42 哈夫曼編碼43 哈夫曼譯碼4三、詳細(xì)設(shè)計51. 算法設(shè)計52. 類設(shè)計5四、實(shí)現(xiàn)部分6五、程序測試97 > 總結(jié) 10一、需求分析說明1、課程設(shè)計目的本課程設(shè)訃的U的考察學(xué)生對常見數(shù)據(jù)結(jié)構(gòu)及相關(guān)算法的綜合應(yīng)用能力，達(dá) 到理論與實(shí)際應(yīng)用相結(jié)合，使同學(xué)們能夠根

2、據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的 方法，解決實(shí)際問題中數(shù)據(jù)的合理存儲表示，并根據(jù)相應(yīng)的存儲結(jié)構(gòu)設(shè)訃效率較 高的算法實(shí)現(xiàn)對問題的求解；通過此次課程設(shè)訃進(jìn)一步培養(yǎng)學(xué)生良好的程序設(shè)計 技巧和分析問題解決問題的能力。2、課程設(shè)計題哈夫曼樹及其應(yīng)用(1) .設(shè)計L1的：熟悉樹的各種存儲結(jié)構(gòu)及其特點(diǎn)及掌握建立哈夫曼樹和哈夫曼編 碼的方法及帶權(quán)路徑長度的計算。(2) .設(shè)計內(nèi)容：欲發(fā)一封內(nèi)容為AABBCAB(共長100字符,其中:A、B、C、 D、E、F分別有7、9、12、22、23、27個)的電報報文，實(shí)現(xiàn)哈夫曼編碼 和譯碼。(3) .設(shè)計要求：分析系統(tǒng)需求。建立哈夫曼樹。進(jìn)行哈夫曼編碼，并求出平均編碼長

3、度。譯碼，對編碼好的內(nèi)容進(jìn)行譯碼。3、程序功能及需求說明功能：編碼，編碼長度，譯碼要實(shí)現(xiàn)編碼譯碼等功能，必須先建立一個哈夫曼樹，編碼長度、譯碼乂通過編碼 求得。這里通過分別創(chuàng)建結(jié)點(diǎn)類(tree)和編碼類(codetype),子函數(shù)有哈夫 曼樹建立(creathuffmantree ),哈夫曼編碼(arrangecode ),哈夫曼譯碼 (transcode),最后通過主函數(shù)調(diào)用執(zhí)行。二、總體設(shè)計1 哈夫曼樹建立A7B-9C-12D-22E-23F-272哈夫曼樹編碼（路徑往左為0,往右為1）7的編碼：1110 9的編碼：1111 12的編碼：1 1 022的編碼：0023的編碼：0 127的編

4、碼：1 0帶權(quán)路徑長度：WPL=7*4+9*4+12*3+22*2+23*2+27*2=244平均編碼長度為：4+5+5+6+6+7=333 哈夫曼樹譯碼假設(shè)發(fā)送的電報報文為:1110110111110000110則譯碼成原文為：7 12 9 27 22 23 27即 “ACBFDEF”三、詳細(xì)設(shè)計(1) .建立哈夫曼樹的算法：左義各廿點(diǎn)類型英中應(yīng)包含兩類數(shù)據(jù)一是權(quán)值域weight：- 是指針域而指針域中應(yīng)該包括指向左右孩子和指向雙親的指針這里分別用lchild、rdhild和 parent來表示，在實(shí)際構(gòu)造中由于是葉子節(jié)點(diǎn)來構(gòu)造新的根節(jié)點(diǎn)苴構(gòu)造過程中僅與葉子節(jié)點(diǎn) 的權(quán)重有關(guān)而與其數(shù)據(jù)域無關(guān)所

5、以構(gòu)造過程中不用考慮苴數(shù)值域，并且在鏈表中從葉子開始 存放，讓后不斷的將兩顆最小權(quán)值的子樹合并為一顆權(quán)值為英和的較大的子樹，逐步生成各 自內(nèi)部節(jié)點(diǎn)直到樹根。(2) .哈夫曼編碼的算法：將建立的哈夫曼樹從每個葉子廿點(diǎn)開始沿著雙親域回到根節(jié)點(diǎn)， 每走一步進(jìn)行編碼得到一位編碼值；由于每個葉子節(jié)點(diǎn)的哈夫曼編碼是從根i'j點(diǎn)到相應(yīng)的葉 子的路徑的各個分支的代碼組成的0和1序列，所以先得到了低位編碼后得到髙位編碼因此 可用一維數(shù)組從后向前來存放各位編碼值，并用start來記錄編碼的起始位苣。(3) .哈夫曼譯碼的算法：通過哈夫曼編碼所得到的0和1序列路徑，判斷是左結(jié)點(diǎn)還是右 結(jié)點(diǎn)的路徑，從而譯碼得

6、到權(quán)值內(nèi)容。(4) .將建立的哈夫曼樹、實(shí)現(xiàn)哈夫曼編碼、哈夫曼譯碼都左義成子函數(shù)的形式，然后在主 函數(shù)中調(diào)用它們。兩個類:class treepublic:int weight;int parent;int lch jch;void creathuffmantree();class codetypepublic:int bitsn+l;int start;void arrangecode();void transcode();codetype coden+l;tree hftreem+l;四、實(shí)現(xiàn)部分（核心代碼）第一步：建立哈夫曼樹void tree:creathuffmantree()int

7、 i, j, pl, p2;int si,s2;for (i=l;i<=m;i+) hftreeEi parent=0; hftreeilch二0; hftreei rch二0; hftreei weight=0;，z«endl;、B、C、cout«zz哈夫曼樹及其應(yīng)用cout«"輸入電報報文內(nèi)容AABBCAB(共長100字符,其中: D、E、F 分別有 7、9、12、22、23、27 個)：，z«endl;cout«"請分別輸入A B C D E F的權(quán)值：”； for(i=l;i<=n;i+)cin»

8、;hftreei weight;for (i=n+l; i<=m; i+) /進(jìn)行 nT 次合并pl二p2=0;/pl、p2分別指向兩個權(quán)值最小的值的位置 si二s2=32767;/sl、s2代表兩個最小權(quán)值 for (j二 1; j<=i-l; j+) /選兩個最小值if (hftree j. parent0)/該權(quán)值還沒有被選中if(hftreej weightsl)s2=sl;sl=hftreej weight;p2二pl;pl二 j;elseif(hftreej. weights2)s2=hftreej weight; P2二 j;/以下為合并hftreepl parent

9、二i;hftreep2 parent二i;hftreeilch二pl;hftreei rch二p2;hftreei weight=hftreepl weight+hftreep2 weight;cout«z/哈夫曼樹建立成功！ "<Xendl;cout«""endl;for (i=l; i二m; i+)/輸出合并后的結(jié)果cout«，z 權(quán)值:z，<<hftreei. weight«，z ""雙親結(jié)點(diǎn)： ，z«hftreei. parent«，z "«

10、;"左孩子："hftreei. lch«""右孩子: "<<hftreei. rch«endl;第二步：對權(quán)值進(jìn)行編碼同時并求出帶權(quán)路徑長度 void codetype: :arrangecodeOcodetype cd;int c, p;for (int i二l;iE;i+)cd. start=n+l;c=i;p=hftreei parent;while(p!=0)cd. start一一；if(hftreeplch二二c)cd. bitsEcd start=0;elsecd. bitsEcd. start二1;

11、c 二p；p二hftreep parent;codei二cd;for(i=l;i<=n;i+)int wpl=hftreei.weight:int ave;cout«endl; cout«"+«endl; cout<<z，編碼："<<endl;cout<</，權(quán)值，<<hftreei. weight«，z"<"編碼為："；for(int j二codei start;j<=n;j+)cout«codei bits j «&

12、quot;"wpl=hftreei. weight*(7-codei. bitsj);/求帶權(quán)路徑長度 ave二wpl/j;/平均編碼長度cout«z/ 帶權(quán)路徑長度為："wpl«endl;cout«，z平均編碼長度為:，z«ave;第三步：對編碼進(jìn)行譯碼void codetype:transcode()int i=m;char word;cout«endl;cout«""<endl;cout«z/進(jìn)行譯碼："endl;cout«請輸入信封內(nèi)容的編碼：&quo

13、t;；cin»word;cout«"(A二7、B二9、012、D二22、E二23、F二27) "endl;cout"譯碼成功！ "endl;cout«endl;cout«""<endl;cout«譯碼為：“；while (word" 0311 (word= f )/譯碼,向左為0,向右為1得到相應(yīng)的 根結(jié)點(diǎn)權(quán)值if (word=，O')i=hftreei. lch;elsei=hftreei rch;if(hftreei. lch=O)cout«hft

14、reei weigh;i=m;cin>>word;五、程序測試哈夫曼樹建立（通過分別輸入A、B、C、D、E、F權(quán)值）:用:A 應(yīng)中 其其 W一長一it八-z273 C : /成 、n±2別曼 i八負(fù) 諳哈i.子t:f =予t:蚩刊齊一子子葫聲脣孩孩孩孩一liks右云右右右右0 3 4 6 9- 0 ® 0 1i.子一騎予/-:一奎刊2?:lilli0 u 1 1 0 8 9 918111 7 7 冷矗疊饕«« =口 =口>二，二亍!:£亍>7*,二->!:"二定 誓親親親親親親親親對 亠II雙雙饕雙發(fā)線

15、223768550 79122212451編碼（對權(quán)值生成的哈夫曼樹進(jìn)行編碼，向左為0,向右為1,并對所得編碼進(jìn)行帶權(quán)路徑 長度和平均編碼長度運(yùn)算）：0帶權(quán)路徑長度為：28<-+ + + + 4-4 + + + + + *- + + + + 4-4 + + +1蒂權(quán)K徑長度為；36< + + + + +4+ + + + +4-+ + + + + 4 + + +帶權(quán)路徑長度為，？6十 * +十 * + 十 *帶權(quán)路徑長度為：44t-r1-r t-r1-帶權(quán)路徑長度為：46帶權(quán)路徑長度為：54餐B-9功進(jìn)請Kfi鐸譯碼（通過輸入已生成的編碼，反推出結(jié)點(diǎn)所在位置的權(quán)值）:1110110111110000110、E-23s F-27>降碼為：?12927222327六、總結(jié)實(shí)驗心得這次實(shí)驗最大遺憾是沒有把二義樹很好的顯示出來，對于本程序的主要部分， 哈夫曼樹的生成和哈夫曼碼的編譯，沒有任何的創(chuàng)新，無論是算法還是基本框架 都是套用課本上的經(jīng)典算法，時間復(fù)雜度都為0(112).51外在創(chuàng)建哈夫曼樹時選擇 兩個權(quán)值的結(jié)點(diǎn)的效率不是太高。每次都要先找到最大的權(quán)值，然后再進(jìn)行比較, 經(jīng)過兩次循環(huán)找到兩個最小的權(quán)值，這一個函數(shù)的時間復(fù)雜度比創(chuàng)建，編碼，