1、摘要 利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。這要求在發送端通過一個編碼系統對待傳輸數據預先編碼，在接收端將傳來的數據進行譯碼（復原），將所得結果存儲到已開辟空間中。試為這樣的信息收發站編寫一個哈夫曼碼的編/譯碼系統。本程序可以對任何大小的字符型文件進行Huffman編碼，生成一個編碼文件。并可以在程序運行結束后的任意時間對它解碼還原生成字符文件。即：先對一條電文進行輸入，并實現Huffman編碼，然后對Huffman編碼生成的代碼串進行譯碼，最后輸出電文數字 Abstract Use hoffmann code was communication can

2、 improve the utilization rate of channel, shorten the information transmission time, reduce the transmission cost. This requirement in the sending end through a coding system in advance to transmit data coding, in the receiver will spread of the data decoding (restoration), will the results of open

3、space to store already. Try for such information sending and receiving station write a hoffmann yards of make up/decoding system. This program can on any of the size of the file type character Huffman coding, generates a code files. And can the running of the application at any time after the end of

4、 the reduction of decoding it generated character files. Namely: first to a message for input, and realize the Huffman coding, and then to Huffman coding generated code string decode, finally digital output message 關鍵字 哈夫曼編碼； 哈夫曼譯碼 Keywords Hoffmann code; Hoffmann decode 1 設計要求 對輸入的一串電文字符實現哈夫曼編碼，輸出電

5、文字符串。通常我們把數據壓縮的過程稱為編碼。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度能盡可能短，即采用最短碼。假設每種字符在電文中出現的次數為Wi，編碼長度為Li，電文中有n種字符，則電文編碼總長度為WiLi。若將此對應到二叉樹上，Wi為葉結點的權，Li為根結點到葉結點的路徑長度。那么，WiLi恰好為二叉樹上帶權路徑長度。因此 ，設計電文總長最短的二進制前綴編碼，就是以n種字符出現的頻率作權，構造一棵哈夫曼樹，此構造過程稱為哈夫曼編碼。設計實現的功能： (1) 哈夫曼樹的建立； (2) 哈夫曼編碼的生成；(3) 對編碼文件的譯碼。 2 系統結構圖 （功能模塊圖）哈

6、夫曼編碼/譯碼器建立哈夫曼樹哈夫曼編碼哈夫曼譯碼 圖2-1 哈夫曼結構圖 3 詳細設計 3.1 哈夫曼樹的建立 3.1.1哈夫曼樹的存儲結構描述為： #define N 50 / 葉子結點數 #define M 2*N-1 / 哈夫曼樹中結點總數 typedef struct int weight; / 葉子結點的權值 int lchild, rchild, parent; / 左右孩子及雙親指針 HTNode; / 樹中結點類型 typedef HTNode HuffmanTreeM+1; 3.1.2哈夫曼樹的算法:void CreateHT(HTNode ht,int n) /調用輸入的數

7、組ht和節點數n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有結點的相關域置初值-1 for (i=n;i<2*n-1;i+) /構造哈夫曼樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權值的兩個結點位置 for (k=0;k<=i-1;k+) if (htk.parent=-1) /只在尚未構造二叉樹的結點中查找 if (htk.w

8、eight<min1) /若權值小于最小的左節點的權值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個最小節點的父節點是i hti.weight=htlnode.weight+htrnode.weight; /兩個最小節點的父節點權值為兩個最小節點權值之和 hti.lchild=lnode;hti.rchild=rnode; /父節點的左節點和右節點3.2哈

9、夫曼編碼void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /根據哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結點結束循環 if (htf.lchild=c) /處理左孩子結點 hc.cdhc.start-='0' else /處理右孩子結點 hc.cdhc.start-='1' c=f;f=htf.parent; hc.start+; /start指向哈夫曼編碼hc

10、.cd中最開始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf(" 輸出哈夫曼編碼:n"); for (i=0;i<n;i+) /輸出data中的所有數據，即A-Z printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /輸出所有data中數據的編碼 printf("%c",hcdi.cdk); printf("n"); void edit

11、HCode(HTNode ht,HCode hcd,int n) /編碼函數char stringMAXSIZE; int i,j,k;scanf("%s",string); /把要進行編碼的字符串存入string數組中printf("n輸出編碼結果:n");for (i=0;stringi!='#'i+) /#為終止標志for (j=0;j<n;j+)if(stringi=htj.data) /循環查找與輸入字符相同的編號，相同的就輸出這個字符的編碼for (k=hcdj.start;k<=n;k+) printf(&quo

12、t;%c",hcdj.cdk);break; /輸出完成后跳出當前for循環3.3哈夫曼譯碼void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code); /把要進行譯碼的字符串存入code數組中while(code0!='#')for (i=0;i<n;i+)m=0; /m為想同編碼個數的計數器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j為記錄所存儲這個字符的編碼個數if(cod

13、ej=hcdi.cdk) /當有相同編碼時m值加1m+;if(m=j) /當輸入的字符串與所存儲的編碼字符串個數相等時則輸出這個的data數據printf("%c",hti.data);for(x=0;codex-1!='#'x+) /把已經使用過的code數組里的字符串刪除codex=codex+j;3.4主函數void main() int n=26,i; char orz,back,flag=1; char str='A','B','C','D','E','F

14、9;,'G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,5

15、7,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立結構體 HCode hcdN; /建立結構體 for (i=0;i<n;i+) /把初始化的數據存入ht結構體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數，當flag為0時跳出循環 3.5顯示部分源程序： printf("n"); printf(" *"); printf("n * 1-顯示編碼 *"); printf("n * 2-進行編碼 *&quo

16、t;); printf("n * 3-進行譯碼 *"); printf("n * 4-退出 *n"); printf(" * *"); printf("n"); printf(" 請輸入選擇的編號:"); scanf("%c",&orz); switch(orz) case 'a': case 'A': system("cls"); /清屏函數 CreateHT(ht,n); CreateHCode(ht,hcd,n

17、); DispHCode(ht,hcd,n); printf("n按任意鍵返回."); getch(); system("cls"); break; case 'b': case 'B': system("cls"); printf("請輸入要進行編碼的字符串(以#結束):n"); editHCode(ht,hcd,n); printf("n按任意鍵返回."); getch(); system("cls"); break; case '

18、c': case 'C': system("cls"); DispHCode(ht,hcd,n); printf("請輸入編碼(以#結束):n"); deHCode(ht,hcd,n); printf("n按任意鍵返回."); getch(); system("cls"); break; case 'd': case 'D': flag=0; break; default: system("cls"); 4 程序運行結果進入主菜單圖4-1選

19、A時的顯示結果圖4-2選B時的顯示結果圖4-3選C時的顯示結果圖4-45 心得體會 通過這次課程設計，我們學習了很多在上課沒懂的知識，并對求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學習有關于哈夫曼編碼的知識，真正學會一種算法了。我們認識到根據不同的需求，采用不同的數據存儲方式，不一定要用棧，二叉樹等高級類型，有時用基本的一維數組，只要運用得當，也能達到相同的效果，甚至更佳，就如這次的課程設計，通過用for的多重循環，舍棄多余的循環，提高了程序的運行效率。這次課程設計，我們在編輯中犯了不應有的錯誤，設計統計字符和合并時忘記應該怎樣保存數據，對文件的操作也很生疏。在不斷分

20、析后明確并改正了錯誤和疏漏，我們的程序有了更高的質量。另外，互幫互助讓我們的程序設計更加完善。參考文獻1 徐孝凱編著，數據結構課程實驗，清華大學出版 2002年第一版2 張乃笑編著，數據結構與算法，電子工業出版社 2004年10月3 嚴蔚敏 數據結構（C語言版） 清華大學出版社4 李春葆 數據結構（C語言篇）習題與解析（修訂版）清華大學出版 2002年4月第一版附錄源程序如下：#include <stdio.h>#include <stdlib.h> /要用system函數要調用的頭文件#include<conio.h> /用getch()要調用的頭文件#i

21、nclude <string.h>#define N 50 /義用N表示50葉節點數#define M 2*N-1 /用M表示節點總數 當葉節點數位n時總節點數為2n-1#define MAXSIZE 100typedef struct char data; /結點值 int weight; /權值 int parent; /雙親結點 int lchild; /左孩子結點 int rchild; /右孩子結點HTNode; typedef struct char cdN; /存放哈夫曼碼 int start; /從start開始讀cd中的哈夫曼碼HCode;void CreateH

22、T(HTNode ht,int n) /調用輸入的數組ht,和節點數n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有結點的相關域置初值-1 for (i=n;i<2*n-1;i+) /構造哈夫曼樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權值的兩個結點位置 for (k=0;k<=i-1;k+) if (htk.parent=-1)

23、 /只在尚未構造二叉樹的結點中查找 if (htk.weight<min1) /若權值小于最小的左節點的權值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個最小節點的父節點是i hti.weight=htlnode.weight+htrnode.weight; /兩個最小節點的父節點權值為兩個最小節點權值之和 hti.lchild=lnode;hti.rch

24、ild=rnode; /父節點的左節點和右節點void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /根據哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結點結束循環 if (htf.lchild=c) /處理左孩子結點 hc.cdhc.start-='0' else /處理右孩子結點 hc.cdhc.start-='1' c=f;f=htf.parent; hc.star

25、t+; /start指向哈夫曼編碼hc.cd中最開始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf(" 輸出哈夫曼編碼:n"); for (i=0;i<n;i+) /輸出data中的所有數據，即A-Z printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /輸出所有data中數據的編碼 printf("%c",hcdi.cdk); printf("

26、n"); void editHCode(HTNode ht,HCode hcd,int n) /編碼函數char stringMAXSIZE; int i,j,k;scanf("%s",string); /把要進行編碼的字符串存入string數組中printf("n輸出編碼結果:n");for (i=0;stringi!='#'i+) /#為終止標志for (j=0;j<n;j+)if(stringi=htj.data) /循環查找與輸入字符相同的編號，相同的就輸出這個字符的編碼for (k=hcdj.start;k<

27、;=n;k+) printf("%c",hcdj.cdk);break; /輸出完成后跳出當前for循環void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code); /把要進行譯碼的字符串存入code數組中while(code0!='#')for (i=0;i<n;i+)m=0; /m為想同編碼個數的計數器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j為記錄所存儲這個字符

28、的編碼個數if(codej=hcdi.cdk) /當有相同編碼時m值加1m+;if(m=j) /當輸入的字符串與所存儲的編碼字符串個數相等時則輸出這個的data數據printf("%c",hti.data);for(x=0;codex-1!='#'x+) /把已經使用過的code數組里的字符串刪除codex=codex+j;void main() int n=26,i; char orz,back,flag=1; char str='A','B','C','D','E','

29、;F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立結構體 HCode hcdN; /建立結構體 for (i=0;i<n;i+) /把初始化的數據存入ht結構體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數，當flag為0時跳出循環 print