哈夫曼樹的應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

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

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

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

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

5、下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“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    實現(xiàn)提示：（1） 編碼結(jié)果以文本方式存儲在文件CodeFile中。（2） 用戶界面可以設(shè)計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。（3） 在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或E命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因為文件hfmTree可能早已建好。二、概要設(shè)計I.初始化E.編碼D.譯碼P.打印編碼代碼Q.退出請重新

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

10、功能后調(diào)用手動譯碼，文本讀入譯碼這兩個函數(shù)(如圖2所示)。手動輸入圖二:各程序模塊之間的層次（調(diào)用）關(guān)系默認文本主函數(shù)初始化編碼譯碼打印編碼代碼退出從文件讀入從文件讀入三、 詳細設(shè)計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; /父親，左孩子，右孩子，權(quán)值；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.主函數(shù)int main()char c;face();int fi,fe,fd;fi=fe=fd=0;printf("數(shù)據(jù)從“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("編碼完成！結(jié)果已存在文件“CodeFile.txt”中n");break;case 'D': if(fi=0)printf("請先初始化操作！n");break;if(fe=0)printf("請先進行編碼操作！n");break;fd=1;printf(&

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

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

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

18、和改進的方法。這次課程設(shè)計的成功，可以說是我們組員一起努力的成果。我們小組由兩個人組成，每個人都有自己在小組中的作用。 我負責譯碼部分和界面函部分，另一組員負責初始化和編碼 部分。  我們總是在不斷地調(diào)試程序和改進程序的功能，最后終于在自己的努力和老師的辛勤指導(dǎo)下順利完成了這次課程設(shè)計。六、 參考文獻1 數(shù)據(jù)結(jié)構(gòu)（c+語言版），嚴蔚敏，吳偉民編著，清華大學出版社 2數(shù)據(jù)結(jié)構(gòu)題集嚴蔚敏編著，清華大學出版社 七、 致謝感謝這次課程設(shè)計中老師的細心和耐心指導(dǎo)，小組成員的的幫助，團結(jié)合作才能使這次任務(wù)圓滿完成。八、 附錄源程序：#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; /父親，左孩子，右孩子，權(quán)值；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字符編碼 結(jié)果存入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中的字符編碼！結(jié)果存入CodeFile.txt文件中。 char s;ifstream in;ofstream out;in.open("ToBeTran.txt");out.open("CodeFile.txt");/讀入字符串存入str字符數(shù)組中。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;"*| 哈 夫 曼 碼 的 編 / 譯 碼 系 統(tǒng) |*"<<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<<&