哈夫曼编码译码器.doc

沈阳航空航天大学课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：哈夫曼编码/译码器院（系）：计算机学院专 业：计算机科学与技术班 级：学 号：姓 名：指导教师：目录沈阳航空航天大学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存储结构自定；2将生成的哈夫曼编码与等长编码进行比较，判断优劣；3给出动态演示过程（选作）。1.2总体结构本程序主要分为3个模块（功能模块图见图1.1）：主模块，编码模块，译码模块。主模块：程序的主体部分，分别调用各个模块，实现各项功能。编码模块：对每个出现的字符进行编码。译码模块：将已有编码译成字符，使之可以直接被读出。 图1.1功能模块图第2章 算法分析2.1核心算法思想哈夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n1次合并，所以共产生n1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有2n1个结点，其中n个结点是初始森林的n个孤立结点。并且哈夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n-1的一维数组来存储哈夫曼树中的结点。哈夫曼编码是可变字长编码。编码时借助哈夫曼树，也即带权路径长度最小的二叉树，来建立编码。译码的基本思想是：读文件中编码，并与原先生成的赫夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。2.2算法结构定义结构体存储表示typedef struct int weight;int parent,lchild,rchild; Htnode,*Hfmtree; /动态分配数组存储哈夫曼树typedef char *Hfmcode; /动态分配数组存储哈弗曼编码表第3章 详细设计3.1功能流程此流程图为构造哈夫曼树的过程，输入字符的次数为权值对每个结点赋值，构造哈夫曼树，如图3.1 图3.1 流程图此流程图（图3.2）为对字符进行哈夫曼编码的过程，将字符转化为哈夫曼编码。 图3.2字符编码模块流程图第4章 系统实现4.1错误分析在此程序调试过程中主要遇到以下几类问题：1、本程序运用了对文件进行操作，一定要注意在操作文件是文件的位置，我在做次程序是就是因为操作的文件位置错了导致程序无法正常运行。2、在函数内部有时需要多定义参数，注意参数的作用域，而且注意传引用调用和传值调用的区别，不能不正确的修改实参的值，否则会导致程序运行的错误。3、本程序用到的外部函数较多，在调用时一定要注意传入的参数是否符合函数的定义，而且位置也不能错，这是引用函数要注意的一点。4、刚开始时清屏函数运用出错，导致操作界面消失，使用户无法操作，因此，在使用一些函数是一定要注意。4.2运行结果运行程序首先出现界面图，如图4.2所示。 图4.1界面图选择操作1后，输入相应的字符大小，字符和权值，生成哈夫曼树。系统会显示每个字符的哈夫曼编码，如图4.2所示。 图4.2程序运行截图选择操作2后，输入字符串，系统会显示对字符串进行哈弗曼编码得到的哈弗曼编码，显示以下界面（图4.3）供用户选择。 图4.3程序运行截图选择操作3后，系统会显示用哈夫曼编码翻译成的字符，显示以下界面（图4.4）供用户选择 图4.4程序运行截图选择操作4后，退出系统，显示以下界面（图4.5）图4.5程序运行截图参考文献1 严蔚敏.数据结构(C语言版).清华大学出版社，20072 谭浩强.C语言程序设计教程.高等教育出版社，20063 苏仕华.数据结构课程设计.机械工业出版社，2007附 录源程序如下：#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<fstream.h>typedef struct /赫夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;Htnode,*Hfmtree; /动态分配数组存储赫夫曼树typedef char *Hfmcode; /动态分配数组存储赫夫曼编码表void Select(Hfmtree &HT,int a,int *s1,int *s2) /Select函数，选出HT树到a为止，权值最小且parent为0的2个节点int i,j,x,y;for(j=1;j<=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTx.weight&&HTi.parent=0)x=i; /选出最小的节点for(j=1;j<=a;+j)if(HTj.parent=0&&x!=j)y=j;break;for(i=j+1;i<=a;+i)if(HTi.weight<HTy.weight&&HTi.parent=0&&x!=i)y=i; /选出次小的节点if(x>y)*s1=y;*s2=x;else*s1=x;*s2=y;void Hfmcoding(Hfmtree &HT,Hfmcode &HC,int n) /构建赫夫曼树HT，并求出n个字符的赫夫曼编码HCint i,start,c,f,m,w;int p1,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;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i<=m;+i) /初始化其余的结点HTi.ch='0'HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i<=m;+i) /建立赫夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(Hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1='0' /-从叶子到根逆向给出每个字符的哈夫曼编码-for(i=1;i<=n;+i) start=n-1; /编码起始符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /从叶子到根逆向求编码if(HTf.lchild=c)cd-start='0'elsecd-start='1'HCi=(char*)malloc(n-start)*sizeof(char); /为地i个字符编码分配空间strcpy(HCi,&cdstart);free(cd);void main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件输入输出流ofstream output_file;char choice,str100;Hfmtree HT;Hfmcode HC;while(choice!='4') /当choice的值4时循环 printf("n"); printf(" *赫夫曼编码/译码器*n"); printf(" * 1 创建哈夫曼树 *n"); printf(" * 2 编码 *n");printf(" * 3 译码 *n");printf(" * 4 退出 *n");printf("n"); printf("请输入您要操作的步骤");cin>>choice; if(choice='1') /初始化赫夫曼树cout<<"请输入字符个数："cin>>n;Hfmcoding(HT,HC,n);for(i=1;i<=n;+i)cout<<HTi.ch<<":"<<HCi<<endl;output_file.open("hfmTree.txt");if(!output_file)cout<<"can't oen file!"<<endl; for(i=1;i<=n;i+)output_file<<"("<<HTi.ch<<HCi<<")"output_file.close();printf("赫夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!n"); else if(choice='2') /进行编码，并将字符放入A.txt，码值放入B.txt中printf("请输入字符：");gets(str);output_file.open("A.txt");if(!output_file)cout<<"can't oen file!"<<endl;output_file<<str<<endl;output_file.close();output_file.open("B.txt");if(!output_file)cout<<"can't oen file!"<<endl;for(i=0;i<strlen(str);i+)for(j=0;j<=n;+j)if(HTj.ch=stri)output_file<<HCj;break;output_file.close();cout<<"n"printf("编码完毕，并且已经存入B.txt文件！n");input_file.open("B.txt"); /从B.txt中读入编码，输出在终端if(!input_file)cout<<"can't oen file!"<<endl;input_file>>code;cout<<"编码码值为："<<code<<endl;input_file.close(); else if(choice='3') /读入B.txt中的编码进行译码，将译出来的字符放入Textfile.txt中input_file.open("B.txt");if(!input_file)cout<<"can't oen file!"<<endl;input_file>>h;input_file.close();output_file.open("Textfile.txt");if(!output_file)cout<<"can't oen file!"<<endl;k=0;while(hk!='0') /先用编码中的前几个和字符的编码相比较，然后往后移for(i=1;i<=n;i+)l=k;for(j=0;j<strlen(HCi);j+,l+)hlj=hl;hlj='0'if(strcmp(HCi,hl)=0)output_file<<HTi.ch;k=k+strlen(HCi);break;output_file.close();input_file.open("Textfile.txt");if(!input_file)cout<<"can't oen file!"<<endl;input_file>>h; cout<<h<<endl;input_file.close();printf("译码结束，字符已经存入Textfile.txt文件中!n"); else if(choice='4') exit(0); else /如果选了选项之外的就让用户重新选择printf("您没有输入正确的步骤，请重新输入！");课程设计总结：通过近两周的课程设计使我对哈夫曼树以及哈夫曼编码译码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。在做课设的过程中我也遇到了很多问题：开始的时候，代码中有许多的错误，特别是有一个“无法找到文件”的错误让我束手无策，最后还是屏蔽了定义的四个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现文章的读入时，由于对文件不是太熟悉，只好翻开C语言和C+语言书本仿照其模式编写，但后来进入了死循环，最后的解决方式是在main函数里有一个控制语句使用不正确。我们遇到问题很正常，说明我们掌握的知识还是太少不灵活，并且这些错误也让我明白了一个道理-细节决定成败。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师和同学也很重要，毕竟对待同一问题我们会有不同的理解和分析，相互之间的交流也是一种学习方法的沟通。通过这次课程设计，我看清楚了自己的编程功底和动手能力还不如人意，这主要是平时实践太少的缘故。我想，在即将到来的寒假中，我会努力尝试编写一些程序，争取提高自己的编程水平。我相信通过我的不断努力，我一定能收获更多果实。指导教师评语：指导教师(签字)： 年 月 日课程设计成绩