哈夫曼编码译码器

沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：哈夫曼编码/译码器院（系）：计算机学院专业：计算机科学与技术班级：学号：姓名：指导教师：沈阳航空航天大学课程设计报告I目录沈阳航空航天大学...........................................................................................................I第1章概要设计............................................................................................................11.1题目的内容与要求.................................................................................................11.2总体结构.................................................................................................................1第2章算法分析............................................................................................................22.1核心算法思想.........................................................................................................22.2算法结构定义.........................................................................................................2第3章详细设计............................................................................................................33.1功能流程.................................................................................................................3第4章系统实现............................................................................................................54.1错误分析.................................................................................................................54.2运行结果.................................................................................................................5参考文献..........................................................................................................................8附录..............................................................................................................................9沈阳航空航天大学课程设计报告1第1章概要设计1.1题目的内容与要求内容：设计一个利用哈夫曼算法的编码和译码系统，可以接收从键盘输入的字符集大小、字符和权值信息，创建哈夫曼树生成哈夫曼编码并能对其进行解码。要求：1．存储结构自定；2．将生成的哈夫曼编码与等长编码进行比较，判断优劣；3．给出动态演示过程（选作）。1.2总体结构本程序主要分为3个模块（功能模块图见图1.1）：主模块，编码模块，译码模块。主模块：程序的主体部分，分别调用各个模块，实现各项功能。编码模块：对每个出现的字符进行编码。译码模块：将已有编码译成字符，使之可以直接被读出。哈夫曼编码/译码器主模块编码模块译码模块图1.1功能模块图沈阳航空航天大学课程设计报告2第2章算法分析2.1核心算法思想哈夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n－1次合并，所以共产生n－1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有2n－1个结点，其中n个结点是初始森林的n个孤立结点。并且哈夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n--1的一维数组来存储哈夫曼树中的结点。哈夫曼编码是可变字长编码。编码时借助哈夫曼树，也即带权路径长度最小的二叉树，来建立编码。译码的基本思想是：读文件中编码，并与原先生成的赫夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。2.2算法结构定义结构体存储表示typedefstruct{intweight;intparent,lchild,rchild;}Htnode,*Hfmtree;//动态分配数组存储哈夫曼树typedefchar**Hfmcode;//动态分配数组存储哈弗曼编码表沈阳航空航天大学课程设计报告3第3章详细设计3.1功能流程此流程图为构造哈夫曼树的过程，输入字符的次数为权值对每个结点赋值，构造哈夫曼树，如图3.1开始以读入字符次数对各结点赋初值并令i=2n-1i为0找出根结点权值最小和次小树s1,s2两树合并成新树n+i结束i减1NY图3.1流程图沈阳航空航天大学课程设计报告4此流程图（图3.2）为对字符进行哈夫曼编码的过程，将字符转化为哈夫曼编码。开始i=n第一个字符，i=1结点是否是根结点双亲结点的左结点是否等于该结点记编码0记编码1i=i+1结束将得到的编码存储YYYNNN图3.2字符编码模块流程图沈阳航空航天大学课程设计报告5第4章系统实现4.1错误分析在此程序调试过程中主要遇到以下几类问题：1、本程序运用了对文件进行操作，一定要注意在操作文件是文件的位置，我在做次程序是就是因为操作的文件位置错了导致程序无法正常运行。2、在函数内部有时需要多定义参数，注意参数的作用域，而且注意传引用调用和传值调用的区别，不能不正确的修改实参的值，否则会导致程序运行的错误。3、本程序用到的外部函数较多，在调用时一定要注意传入的参数是否符合函数的定义，而且位置也不能错，这是引用函数要注意的一点。4、刚开始时清屏函数运用出错，导致操作界面消失，使用户无法操作，因此，在使用一些函数是一定要注意。4.2运行结果运行程序首先出现界面图，如图4.2所示。图4.1界面图选择操作1后，输入相应的字符大小，字符和权值，生成哈夫曼树。系统会显示每个字符的哈夫曼编码，如图4.2所示。沈阳航空航天大学课程设计报告6图4.2程序运行截图选择操作2后，输入字符串，系统会显示对字符串进行哈弗曼编码得到的哈弗曼编码，显示以下界面（图4.3）供用户选择。图4.3程序运行截图选择操作3后，系统会显示用哈夫曼编码翻译成的字符，显示以下界面（图4.4）供用户选择图4.4程序运行截图选择操作4后，退出系统，显示以下界面（图4.5）沈阳航空航天大学课程设计报告7图4.5程序运行截图沈阳航空航天大学课程设计报告8参考文献[1]严蔚敏.数据结构(C语言版).清华大学出版社，2007[2]谭浩强.C语言程序设计教程.高等教育出版社，2006[3]苏仕华.数据结构课程设计.机械工业出版社，2007沈阳航空航天大学课程设计报告9附录源程序如下：#includeiostream.h#includestdio.h#includestdlib.h#includestring.h#includefstream.htypedefstruct{//赫夫曼树的结构体charch;intweight;//权值intparent,lchild,rchild;}Htnode,*Hfmtree;//动态分配数组存储赫夫曼树typedefchar**Hfmcode;//动态分配数组存储赫夫曼编码表voidSelect(Hfmtree&HT,inta,int*s1,int*s2)//Select函数，选出HT树到a为止，权值最小且parent为0的2个节点{inti,j,x,y;for(j=1;j=a;++j){if(HT[j].parent==0){x=j;break;}}for(i=j+1;i=a;++i){if(HT[i].weightHT[x].weight&&HT[i].parent==0){x=i;//选出最小的节点沈阳航空航天大学课程设计报告10}}for(j=1;j=a;++j){if(HT[j].parent==0&&x!=j){y=j;break;}}for(i=j+1;i=a;++i){if(HT[i].weightHT[y].weight&&HT[i].parent==0&&x!=i){y=i;//选出次小的节点}}if(xy){*s1=y;*s2=x;}else{*s1=x;*s2=y;}}voidHfmcoding(Hfmtree&HT,Hfmcode&HC,intn)//构建赫夫曼树HT，并求出n沈阳航空航天大学课程设计报告11个字符的赫夫曼编码HC{inti,start,c,f,m,w;intp1,p2;char*cd,z;if(n=1){return;}m=2*n-1;HT=(Hfmtree)malloc((m+1)*sizeof(Htnode));for(i=1;i=n;++i)//初始化n个叶子结点{printf(请输入第%d字符信息和权值：,i);scanf(%c%d,&z,&w);while(getchar()!='\n'){continue;}HT[i].ch=z;HT[i].weight=w;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(;i=m;++i)//初始化其余的结点{HT[i].ch='0';沈阳航空航天大学课程设计报告12HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=n+1;i=m;++i)//建立赫夫曼树{Select(HT,i-1,&p1,&p2);HT[p1].parent=i;HT[p2].parent=i;HT[i].lchild=p1;HT[i].rchild=p2;HT[i].weight=HT[p1].weight+HT[p2].weight;}HC=(Hfmcode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0';//-------从叶子到根逆向给出每个字符的哈夫曼编码--------------for(i=1;i=n;++i){start=n-1;//编码起始符位置for(c=i,f