哈夫曼課程設(shè)計報告

1、<p><b>　　摘 要</b></p><p>　　在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成二進(jìn)制字符0和1組成的二進(jìn)制代碼，而這稱之為編碼。如果在編碼時考慮字符出現(xiàn)的頻率，讓出現(xiàn)頻率高的字符采用盡可能短的編碼，出現(xiàn)頻率低的字符采用稍長的編碼，構(gòu)成一種不等長的編碼，則電文的代碼就可能更短。哈夫曼是一種用于構(gòu)造使電文的編碼總長最短的編碼方案。</p><p&

2、gt;　　關(guān)鍵詞：哈夫曼編碼 數(shù)據(jù)通信 電文 頻率 二進(jìn)制</p><p><b>　　目 錄</b></p><p>　　1 哈夫曼編碼器1</p><p><b>　　1.1設(shè)計目的1</b></p><p><b>　　1.2設(shè)計要求1</b>&

3、lt;/p><p>　　2 問題的描述與解決2</p><p>　　3 哈夫曼編碼器的概要設(shè)計5</p><p><b>　　3.1 結(jié)構(gòu)圖5</b></p><p>　　3.2概要設(shè)計介紹5</p><p>　　4 結(jié)果顯示及說明7</p><p><b>

4、;　　4.1結(jié)果顯示7</b></p><p>　　4.2執(zhí)行方法說明9</p><p><b>　　5 小結(jié)10</b></p><p><b>　　參考文獻(xiàn)11</b></p><p><b>　　附錄12</b></p><p&g

5、t;<b>　　1 哈夫曼編碼器</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及對數(shù)據(jù)的各種操作。因此，主要有三個方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲結(jié)構(gòu)；對數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實現(xiàn)取決于數(shù)據(jù)的物理存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應(yīng)，通

6、過這組算法集合可以對數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。</p><p>　　在當(dāng)今信息時代，信息技術(shù)己成為當(dāng)代知識經(jīng)濟(jì)的核心技術(shù)。我們時刻都在和數(shù)據(jù)打交道。比如人們在外出工作時找最短路徑，在銀行查詢存款、通過互聯(lián)網(wǎng)查新聞、以及遠(yuǎn)程教育報名等，所有這些都在與數(shù)據(jù)發(fā)生關(guān)系。實際上，現(xiàn)實世界中的實體經(jīng)過抽象以后，就可以成為計算機(jī)上所處理的數(shù)據(jù)。</p><p>　　數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的

7、程序設(shè)計問題中所出現(xiàn)的計算機(jī)操作對象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機(jī)軟件和計算機(jī)硬件之間的一門計算機(jī)專業(yè)的核心課程，它是計算機(jī)程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。</p><p><b>　　1.1設(shè)計目的</b></p><p>　　（1）復(fù)習(xí)并靈活掌握二叉樹的各種存儲結(jié)構(gòu)和遍

8、歷方法</p><p>　　（2）了解靜態(tài)鏈表，并掌握其構(gòu)造方法</p><p>　　（3）掌握哈夫曼樹的構(gòu)造過程和哈夫曼編碼的求解方法</p><p>　?。?）復(fù)習(xí)并掌握文件讀寫的基本方法</p><p><b>　　1.2設(shè)計要求</b></p><p>　?。?）結(jié)點的權(quán)值由人工輸入，輸入

9、保存至文件中</p><p>　?。?）求得的哈夫曼編碼及WPL也必須寫入編碼文件中</p><p>　?。?）哈夫曼樹的存儲可以采用靜態(tài)鏈表或二叉鏈表</p><p>　　2 問題的描述與解決</p><p>　　問題描述：利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對

10、待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)。</p><p>　　程序設(shè)計包含的幾個方面：哈夫曼樹的建立，哈夫曼樹的編譯，求WPL</p><p>　　哈夫曼樹的建立由哈夫曼算法的定義可知，初始森林中共有n棵只含有根結(jié)點的二叉樹。算法的第二步是：將當(dāng)前森

11、林中的兩棵根結(jié)點權(quán)值最小的二叉樹，合并成一棵新的二叉樹；每合并一次，森林中就減少一棵樹，產(chǎn)生一個新結(jié)點。顯然要進(jìn)行n－1次合并，所以共產(chǎn)生n－1個新結(jié)點，它們都是具有兩個孩子的分支結(jié)點。由此可知，最終求得的哈夫曼樹中一共有2n－1個結(jié)點，其中n個結(jié)點是初始森林的n個孤立結(jié)點。并且哈夫曼樹中沒有度數(shù)為1的分支結(jié)點。我們可以利用一個大小為2n--1的一維數(shù)組來存儲哈夫曼樹中的結(jié)點。</p><p><b>

12、　　舉例：</b></p><p>　　求哈夫曼編碼的方法：</p><p><b>　　（1）構(gòu)造哈夫曼樹</b></p><p>　　（2）在哈夫曼樹上求葉結(jié)點的編碼。</p><p>　　假設(shè)哈夫曼樹按數(shù)據(jù)頻度的權(quán)值從小到大，采用順序存儲結(jié)構(gòu)存儲。每次找到的權(quán)值最小值作為新生結(jié)點的左孩子，權(quán)值次小值作為

13、新生結(jié)點的右孩子，則左孩子的權(quán)值加右孩子的權(quán)值之和為根結(jié)點的權(quán)值。</p><p>　　規(guī)定哈夫曼樹中的左分支代表0，右分支代表1，則從根結(jié)點到每個葉結(jié)點所經(jīng)過的路徑分支組成的0和1的序列便成為該葉子結(jié)點對應(yīng)的編碼。</p><p>　　WPL:從根結(jié)點到各個葉結(jié)點的路徑長度與相應(yīng)結(jié)點權(quán)值的乘積之和。</p><p>　　3 哈夫曼編碼器的概要設(shè)計</p>

14、;<p><b>　　3.1 結(jié)構(gòu)圖</b></p><p><b>　　系統(tǒng)結(jié)構(gòu)圖</b></p><p><b>　　3.2概要設(shè)計介紹</b></p><p>　?。╝）哈夫曼樹結(jié)點的類型定義：</p><p>　　typedef struct

15、 //結(jié)點類型定義</p><p><b>　　{</b></p><p>　　int wi; // 權(quán)值</p><p>　　char data; </p><p>　　int Parent,Lchild,Rchild; //定義父結(jié)點、左孩子、右

16、孩子</p><p><b>　　}huffm;</b></p><p>　　（b）哈夫曼樹的編碼類型定義;</p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　char bits[n+1];

17、 //用來存放0和1編碼</p><p>　　int start;</p><p><b>　　char ch;</b></p><p><b>　　}ctype;</b></p><p>　　ctype code[n+1];</p><p>　　這一次的程序中

18、，我們一共用了三個函數(shù)：</p><p>　　void HuffmTree(huffm HT[m+1]); // 構(gòu)造HuffmTree的函數(shù)</p><p>　　1.由給定的8個權(quán)值，構(gòu)造8顆由二叉樹擴(kuò)充得到的擴(kuò)充二叉樹，每一個擴(kuò)充二叉樹只有一個外部結(jié)點。2.在已經(jīng)構(gòu)造的所有擴(kuò)充二叉樹中，選取根結(jié)點的權(quán)值最小和次小的兩個，將它們作為左右子樹，構(gòu)造成一顆新的擴(kuò)充二叉樹，它的根結(jié)點的

19、權(quán)值為兩子樹的權(quán)值之和。3.重復(fù)執(zhí)行步驟2，每次都使擴(kuò)充二叉樹的個數(shù)減一，當(dāng)只剩下一顆擴(kuò)充二叉樹時，它便是所要構(gòu)造的哈夫曼樹。</p><p>　　void Huffmcode(ctype code[n+1]); //求HuffmTree編碼的函數(shù)</p><p>　　從根結(jié)點開始，尋找每一個葉子結(jié)點，在尋找的過程中，經(jīng)過左子樹時，編碼增加0，經(jīng)過右子樹時編碼增加1，當(dāng)每個葉子結(jié)點都

20、被訪問過時，便得到相應(yīng)的編碼。</p><p>　　void Output (ctype code[n+1]); //打印編碼函數(shù)</p><p>　　只要將已經(jīng)建立好的哈夫曼編碼，一一輸出就行了，用程序來實現(xiàn)，再好好排版，就能顯示出來了。</p><p><b>　　4 結(jié)果顯示及說明</b></p><p>

21、;<b>　　4.1結(jié)果顯示</b></p><p><b>　　圖（1）</b></p><p><b>　　圖（2）</b></p><p>　　圖（3） 圖（4）</p><p><b>　

22、　4.2執(zhí)行方法說明</b></p><p>　　圖（1）：執(zhí)行菜單主界面 </p><p>　　圖（2）：輸入“1”，執(zhí)行哈夫曼編碼。根據(jù)上面的提示輸入8個字符和8個權(quán)值，按回車后就會顯示出字符，權(quán)值，葉結(jié)點及哈夫曼編碼</p><p>　　圖（3）：將輸入的字符及權(quán)值保存至記事本huffman中</p><p>　　圖（4）：

23、將執(zhí)行后得到的哈夫曼編碼保存至huffmancode中</p><p><b>　　5 小結(jié)</b></p><p>　　在這一次的課程設(shè)計中，我們編寫好源代碼后的調(diào)試過程中出現(xiàn)了不少的錯誤，遇到了很多麻煩及困難，經(jīng)過千辛萬苦的糾結(jié)最終我們最終還是找出錯誤，調(diào)試成功了。</p><p>　　在編寫這個程序的過程中，我復(fù)習(xí)了之前學(xué)的基本語法，哈弗

24、曼樹最小路徑的求取，哈弗曼編碼及譯碼的應(yīng)用范圍，程序結(jié)構(gòu)算法等一系列的問題，它使我對數(shù)據(jù)結(jié)構(gòu)改變了看法。在這次設(shè)計過程中，體現(xiàn)出自己設(shè)計模具的能力以及綜合運用知識的能力，體會了學(xué)以致用、突出自己勞動成果的喜悅心情，也從中發(fā)現(xiàn)自己平時學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補。</p><p>　　我們編好后在老師的指導(dǎo)下，努力想使程序更完美，更符合要求，老師讓我們在做好的基礎(chǔ)上，嘗試一下哈夫曼譯碼的實現(xiàn)。于是我在課后參考

25、了老師給的程序，我花費了很多的時間去把載入文件這塊做的更好，功夫不負(fù)有心人，我最終勝利的完成了。但譯碼的實現(xiàn)最終沒有成功，但通過對譯碼的編寫過程中，我們也了解了哈夫曼譯碼的求解思想。</p><p>　　通過本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計，我學(xué)到了很多在上課沒來得及消化的知識，并對求哈夫曼樹及哈夫曼編碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識，真正學(xué)會一種算法了。當(dāng)求解一個算法時,不是拿到問題就

26、不加思索地做，而是首先要先對它有個大概的了解，接著再詳細(xì)地分析每一步怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]. 譚浩強．C程序設(shè)計（第四版）. 清華大學(xué)出版社</p><p>　　[2] 陳元春，王中華，張亮，王勇 編著． 實用

27、數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（第三版）.中國鐵道出版社.</p><p>　　[3] 何欽銘，馮雁，陳越 著. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計. 浙江大學(xué)出版社</p><p>　　[4] 陳媛，何波，蔣鵬，劉潔 編著. 數(shù)據(jù)結(jié)構(gòu) 學(xué)習(xí)指導(dǎo)·實驗指導(dǎo)·課程設(shè)計. 機(jī)械工業(yè)出版社</p><p>　　[5] 秦鋒，袁志祥 主編 陳學(xué)進(jìn)，鄭嘯，程澤凱，王森玉副編. 數(shù)據(jù)結(jié)構(gòu)（C

28、語言版）例題詳解與課程設(shè)計. 指導(dǎo)中國科學(xué)技術(shù)大學(xué)出版社</p><p><b>　　附錄</b></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <string.h></

29、p><p>　　#define n 8 //n為定的8個數(shù)</p><p>　　#define m 2*n-1 //具有n個葉結(jié)點的哈夫曼樹共有2n-1個結(jié)點*/</p><p>　　#define max 2000 //最大值</p><p>　　typedef struc

30、t</p><p><b>　　{</b></p><p>　　int wi; //權(quán)值</p><p>　　char data;</p><p>　　int Parent,Lchild,Rchild; //定義父結(jié)點、左孩子、右孩子</p><p><

31、;b>　　}huffm;</b></p><p>　　huffm HT[m+1];</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　char bits[n+1];</p><p>　　int start;</p&

32、gt;<p><b>　　char ch;</b></p><p><b>　　}ctype;</b></p><p>　　ctype code[n+1];</p><p>　　void HuffmTree(huffm HT[m+1]);</p><p>　　void Huffmcod

33、e(ctype code[n+1]);</p><p>　　void Output (ctype code[n+1]);</p><p>　　//構(gòu)造HuffmTree的函數(shù)</p><p>　　void HuffmTree(huffm *HT)</p><p><b>　　{</b></p><p&

34、gt;　　int i,j,p1,p2;</p><p>　　int s1,s2;</p><p>　　for(i=n+1;i<=m;i++)</p><p><b>　　{</b></p><p><b>　　p1=p2=0;</b></p><p>　　s1=s2=m

35、ax;</p><p>　　for(j=1;j<=i-1;j++)</p><p>　　if(HT[j].Parent==0)</p><p>　　if(HT[j].wi <s1)</p><p><b>　　{</b></p><p><b>　　s2=s1;</b&

36、gt;</p><p>　　s1=HT[j].wi;</p><p>　　p2=p1; p1=j;</p><p><b>　　}</b></p><p>　　else if(HT[j].wi<s2)</p><p><b>　　{</b></p><

37、;p>　　s2=HT[j].wi ;</p><p><b>　　p2=j;</b></p><p><b>　　}</b></p><p>　　HT[p1].Parent=HT[p2].Parent=i;</p><p>　　HT[i].Lchild=p1;</p><p

38、>　　HT[i].Rchild=p2;</p><p>　　HT[i].wi=HT[p1].wi+HT[p2].wi;</p><p><b>　　}</b></p><p><b>　　return ;</b></p><p><b>　　}</b></p>

39、<p>　　//求HuffmTree編碼的函數(shù)</p><p>　　void Huffmcode(ctype code[n+1])</p><p><b>　　{</b></p><p>　　int i,p,s;</p><p><b>　　ctype md;</b></p>

40、;<p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　md.ch=code[i].ch;</p><p>　　md.start = n+1;</p><p><b>　　s=i;</b></p><p&g

41、t;　　p=HT[i].Parent;</p><p>　　while(p!=0)</p><p><b>　　{</b></p><p>　　md.start--;</p><p>　　if(HT[p].Lchild==s)</p><p>　　md.bits[md.start]='0&

42、#39;;</p><p><b>　　else </b></p><p>　　md.bits[md.start] ='1';</p><p><b>　　s=p;</b></p><p>　　p=HT[p].Parent;</p><p><b>

43、　　}</b></p><p>　　code[i] = md;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　//打印編碼函數(shù)</b></p><p>　　void Output(

44、ctype code[n+1])</p><p><b>　　{</b></p><p><b>　　FILE *fp;</b></p><p>　　if ((fp=fopen("huffmancode.txt","w"))==NULL)</p><p>&l

45、t;b>　　{</b></p><p>　　printf("不能打開文件\n");</p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p>　　fprintf(fp,"\n哈夫曼編碼");

46、</p><p><b>　　int i,j;</b></p><p>　　int WPL=0,count=0;</p><p>　　printf("\n");</p><p>　　printf("\n");</p><p>　　puts("

47、\t\t========================================");</p><p>　　printf("\n");</p><p>　　printf("\t\t\t葉結(jié)點\t\t哈夫曼編碼");</p><p>　　for(i=1;i<=n;i++)</p><p

48、><b>　　{</b></p><p>　　printf("\n\t\t\t %c\t\t",code[i].ch );</p><p>　　for(j=1;j<=n;j++)</p><p><b>　　{</b></p><p>　　if(j<code

49、[i].start)</p><p>　　printf(" ");</p><p><b>　　else</b></p><p>　　if((code[i].bits[j]=='0')||(code[i].bits[j]=='1'))</p><p><b>

50、　　{</b></p><p>　　printf("%c",code[i].bits[j]);</p><p><b>　　count++;</b></p><p>　　fputc(code[i].bits[j],fp);</p><p><b>　　}</b><

51、;/p><p>　　} fprintf(fp,"\n");</p><p>　　WPL=WPL+count*HT[i].wi;</p><p><b>　　count=0;</b></p><p><b>　　}</b></p><p>　　printf(&

52、quot;\n\n");</p><p>　　printf("\t\t\t\tWPL=%d\n",WPL);</p><p>　　fprintf(fp,"\n WPL=%d",WPL);</p><p>　　puts(" \t\t=====================================

53、=== ");</p><p>　　fclose(fp);</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　FILE *fp;</b><

54、;/p><p>　　if ((fp=fopen("huffman.txt","w"))==NULL)</p><p><b>　　{</b></p><p>　　printf("不能打開文件\n");</p><p><b>　　exit(0);</

55、b></p><p><b>　　}</b></p><p><b>　　int i,j;</b></p><p><b>　　int w;</b></p><p>　　int flag=1;</p><p>　　int choice;</p

56、><p>　　ctype code[n+1];</p><p>　　char temp[n+1];</p><p>　　int temp2[n+1];</p><p>　　printf("\n");</p><p>　　(" \n\t\t 哈夫曼編碼器

57、 \n");</p><p>　　printf(" \n\t\t printf 主菜單 \n");</p><p>　　printf(" \n\t\t******************************************\n");&l

58、t;/p><p>　　printf(" \n\t\t* Would you want to play? *\n");</p><p>　　printf(" \n\t\t* 1-Yes and Start *\n");</p><p>　　pri

59、ntf(" \n\t\t* 0-No and Exit *\n");</p><p>　　printf(" \n\t\t******************************************\n");</p><p>　　printf(" \n\t\t請選擇菜單號:

60、 ");</p><p>　　scanf("%d",&choice);</p><p>　　printf("\n");</p><p>　　while(flag&&(choice==1))</p><p><b>　　{</b></p>

61、<p>　　choice = 0;</p><p>　　for(i=1;i<=m;i++)//初始化</p><p><b>　　{ </b></p><p>　　HT[i].data =NULL;</p><p>　　HT[i].wi=0;</p><p>　　HT[i].P

62、arent = 0;</p><p>　　HT[i].Lchild = HT[i].Rchild = 0;</p><p><b>　　}</b></p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　cod

63、e[i].start = 0;</p><p>　　code[i].ch = NULL;</p><p>　　for(j=1;j<=n;j++)</p><p>　　code[i].bits[j] = NULL;</p><p><b>　　}</b></p><p>　　printf(&q

64、uot; \t\tPlease input %d char(用空格隔開，以回車結(jié)束): \n",n);/*輸入字母*/</p><p>　　printf(" \t\t");</p><p>　　getchar();</p><p>　　scanf("%c %c %c %c %c %c %c %c",&

65、temp[1],&temp[2],&temp[3],&temp[4],&temp[5],&temp[6],&temp[7],&temp[8]);</p><p>　　fprintf(fp,"字符");</p><p>　　for(i=1;i<=n;i++)</p><p><b&

66、gt;　　{</b></p><p>　　code[i].ch =temp[i];</p><p>　　HT[i].data =temp[i];</p><p>　　fputc(temp[i],fp);</p><p><b>　　}</b></p><p>　　printf(&quo

67、t;\n\n");</p><p>　　printf(" \t\tPlease input %d rate(用空格隔開，以回車結(jié)束): \n",n);/*輸入權(quán)值*/</p><p>　　fprintf(fp,"\n權(quán)值");</p><p>　　printf(" \t\t");</

68、p><p>　　getchar();</p><p>　　scanf("%d %d %d %d %d %d %d %d",&temp2[1],&temp2[2],&temp2[3],&temp2[4],&temp2[5],&temp2[6],&temp2[7],&temp2[8]);</p>&l

69、t;p>　　fprintf(fp,"%d %d %d %d %d %d %d %d",temp2[1],temp2[2],temp2[3],temp2[4],temp2[5],temp2[6],temp2[7],temp2[8]);</p><p>　　printf("\n");</p><p>　　puts(" \t\t====

70、=================================");</p><p>　　printf(" \t\t\t 字符 權(quán)值\n");</p><p>　　for(i=1;i<n+1;i++)</p><p><b>　　{</b></p><p>　　print

71、f(" \t\t\t %c %4d \n",temp[i],temp2[i]);</p><p><b>　　}</b></p><p>　　puts(" \t\t======================================");</p><p>　　for(i=1;i&

72、lt;=n;i++)</p><p><b>　　{</b></p><p>　　w= temp2[i];</p><p>　　HT[i].wi = w;</p><p><b>　　}</b></p><p>　　HuffmTree(HT);</p><

73、p>　　Huffmcode(code);</p><p>　　Output(code);</p><p>　　printf("\n");</p><p>　　printf("\n");</p><p>　　printf(" \n\t\t************************

74、********************\n");</p><p>　　printf(" \n\t\t Continue? \n");</p><p>　　printf(" \n\t\t* 1--Contine *\n

75、");</p><p>　　printf(" \n\t\t* 0--Exit *\n");</p><p>　　printf(" \n\t\t********************************************\n");</p>&l

76、t;p>　　printf(" \n\t\t請選擇菜單號: ");</p><p>　　scanf("%d",&choice);</p><p>　　if(choice!=1)</p><p><b>　　break;</b></p><p><b>