哈夫曼编译码器数据结构实践环节实验报告(课程设计)

1、洛阳理工学院课程设计说明书课程名称数据结构设计课题哈夫曼编/译码器专业计算机科学与技术班级XXXXX学号B12XXXXXXX姓名XXX完成日期2014年6月14日课程设计任务书设计题目_哈夫曼编/译码器设计内容与要求：设计内容：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，设计一个哈夫曼编/译码系统。要求：以每个字符出现的次数为权值，建立哈夫曼树，求出哈夫曼编码，对文件yuanwen中的正文进行编码，将结果存到文件yiwen中，再对文件yiwen中的代码进行译码，结果存到textfile中。指导教师：XXXX2014年6月5日课程设计评语成绩：指导教师：年月日洛阳理工学

2、院课程设计报告【问题描述】打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，设计一个哈夫曼编/译码系统。利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。【基本要求】以每个字符出现的次数为权值，建立哈夫曼树，求出哈夫曼编码，对文件yuanwen中的正文进行编码，将结果存到文件yiwen中，再对文件yiwen中的代码进行译码，结果存到

3、textfile中。一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E:编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D:译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。【测试数据】用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下英文的编码和译码：“Il

4、ikeplayingfootball”。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161【算法思想】哈夫曼编译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。最简单的二进制编码方式是等长编码。若采用

5、不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。121)其主要流程图如图1-1所示。开始否结点数是否大于1是否Iv2*N?是否是是否是否结束是否为根结点?左子是否为空?右子是否为空输出根结点和权值/输出两子结点和已构造的结点将data和权值赋给htI+调用SELECT函数父结点为两子结点之和此时编码为0编码为1计算根结点函数(2)设计包含的几个方面：赫夫曼树的建立哈夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值

6、最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n1次合并，所以共产生n1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有2n-1个结点，其中n个结点是初始森林的n个孤立结点。并且赫夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n-1的一维数组来存储赫夫曼树中的结点。 哈夫曼编码要求电文的哈夫曼编码，必须先定义哈夫曼编码类型，根据设计要求和实际需要定义的类型如下：typedetstructcharch;/存放编码的字符charbitsN1;/存放编码位串intlen;/编码的长度CodeNode;/编码结构体

7、类型 代码文件的译码译码的基本思想是：读文件中编码，并与原先生成的哈夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。【模块划分】1) 问题分析哈夫曼树的定义1. 哈夫曼树节点的数据类型定义为：typedefstruct/哈夫曼树的结构体charch;intweight;/权值intparent,lchild,rchild;htnode,*hfmtree;2) 所实现的功能函数如下1、voidhfmcoding(hfmtree&HT,hfmcode&HC,intn初始化哈夫曼树，处理InputHuffman(HuffmanHfm)函数得到的数据，按照哈夫曼规则建立2

8、叉树。此函数块调用了Select()函数。2、voidSelect(hfmtree&HT,inta,int*p1,int*p2)/Select函数，选出HT树到a为止，权值最小且parent为0的2个节点3、Encoding编码功能：对输入字符进行编码4、Decoding译码功能：利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat中。5、主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。3) 系统功能模块图：/构造

9、哈夫曼树/int的范围是-3276832767/lnode和rnode记录最小权值的/只在尚未构造二叉树的结/若权值小于最小的左【数据结构】(1) 哈夫曼树的存储结构描述为：#defineN50/叶子结点数#defineM2*N-1/哈夫曼树中结点总数typedefstructintweight;/叶子结点的权值intlchild,rchild,parent;/左右孩子及双亲指针HTNode;/树中结点类型typedefHTNodeHuffmanTreeM+1;哈夫曼树的算法voidCreateHT(HTNodeht,intn)/调用输入的数组ht,和节点数ninti,k,lnode,rnod

10、e;intmin1,min2;for(i=0;i<2*n-1;i+)hti.parent=hti.lchild=hti.rchild=-1;/所有结点的相关域置初值-1for(i=n;i<2*n-1;i+)min1=min2=32767;lnode=rnode=-1;两个结点位置for(k=0;k<=i-1;k+)if(htk.parent=-1)点中查找if(htk.weight<min1)节点的权值min2=min1;rnode=lnode;min1=htk.weight;lnode=k;elseif(htk.weight<min2)min2=htk.weig

11、ht;rnode=k;htlnode.parent=i;htrnode.parent=i;/两个最小节点的父节点是ihti.weight=htlnode.weight+htrnode.weight;/两个最小节点的父节点权值为两个最小节点权值之和hti.lchild=lnode;hti.rchild=rnode;/父节点的左节点和右节点(2) 哈夫曼编码voidCreateHCode(HTNodeht,HCodehcd,intn)inti,f,c;HCodehc;for(i=0;i<n;i+)码hc.start=n;c=i;f=hti.parent;while(f!=-1)环if(htf

12、.lchild=c)hc.cdhc.start-='0'elsehc.cdhc.start-='1'c=f;f=htf.parent;hc.start+;hc.cd中最开始字符hcdi=hc;/根据哈夫曼树求哈夫曼编/循序直到树根结点结束循/处理左孩子结点/处理右孩子结点/start指向哈夫曼编码voidDispHCode(HTNodeht,HCodehcd,intn)/输出哈夫曼编码的列表inti,k;printf("输出哈夫曼编码:n");/输出data中的所有数/输出所有data中数for(i=0;i<n;i+)据，即A-Zpri

13、ntf("%c:t",hti.data);for(k=hcdi.start;k<=n;k+)据的编码printf("%c",hcdi.cdk);printf("n");voideditHCode(HTNodeht,HCodehcd,intn)/编码函数charstringMAXSIZE;/把要进行编码的字符串存/#为终止标志/循环查找与输入字符相inti,j,k;scanf("%s",string);入string数组中printf("n输出编码结果:n");for(i=0;stringi

14、!='#'i+)for(j=0;j<n;j+)if(stringi=htj.data)同的编号，相同的就输出这个字符的编码for(k=hcdj.start;k<=n;k+)printf("%c",hcdj.cdk);break;/输出完成后跳出当前for循环(3)哈夫曼译码voiddeHCode(HTNodeht,HCodehcd,intn)/译码函数charcodeMAXSIZE;inti,j,l,k,m,x;scanf("%s",code);/把要进行译码的字符串存入code数组中while(code0!='#&#

15、39;)for(i=0;i<n;i+)m=0;/m为想同编码个数的计数器for(k=hcdi.start,j=0;k<=n;k+,j+)/j为记录所存储这个字符的编码个数if(codej二二hcdi.cdk)/当有相同编码时m值加1m+;if(m=j)/当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf("%c",hti.data);for(x=0;codex-1!='#'x+)/把已经使用过的code数组里的字符串删除codex=codex+j;测试情况】1)程序运行时，进入的主界面如图2）选择1进入，创建名称为y

16、uanwen的文件，如图：（3）输入英语原文为Ilikeplayingfootball,如图所示：馬输入原文结東标志为：勺IlikeplacingfootballA£主意：原文件将保存在名称为Wangen的文件中|是否继续？C1-VES2,NO）：.4）程序对原文进行编码运行输出结果，程序如图：舉鑼礬霜眾1矗下:T的个数为江X的个数为的个数为江”夕的个数为汐，的个数为叮f的个数为5,的个数为的个数为江J的个数为：4Ji，的个数为汐的个数为江的个数为汐W的个数为江，的个数为f的个数为江尚字符编码结果为:I的编码为：00111的编码为：011丄的编码为:010i的编码为：0001*的编码

17、为:00110卜的编码为:1001卜的编码为：1盹0卜的编码为：0000P的编码为：1011斤的编码为：1010b的编码为:H01F的编码为:H00b的编码为：0010*的编码为：1111b的编码为：iii0原文的编码为：001110110100001001101001011100001000001011000110101101011110000100010111111100000010010眩意：原文的编码将尿存在以名称为9"曲的文件中|展否继续？(1-VES2,NO)：【心得】在我自己课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难，我的调试及其中的错

18、误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了：在定义头文件时可多不可少，即我们可多写些头文件，肯定不会出错，但是若没有定义所引用的相关头文件，必定调试不通过；在执行译码操作时，不知什么原因，总是不能把要编译的二进制数与编译成的字符用连接号连接起来，而是按顺序直接放在一起，视觉效果不是很好。还有就是，很遗憾的是，我们的哈夫曼编码/译码器没有像老师要求的那样完成编一个文件的功能，这是我们设计的失败之处。通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识源程序】#incl

19、ude<stdio.h>#include<stdlib.h>#include<string.h>#defineN5000#definem128/叶子结点个数，即字符总类数#defineM2*m-1/哈夫曼树的节点数charCHN;/记录原文字符数组charYWN;/记录译文字符数组typedefchar*Hcodem+1;/存放哈夫曼字符编码串的头指针的数组typedefstructchara;intnum;dangenode;/记录单个字符的类别和出现的次数typedefstructdangenodeb129;inttag;jilunode;/统计原文出现

20、的字符种类数typedefstructnode1intweight;/结点权值intparent;/双亲下标intLchild;/左孩子结点的下标intRchild;/右孩子的下标htnode,hnM;静态三叉的哈夫曼树的定义voidjianliwenjian()FILE*fp;printf("现在建立文件，以存储原文(文件名称默认为yuanwen)n");printf("文件建立中n");if(fp=fopen("yuanwen","wb")=NULL)/建立文件printf("Cannotopenfi

21、len");exit(0);printf(”文件已建立，名称为：yuanwen");fclose(fp);/关闭文件voidluruyuanwen()/原文输入完后，将其保存到文件yuanwen中charch;FILE*fp;洛阳理工学院课程设计报告if(fp=fopen("yuanwen","wb")=NULL)printf("Cannotopenfilen");exit(0);/打开文件printf(”请输入原文(结束标志为：A)n");doch=getchar();fputc(ch,fp);whil

22、e(ch!='A');getchar();fclose(fp);/将字符保存到文件中/判断结束/接收回车命令符/关闭文件voidmin_2(hnht,intn,int*tagl,int*tag2)/在建哈夫曼树的过程中，选择权值小的两/个结点inti,min,s;min=N;for(i=l;i<=n;i+)if(hti.weight<min&&hti.parent=0)min=hti.weight;*tagl=i;min=N;/记录权值最小的结点下标for(i=l;i<=n;i+)if(hti.weight<min&&ht

23、i.parent=0&&i!=*tagl)min=hti.weight;*tag2=i;if(ht*tagl.weight=ht*tag2.weight&&ht*tag2.Lchild!=0)s=(*tagl);/如果结点权值相同，先出现的放在哈夫曼树的左边(*tagl)=(*tag2);(*tag2)=s;voidchuangjian(jilunode*jilu,hnht)/建立哈夫曼树、以及对原FILE*fp;文字符的类别和数量统计inti=-l,j,s=0,tagl,tag2;/s=0;/i=-1;/charch;if(fp=fopen("yua

24、nwen","rb")=NULL)/以只读的方式打开文件printf("Cannotopenfilen");exit(0);while(!feof(fp)/判断文件指示标志是否移动到了文件尾处charch;ch=fgetc(fp);if(ch!=w)判断字符是否是结束标志+i;CHi=ch;for(j=1;j<=jilu->tag;j+)if(CHi=jilu->bj.a)jilu->bj.num+;break;if(j-1=jilu->tag&&CHi!=jilu->bj-1.a)jilu-

25、>tag+;jilu->bjilu->tag.a=CHi;jilu->bjilu->tag.num=1;jilu->tag-;fclose（fp）;/关闭文件printf（”原文中的各字符统计状况如下：n"）;printf（"*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*八*n"）；for(i=1;i<=jilu->tag;i+)s+;printf("'%c'的个数为:%d",jilu->bi.a,jil

26、u->bi.num);if(s%4=0)/每行放四个数据printf("n");printf("n");for(i=1;i<=2*(jilu->tag)-1;i+)if(i<=jilu->tag)hti.weight=jilu->bi.num;/初始化叶子结点权值hti.Lchild=0;hti.parent=0;hti.Rchild=0;/初始化叶子结点左孩子/初始化叶子结点父母/初始化叶子结点右孩子elsehti.Lchild=0;hti.parent=0;hti.Rchild=0;hti.weight=0;/初始

27、化非叶子结点左孩子/初始化非叶子结点父母/初始化非叶子结点右孩子/初始化非叶子结点权值for(i=jilu->tag+1;i<=2*(jilu->tag)-1;i+)min_2(ht,i-1,&tag1,&tag2);/需找权值小的两个父母为0的结点httag1.parent=i;httag2.parent=i;hti.Lchild=tag1;hti.Rchild=tag2;hti.weight=httag1.weight+httag2.weight;voidbianma(jilunode*jilu,hnht,Hcodehc,intn)/哈夫曼树建完后，对叶/

28、子结点逐个编码char*cd;/申请存储字符的临时空间/加结束标志intstart,i,p,c;cd=(char*)malloc(n+1)*sizeof(char);cdn-1='0'for(i=1;i<=n;i+)start=n-1;c=i;p=hti.parent;while(p!=0)-start;if(htp.Lchild=c)cdstart='1'/结点在左边置1if(htp.Rchild=c)cdstart='0'/结点在右边置0c=p;p=htp.parent;printf("%c的编码为：sn",jilu

29、->bi.a，&cdstart);hci=(char*)malloc(n-start)*sizeof(char);/为字符数组分配空间strcpy(hci,&cdstart);将临时空间中的编码复制到字符数组中free(cd);/释放临时空间voidbianmabaocun(Hcodehc,jilunode*jilu)inti,j;FILE*fp;if(fp=fopen("yiwen","wb")=NULL)printf("Cannotopenfilen");exit(0);for(i=0;i<=N&

30、;&CHi!='A'i+)for(j=1;j<=jilu->tag;j+)if(CHi=jilu->bj.a)fputs(hcj,fp);printf("%s",hcj);fclose(fp);voidyiwen(Hcodehc,jilunode*jilu)中inttag1,tag2,i,j,s=0;/将原文以编码的形式保存到char*c;if(fp=fopen("yiwen","rb")=NULL)printf("cannotopenfilen");exit(0);whi

31、le(!feof(fp)tag1=1;/结束for循环的辅助标志/文件yiwen中/以写的方式打开文件/文件打开失败退出/将文件中的字符输出到字符数组中/关闭文件读取yiwen中的编码，并将其翻译/为原文存放到字符数组YWN/文件指针/以只读的方式打开文件FILE*fp;tag2=1;/结束for循环的辅助标志c=(char*)malloc(200*sizeof(char);for(i=0;i<200&&tag1;i+)ci=fgetc(fp);/将文件中的字符输出到数组中ci+1='0'/加结束标志for(j=1;(j<=jilu->tag)

32、&&tag2;j+)if(strcmp(hcj,c)=0)/将编码与原文字符匹配YWs=jilu->bj.a;匹配成功后将字符保存到数组YW中tag1=0;s+;free(c);/释放临时字符存储空间tag2=0;YWs='0'将翻译的译文保存到文件textfile中voidbaocunyiwen()inti;FILE*fp;if(fp=fopen("textfile","wb")=NULL)printf("Cannotopenfilen");exit(0);for(i=0;YWi!='0

33、'i+)/将数组中的字符保存到文件中/关闭文件/从文件textfile中读取译文fputc(YWi,fp);putchar(YWi);fclose(fp);voidduquyiwen()charch;FILE*fp;if(fp=fopen("textfile","rb")=NULL)/以只读的方式打开文件22printf("cannotopenfilen");exit(0);while(!feof(fp)ch=fgetc(fp);printf("%c",ch);fclose(fp);voidduquyuan

34、wen()charch;将文件中的字符赋给字符变量ch/输出字符/关闭文件/从文件yuanwen中读取原文FILE*fp;if(fp=fopen("yuanwen","rb")=NULL)/以只读的方式打开文件printf("cannotopenfilen");exit(0);while(!feof(fp)ch=fgetc(fp);printf("%c",ch);fclose(fp);voidduqubianma()charch;FILE*fp;将文件中的字符赋给字符变量ch/输出字符/关闭文件从文件yiwen中读

35、取原文if(fp=fopen("yiwen","rb")=NULL)printf("cannotopenfilen");exit(0);while(!feof(fp)ch=fgetc(fp);将文件中的字符赋给字符变量chprintf("%c",ch);/输出字符fclose(fp);/关闭文件voidmain()inta,c,tep=1;hnhumtree;Hcodehc;jilunodeji;jilunode*jilu;jilu=&ji;jilu->tag=0;while(tep)/定义用三叉链表

36、方式实现的哈夫曼树/定义存放哈夫曼字符编码串的头指针的数组/定义存放字符种类数量的栈/取指针/字符种类数标志初始化printf(”(*a_a*)哈夫曼编码系统欢迎您(杯_心)n")；printf("*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*n");printf("printf("printf("printf("printf("printf("printf("printf("1-创建存贮原文件的文件n”)；2

37、输入原文n");3- -对原文编码n");4- -对编码译码n");5- -输出原文n");6- -输出译码n");7- -输出译文n");8- -退出n");printf(”注意：如果您未创建原文件原文操作，请不要进行后续项操作！n");printf("*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*n");printf("请输入服务选项(1-8):");scanf("%d",

38、&a);getchar();switch(a)case1:jianliwenjian();/建立存储字符的文件printf("是否继续？(1.YES2，NO)：");scanf("%d",&c);if(c=1)tep=1;elsetep=0;system("cls");break;case2:system("cls");luruyuanwen();/将原文录入到文件中printf("n注意：原文件将保存在名称为yuanwen的文件中！n");printf("是否继续？(1.YES2，NO)：");scanf("%d",&c);if(c=1)tep=1;elsetep=0;case3:system("cls");break;chuangjian(jilu,humtree);/创建哈夫曼树printf（"n各字符编码结果为：n"）;bianma（jilu,humtree,hc,jilu->tag）;/对哈夫曼树的叶子结点编码printf（"