《哈夫曼樹(shù)的應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》由會(huì)員分享，可在線閱讀，更多相關(guān)《哈夫曼樹(shù)的應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)（20頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、各專業(yè)完整優(yōu)秀畢業(yè)論文設(shè)計(jì)圖紙
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告
題 目： 哈夫曼樹(shù)應(yīng)用
學(xué)生姓名：
學(xué) 號(hào)： 201317010201
專業(yè)班級(jí)： 計(jì)科13102
同組姓名：
指導(dǎo)教師：
設(shè)計(jì)時(shí)
2、間： 2014年下學(xué)期第18周
指導(dǎo)老師意見(jiàn):
評(píng)定成績(jī): 簽名: 日期:
目錄
一、 需求分析 2
1. 分析問(wèn)題 2
2. 確定解決方案 2
3. 輸入的形式和輸入值的范圍 3
4.輸出的形式 3
5.程序所能達(dá)到的功能 3
二、概要設(shè)計(jì) 4
1. 主程序的流程圖： 4
2．程序中數(shù)據(jù)類型的定義： 4
3．各程序模塊之間的層次(調(diào)用)關(guān)系： 4
三、 詳細(xì)設(shè)計(jì) 5
1． 哈夫曼樹(shù)存儲(chǔ)及類的定義： 5
2.哈夫曼樹(shù)的基本操作: 6
3.主函數(shù) 7
四
3、、 調(diào)試分析和測(cè)試結(jié)果. 9
1. 測(cè)試數(shù)據(jù)及其輸出結(jié)果： 9
2. 調(diào)試過(guò)程中遇到的問(wèn)題及解決辦法: 13
五、 總結(jié) 14
六、 參考文獻(xiàn) 14
七、 致謝 14
八、 附錄 14
一、 需求分析
1. 分析問(wèn)題
利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。
2. 確定解決方案
設(shè)計(jì)建立帶權(quán)的哈夫曼樹(shù)，確定哈夫曼
4、樹(shù)的類與成員函數(shù)，以及各函數(shù)之間的調(diào)用關(guān)系，采用動(dòng)態(tài)數(shù)組的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)所需要的數(shù)據(jù)，通過(guò)不同的函數(shù)來(lái)實(shí)現(xiàn)編碼，譯碼以及打印二進(jìn)制編碼、哈夫曼樹(shù)，把不同的數(shù)據(jù)存入不同的txt文件中，通過(guò)主函數(shù)調(diào)用來(lái)實(shí)現(xiàn)功能檢測(cè)。
3. 輸入的形式和輸入值的范圍
手動(dòng)或者從文本中讀入數(shù)據(jù)的形式初始化哈夫曼樹(shù)，從鍵盤中或者文件中讀入數(shù)據(jù)，以字母A-Z代表結(jié)點(diǎn)，以自然數(shù)代表權(quán)值，字符串提示使用者所要執(zhí)行的操作。
4.輸出的形式
在顯示器界面上或者以文本的形式來(lái)實(shí)現(xiàn)程序調(diào)試的輸出。
5.程序所能達(dá)到的功能
（1）I:初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，
5、建立哈夫曼樹(shù)，并將它存于文件hfmTree中。
（2）E:編碼（Encoding）。利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。
（3）D:譯碼（Decoding）。利用已建好的哈夫曼樹(shù)將文件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ò)中只可
6、能出現(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ù)，并實(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
7、
實(shí)現(xiàn)提示：
（1） 編碼結(jié)果以文本方式存儲(chǔ)在文件CodeFile中。
（2） 用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表示退出運(yùn)行Quit。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。
（3） 在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行I，D或E命令之后，哈夫曼樹(shù)已經(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)
主菜單
開(kāi)始
1. 主程序的流
8、程圖：
是
否
圖一：主程序流程圖
2．程序中數(shù)據(jù)類型的定義：
用到三組結(jié)構(gòu)體，分別是哈夫曼樹(shù)的動(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以及哈夫曼樹(shù)類定義classHuffman。
3．各程序模塊之間的層次(調(diào)用)關(guān)系：
主函數(shù)main（）調(diào)用初始化，編碼，譯碼，打印二進(jìn)制編碼，打印哈夫曼樹(shù)這五個(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ù)(
9、如圖2所示)。
手動(dòng)輸入
圖二:各程序模塊之間的層次（調(diào)用）關(guān)系
默認(rèn)文本
主函數(shù)
初始化
編碼
譯碼
打印編碼代碼
退出
從文件讀入
從文件讀入
三、 詳細(xì)設(shè)計(jì)
1． 哈夫曼樹(shù)存儲(chǔ)及類的定義：
#include
#include
#include
#include
#include
using namespace std;
#define MAXN 60
#define INF 9999
int d
10、ate[40]={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的頻率存放在date[65-c+i]中
int n=27;
typedef struct node{
int fa,lchild,rchild,w; //父親，左孩子，右孩子，權(quán)值；
}hfmTree;
char info[30];
typedef struct{
char code[50];
11、 int start;
}Hfmcode;
Hfmcode hfmcode[MAXN]; //哈夫曼編碼
hfmTree hfmtree[MAXN]; //哈夫曼樹(shù)
void inithead(int n,char d[]) ; //初始化表
void initialization(int n,char d[]); //建樹(shù)
void encoding(int n) ; //編碼
void decoding(); //譯碼
void print() //打印編碼代碼
2.哈夫曼樹(shù)的基本
12、操作:
void inithead(int n,char d[]) //初始化表
void initialization(int n,char d[]) //建樹(shù)
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;
pr
13、intf("數(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;
14、
}
fe=1;
encoding(n);
printf("將“ToBeTran.txt”中的正文");
printf("編碼完成！結(jié)果已存在文件“CodeFile.txt”中\(zhòng)n");
break;
case D: if(fi==0)
{
printf("請(qǐng)先初始化操作！\n");
break;
}
if(fe==0)
{
printf("請(qǐng)先進(jìn)行編碼操作！\n");
break;
15、
}
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é)果已保存在文件“CodeP
16、rin.txt”中\(zhòng)n");
break;
default: printf("輸入有誤，請(qǐng)重新輸入\n");
}
}
return 0;
}
四、 調(diào)試分析和測(cè)試結(jié)果.
測(cè)試數(shù)據(jù)及其輸出結(jié)果：
(1) 進(jìn)入主菜單界面：
用戶可以選擇所要執(zhí)行的操作，比如：初始化<建立哈夫曼樹(shù)>，編碼，譯碼，打印二進(jìn)制編碼代碼。在執(zhí)行編碼、譯碼操作前，請(qǐng)先初始化默認(rèn)的哈夫曼樹(shù)(如圖3所示)。
圖3：主菜單界面
當(dāng)輸入錯(cuò)誤的指令時(shí)（如圖4所示）:
圖4
當(dāng)未進(jìn)行初始化時(shí)進(jìn)行編碼是輸出（如圖5所示）：
圖5
(2) 進(jìn)入初始化界面（如圖
17、6所示）：
圖6
(3) 進(jìn)入編碼界面（如圖7所示）：
圖7
(4) 進(jìn)入譯碼界面（如圖8所示）：
圖8
(5) 進(jìn)入打印編碼代碼界面(如圖9所示)：
圖9
（6） 退出系統(tǒng)（如圖10所示）：
1.調(diào)試過(guò)程中遇到的問(wèn)題及解決辦法:
在此系統(tǒng)中，我負(fù)責(zé)的是編碼，赫夫曼樹(shù)的建立在譯碼之前，數(shù)據(jù)從文件“SourceChar.txt”中輸入，對(duì)26個(gè)英文字母以及空格進(jìn)行編碼。分別存入hfmcode[1-26]中，空格的編碼存入hfmcode[27]中。
五、 總結(jié)
一周的課程設(shè)計(jì)結(jié)束了。在此過(guò)程中，我們小組齊心協(xié)力，互相幫助，分工明確，相互學(xué)習(xí)和探討。
18、
完成這次的課程設(shè)計(jì)任務(wù)，我們要做好以下準(zhǔn)備：
(1)首先要熟練掌握二叉樹(shù)的性質(zhì)、先序遍歷二叉樹(shù)、最優(yōu)二叉樹(shù)的構(gòu)建、字符串匹配等，然后在此基礎(chǔ)上掌握理解huffman樹(shù)和編碼和譯碼。
(2)完成哈夫曼編譯器，我們要考慮如何把文件當(dāng)中的英文字母編成二進(jìn)制代碼，如何將二進(jìn)制代碼翻譯成英文字母以及如何構(gòu)建一棵哈夫曼樹(shù)。
每次出現(xiàn)問(wèn)題我們都一起討論，研究解決和改進(jìn)的方法。這次課程設(shè)計(jì)的成功，可以說(shuō)是我們組員一起努力的成果。我們小組由兩個(gè)人組成，每個(gè)人都有自己在小組中的作用。我負(fù)責(zé)譯碼部分和界面函部分，另一組員負(fù)責(zé)初始化和編碼部分。我們總是在不斷地調(diào)試程序和改進(jìn)程序的功能，最后終于在自己的努力和老
19、師的辛勤指導(dǎo)下順利完成了這次課程設(shè)計(jì)。
六、 參考文獻(xiàn)
1《數(shù)據(jù)結(jié)構(gòu)》（c++語(yǔ)言版），嚴(yán)蔚敏，吳偉民編著，清華大學(xué)出版社
2《數(shù)據(jù)結(jié)構(gòu)題集》嚴(yán)蔚敏編著，清華大學(xué)出版社
七、 致謝
感謝這次課程設(shè)計(jì)中老師的細(xì)心和耐心指導(dǎo)，小組成員的的幫助，團(tuán)結(jié)合作才能使這次任務(wù)圓滿完成。
八、 附錄
源程序：
#include
#include
#include
#include
#include
using namespace std;
#define MAXN 60
#defi
20、ne INF 9999
int date[40]={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的頻率存放在date[65-c+i]中
int n=27;
typedef struct node{
int fa,lchild,rchild,w; //父親，左孩子，右孩子，權(quán)值；
}hfmTree;
char info[30];
typedef struct{
21、 char code[50];
int start;
}Hfmcode;
Hfmcode hfmcode[MAXN]; //哈夫曼編碼
hfmTree hfmtree[MAXN]; //哈夫曼樹(shù)
void inithead(int n,char d[]) //初始化表
{
for(int i=1;i<=n;i++)
{
hfmtree[i].fa=-1;
hfmtree[i].lchild=hfmtree[i].rchild=-1;
if(d[i]== )
hfmtree[27].w=1
22、86;
else
hfmtree[i].w=date[ d[i]-64];
}
for(int j=n+1;j<=2*n-1;j++)
{
hfmtree[j].fa=-1;
hfmtree[j].lchild=hfmtree[j].rchild=hfmtree[j].w=-1;
}
}
void initialization(int n,char d[]) //建樹(shù)成功
{
int s1,s2,rnode,min1,min2;
inithead(n,d);
for(in
23、t i=n+1;i<=n*2-1;i++)
{
min1=INF;
min2=INF;
s1=s2=-1;
for(int k=1;k<=i-1;k++)
{
if(hfmtree[k].fa==-1)
{
if(hfmtree[k].wmin
24、1)
{
min2=hfmtree[k].w;
s2=k;
}
}
}
hfmtree[i].w=hfmtree[s1].w+hfmtree[s2].w;
hfmtree[i].lchild=s1s2?s1:s2;
hfmtree[s1].fa=i;
hfmtree[s2].fa=i;
}
}
void encoding(int n) //編碼完成
{
int c,fa;
Hfmcode hco
25、de;
//對(duì)A~Z字符編碼 結(jié)果存入hfmcode中。
for(int i=1;i<=n;i++)
{
c=i;
hcode.start=n;
fa=hfmtree[i].fa;
while(fa!=-1)
{
if(hfmtree[fa].lchild==c)
hcode.code[hcode.start--]=0;
else
hcode.code[hcode
26、.start--]=1;
c=fa;
fa=hfmtree[fa].fa;
}
hcode.start++;
hfmcode[i]=hcode;
}
//對(duì)ToBeTran.txt中的字符編碼！結(jié)果存入CodeFile.txt文件中。
char s;
ifstream in;
ofstream out;
in.open("ToBeTran.txt");
out.open("CodeFile.txt");
//讀入字符串存入str字符數(shù)組
27、中。
char str;
while(in.get(str))
{
if(str!= )
{
int start=hfmcode[str-64].start;
for(int i=start;i<=n;i++)
out.put(hfmcode[str-64].code[i]);
}
else
{
int start=hfmcode[27].start;
for(int i=start;i<=n;i++)
out.put(hfmcode[27].code[i]);
}
out.put(\n)
28、;
}
}
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<
29、ndl;
}
void decoding()
{
ifstream in;
int i,k;
in.open("CodeFile.txt");
char str[15],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=hfmcode[k].start,p=1;j<=n&&p
30、j])
{
flag=0;
break;
}
}
if(flag==1)
{
fg=1;
break;
}
}
if(fg==1){
if(k==27)
cout<< ;
else
printf("%c",A+k-1);
}
i=1;
continue;
}
str[i]=c;
i++;
}
cout<
31、;
int i=1;
ifstream finsourcechar;
finsourcechar.open("SourceChar.txt");
while(finsourcechar.get(c))
info[i++]=c;
n=i-1;
initialization(n,info);
}
void face()
{
cout<<" "<<"* * * * * * * * * * * * * * * * * * * * * * * * * * *"<
32、*|-------------------------------------------------|*"<
33、 |*"<
34、 "<<"*| I. 初 始 化 |*"<
35、 |*"<
36、ndl;
cout<<" "<<"*| |*"<
37、"* * * * * * * * * * * * * * * * * * * * * * * * * * *"<");
cin>>c;
if(c==Q)
break;
switch(c)
{
case I: fi=1;
init();
p
38、rintf("初始化完畢！\n");
break;
case E: if(fi==0)
{
printf("請(qǐng)先初始化操作！\n");
break;
}
fe=1;
encoding(n);
printf("將“ToBeTran.txt”中的正文");
printf("編碼完成！結(jié)果已存在文件“CodeFile.txt”中\(zhòng)n");
break;
case D: if(fi==0)
{
39、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”中\(zhòng)n");
break;
default: printf("輸入有誤，請(qǐng)重新輸入\n");
}
}
return 0;
}
20
哈夫曼樹(shù)的應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
