數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 題 目： 哈夫曼樹應(yīng)用 學(xué)生姓名： 謝輝 學(xué) 號(hào)： 201317010201 專業(yè)班級(jí)： 計(jì)科13102 同組姓名： 趙麗娜 指導(dǎo)教師： 徐曉蓉 設(shè)計(jì)時(shí)間： 2014年下學(xué)期第18周 指導(dǎo)老師意見: 評(píng)定成績(jī): 簽名: 日期:目錄一、需求分析21.分析問題22.確定解決方案23.輸入的形式和輸入值的范圍34.輸出的形式35.程序所能達(dá)到的功能3二、概要設(shè)計(jì)41. 主程序的流程圖：42程序中數(shù)據(jù)類型的定義：43各程序模塊之間的層次(調(diào)用)關(guān)系：4三、詳細(xì)設(shè)計(jì)51哈夫曼樹存儲(chǔ)及類的定義：52.哈夫曼樹的基本操作:63.主函數(shù)7四、調(diào)試分析和測(cè)試結(jié)果.91.測(cè)試數(shù)據(jù)及其輸出結(jié)果：92.調(diào)試過程中遇到的問題及解決辦法:13五、總結(jié)14六、參考文獻(xiàn)14七、致謝14八、附錄14一、 需求分析1. 分析問題 利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。2. 確定解決方案設(shè)計(jì)建立帶權(quán)的哈夫曼樹，確定哈夫曼樹的類與成員函數(shù)，以及各函數(shù)之間的調(diào)用關(guān)系，采用動(dòng)態(tài)數(shù)組的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)所需要的數(shù)據(jù)，通過不同的函數(shù)來實(shí)現(xiàn)編碼，譯碼以及打印二進(jìn)制編碼、哈夫曼樹，把不同的數(shù)據(jù)存入不同的txt文件中，通過主函數(shù)調(diào)用來實(shí)現(xiàn)功能檢測(cè)。3. 輸入的形式和輸入值的范圍 手動(dòng)或者從文本中讀入數(shù)據(jù)的形式初始化哈夫曼樹，從鍵盤中或者文件中讀入數(shù)據(jù)，以字母A-Z代表結(jié)點(diǎn)，以自然數(shù)代表權(quán)值，字符串提示使用者所要執(zhí)行的操作。4.輸出的形式在顯示器界面上或者以文本的形式來實(shí)現(xiàn)程序調(diào)試的輸出。5.程序所能達(dá)到的功能（1）I:初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E:編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。（3）D:譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。（4）P:打印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。測(cè)試數(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è)計(jì)哈夫曼編碼。（2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。字符 空格 A B C D E F G H I J 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 X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 實(shí)現(xiàn)提示：（1） 編碼結(jié)果以文本方式存儲(chǔ)在文件CodeFile中。（2） 用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表示退出運(yùn)行Quit。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。（3） 在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或E命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。二、概要設(shè)計(jì)I.初始化E.編碼D.譯碼P.打印編碼代碼Q.退出請(qǐng)重新輸入選項(xiàng)判斷選項(xiàng)是否正確選擇菜單項(xiàng)主菜單開始1. 主程序的流程圖：是否圖一：主程序流程圖2程序中數(shù)據(jù)類型的定義：用到三組結(jié)構(gòu)體，分別是哈夫曼樹的動(dòng)態(tài)數(shù)組存儲(chǔ)結(jié)構(gòu)*HuffmanTree，哈夫曼編碼表的存儲(chǔ)結(jié)構(gòu)HuffmanCode，字符結(jié)點(diǎn)的動(dòng)態(tài)數(shù)組存儲(chǔ)結(jié)構(gòu)wElem以及哈夫曼樹類定義classHuffman。3各程序模塊之間的層次(調(diào)用)關(guān)系：主函數(shù)main（）調(diào)用初始化，編碼，譯碼，打印二進(jìn)制編碼，打印哈夫曼樹這五個(gè)子函數(shù)；進(jìn)入初始化功能后調(diào)用手動(dòng)輸入，文本讀入，默認(rèn)文本這三個(gè)函數(shù)；進(jìn)入編碼功能后調(diào)用手動(dòng)編碼，文本讀入編碼這兩個(gè)函數(shù)；進(jìn)入譯碼功能后調(diào)用手動(dòng)譯碼，文本讀入譯碼這兩個(gè)函數(shù)(如圖2所示)。手動(dòng)輸入圖二:各程序模塊之間的層次（調(diào)用）關(guān)系默認(rèn)文本主函數(shù)初始化編碼譯碼打印編碼代碼退出從文件讀入從文件讀入三、 詳細(xì)設(shè)計(jì)1 哈夫曼樹存儲(chǔ)及類的定義：#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,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; /哈夫曼樹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() /輸出菜單界面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");break;case E: if(fi=0)printf("請(qǐng)先初始化操作！n");break;fe=1;encoding(n);printf("將“ToBeTran.txt”中的正文"); printf("編碼完成！結(jié)果已存在文件“CodeFile.txt”中n");break;case D: if(fi=0)printf("請(qǐng)先初始化操作！n");break;if(fe=0)printf("請(qǐng)先進(jìn)行編碼操作！n");break;fd=1;printf("譯碼成功,譯碼結(jié)果為：n"); decoding();break;case P:if(fi=0)printf("請(qǐng)先初始化操作！n");break;if(fe=0)printf("請(qǐng)先進(jìn)行編碼操作！n");break;print();printf("編碼結(jié)果已保存在文件“CodePrin.txt”中n");break;default:printf("輸入有誤，請(qǐng)重新輸入n"); return 0;四、 調(diào)試分析和測(cè)試結(jié)果.測(cè)試數(shù)據(jù)及其輸出結(jié)果：(1) 進(jìn)入主菜單界面：用戶可以選擇所要執(zhí)行的操作，比如：初始化<建立哈夫曼樹>，編碼，譯碼，打印二進(jìn)制編碼代碼。在執(zhí)行編碼、譯碼操作前，請(qǐng)先初始化默認(rèn)的哈夫曼樹(如圖3所示)。圖3：主菜單界面當(dāng)輸入錯(cuò)誤的指令時(shí)（如圖4所示）:圖4當(dāng)未進(jìn)行初始化時(shí)進(jìn)行編碼是輸出（如圖5所示）：圖5(2) 進(jìn)入初始化界面（如圖6所示）：圖6(3) 進(jìn)入編碼界面（如圖7所示）：圖7(4) 進(jìn)入譯碼界面（如圖8所示）：圖8(5) 進(jìn)入打印編碼代碼界面(如圖9所示)：圖9（6） 退出系統(tǒng)（如圖10所示）：1.調(diào)試過程中遇到的問題及解決辦法:在此系統(tǒng)中，我負(fù)責(zé)的是編碼，赫夫曼樹的建立在譯碼之前，數(shù)據(jù)從文件“SourceChar.txt”中輸入，對(duì)26個(gè)英文字母以及空格進(jìn)行編碼。分別存入hfmcode1-26中，空格的編碼存入hfmcode27中。五、 總結(jié)一周的課程設(shè)計(jì)結(jié)束了。在此過程中，我們小組齊心協(xié)力，互相幫助，分工明確，相互學(xué)習(xí)和探討。完成這次的課程設(shè)計(jì)任務(wù)，我們要做好以下準(zhǔn)備：(1)首先要熟練掌握二叉樹的性質(zhì)、先序遍歷二叉樹、最優(yōu)二叉樹的構(gòu)建、字符串匹配等，然后在此基礎(chǔ)上掌握理解huffman樹和編碼和譯碼。(2)完成哈夫曼編譯器，我們要考慮如何把文件當(dāng)中的英文字母編成二進(jìn)制代碼，如何將二進(jìn)制代碼翻譯成英文字母以及如何構(gòu)建一棵哈夫曼樹。每次出現(xiàn)問題我們都一起討論，研究解決和改進(jìn)的方法。這次課程設(shè)計(jì)的成功，可以說是我們組員一起努力的成果。我們小組由兩個(gè)人組成，每個(gè)人都有自己在小組中的作用。我負(fù)責(zé)譯碼部分和界面函部分，另一組員負(fù)責(zé)初始化和編碼部分。我們總是在不斷地調(diào)試程序和改進(jìn)程序的功能，最后終于在自己的努力和老師的辛勤指導(dǎo)下順利完成了這次課程設(shè)計(jì)。六、 參考文獻(xiàn)1數(shù)據(jù)結(jié)構(gòu)（c+語言版），嚴(yán)蔚敏，吳偉民編著，清華大學(xué)出版社2數(shù)據(jù)結(jié)構(gòu)題集嚴(yán)蔚敏編著，清華大學(xué)出版社七、 致謝感謝這次課程設(shè)計(jì)中老師的細(xì)心和耐心指導(dǎo)，小組成員的的幫助，團(tuán)結(jié)合作才能使這次任務(wù)圓滿完成。八、 附錄源程序：#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,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; /哈夫曼樹void inithead(int n,char d) /初始化表for(int i=1;i<=n;i+)hfmtreei.fa=-1;hfmtreei.lchild=hfmtreei.rchild=-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(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=i; void encoding(int n) /編碼完成 int c,fa; Hfmcode hcode;/對(duì)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; /對(duì)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);elseint 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(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.codej)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; initialization(n,info);void face()cout<<" "<<"* * * * * * * * * * * * * * * * * * * * * * * * * * *"<<endl;cout<<" "<<"*|-|*"<<endl;cout<<" "<<"*| |*"<<endl;cout<<" "<<"*| 哈 夫 曼 碼 的 編 / 譯 碼 系 統(tǒng) |*"<<endl;cout<<" "<<"*| |*"<<endl;cout<<" "<<"*| |*"<<endl;cout<<" "<<"*| $. 主 菜 單 |*"<<endl; cout<<" "<<"*| |*"<<endl;cout<<" "<<"*| I. 初 始 化 |*"<<endl; cout<<" "<<"*| |*"<<endl;cout<<" "<<"*| E. 編 碼 |*"<<endl; cout<<" "<<"*| |*"<<endl;cout<<" "<<"*| D. 譯 碼 |*"<<endl; cout<<" "<<"*| |*"<<endl;cout<<" "<<"*| P. 打 印 代 碼 文 件 |*"<<endl; cout<<" "<<"*| |*"<<endl; cout<<" "<<"*| Q. 推 出 系 統(tǒng) |*"<<endl;cout<<" "<<"*|-|*"<<endl;cout<<" "<<"* * * * * * * * * * * * * * * * * * * * * * * * * * *"<<endl;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=Q)break;switch(c)case I:fi=1;init();printf("初始化完畢！n");break;case E: if(fi=0)printf("請(qǐng)先初始化操作！n");break;fe=1;encoding(n);printf("將“ToBeTran.txt”中的正文"); printf("編碼完成！結(jié)果已存在文件“CodeFile.txt”中n");break;case D: if(fi=0)printf("請(qǐng)先初始化操作！n");break;if(fe=0)printf("請(qǐng)先進(jìn)行編碼操作！n");break;fd=1;printf("譯碼成功,譯碼結(jié)果為：n"); decoding();break;case P:if(fi=0)printf("請(qǐng)先初始化操作！n");break;if(fe=0)printf("請(qǐng)先進(jìn)行編碼操作！n");break;print();printf("編碼結(jié)果已保存在文件“CodePrin.txt”中n");break;default:printf("輸入有誤，請(qǐng)重新輸入n"); return 0;