1、 蘭州商學院隴橋學院 工學系課程設計報告設 計 題 目：哈夫曼（huffman）編譯碼器 系 別： 專 業 (方 向)： 年 級、 班： 學 生 姓 名： 學 生 學 號： 指 導 教 師： 年 月日 目 錄哈夫曼(huffman )編譯碼器3一、 編譯碼器開發的背景3二、系統的分析與設計3（一）系統功能要求3（二）系統模塊結構設計4三、系統的設計與實現6（一）main()6（二）運算71. 權值運算quanzhi()72. 印二叉樹函數huffmantree( )73.編譯碼運算huffmancode()94. 輸出運算 shuchu()9四、系統測試10（一）測試主函數10（二）測試印二叉

2、樹函數10（三） 測試譯碼運算函數11五、總結12六、附件（代碼、部分圖表）13哈夫曼(huffman )編譯碼器1、 編譯碼器開發的背景 利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接收端將傳來的數據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統。二、系統的分析與設計（一）系統功能要求一個完整的系統應具有以下功能：1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。

3、2) E：編碼（Encoding）。利用以建好的哈夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。3) D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。4) P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。5) T：印哈夫曼樹（Tree Printing）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫

4、曼樹寫入文件TreePrint中。（二）系統模塊結構設計通過對系統功能的分析，哈夫曼（huffman）編譯碼器功能如圖（1）所示。哈夫曼（huffman ）編譯碼器初 始 化輸出二叉樹編 譯 碼輸出 代碼選 擇 操 作 圖（1）哈夫曼（huffman)編譯碼器功能圖通過上圖的功能分析，把整個系統分為四個模塊：1.初始化模塊，該模塊主要實現：輸入二叉樹的結點數，以及要加密的句子，建立哈夫曼樹。2.輸出二叉樹模塊，該運算模塊主要實現：將輸入的字符串中每個字符出現的次數當作權值，建立二叉樹，將二叉樹的parent,weight,lchild,rchild輸出。3.譯碼模塊，該操作主要實現：對編碼后的

5、代碼進行譯碼，然后輸出。4.輸出模塊，該操作主要進行表頭的輸出。開始是 用戶選擇否y=1否y=2 輸入葉子節點數y=3對輸入的句子進行編碼 輸入句子 退出系統輸出每個字符的編碼建立二叉樹，輸出二叉樹 結束 圖流程圖三、系統的設計與實現（一）main()輸出1.輸出二叉樹操作2.進行輸出二叉樹操作3.退出編譯碼操作系統，并讓用戶選擇所進行的操作，對其調用。 該模塊的具體代碼如下所示：void main()int i,n,s=1; hnodetype huffnodemaxnode;while(s) shuchu(); scanf("%d",&i); switch(i)

6、 case 1: haffmantree(huffnode,&n); break; case 2: haffmancode(); break; case 3: s=0; break; 分析：首先輸出一個主菜單，方便用戶進行操作，用switch語句調用函數使用戶對其進行選擇要執行的操作（1.輸出二叉樹操作，2.進行編譯碼操作，3.退出程序）。（二）運算 該模塊的具體代碼如下所示：1. 權值運算quanzhi() 分析：此函數用于對一串字符進行求權值運算，利用循環將一串字符中每個字符的個數設定為權值。void quanzhi(int tmaxleaf,char smaxleaf,int n

7、)/求權值函數，將句子中的字符出現的個數當作權值int i,j,h;for(i=0;i<n;i+)for(j=0;j<n;j+)if(si=sj)h+;ti=h;2. 印二叉樹函數huffmantree( )void haffmantree(hnodetype huffnodemaxnode,int *m)int i,j,n,k;int m1,m2,x1,x2;char smaxleaf,tmaxleaf; printf("輸入葉子結點個數：");scanf("%d",&n);for(i=0;i<2*n-1;i+)/數組huff

8、node初始化huffnodei.weight=0; huffnodei.parent=-1;huffnodei.lchild=-1;huffnodei.rchild=-1;printf("輸入要編譯的句子的n"); for(i=0;i<n;i+) printf("第%d個結點",i+1);scanf("%d",&huffnodei.weight);getchar();printf("印二叉樹：n"); for(i=0;i<n;i+)quanzhi(t,s,n); k=huffnodei.wei

9、ght;for(i=0;i<n-1;i+)/構造哈夫曼樹m1=m2=maxvalue; x1=x2=0;for(j=0;j<n+i;j+)/選取最小和次小兩個權值if(huffnodej.parent=-1&&huffnodej.weight<m1)m2=m1;x2=x1;m1=huffnodej.weight;x1=j;elseif(huffnodej.parent=-1&&huffnodej.weight<m2)m2=huffnodej.weight;x2=j;/將找出的兩棵子樹合并為一顆子樹 huffnodex1.parent=n+

10、i; huffnodex2.parent=n+i; huffnoden+i.weight=huffnodex1.weight+huffnodex2.weight; huffnoden+i.lchild=x1; huffnoden+i.rchild=x2;for(i=0;i<2*n-1;i+)printf(" %4d",k); printf(" %4d",huffnodei.lchild);printf(" %4d",huffnodei.rchild);printf(" %4dn",huffnodei.pare

11、nt);*m=n;3.編譯碼運算huffmancode()void haffmancode()hnodetype huffnodemaxnode;hcodetype huffcodemaxleaf,cd;int i,j,c,p,n=0;haffmantree(huffnode,&n);for(i=0;i<n;i+)cd.start=n-1;c=i;p=huffnodec.parent;while(p!=-1)if(huffnodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=huffnodec.p

12、arent;for(j=cd.start+1;j<n;j+)huffcodei.bitj=cd.bitj;huffcodei.start=cd.start;for(i=0;i<n;i+)printf("第%d個譯碼為：",i+1);for(j=huffcodei.start+1;j<n;j+)printf("%4d",huffcodei.bitj);printf("n");4. 輸出運算 shuchu()void shuchu()printf("*n");printf("* |* 哈夫曼

13、樹的編譯碼 * | *n");printf("* |* 1.輸出二叉樹操作 * | *n");printf("* |* 2.進行編譯碼操作 * | *n");printf("* |* 3.退出編譯碼操作系統* | *n");printf("*n"); printf("請選擇要進行的操作:");四、系統測試（一）測試主函數main（）函數該測試主要進行對主函數調用以及輸出的測試，測試的結果：（二）測試印二叉樹函數 測試選擇1，選擇1操作首先輸入葉子節點數，然后輸入要編譯的句子，分別輸入第

14、n+1個節點，然后系統會將輸入字符的個數當作權值進行編譯輸出二叉樹，測試結果為：（3） 測試譯碼運算函數測試選擇2，輸入要選擇的操作2，然后按要求依次輸入需要的值，系統會根據輸入的數據進行譯碼操作，最后輸出譯碼。輸出結果為： （4） 測試退出函數 測試選擇3進行退出，測試結果為:五、總結系統功能：系統完成了將一段字符串進行哈夫曼加密，用戶將自己的選擇輸入程序，然后按照程序的提示進行輸入，系統將根據輸入進行編碼、譯碼操作，然后印出編譯的二叉樹，以及每個字符的譯碼。不足：系統沒有將印哈夫曼樹操作完成，系統沒有將字符的權值根據大小將左孩子設為最小權值，將次小權值設為右孩子，導致加密有許多種，哈夫曼樹

15、也創建了許多種，輸出的譯碼不唯一。收獲：通過一學期數據結構的學習，我發現數據結構比較難，沒有完整的自己獨立完成一個程序。但也學到了許多東西，學會了以前不會的函數調用，在編程時，有許多小問題還是不能夠及時的發現，老是被一點小問題卡住導致程序不執行或輸出死循環，一些程序的指針還不太熟悉。 通過這次程序設計，我發現了許多自己的不足，對一些算法還不能熟練運用，不能將所學的運用到程序中，一些語句還是不太懂；同時，也有一些收獲，對函數調用能夠熟練運用，也明白了結構體的作用，掌握了最優二叉樹的建立和原理，對哈夫曼樹有了更深一步的了解。六、附件（代碼、部分圖表） /*哈弗曼樹*/#include <st

16、dio.h>#define maxvalue 1000/定義最大權值#define maxleaf 50/定義哈夫曼樹中葉子結點個數#define maxnode maxleaf*2-1/定義哈夫曼樹中結點個數整數常量maxnode#define maxbit 100/定義哈夫曼樹的最大長度整數常量typedef struct/定義結構體int weight;int parent;int lchild;int rchild;hnodetype;typedef structint bitmaxbit;int start;hcodetype; /求權值函數void quanzhi(int t

17、maxleaf,char smaxleaf,int n)/求權值函數，將句子中的字符出現的個數當作權值int i,j,h;for(i=0;i<n;i+)for(j=0;j<n;j+)if(si=sj)h+;ti=h; /印二叉樹函數void haffmantree(hnodetype huffnodemaxnode,int *m)int i,j,n,k;int m1,m2,x1,x2;char smaxleaf,tmaxleaf; printf("輸入葉子結點個數：");scanf("%d",&n);for(i=0;i<2*n-

18、1;i+)/數組huffnode初始化huffnodei.weight=0; huffnodei.parent=-1;huffnodei.lchild=-1;huffnodei.rchild=-1;printf("輸入要編譯的句子的n"); for(i=0;i<n;i+) printf("第%d個結點",i+1);scanf("%d",&huffnodei.weight);getchar();printf("印二叉樹：n"); for(i=0;i<n;i+)quanzhi(t,s,n); k=h

19、uffnodei.weight;for(i=0;i<n-1;i+)/構造哈夫曼樹m1=m2=maxvalue; x1=x2=0;for(j=0;j<n+i;j+)/選取最小和次小兩個權值if(huffnodej.parent=-1&&huffnodej.weight<m1)m2=m1;x2=x1;m1=huffnodej.weight;x1=j;elseif(huffnodej.parent=-1&&huffnodej.weight<m2)m2=huffnodej.weight;x2=j;/將找出的兩棵子樹合并為一顆子樹 huffnode

20、x1.parent=n+i; huffnodex2.parent=n+i; huffnoden+i.weight=huffnodex1.weight+huffnodex2.weight; huffnoden+i.lchild=x1; huffnoden+i.rchild=x2;for(i=0;i<2*n-1;i+)printf(" %4d",k); printf(" %4d",huffnodei.lchild);printf(" %4d",huffnodei.rchild);printf(" %4dn",hu

21、ffnodei.parent);*m=n; /編譯碼函數void haffmancode()hnodetype huffnodemaxnode;hcodetype huffcodemaxleaf,cd;int i,j,c,p,n=0;haffmantree(huffnode,&n);for(i=0;i<n;i+)cd.start=n-1;c=i;p=huffnodec.parent;while(p!=-1)if(huffnodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=huffnodec.parent;