哈夫曼树的应用数据结构课程设计.doc

数据结构课程设计报告 题 目： 哈夫曼树应用 学生姓名： 谢辉 学 号： 201317010201 专业班级： 计科13102 同组姓名： 赵丽娜 指导教师： 徐晓蓉 设计时间： 2014年下学期第18周 指导老师意见: 评定成绩: 签名: 日期:目录一、需求分析21.分析问题22.确定解决方案23.输入的形式和输入值的范围34.输出的形式35.程序所能达到的功能3二、概要设计41. 主程序的流程图：42程序中数据类型的定义：43各程序模块之间的层次(调用)关系：4三、详细设计51哈夫曼树存储及类的定义：52.哈夫曼树的基本操作:63.主函数7四、调试分析和测试结果.91.测试数据及其输出结果：92.调试过程中遇到的问题及解决办法: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以及哈夫曼树类定义classHuffman。3各程序模块之间的层次(调用)关系：主函数main（）调用初始化，编码，译码，打印二进制编码，打印哈夫曼树这五个子函数；进入初始化功能后调用手动输入，文本读入，默认文本这三个函数；进入编码功能后调用手动编码，文本读入编码这两个函数；进入译码功能后调用手动译码，文本读入译码这两个函数(如图2所示)。手动输入图二:各程序模块之间的层次（调用）关系默认文本主函数初始化编码译码打印编码代码退出从文件读入从文件读入三、 详细设计1 哈夫曼树存储及类的定义：#include #include #include #include #include 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; /父亲，左孩子，右孩子，权值；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.主函数int main()char c;face();int fi,fe,fd;fi=fe=fd=0;printf(数据从“sourceChar.txt”文件中输入!n); while(1)printf(-);cinc;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个英文字母以及空格进行编码。分别存入hfmcode1-26中，空格的编码存入hfmcode27中。五、 总结一周的课程设计结束了。在此过程中，我们小组齐心协力，互相帮助，分工明确，相互学习和探讨。完成这次的课程设计任务，我们要做好以下准备：(1)首先要熟练掌握二叉树的性质、先序遍历二叉树、最优二叉树的构建、字符串匹配等，然后在此基础上掌握理解huffman树和编码和译码。(2)完成哈夫曼编译器，我们要考虑如何把文件当中的英文字母编成二进制代码，如何将二进制代码翻译成英文字母以及如何构建一棵哈夫曼树。每次出现问题我们都一起讨论，研究解决和改进的方法。这次课程设计的成功，可以说是我们组员一起努力的成果。我们小组由两个人组成，每个人都有自己在小组中的作用。我负责译码部分和界面函部分，另一组员负责初始化和编码部分。我们总是在不断地调试程序和改进程序的功能，最后终于在自己的努力和老师的辛勤指导下顺利完成了这次课程设计。六、 参考文献1数据结构（c+语言版），严蔚敏，吴伟民编著，清华大学出版社2数据结构题集严蔚敏编著，清华大学出版社七、 致谢感谢这次课程设计中老师的细心和耐心指导，小组成员的的帮助，团结合作才能使这次任务圆满完成。八、 附录源程序：#include #include #include #include #include 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; /父亲，左孩子，右孩子，权值；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.wmin1)min2=min1;s2=s1;min1=hfmtreek.w;s1=k;else if(hfmtreek.wmin1)min2=hfmtreek.w;s2=k;hfmtreei.w=hfmtrees1.w+hfmtrees2.w;hfmtreei.lchild=s1s2?s1:s2;hfmtrees1.fa=i;hfmtrees2.fa=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; /对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);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+;coutstr;out.put(str);if(i%50=0)coutendl;out.put(n);coutendl; 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π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+;coutendl;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 *| 哈 夫 曼 码 的 编 / 译 码 系 统 |*endl;cout *| |*endl;cout *| |*endl;cout *| $. 主 菜 单 |*endl; cout *| |*