《哈夫曼编码译码课程设计》报告

1、 计算机与信息工程系实践环节名称报告专业：计算机科学与技术 班级：* 学号：* 姓名：杨明英 报告完成日期 ：2011/6/10 指导教师：* 评语：成绩：批阅教师签名： 批阅时间：目录1问题描述1 2基本要求13数据结构14总体设计15详细设计25.1主函数 void main() 2 5.2建立文件 void jianliwenjian()3 5.3输入原文 void luruyuanwen()4 5.4创建哈夫曼树 void chuangjian()5 5.5编码 void bianma()6 5.6对哈夫曼码译码 void yiwen()7 5.7保存译文 void baocunyiw

2、en()8 5.8输出原文 void duquyuanwen() 9 5.9输出原文编码 void duqubianma()10 5.10输出译文 void duquyiwen()116测试与调试117源程序清单8 8实验心得281. 问题描述打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，设计一个哈夫曼编/译码系统。2. 基本要求以每个字符出现的次数为权值，建立哈夫曼树，求出哈夫曼编码，对文件yuanwen中的正文进行编码，将结果存到文件yiwen中，再对文件yiwen中的代码进行译码，结果存到textfile中。3. 数据结构char chn; /记录原文字符数组ch

3、ar ywn; /记录译文字符数组typedef char * hcodem+1; /存放哈夫曼字符编码串的头指针的数组typedef struct char a; int num;dangenode; /记录单个字符的类别和出现的次数typedef structdangenode bm; int tag;jilunode; /统计原文出现的字符种类和数量typedef struct node /静态三叉的哈夫曼树的定义 int weight; /结点的权值 int parent; /双亲的下标 int lchild; /左孩子结点的下标 int rchild; /右孩子结点的下标htnode

4、,hnm+1; / hn是结构数组类型，0号单元不用4. 总体设计功能函数模块划分void main() /主函数void jianliwenjian() /建立存储原文的文件yuanwenvoid luruyuanwen() /通过程序录入原文到文件yuanwen中void min_2(hn ht,int n,int *tag1,int *tag2) /选择权值较小的两个结点void chuangjian(jilunode * jilu,hn ht) /建立哈夫曼树void bianma(jilunode * jilu,hn ht,hcode hc,int n) /对原文进行编码void b

5、ianmabaocun(hcode hc,jilunode * jilu) /保存编码在文件yiwen中void yiwen(hcode hc,jilunode * jilu) /读取yiwen中的编码，并将其翻译为原文void baocunyiwen() /将翻译的译文保存到文件textfile中void duqubianma() /在编码文件yiwen中读取编码void duquyiwen() /从文件textfile中读取译文5. 详细设计5.1 主函数 void main()开始int tep=1;ntep=1ya=1nyna=2yjianliwenjian();nya=3luruyu

6、anwen();nyc=1chuangjian(jilu,humtree);na=4nc=1yytep=0;nbianma(jilu,humtree,hc,jilu-tag);hc,jilu);yyiwen(hc,jilu);tep=0;a=5system(cls);yna=6duquyuanwen();bianmabaocun(hc,jiolu);system(cls);break;ybaocunyiwen();na=7break;nnc=1c=1nc=1duqubianma();ynyyduquyiwen();c=1tep=0;tep=0;nya=8tep=0;system(cls);ny

7、c=1tep=0;system(cls);yybreak;system(cls);tep=0;system(cls);break;if yesbreak;system(cls);break;结束5.2建立文件 void jianliwenjian()首先，要建立一个文件来存储原文，在这里文件的名称按要求默认为yuanwen，文件建立时有可能成功，有可能失败，建立失败时输出“cannot open file”，成功后会提示：“文件已建立，名称为yuanwen”。ny 5.3输入原文 void luruyuanwen() 输入原文时首先要打开原文件，成功打开文件后逐个读取输入的字符存放到文件中，直

8、到遇到结束标志，然后关闭文件。ynny 5.4创建哈夫曼树 void chuangjian() 打开存储原文的文件yuanwen，将字符逐个读出，然后统计字符的种类，类别和数量，最后建立静态的三叉链表来建立哈夫曼树，树中的叶子结点对应出现的个字符。ynyn 5.5编码 void bianma() 该函数实现对哈夫曼树的编码，先申请一个能存储字符编码的临时空间cd，编码从哈夫曼树的叶子结点开始，寻找其父母结点，然后根据父母结点判断孩子结点的左右位置，左边置1，右边置0，并将1,0这样的字符从后往前逆序存放在cd中，每求得一个叶子结点的编码，就将其复制到存储哈夫曼编码的头指正数组中，找完叶子结点的

9、编码后就释放临时空间cd。 ny 5.6对哈夫曼码译码 void yiwen() 打开文件yiwen，打开成功后，逐个读取存放在里边的编码字符，并与先前的编码相匹配，直到找到编码对应的原字符，当找完编码后就关闭文件。nyynyn 5.7保存译文 void baocunyiwen() 打开文件textfile，打开成功后，将译文保存到文件中，然后关闭文件。 yn 5.8输出原文 void duquyuanwen() 打开文件yuanwen，将里边的原文输出，以便查看。yn 5.9输出原文编码 void duqubianma() 打开文件yiwen，打开成功后，将文件中存放的编码输出，然后关闭文件

10、。 yn 5.10输出译文 void duquyiwen() 打开文件textfile，打开成功后，输出里边的译文，然后关闭文件。 ny 6. 测试与调试程序调试采用microsoft visual studio2008，程序在调试过程中遇到了各种问题，首先在建立哈夫曼树时我是用静态三叉链表实现的，但里边的参数parent，lchild，rchild定义为指针类型，在原理上是可行，但调试时总得不到正确结果，后来改为书中用基本类型整型后就很好的得到了满意结果，其它一些小错误在不断地调试，不断地改善后，基本达到可满意的效果。各模块的调试结果截屏如下：6.1主函数菜单 6.2建立文件6.3通过程序输

11、入原文6.4直接将原文存放到文件yuawen中6.5对原文编码6.6对编码译码6.7输出原文6.8输出编码6.9输出译文7.源程序清单#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; /记录单个字符的类别和出现的次数ty

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

13、文件printf(cannot 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!=); /判断结束 getc

14、har(); /接收回车命令符 fclose(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*ta

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

16、!feof(fp) /判断文件指示标志是否移动到了文件尾处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;i

17、+) 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; /初

18、始化非叶子结点右孩子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 start

19、,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=fopen(yi

20、wen,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; /文件指针char *

21、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-bj.a; /

22、匹配成功后将字符保存到数组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中读取译文char ch; f

23、ile *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);while

24、(!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,tep=1; h

25、n 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

26、); printf( 7输出译文n);printf( 8退出n);printf(注意：如果您未创建原文件原文操作，请不要进行后续项操作！n);printf(*n);printf(请输入服务选项（-8）:);scanf(%d,&a);getchar();switch(a)case 1: jianliwenjian(); /建立存储字符的文件 printf(是否继续？（.yes 2，no ）：);scanf(%d,&c);getchar();if(c=1)tep=1;else tep=0; system(cls); break;case 2: system(cls); luruyuanwen();

27、 /将原文录入到文件中printf(n注意：原文件将保存在名称为“yuanwen”的文件中！n);printf(是否继续？（.yes 2，no ）：);scanf(%d,&c);getchar();if(c=1)tep=1;else tep=0; system(cls);break;case 3: chuangjian(jilu,humtree); /创建哈夫曼树printf(n各字符编码结果为：n); bianma(jilu,humtree,hc,jilu-tag); /对哈夫曼树的叶子结点编码printf(原文的编码为：n); printf(*n); bianmabaocun(hc,jil

28、u); /保存编码printf(n*n);printf(n注意：原文的编码将保存在以名称为“yiwen”的文件中！n); printf(是否继续？（.yes 2，no ）：);scanf(%d,&c);getchar();if(c=1)tep=1;else tep=0; system(cls);break;case 4: system(cls);printf(编码对应的译文为：n); yiwen(hc,jilu); /对编码译码 baocunyiwen(); /保存译文printf(n注意：译文将保存在以名称为“textfile”的文件中！n);printf(是否继续？（.yes 2，no ）：);scanf(%d,&c);getchar();if(c=1)tep=1;else tep=0; system(cls);break;case 5: system(cls); printf(原文为：n); duquyuanwen(); /从文件中读取原文 printf(n是否继续？（.yes 2，no ）：); scanf(%d,&c);g