哈夫曼树的应用数据结构-学位论文.doc

各专业完整优秀毕业论文设计图纸

《数据结构》课程设计报告

题 目： 哈夫曼树应用
学生姓名：
学 号： 201317010201
专业班级： 计科13102
同组姓名：
指导教师：
设计时间： 2014年下学期第18周

指导老师意见:

评定成绩: 签名: 日期:

目录
一、 需求分析 2
1. 分析问题 2
2. 确定解决方案 2
3. 输入的形式和输入值的范围 3
4.输出的形式 3
5.程序所能达到的功能 3
二、概要设计 4
1. 主程序的流程图： 4
2．程序中数据类型的定义： 4
3．各程序模块之间的层次(调用)关系： 4
三、 详细设计 5
1． 哈夫曼树存储及类的定义： 5
2.哈夫曼树的基本操作: 6
3.主函数 7
四、 调试分析和测试结果. 9
1. 测试数据及其输出结果： 9
2. 调试过程中遇到的问题及解决办法: 13
五、 总结 14
六、 参考文献 14
七、 致谢 14
八、 附录 14

一、 需求分析
1. 分析问题
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。为这样的信息收发站写一个哈夫曼码的编/译码系统。
2. 确定解决方案
设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储结构存储所需要的数据，通过不同的函数来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的txt文件中，通过主函数调用来实现功能检测。
3. 输入的形式和输入值的范围
手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。
 4.输出的形式 
在显示器界面上或者以文本的形式来实现程序调试的输出。
5.程序所能达到的功能 
（1）I:初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
（2）E:编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件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）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“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   
实现提示：
（1） 编码结果以文本方式存储在文件CodeFile中。
（2） 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。
（3） 在程序的一次执行过程中，第一次执行I，D或E命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
二、概要设计
I.初始化
E.编码
D.译码
P.打印编码代码
Q.退出
请重新输入选项
判断选项
是否正确
选择菜单项
主菜单
开始
1. 主程序的流程图：
是
否

图一：主程序流程图

2．程序中数据类型的定义：
用到三组结构体，分别是哈夫曼树的动态数组存储结构*HuffmanTree，哈夫曼编码表的存储结构HuffmanCode，字符结点的动态数组存储结构wElem 以及哈夫曼树类定义class Huffman。
3．各程序模块之间的层次(调用)关系： 
主函数main（）调用初始化，编码，译码，打印二进制编码，打印哈夫曼树这五个子函数；进入初始化功能后调用手动输入，文本读入，默认文本这三个函数；进入编码功能后调用手动编码，文本读入编码这两个函数；进入译码功能后调用手动译码，文本读入译码这两个函数(如图2所示)。
手动输入
图二:各程序模块之间的层次（调用）关系
默认文本
主函数
初始化

编码

译码
打印编码代码

退出

从文件读入
从文件读入

三、 详细设计
1． 哈夫曼树存储及类的定义：
#include <iostream>
#include <cstdio>
#include <windows.h>
#include <queue>
#include <fstream>
using namespace std;
#define MAXN 60
#define 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; //父亲，左孩子，右孩子，权值；
}hfmTree;
char info[30];
typedef struct{
char code[50];
int start;
}Hfmcode;
Hfmcode hfmcode[MAXN]; //哈夫曼编码
hfmTree hfmtree[MAXN]; //哈夫曼树
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.主函数
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");
break;
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("译码成功,译码结果为：\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) 进入主菜单界面：
用户可以选择所要执行的操作，比如：初始化<建立哈夫曼树>，编码，译码，打印二进制编码代码。在执行编码、译码操作前，请先初始化默认的哈夫曼树(如图3所示) 。

图3：主菜单界面
当输入错误的指令时（如图4所示）:

图4
当未进行初始化时进行编码是输出（如图5所示）：

图5
(2) 进入初始化界面（如图6所示）：

图6
(3) 进入编码界面（如图7所示）：

图7
(4) 进入译码界面（如图8所示）：

图8
(5) 进入打印编码代码界面(如图9所示)：

图9
（6） 退出系统（如图10所示）：

1.调试过程中遇到的问题及解决办法:
在此系统中，我负责的是编码，赫夫曼树的建立在译码之前，数据从文件“SourceChar.txt”中输入，对26个英文字母以及空格进行编码。分别存入hfmcode[1-26]中，空格的编码存入hfmcode[27]中。

五、 总结
一周的课程设计结束了。在此过程中，我们小组齐心协力，互相帮助，分工明确，相互学习和探讨。
完成这次的课程设计任务，我们要做好以下准备： 
(1)首先要熟练掌握二叉树的性质、先序遍历二叉树、最优二叉树的构建、字符串匹配等，然后在此基础上掌握理解huffman树和编码和译码。 
(2) 完成哈夫曼编译器，我们要考虑如何把文件当中的英文字母编成二进制代码，如何将二进制代码翻译成英文字母以及如何构建一棵哈夫曼树。
每次出现问题我们都一起讨论，研究解决和改进的方法。这次课程设计的成功，可以说是我们组员一起努力的成果。我们小组由两个人组成，每个人都有自己在小组中的作用。 我负责译码部分和界面函部分，另一组员负责初始化和编码 部分。  我们总是在不断地调试程序和改进程序的功能，最后终于在自己的努力和老师的辛勤指导下顺利完成了这次课程设计。
六、 参考文献
1 《数据结构》（c++语言版），严蔚敏，吴伟民编著，清华大学出版社
 2《数据结构题集》严蔚敏编著，清华大学出版社 
七、 致谢
感谢这次课程设计中老师的细心和耐心指导，小组成员的的帮助，团结合作才能使这次任务圆满完成。
八、 附录
源程序：
#include <iostream>
#include <cstdio>
#include <windows.h>
#include <queue>
#include <fstream>
using namespace std;
#define MAXN 60
#define 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; //父亲，左孩子，右孩子，权值；
}hfmTree;
char info[30];
typedef struct{
char code[50];
int start;
}Hfmcode;
Hfmcode hfmcode[MAXN]; //哈夫曼编码
hfmTree hfmtree[MAXN]; //哈夫曼树
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=186;
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[]) //建树成功
{
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(hfmtree[k].fa==-1)
{
if(hfmtree[k].w<min1)
{
min2=min1;
s2=s1;
min1=hfmtree[k].w;
s1=k;
}
else if(hfmtree[k].w<min2&&hfmtree[k].w>min1)
{
min2=hfmtree[k].w;
s2=k;
}
}
}

hfmtree[i].w=hfmtree[s1].w+hfmtree[s2].w;
hfmtree[i].lchild=s1<s2?s1:s2;
hfmtree[i].rchild=s1>s2?s1:s2;
hfmtree[s1].fa=i;
hfmtree[s2].fa=i;
}
}
void encoding(int n) //编码完成
{
int c,fa;
Hfmcode hcode;
//对A~Z字符编码 结果存入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.start--]='1';
c=fa;
fa=hfmtree[fa].fa;
}
hcode.start++;
hfmcode[i]=hcode;
}
//对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=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');
}
}
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 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<i;j++,p++)
{
if(str[p]!=hfmcode[k].code[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<<endl;
}
void init()
{
char c;
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<<" "<<"* * * * * * * * * * * * * * * * * * * * * * * * * * *"<<endl;
cout<<" "<<"*|-------------------------------------------------|*"<<endl;
cout<<" "<<"*| |*"<<endl;
cout<<" "<<"*| 哈 夫 曼 码 的 编 / 译 码 系 统 |*"<<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. 推 出 系 统 |*"<<endl;
cout<<" "<<"*|-------------------------------------------------|*"<<endl;
cout<<" "<<"* * * * * * * * * * * * * * * * * * * * * * * * * * *"<<endl;
}

int main()
{
char c;
face();
int fi,fe,fd;
fi=fe=fd=0;
printf("数据从“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("请先初始化操作！\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("译码成功,译码结果为：\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;
}

20