數(shù)據(jù)結構課程設計---哈夫曼編碼器

1、<p><b>　　摘 要</b></p><p>　　哈夫曼（huffman）樹是一種帶權路徑長度最小的二叉樹，也稱最優(yōu)二叉樹，它有著極為廣泛的應用。而我今天做的課程設計就是其中的一個應用---哈夫曼編碼器。其實它的思想很簡單，顯示根據(jù)輸入的權值建立一棵哈夫曼樹，然后根據(jù)哈夫曼數(shù)求出各個葉結點的編碼。這樣就構成了一個最簡單的哈夫曼編碼器。</p><p>

2、;　　關鍵詞：哈夫曼樹 編碼器 最優(yōu)二叉樹 帶權路徑長度</p><p><b>　　目 錄</b></p><p><b>　　1 課題分析1</b></p><p>　　1.1 設計目的1</p><p>　　1.2 設計要求1</p><p><

3、;b>　　1.3設計內容1</b></p><p>　　2 總體設計與分析3</p><p>　　2．1功能函數(shù)設計3</p><p>　　2.1.1建立哈夫曼樹3</p><p>　　2.2.2求哈夫曼編碼函數(shù)3</p><p>　　2.2.3打印編碼函數(shù)3</p>&l

4、t;p><b>　　3 程序說明4</b></p><p><b>　　3.1 結構圖4</b></p><p><b>　　4 程序調試5</b></p><p><b>　　4.1 菜單5</b></p><p>　　4.2 輸入葉結點和

5、權值6</p><p>　　4.3 輸出哈夫曼編碼7</p><p><b>　　5 設計問題8</b></p><p><b>　　5.1存入文件8</b></p><p>　　5.1.1問題18</p><p>　　5.1.2問題28</p>&

6、lt;p><b>　　6 小結9</b></p><p><b>　　參考文獻10</b></p><p><b>　　源代碼11</b></p><p><b>　　1 課題分析</b></p><p>　　在當今信息爆炸時代，如何采用有效的

7、數(shù)據(jù)壓縮技術節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡的傳送時間已越來越引起人們的重視，哈夫曼編碼正是一種應用廣泛且非常有效的數(shù)據(jù)壓縮技術。哈夫曼編碼是一種編碼方式，以哈夫曼樹—即最優(yōu)二叉樹，帶權路徑長度最小的二叉樹，經(jīng)常應用于數(shù)據(jù)壓縮。哈夫曼編碼使用一張?zhí)厥獾木幋a表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編

8、碼，這便使編碼之后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的）。赫夫曼編碼的應用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個葉子對應的字符的編碼，這就是哈夫曼編碼。</p><p><b>　　1.1 設計目的<

9、/b></p><p>　?。?）復習并靈活掌握二叉樹的各種儲存結構和遍歷方法。</p><p>　?。?）了解靜態(tài)鏈表，并掌握其構造方法。</p><p>　　（3）掌握哈夫曼樹的構造過程和哈夫曼編碼的求解方法。</p><p>　　（4）復習掌握文件讀寫的基本方法。</p><p><b>　　1.

10、2 設計要求</b></p><p>　?。?）求得的哈夫曼編碼及WPL必須寫入編碼文件。</p><p>　?。?）哈夫曼樹的存儲可以采用靜態(tài)鏈表或二叉鏈表。</p><p><b>　　1.3設計內容</b></p><p>　　我在實驗中采用的是靜態(tài)鏈表作為存儲結構，其數(shù)據(jù)類型可以定義為：</p&

11、gt;<p>　　#define m 2*n-1 /*m為哈夫曼樹的結點*/ /*具有n個葉結點的哈夫曼樹共有2n-1個結點*/</p><p>　　typedef struct</p><p>　　{int wi; /*定義權值*/</p><p>　　char data;

12、 /*定義葉結點*/</p><p>　　int Parent,Lchild,Rchild; /*定義父結點、左孩子、右孩子*/</p><p><b>　　}huffm;</b></p><p>　　huffm HT[m+1]; /*靜態(tài)鏈表HT[m+1]*/</p>&l

13、t;p>　　(1)從文件中讀取所有結點的權值，將讀取的權值放到靜態(tài)鏈表中，并初始化靜態(tài)鏈表。</p><p>　　（2）依據(jù)給定的權值，不斷生成各分支結點，直到生成樹根結點為止，得到生成</p><p>　　哈夫曼樹后的靜態(tài)鏈表。</p><p>　?。?）規(guī)定所有的左分支為0，右分支為1，從樹根到葉子所經(jīng)過的分支構成的01編碼，即是對應葉子的哈夫曼編碼。&l

14、t;/p><p>　?。?）求出所有葉子的哈夫曼編碼，并將編碼寫入文件。</p><p>　　2 總體設計與分析</p><p>　　通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字符串。構造一棵赫夫曼樹，此構造過程稱為赫夫曼編碼。設計實現(xiàn)的功能： (1) 赫夫曼樹的建立； (2) 赫夫曼編碼的生成； (3) 編碼文件的譯碼

15、。</p><p><b>　　2．1功能函數(shù)設計</b></p><p>　　2.1.1建立哈夫曼樹</p><p>　　void HuffmTree(huffm HT[m+1]);</p><p>　　我用的是手動輸入，首先提醒用戶輸入8個葉結點，即8個字母，輸入完畢后提醒用戶輸入8個權值。以上的兩個輸入的輸入格式都

16、用空格隔開，以回車結束。哈夫蠻樹建立成功。</p><p><b>　　其基本算法是：</b></p><p>　?、儆山o定的8個權值，構造由空二叉樹擴充得到的擴充二叉樹，每個數(shù)只有一個外部結點。</p><p>　?、谠谝呀?jīng)構造的擴充二叉樹中，選取根結點權值最小和次小的兩個。將它們作為左子樹、右子樹，構造成一顆新的擴充二叉樹，它的根結點的權值

17、為兩子樹的權值之和。</p><p>　?、壑貜蛨?zhí)行步驟②，每次都使擴充的二叉樹的個數(shù)減一，當只剩下一棵擴充二叉樹時，它便是所要構造的哈夫曼樹。</p><p>　　2.2.2求哈夫曼編碼函數(shù)</p><p>　　void Huffmcode(ctype code[n+1]);</p><p>　　從根結點開始，尋找每一個葉結點，在尋找過程中

18、，經(jīng)過左子樹時，編碼增加“0”，經(jīng)過右子樹時，編碼增加“1”，當每一個葉結點都訪問過時，便得到相應的編碼。</p><p>　　2.2.3打印編碼函數(shù)</p><p>　　void Output (ctype code[n+1]);</p><p>　　打印編碼函數(shù)即輸出編碼函數(shù)。當用戶輸好葉結點和權值后，通過哈夫曼編碼函數(shù)進行編碼，然后通過打印編碼函數(shù)將哈夫曼編碼

19、顯示在屏幕上。</p><p><b>　　3 程序說明</b></p><p><b>　　3.1 結構圖</b></p><p>　　這就是整個程序的基本流程，總共分為三大塊：建立哈夫曼樹、哈夫曼編碼、輸出哈夫曼編碼。其實思想很簡單，按照這個步驟來就行了。首先，用戶手動輸入8個字母和權，建立好哈夫曼樹后，左子樹為‘0’

20、，右子樹為‘1’，根據(jù)這個可以寫出每個葉結點的編碼。最后輸出即可。</p><p>　　這整個程序過程都是通過C語言實現(xiàn)的，所以都是一些很簡單的語句，通俗易懂，這樣我修改起來也比較方便。</p><p><b>　　4 程序調試</b></p><p><b>　　4.1 菜單</b></p><p&g

21、t;　　這只是一個很簡單的菜單，在這次的實驗中，我沒有在菜單上花很多功夫，所以這只是一個再簡單不過的開始界面，就是詢問用戶是否要繼續(xù)玩下去。</p><p>　　4.2 輸入葉結點和權值</p><p><b>　　用戶手動輸入</b></p><p><b>　　輸入8個字母：</b></p><p&

22、gt;　　a s d f g h j k</p><p><b>　　輸入8個權值：</b></p><p>　　12 22 33 45 6 9 8 24</p><p>　　4.3 輸出哈夫曼編碼</p><p>　　在這個環(huán)節(jié)中，先輸出編譯好的哈夫曼編碼，接下來還要求最短路徑WPL。然后下面的那個菜單一開始的那個菜單

23、是相同的意思，就是詢問用戶是否要繼續(xù)玩下去，如果選擇1，則用戶再次手動輸入葉結點和權值，再進行編譯。</p><p><b>　　5 設計問題</b></p><p><b>　　5.1存入文件</b></p><p>　　這次課程設計輸入的葉結點和權值，還有最后的哈夫曼編碼都是要存入文件。剛開始以為加進去個文件會很簡單，

24、因為我們上學期也做過課程設計，是C語言的，最主要的就是弄文件，所以這個本來沒有多大問題。但是這次加了文件后出現(xiàn)了比較麻煩的問題。</p><p><b>　　5.1.1問題1</b></p><p>　?、贋槭裁从浭卤緯霈F(xiàn)空白？</p><p>　　在我加入文件后顯示出現(xiàn)了許多小問題,具體是什么問題我已經(jīng)記得不清，只知道最后總算是把錯誤全找出

25、來了，調通了，本來以為沒錯了，后來運行的一切都很正常。等到最后都執(zhí)行完了，打開文件發(fā)現(xiàn)文件是空白的，什么都沒有，就這個問題我嘗試過很多遍，可記事本始終是空白的，后來我發(fā)現(xiàn)記事本的大小為1KB，就說明里面是肯定有東西，在研究了多遍后，發(fā)現(xiàn)記事本里都是空格，所以我們是看不見的，但用鼠標全選一下就會發(fā)現(xiàn)有東西。</p><p><b>　　5.1.2問題2</b></p><p

26、>　　②為什么記事本中會全都是空格鍵？</p><p>　　上面那個問題算是解決了，但接下來有個更頭疼的問題---為什么記事本中會都是空格鍵呢？怎么樣才能讓記事本中出現(xiàn)我輸入的哪些字符和數(shù)字呢？</p><p>　　本來我是把保存文件單獨弄一個函數(shù)的---void save();但是由于文件出了問題，所以我就把文件的那個函數(shù)刪掉了，把它加入到程序中。然后我發(fā)現(xiàn)把文件加入主函數(shù)中后、文

27、件夾中就會出現(xiàn)東西。但是至于為什么將文件單獨作為一個函數(shù)時，文件夾中出現(xiàn)的都是空格還沒有弄清楚。</p><p><b>　　6 小結</b></p><p>　　在我自己課程設計中，就在編寫好源代碼后的調試中出現(xiàn)了不少的錯誤，遇到了很多麻煩及困難，我的調試及其中的錯誤和我最終找出錯誤，修改為正確的能夠執(zhí)行的程序中，通過分析，我學到了：</p><

28、p>　　通過這次課程設計，讓我對一個程序的數(shù)據(jù)結構有更全面更進一步的認識，根據(jù)不同的需求，采用不同的數(shù)據(jù)存儲方式，不一定要用棧，二叉樹等高級類型，有時用基本的一維數(shù)組，只要運用得當，也能達到相同的效果，甚至更佳，就如這次的課程設計，通過用for的多重循環(huán)，舍棄多余的循環(huán)，提高了程序的運行效率。在編寫這個程序的過程中，我復習了之前學的基本語法，哈弗曼樹最小路徑的求取，哈弗曼編碼的應用范圍，程序結構算法等一系列的問題它使我對數(shù)據(jù)結構改

29、變了看法。在這次設計過程中，體現(xiàn)出自己單獨設計模具的能力以及綜合運用知識的能力，體會了學以致用、突出自己勞動成果的喜悅心情，也從中發(fā)現(xiàn)自己平時學習的不足和薄弱環(huán)節(jié)，從而加以彌補。</p><p>　　而且我還學習了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學習有關于哈夫曼編碼的知識，真正學會一種算法了。當求解一個算法時,不是拿到問題就不加思索地做，而是首先要先對

30、它有個大概的了解，接著再詳細地分析每一步怎么做，無論自己以前是否有處理過相似的問題，只要按照以上的步驟，必定會順利地做出來。</p><p>　　一個成功的項目必須在寫代碼前，先要對課題有充分的思考和規(guī)劃，否則即使完成了項目也會浪費很多的時間和精力，我認為科學合理的編程方法是我這次課程設計的最大收獲。</p><p><b>　　參考文獻</b></p>

31、<p>　　[1]. 譚浩強著．C語言設計（第四版）．北京：清華大學大學出版社，2010．</p><p>　　[2] 陳元春 王中華 張亮 王勇等著．實用數(shù)據(jù)結構基礎（第三版）.北京，中國鐵道出版社，2011 </p><p>　　[3] 秦鋒 袁志祥著.數(shù)據(jù)結構（C語言版）例題詳解與課程設計指導. 安徽:中國科學技術大學出版社,2007</p><p&g

32、t;<b>　　源代碼</b></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <string.h></p><p>　　#define n 8 /

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

34、b>　　{</b></p><p>　　int wi; /*權值*/</p><p>　　char data;</p><p>　　int Parent,Lchild,Rchild;/*定義父結點、左孩子、右孩子*/</p><p><b>　　}huffm;</b>

35、</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><p><b>　　

36、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 Huffmcode(ctype code[n+1]);</p

37、><p>　　void Output (ctype code[n+1]);</p><p>　　/* 構造HuffmTree的函數(shù)*/</p><p>　　void HuffmTree(huffm *HT)</p><p><b>　　{</b></p><p>　　int i,j,p1,p2;<

38、;/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=max;</p><p&g

39、t;　　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></p><p&g

40、t;　　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><p>　　s2=HT[j].wi ;&

41、lt;/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>　　HT[i].Rchild=p2;

42、</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><p>　　/* 求Huffm

43、Tree編碼的函數(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><p>　　for(i

44、=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>　　p=HT[i].Parent;

45、</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';</p>&l

46、t;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>　　}</b></p

47、><p>　　code[i] = md;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　/*打印編碼函數(shù)*/</p><p>　　void Output(ctype code[n+1])</p><p>

48、;<b>　　{</b></p><p><b>　　FILE *fp;</b></p><p>　　if ((fp=fopen("huffmancode.txt","w"))==NULL)</p><p><b>　　{</b></p><

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

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

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

52、<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[i].start)</p><p>　　pri

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

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

55、/b></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>　　pr

56、intf("\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===============================

57、========= ");</p><p>　　fclose(fp);</p><p><b>　　}</b></p><p><b>　　/*主函數(shù)*/</b></p><p>　　void main()</p><p><b>　　{</b>

58、;</p><p><b>　　FILE *fp;</b></p><p>　　if ((fp=fopen("huffman.txt","w"))==NULL)</p><p><b>　　{</b></p><p>　　printf("不能打開文件

59、\n");</p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p>　　int i,j,w;</p><p>　　int flag=1;</p><p>　　int choice;</p><

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

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

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

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

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

65、　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].Parent = 0;&l

66、t;/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>　　code[i].start =

67、 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(" \t\tP

68、lease input %d char(用空格隔開，以回車結束): \n",n);/*輸入字母*/</p><p>　　printf(" \t\t");</p><p>　　getchar();</p><p>　　scanf("%c %c %c %c %c %c %c %c",&temp[1],&

69、;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>　　{</b

70、></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("\n\n"

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

72、>　　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><p>　　fpr

73、intf(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================

74、=====================");</p><p>　　printf(" \t\t\t 字符 權值\n");</p><p>　　for(i=1;i<n+1;i++)</p><p>　　printf(" \t\t\t %c %4d \n",temp[i],temp2[i]

75、);</p><p>　　puts(" \t\t======================================");</p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　w= temp2[i];</p>

76、<p>　　HT[i].wi = w;</p><p><b>　　}</b></p><p>　　HuffmTree(HT);</p><p>　　Huffmcode(code);</p><p>　　Output(code);</p><p>　　printf("\n&

77、quot;);</p><p>　　printf("\n");</p><p>　　printf(" \n\t\t********************************************\n");</p><p>　　printf(" \n\t\t Continue

78、? \n");</p><p>　　printf(" \n\t\t* 1--Contine *\n");</p><p>　　printf(" \n\t\t* 0--Exit *\

79、n");</p><p>　　printf(" \n\t\t********************************************\n");</p><p>　　printf(" \n\t\t請選擇菜單號: ");</p><p>　　scanf("%d",&ch

80、oice);</p><p>　　if(choice!=1)</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　getchar();</p><p><b>　　return;</b></