数据结构课程设计-哈夫曼编码和译码报告.doc

内蒙古科技大学课程设计说明书内蒙古科技大学本科生课程设计说明书题 目：数据结构课程设计 哈夫曼编码和译码学生姓名：学 号：专 业：软件工程班 级：1班指导教师：日 期：2016年1月8日I内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目Huffman编码和译码指导教师时间2015.122016.1一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。Huffman编码和译码根据给定的字符集和各字符的频率值，求出其中给定字符Huffman编码，并针对一段文本（定义在该字符集上）进行编码和译码，实现一个Huffman编码/译码系统。要求设计类（或类模板）来描述Huffman树及其操作，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 求Huffman编码v 输入字符串，求出编码v 输入一段编码，实现译码 并设计主函数测试该类。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1数据结构 （C语言版）严蔚敏、吴伟民 主编 清华大学出版社 2004.112数据结构课程设计案例精编（用C/C+描述），李建学 等 编著，清华大学出版社 2007.23.数据结构:用面向对象方法与C+语言描述，殷人昆 主编，清华大学出版社 200719目 录内蒙古科技大学课程设计任务书1第一章 需求分析31.1程序的功能31.2输入输出的要求3第二章概要设计32.1总体设计32.2数据类型设计（或数据结构设计）42.3接口设计 /函数声明5第三章详细设计63.1工程视图63.2类图视图63.3函数的调用关系73.4主程序流程图83.5主要算法流程图9第四章测试分析114.1测试程序执行情况11第五章 用户手册（可选）12第六章课程设计总结13附录：程序代码14第一章 需求分析1.1.程序的功能能对输入的字符串实现Huffman编码，且能利用生成的编码对Huffman代码串进行译码，输出相应字符串。2.2.输入输出的要求首先，输入一个字符串，程序会列出字符串中包含的字符种类及每一种字符出现的次数，然后输出通过Huffman编码得到的各种字符的Huffman编码。此时程序要求输入一串Huffman代码串，输入完毕程序会判断输入的代码串是否合法，若合法则输出译码结果。第二章 概要设计2.1 总体设计主函数哈夫曼树译码函数哈夫曼树编码函数哈夫曼树初始化函数权值大小比较函数2.2 数据类型设计（或数据结构设计）enum Childnone,lchild,rchild; /采用枚举，标记是左孩子还是右孩子class element /元素类public:/类的公有成员elememt(); /构造函数void change(char l,char *c,int p,Child h,int w) /对对象进行修改操作void getparent(int p) /对父结点的值进行修改操作void geta(Child h) /对孩子结点进行修改操作void getweight(int w) /对权值进行修改操作int returnweight() /返回权值操作friend void Select(element h,int k,int *a,int *b);/友元函数的声明friend void HuffmanTreeCode(element HT);friend void HuffmanTreeYima(element huff,char cod,int b);private:/类的私有成员char letter,*code; /letter为字符,*code指向编码字符串 int weight; /权值int parent; /父结点Child a; /为父结点的左孩子还是右孩子;2.3 接口设计 主函数：对输入的字符段进行存储，并对字符数和对应的权值（字符个数）进行统计存储。哈夫曼树初始化函数：对给定的字符数和权值，创建一棵哈夫曼树。权值大小比较函数：找到每次所给集合的最小值和次小值，并返回给哈夫曼树初始化函数。哈夫曼树编码函数：对创建的哈夫曼树，为左孩子的赋值为0，右孩子赋值为1，然后对叶子结点依次编码。哈夫曼树译码函数：对输入的01二进制数一一与叶子结点的编码依次比较匹配。第三章 详细设计3.1 工程视图 图3.1工程视图3.2 类图视图 图3.2类图视图3.3 函数的调用关系主函数main()哈夫曼初始化函数InitHuffmanTree（）寻找最小和次小结点函数Select()字符编码函数HuffmanTreeCode（）字符译码函数HuffmanTreeYima（）如下图：图3.3函数调用关系图3.4 主程序流程图主函数编码字符的录入初始化字符和权值的统计寻找父结点为空的最小和次小结点哈夫曼树是否创建完毕？最小结点和次小结点相加生成新的结点，并置父结点为新生成结点的数组下标编码录入一段二进制数译码是否继续 译码？结束NOYES YESNO 图3.4主程序流程图3.5 主要算法流程图开始HTi调出结点孩子信息，若为左孩子，0进栈；右孩子，1进栈父结点是否为空？01字码依次出栈，并赋值给HTi的编码in?结束i+通过下标找到父结点i=0NOYESYESNO图3.5.1哈夫曼编码函数开始输入二进制字符进行译码操作，以#结束i=0调出HTi的编码与二进制编码进行匹配是否匹配成功？i+in?/用队列存储HTi的字符二进制编码是否结束？译码成功！输出队列中的字符译码结束输入有误！译码失败NOYESNOYESNOYES图3.5.2哈夫曼译码函数第四章 测试分析4.1 测试程序执行情况准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果：输入： 编码输入演示图 输出： 编码输出演示图正确输入哈夫曼编码代号： 正确译码输入演示图输出： 正确输入译码译码结果输出演示图错误输入哈夫曼编码代号： 错误输入哈夫曼编码代码串示意图输出： 错误输入哈夫曼编码代码串输出示意图 第五章 用户手册（可选）1. 运行程序，程序首先会要求你输入需要编码的字符串，输入完毕按回车即可进行编码： 程序启动画面输出： 编码输出画面2. 输出编码后，程序会提示输入需要译码的哈夫曼编码串，输入后按回车即可进行译码： 译码输入界面输出： 译码输出界面 3.译码结束后，输入N可退出程序，输入Y可继续进行译码。第六章 课程设计总结此次课程设计，我编写程序的时候遇到了不少问题，在攻克这些问题，最终实现课题任务的过程中，我学到了不少东西： 首先，在完成一个课题之前，要仔细理解课题要求。我在此次课程设计中犯的最严重的错误，应该算没有仔细审题。课题的要求是用读取文件的方式输入需要编码字符，译码所需的编码代号也要用文本方式输入。我在拿到这个课题的时候，因为没有仔细理解这些要求，就采用了键盘输入字符进行编码和译码的方式，以致没有完全达到课题的要求。 另外，这次课程设计充分暴露了我的惰性思想。在拿到这个课题后，因为对哈夫曼编码这个知识点理解比较到位，所以没花多少时间就完成了课题要求实现的功能。然而，在此之后，我由于自我感觉良好和惰性，没有积极地去寻找改进程序的方法，也没对程序运行的界面进行美化，使其拥有良好的用户使用体验。最终在考核的时候，交给老师的是一个界面简陋，功能不全面的程序。 通过这次课程设计，我更加深入了理解了哈夫曼编码的过程，以及利用哈夫曼编码对数据进行压缩的优越性，并且使我能够更熟练地运用树形的数据结构。并且体会到了在学习中，要严格要求自己，不能因为一点点的成功就骄傲自满，停止不前。附录：程序代码#include #include#include #include #include const int Lengh=1000; /最大长度为1000char coding100; /存储二进制字符串int n; /定义全局变量ofstream file1(编码.txt); /创建编码保存文件ofstream file2(译码.txt); /创建译码保存文件enum Childnone,lchild,rchild; /采用枚举标记事左孩子还是右孩子class elementpublic:elememt();void change(char l,char *c,int p,Child h,int w)code=c;letter=l;a=h;weight=w;parent=p;void getparent(int p)parent=p;void geta(Child h)a=h;void getweight(int w)weight=w;int returnweight()return weight;friend void Select(element h,int k,int *a,int *b);friend void HuffmanTreeCode(element HT);friend void HuffmanTreeYima(element huff,char cod,int b);private:char letter,*code; /letter为字符,*code指向编码字符串 int weight; /权值域int parent; /父结点序号Child a; /为父结点的左孩子还是右孩子;void Select(element h,int k,int *a,int *b);/寻找最小和次小节点的序号void InitHuffmanTree(element huffTree,char t,int w) /哈夫曼树的初始化int i,m=2*n-1,s1,s2; /no+n2=n 所以一要申请m个空间for(i=0;in;i+) /初始前n个结点 huffTreei.change(ti,0,-1,none,wi);for(;i=m;i+) /后m-n个结点置空 huffTreei.change( ,0,-1,none,0);for(i=n;im;i+) /建立哈夫曼树Select(huffTree,i-1,&s1,&s2); /在huffTree中找权值最小的两个结点s1,s2huffTrees1.getparent(i); /将s1,s2合并，则s1,s2的双亲是ihuffTrees2.getparent(i);huffTrees1.geta(lchild); /s1是左孩子huffTrees2.geta(rchild); /s2是右孩子huffTreei.getweight(huffTrees1.returnweight()+huffTrees2.returnweight();/s1,s2的双亲的权值为s1，s2权值之和void Select(element h,int k,int *a,int *b) /寻找最小和次小节点的序号 int i; int min1=1000; /初始化最小结点和次小结点 int min2=1000; for (i=0;i=k;i+)/找最小的结点序号 if (hi.parent=-1&hi.weightmin1) /如果没有父结点并且它的权值小于min1的权值 *a=i; /将i放入a中min1=hi.weight; /找到第一个最小结点 for(i=0;i=k;i+) /找次小结点的序号 if(hi.parent=-1&(*a!=i)&hi.weightmin2) /满足没有父结点，此序号不等于最小结点的序号，权值小于min2 *b=i; min2=hi.weight; /找到次最小结点 void HuffmanTreeCode(element HT) /字符编码int i; char *temp; temp=(char *)malloc(n*sizeof(char); /分配n个字符空间 tempn-1=0; /最后一个字符以后结束字符串 int p; int s; for(i=0;in;i+) /n个字符结点一个个处理 p=i; s=n-1; /s为最后一个结点 while(HTp.parent!=-1) /从字符结点回溯,直至根结点if(HTp.a=lchild) /p指向的如果是左孩子temp-s=0; /s位置字符为0 else if(HTp.a=rchild) /p指向的如果是右孩子temp-s=1; /s位置字符为1 p=HTp.parent; /回溯父结点 HTi.code=(char *)malloc(n-s)*sizeof(char);/分配结点编码长度的内存空间 strcpy(HTi.code,temp+s); /将temp中从第s个位置开始，将编码拷贝到 HTi.code printf(%c,HTi.letter);printf(: ); printf(%sn,HTi.code); /打印出字符即对应的二进制字符串 file1HTi.letter :HTi.code endl; /保存至编码文件中 void HuffmanTreeYima(element huff,char cod,int b) /译码 char sen100; char temp50; char voidstr= ; /空白字符串 int t=0; int s=0; int xx=0; for(int i=0 ; ib; i+) tempt+=codi; /读取字符 tempt = 0; /有效字符串 for(int j=0;jn;j+) /依次与所有字符编码开始匹配 if (!strcmp(huffj.code,temp) /匹配成功sens=huffj.letter; /将字符保存到sen中 s+; xx+=t; strcpy(temp,voidstr); /将TEMP置空 t=0; /t置空 break; if(t=0) /t如果被置空了，表示都匹配出来了，打印译码sens=0;cout译码为:endl; file2sen;coutsenendl;else /t如果没有被置空 ， 源码无法被完全匹配 cout二进制源码有错！从第xx+1位开始endl;file2二进制源码有错！从第xx+1位开始endl; void main()char aLengh,p;int i,bLengh; int symbol=1;int x;i