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

数据结构课程设计汇报 题 目： 哈夫曼树应用 学生姓名： 谢辉 学 号： 17010201 专业班级： 计科13102 同组姓名： 赵丽娜 指导老师： 徐晓蓉 设计时间： 下学期第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 *| |*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 * * * * * * * * * * * * * * * * * * * * * * * * * * *);cinc;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;