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

1、课 程 设 计 说 明 书课 程 设 计 任 务 书设计题目：_哈夫曼编/译码器_设计内容与要求：设计内容：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，设计一个哈夫曼编/译码系统。要求： 以每个字符出现的次数为权值，建立哈夫曼树，求出哈夫曼编码，对文件yuanwen中的正文进行编码，将结果存到文件yiwen中，再对文件yiwen中的代码进行译码，结果存到textfile中。课 程 设 计 评 语成绩： 指导教师： 年 月 日洛 阳 理 工 学 院 课 程 设 计 报 告【问题描述】打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，设计一个哈夫曼编/

2、译码系统。利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。 【基本要求】以每个字符出现的次数为权值，建立哈夫曼树，求出哈夫曼编码，对文件yuanwen中的正文进行编码，将结果存到文件yiwen中，再对文件yiwen中的代码进行译码，结果存到textfile中。一个完整的系统应具有以下功能：(1) I：初始化（Initialization）。从终端读入

3、字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。(2) E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。(3) D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。【测试数据】用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下英文的编码和译码：“I like playing football”。字符ABCDEFGHIJKLM频度1866413223210

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

5、文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。 （1） 其主要流程图如图1-1所示。开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I2*N?I+编码为1结束否否否右子是否为空是是否否是是是（2）设计包含的几个方面： 赫夫曼树的建立哈夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n1

6、次合并，所以共产生n1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有2n1个结点，其中n个结点是初始森林的n个孤立结点。并且赫夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n-1的一维数组来存储赫夫曼树中的结点。 哈夫曼编码 要求电文的哈夫曼编码，必须先定义哈夫曼编码类型，根据设计要求和实际需要定义的类型如下： typedet struct char ch; / 存放编码的字符 char bitsN1; / 存放编码位串 int len; / 编码的长度 CodeNode; / 编码结构体类型 代码文件的译码 译码的基本思想是：读文件中编码，并与原先生

7、成的哈夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。【模块划分】1) 问题分析哈夫曼树的定义1.哈夫曼树节点的数据类型定义为：typedef struct /哈夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;2）所实现的功能函数如下1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼树，处理InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立2叉树。此函数块调用了Select（）函数。2、void S

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

9、ne N 50 / 叶子结点数 #define M 2*N-1 / 哈夫曼树中结点总数 typedef struct int weight; / 叶子结点的权值 int lchild, rchild, parent; / 左右孩子及双亲指针 HTNode; / 树中结点类型 typedef HTNode HuffmanTreeM+1; 哈夫曼树的算法void CreateHT(HTNode ht,int n) /调用输入的数组ht,和节点数n int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchil

10、d=hti.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-3276832767 lnode=rnode=-1; /lnode和rnode记录最小权值的两个结点位置 for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未构造二叉树的结点中查找 if (htk.weightmin1) /若权值小于最小的左节点的权值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin

11、2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和 hti.lchild=lnode;hti.rchild=rnode; /父节点的左节点和右节点（2）哈夫曼编码void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;in;i+) /根据哈夫曼树求哈夫曼编码 hc.sta

12、rt=n;c=i; f=hti.parent; while (f!=-1) /循序直到树根结点结束循环 if (htf.lchild=c) /处理左孩子结点 hc.cdhc.start-=0; else /处理右孩子结点 hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼编码hc.cd中最开始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /输出哈夫曼编码的列表 int i,k; printf( 输出哈夫曼编码:n); for (i=0;in;i+) /输出data中的

13、所有数据，即A-Z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /输出所有data中数据的编码 printf(%c,hcdi.cdk); printf(n); void editHCode(HTNode ht,HCode hcd,int n) /编码函数char stringMAXSIZE; int i,j,k;scanf(%s,string); /把要进行编码的字符串存入string数组中printf(n输出编码结果:n);for (i=0;stringi!=#;i+) /#为终止标志for (j=0;jn;j+)if(stringi=

14、htj.data) /循环查找与输入字符相同的编号，相同的就输出这个字符的编码for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /输出完成后跳出当前for循环（3）哈夫曼译码void deHCode(HTNode ht,HCode hcd,int n) /译码函数char codeMAXSIZE;int i,j,l,k,m,x;scanf(%s,code); /把要进行译码的字符串存入code数组中while(code0!=#)for (i=0;in;i+)m=0; /m为想同编码个数的计数器 for (k=hcdi.start,j=0;

15、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进入，创建名称为yuanwen的文件，如图：(3)输入英语原文为 I like playing football ,如图所示：（4）程序对原文进行编码运行输出结果，程序如图

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

17、对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识【源程序】#include#include#include#define N 5000#define m 128 /叶子结点个数，即字符总类数#define M 2*m-1 /哈夫曼树的节点数 char CHN; /记录原文字符数组char YWN; /记录译文字符数组typedef char * Hcodem+1; /存放哈夫曼字符编码串的头指针的数组typedef struct char a; int num;dangenode; /记录单个字符的类别和出现的次数typedef struct d

18、angenode b129; int tag;jilunode; /统计原文出现的字符种类数typedef struct node int weight; /结点权值 int parent; /双亲下标 int Lchild; /左孩子结点的下标 int Rchild; /右孩子的下标htnode,hnM;/静态三叉的哈夫曼树的定义void jianliwenjian()FILE *fp;printf(现在建立文件，以存储原文（文件名称默认为yuanwen）n);printf( 文件建立中.n);if(fp=fopen(yuanwen,wb)=NULL) /建立文件printf(Cannot

19、open filen);exit(0);printf(文件已建立,名称为：yuanwen); fclose(fp); /关闭文件void luruyuanwen() /原文输入完后，将其保存到文件yuanwen中char ch;FILE *fp;if(fp=fopen(yuanwen,wb)=NULL) /打开文件printf(Cannot open filen);exit(0); printf(请输入原文（结束标志为：）n); do ch=getchar(); fputc(ch,fp); /将字符保存到文件中 while(ch!=); /判断结束 getchar(); /接收回车命令符 fc

20、lose(fp); /关闭文件 void min_2(hn ht,int n,int *tag1,int *tag2)/在建哈夫曼树的过程中，选择权值小的两 /个结点int i,min,s; min=N; for(i=1;i=n;i+) if(hti.weightmin&hti.parent=0) min=hti.weight; *tag1=i; /记录权值最小的结点下标 min=N;for(i=1;i=n;i+) if(hti.weightmin&hti.parent=0&i!=*tag1) min=hti.weight; *tag2=i; if(ht*tag1.weight=ht*tag2

21、.weight&ht*tag2.Lchild!=0)s=(*tag1); /如果结点权值相同，先出现的放在哈夫曼树的左边(*tag1)=(*tag2);(*tag2)=s; void chuangjian(jilunode * jilu,hn ht) /建立哈夫曼树、以及对原 FILE *fp;/文字符的类别和数量统计 int i=-1,j,s=0,tag1,tag2; / s=0; / i=-1; /char ch;if(fp=fopen(yuanwen,rb)=NULL) /以只读的方式打开文件printf(Cannot open filen);exit(0); while(!feof(f

22、p) /判断文件指示标志是否移动到了文件尾处 char ch;ch=fgetc(fp);if(ch!=) /判断字符是否是结束标志 +i; CHi=ch; for(j=1;jtag;j+) if(CHi=jilu-bj.a) jilu-bj.num+; break; if(j-1=jilu-tag&CHi!=jilu-bj-1.a) jilu-tag+; jilu-bjilu-tag.a=CHi; jilu-bjilu-tag.num=1; jilu-tag-;fclose(fp); /关闭文件 printf(原文中的各字符统计状况如下：n); printf(*n); for(i=1;itag

23、;i+) s+; printf(%c的个数为:%d ,jilu-bi.a,jilu-bi.num); if(s%4=0) /每行放四个数据 printf(n); printf(n); for(i=1;itag)-1;i+) if(itag) hti.weight=jilu-bi.num; /初始化叶子结点权值hti.Lchild=0; /初始化叶子结点左孩子hti.parent=0; /初始化叶子结点父母hti.Rchild=0; /初始化叶子结点右孩子 else hti.Lchild=0; /初始化非叶子结点左孩子hti.parent=0; /初始化非叶子结点父母hti.Rchild=0;

24、/初始化非叶子结点右孩子hti.weight=0; /初始化非叶子结点权值 for(i=jilu-tag+1;itag)-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; void bianma(jilunode * jilu,hn ht,Hcode hc,int n) /哈夫曼树建完后，对叶 /子结点逐个编码char * cd;int

25、start,i,p,c;cd=(char *)malloc(n+1)*sizeof(char); /申请存储字符的临时空间cdn-1=0; /加结束标志for(i=1;ibi.a,&cdstart);hci=(char *)malloc(n-start)*sizeof(char); /为字符数组分配空间strcpy(hci,&cdstart);/将临时空间中的编码复制到字符数组中free(cd); /释放临时空间void bianmabaocun(Hcode hc,jilunode * jilu) /将原文以编码的形式保存到 /文件yiwen中int i,j;FILE *fp;if(fp=fo

26、pen(yiwen,wb)=NULL) /以写的方式打开文件printf(Cannot open filen);exit(0); /文件打开失败退出for(i=0;i=N&CHi!=;i+) for(j=1;jtag;j+)if(CHi=jilu-bj.a)fputs(hcj,fp); /将文件中的字符输出到字符数组中 printf(%s,hcj);fclose(fp); /关闭文件void yiwen(Hcode hc,jilunode * jilu) /读取yiwen中的编码，并将其翻译 /为原文存放到字符数组YWN中int tag1,tag2,i,j,s=0;FILE *fp; /文件指

27、针char *c;if(fp=fopen(yiwen,rb)=NULL) /以只读的方式打开文件printf(cannot open filen);exit(0);while(!feof(fp)tag1=1; /结束for循环的辅助标志tag2=1; /结束for循环的辅助标志c=(char *)malloc(200*sizeof(char);for(i=0;i200&tag1;i+)ci=fgetc(fp); /将文件中的字符输出到数组中ci+1=0; /加结束标志 for(j=1;(jtag)&tag2;j+)if(strcmp(hcj,c)=0) /将编码与原文字符匹配YWs=jilu-

28、bj.a; /匹配成功后将字符保存到数组YW中tag1=0;s+;free(c); /释放临时字符存储空间 tag2=0;YWs=0;void baocunyiwen() /将翻译的译文保存到文件textfile中int i;FILE *fp;if(fp=fopen(textfile,wb)=NULL)printf(Cannot open filen);exit(0);for(i=0;YWi!=0;i+)fputc(YWi,fp); /将数组中的字符保存到文件中putchar(YWi);fclose(fp); /关闭文件void duquyiwen() /从文件textfile中读取译文cha

29、r ch; FILE *fp;if(fp=fopen(textfile,rb)=NULL) /以只读的方式打开文件printf(cannot open filen);exit(0);while(!feof(fp)ch=fgetc(fp); /将文件中的字符赋给字符变量chprintf(%c,ch); /输出字符 fclose(fp); /关闭文件void duquyuanwen() /从文件yuanwen中读取原文char ch; FILE *fp;if(fp=fopen(yuanwen,rb)=NULL) /以只读的方式打开文件printf(cannot open filen);exit(0

30、);while(!feof(fp)ch=fgetc(fp); /将文件中的字符赋给字符变量chprintf(%c,ch); /输出字符 fclose(fp); /关闭文件void duqubianma() /从文件yiwen中读取原文char ch; FILE *fp;if(fp=fopen(yiwen,rb)=NULL)printf(cannot open filen);exit(0);while(!feof(fp)ch=fgetc(fp); /将文件中的字符赋给字符变量chprintf(%c,ch); /输出字符 fclose(fp); /关闭文件void main() int a,c,t

31、ep=1; hn humtree; /定义用三叉链表方式实现的哈夫曼树Hcode hc; /定义存放哈夫曼字符编码串的头指针的数组 jilunode ji; /定义存放字符种类数量的栈 jilunode *jilu; jilu=&ji; /取指针 jilu-tag=0; /字符种类数标志初始化while(tep)printf( (*_*) 哈夫曼编码系统欢迎您(*_*) n); printf(*n); printf( 1-创建存贮原文件的文件n);printf( 2-输入原文n); printf( 3-对原文编码n);printf( 4-对编码译码n); printf( 5-输出原文n);printf( 6-输出译码n); printf( 7-输出译文n);printf( 8-退出n);printf(注意：如果您未创建原文件原文操作，请不要进行后续项操作！n);printf(*n);printf(请输入服务选项（1-8）:);scanf(%d,&a);getchar();switch(a)cas