1、 數據結構課程設計報告 題 目： 哈夫曼樹應用 學生姓名： 謝輝 學 號： 201317010201 專業班級： 計科13102 同組姓名： 趙麗娜 指導教師： 徐曉蓉 設計時間： 2014年下學期第18周 指導老師意見: 評定成績: 簽名: 日期:目錄一、需求分析21.分析問題22.確定解決方案23.輸入的形式和輸入值的范圍34.輸出的形式35.程序所能達到的功能3二、概要設計41. 主程序的流程圖：42程序中數據類型的定義：43各程序模塊之間的層次(調用)關系：4三、詳細設計51哈夫曼樹存儲及類的定義：52.哈夫曼樹的基本操作:63.主函數7四、調試分析和測試結果.91.測試數據及其輸出結

2、果：92.調試過程中遇到的問題及解決辦法:13五、總結14六、參考文獻14七、致謝14八、附錄14一、 需求分析1. 分析問題 利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接收端將傳來的數據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統。為這樣的信息收發站寫一個哈夫曼碼的編/譯碼系統。2. 確定解決方案設計建立帶權的哈夫曼樹，確定哈夫曼樹的類與成員函數，以及各函數之間的調用關系，采用動態數組的存儲結構存儲所需要的數據，通過不同的函數來實現編碼，譯碼以及打印二

3、進制編碼、哈夫曼樹，把不同的數據存入不同的txt文件中，通過主函數調用來實現功能檢測。3. 輸入的形式和輸入值的范圍 手動或者從文本中讀入數據的形式初始化哈夫曼樹，從鍵盤中或者文件中讀入數據，以字母A-Z代表結點，以自然數代表權值，字符串提示使用者所要執行的操作。 4.輸出的形式 在顯示器界面上或者以文本的形式來實現程序調試的輸出。5.程序所能達到的功能 （1）I:初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E:編碼（Encoding）。利用已建好的哈夫曼樹（如不在內存

4、，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。（3）D:譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。（4）P:打印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。測試數據：（1） 利用下面這道題中的數據調試程序。某系統在通信聯絡中只可能出現八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設計哈夫曼編碼。（2）用

5、下表給出的字符集和頻度的實際統計數據建立哈夫曼樹，并實現以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。字符    空格    A    B    C    D    E    F    G    H    I    J &#

6、160;  K    L    M頻度 64 13 22 32 103 21 15 47 57 1 5 32 20字符    N    O    P    Q    R    S    T    U    V    W 

7、   X    Y    Z    頻度    57    63    15    1    48    51    80    23    8    18   

8、; 1    16    1    實現提示：（1） 編碼結果以文本方式存儲在文件CodeFile中。（2） 用戶界面可以設計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。（3） 在程序的一次執行過程中，第一次執行I，D或E命令之后，哈夫曼樹已經在內存了，不必再讀入。每次執行中不一定執行I命令，因為文件hfmTree可能早已建好。二、概要設計I.初始化E.編碼D.譯碼P.打印編碼代碼Q.退出請重新

9、輸入選項判斷選項是否正確選擇菜單項主菜單開始1. 主程序的流程圖：是否圖一：主程序流程圖 2程序中數據類型的定義：用到三組結構體，分別是哈夫曼樹的動態數組存儲結構*HuffmanTree，哈夫曼編碼表的存儲結構HuffmanCode，字符結點的動態數組存儲結構wElem 以及哈夫曼樹類定義class Huffman。3各程序模塊之間的層次(調用)關系： 主函數main（）調用初始化，編碼，譯碼，打印二進制編碼，打印哈夫曼樹這五個子函數；進入初始化功能后調用手動輸入，文本讀入，默認文本這三個函數；進入編碼功能后調用手動編碼，文本讀入編碼這兩個函數；進入譯碼

10、功能后調用手動譯碼，文本讀入譯碼這兩個函數(如圖2所示)。手動輸入圖二:各程序模塊之間的層次（調用）關系默認文本主函數初始化編碼譯碼打印編碼代碼退出從文件讀入從文件讀入三、 詳細設計1 哈夫曼樹存儲及類的定義：#include <iostream>#include <cstdio>#include <windows.h>#include <queue>#include <fstream>using namespace std;#define MAXN 60#define INF 9999int date40=INF,64,13,22,

11、32,103,21,15,47,57,1,5,32, 20,57,63,15,1,48,51,80,23,8,18,1,6,1,INF,INF,INF,INF,INF,INF,INF,186;/字符c的頻率存放在date65-c+i中int n=27;typedef struct node int fa,lchild,rchild,w; /父親，左孩子，右孩子，權值；hfmTree;char info30;typedef struct char code50; int start;Hfmcode;Hfmcode hfmcodeMAXN; /哈夫曼編碼hfmTree hfmtreeMAXN; /

12、哈夫曼樹void inithead(int n,char d) ; /初始化表void initialization(int n,char d); /建樹void encoding(int n) ; /編碼void decoding(); /譯碼void print() /打印編碼代碼2.哈夫曼樹的基本操作:void inithead(int n,char d) /初始化表void initialization(int n,char d) /建樹void encoding(int n) /編碼void decoding(); /譯碼void print() /打印編碼代碼void face()

13、 /輸出菜單界面3.主函數int main()char c;face();int fi,fe,fd;fi=fe=fd=0;printf("數據從“sourceChar.txt”文件中輸入!n"); while(1)printf("->");cin>>c;if(c>='a'&&c<='z')c-=32;if(c='Q')break;switch(c)case 'I':fi=1;init();printf("初始化完畢！n");b

14、reak;case 'E': if(fi=0)printf("請先初始化操作！n");break;fe=1;encoding(n);printf("將“ToBeTran.txt”中的正文"); printf("編碼完成！結果已存在文件“CodeFile.txt”中n");break;case 'D': if(fi=0)printf("請先初始化操作！n");break;if(fe=0)printf("請先進行編碼操作！n");break;fd=1;printf(&

15、quot;譯碼成功,譯碼結果為：n"); decoding();break;case 'P':if(fi=0)printf("請先初始化操作！n");break;if(fe=0)printf("請先進行編碼操作！n");break;print();printf("編碼結果已保存在文件“CodePrin.txt”中n");break;default:printf("輸入有誤，請重新輸入n"); return 0;四、 調試分析和測試結果.測試數據及其輸出結果：(1) 進入主菜單界面：用戶可以

16、選擇所要執行的操作，比如：初始化<建立哈夫曼樹>，編碼，譯碼，打印二進制編碼代碼。在執行編碼、譯碼操作前，請先初始化默認的哈夫曼樹(如圖3所示) 。圖3：主菜單界面當輸入錯誤的指令時（如圖4所示）:圖4當未進行初始化時進行編碼是輸出（如圖5所示）：圖5(2) 進入初始化界面（如圖6所示）：圖6(3) 進入編碼界面（如圖7所示）：圖7(4) 進入譯碼界面（如圖8所示）：圖8(5) 進入打印編碼代碼界面(如圖9所示)：圖9（6） 退出系統（如圖10所示）：1.調試過程中遇到的問題及解決辦法:在此系統中，我負責的是編碼，赫夫曼樹的建立在譯碼之前，數據從文件“SourceChar

17、.txt”中輸入，對26個英文字母以及空格進行編碼。分別存入hfmcode1-26中，空格的編碼存入hfmcode27中。五、 總結一周的課程設計結束了。在此過程中，我們小組齊心協力，互相幫助，分工明確，相互學習和探討。完成這次的課程設計任務，我們要做好以下準備： (1)首先要熟練掌握二叉樹的性質、先序遍歷二叉樹、最優二叉樹的構建、字符串匹配等，然后在此基礎上掌握理解huffman樹和編碼和譯碼。 (2) 完成哈夫曼編譯器，我們要考慮如何把文件當中的英文字母編成二進制代碼，如何將二進制代碼翻譯成英文字母以及如何構建一棵哈夫曼樹。每次出現問題我們都一起討論，研究解決

18、和改進的方法。這次課程設計的成功，可以說是我們組員一起努力的成果。我們小組由兩個人組成，每個人都有自己在小組中的作用。 我負責譯碼部分和界面函部分，另一組員負責初始化和編碼 部分。  我們總是在不斷地調試程序和改進程序的功能，最后終于在自己的努力和老師的辛勤指導下順利完成了這次課程設計。六、 參考文獻1 數據結構（c+語言版），嚴蔚敏，吳偉民編著，清華大學出版社 2數據結構題集嚴蔚敏編著，清華大學出版社 七、 致謝感謝這次課程設計中老師的細心和耐心指導，小組成員的的幫助，團結合作才能使這次任務圓滿完成。八、 附錄源程序：#i

19、nclude <iostream>#include <cstdio>#include <windows.h>#include <queue>#include <fstream>using namespace std;#define MAXN 60#define INF 9999int date40=INF,64,13,22,32,103,21,15,47,57,1,5,32, 20,57,63,15,1,48,51,80,23,8,18,1,6,1,INF,INF,INF,INF,INF,INF,INF,186;/字符c的頻率存放在d

20、ate65-c+i中int n=27;typedef struct node int fa,lchild,rchild,w; /父親，左孩子，右孩子，權值；hfmTree;char info30;typedef struct char code50; int start;Hfmcode;Hfmcode hfmcodeMAXN; /哈夫曼編碼hfmTree hfmtreeMAXN; /哈夫曼樹void inithead(int n,char d) /初始化表for(int i=1;i<=n;i+)hfmtreei.fa=-1;hfmtreei.lchild=hfmtreei.rchild=

21、-1;if(di=' ') hfmtree27.w=186; else hfmtreei.w=date di-64;for(int j=n+1;j<=2*n-1;j+)hfmtreej.fa=-1;hfmtreej.lchild=hfmtreej.rchild=hfmtreej.w=-1;void initialization(int n,char d) /建樹成功 int s1,s2,rnode,min1,min2; inithead(n,d); for(int i=n+1;i<=n*2-1;i+) min1=INF; min2=INF; s1=s2=-1;for

22、(int k=1;k<=i-1;k+)if(hfmtreek.fa=-1)if(hfmtreek.w<min1)min2=min1;s2=s1;min1=hfmtreek.w;s1=k;else if(hfmtreek.w<min2&&hfmtreek.w>min1)min2=hfmtreek.w;s2=k;hfmtreei.w=hfmtrees1.w+hfmtrees2.w;hfmtreei.lchild=s1<s2?s1:s2;hfmtreei.rchild=s1>s2?s1:s2;hfmtrees1.fa=i;hfmtrees2.fa=

23、i; void encoding(int n) /編碼完成 int c,fa; Hfmcode hcode;/對AZ字符編碼 結果存入hfmcode中。 for(int i=1;i<=n;i+) c=i; hcode.start=n; fa=hfmtreei.fa; while(fa!=-1) if(hfmtreefa.lchild=c) hcode.codehcode.start-='0' else hcode.codehcode.start-='1' c=fa; fa=hfmtreefa.fa; hcode.start+; hfmcodei=hcode

24、; /對ToBeTran.txt中的字符編碼！結果存入CodeFile.txt文件中。 char s;ifstream in;ofstream out;in.open("ToBeTran.txt");out.open("CodeFile.txt");/讀入字符串存入str字符數組中。char str;while(in.get(str)if(str!=' ')int start=hfmcodestr-64.start;for(int i=start;i<=n;i+)out.put(hfmcodestr-64.codei);elsein

25、t start=hfmcode27.start;for(int i=start;i<=n;i+)out.put(hfmcode27.codei);out.put('n');void print()ifstream in;ofstream out;out.open("CodePrin.txt");char str;in.open("CodeFile.txt");int i=0;while(in.get(str)if(str='n')continue;i+;cout<<str;out.put(str);if(

26、i%50=0)cout<<endl;out.put('n');cout<<endl; void decoding()ifstream in;int i,k;in.open("CodeFile.txt");char str15,c;i=1;while(in.get(c)if(c='n')int fg=0;for(k=1;k<=27;k+)int flag=1;for(int j=hfmcodek.start,p=1;j<=n&&p<i;j+,p+)if(strp!=hfmcodek.co

27、dej)flag=0;break;if(flag=1)fg=1;break;if(fg=1)if(k=27)cout<<' 'elseprintf("%c",'A'+k-1); i=1;continue;stri=c;i+;cout<<endl;void init()char c;int i=1;ifstream finsourcechar;finsourcechar.open("SourceChar.txt");while(finsourcechar.get(c)infoi+=c;n=i-1; i

28、nitialization(n,info);void face()cout<<" "<<"* * * * * * * * * * * * * * * * * * * * * * * * * * *"<<endl;cout<<" "<<"*|-|*"<<endl;cout<<" "<<"*| |*"<<endl;cout<<" "<&

29、lt;"*| 哈 夫 曼 碼 的 編 / 譯 碼 系 統 |*"<<endl;cout<<" "<<"*| |*"<<endl;cout<<" "<<"*| |*"<<endl;cout<<" "<<"*| $. 主 菜 單 |*"<<endl; cout<<" "<<"*| |*&q

30、uot;<<endl;cout<<" "<<"*| I. 初 始 化 |*"<<endl; cout<<" "<<"*| |*"<<endl;cout<<" "<<"*| E. 編 碼 |*"<<endl; cout<<" "<<"*| |*"<<endl;cout<<" "<<"*| D. 譯 碼 |*"<<endl; cout<<" "<<"*| |*"<<endl;cout<<" "<<"*| P. 打 印 代 碼 文 件 |*"<<endl; cout<<" "<<"*| |*"<<endl; cout<<&