完整word版,《哈夫曼编码译码课程设计》报告

1、计算机与信息工程系实践环节名称报告专业：计算机科学与技术班级： *学号： *姓名：杨明英报告完成日期：2011/6/10指导教师： *评语：成绩：批阅教师签名：批阅时间：目录1问题描述12 基本要求13数据结构14总体设计15详细设计25.1void main()25.2void jianliwenjian()35.3void luruyuanwen()45.4void chuangjian()55.5void bianma()65.6void yiwen()75.7void baocunyiwen()85.8void duquyuanwen()95.9void duqubianma()105

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

3、 structchar a;int num;dangenode;/ 记录单个字符的类别和出现的次数typedef structdangenode bm;int tag;jilunode;/ 统计原文出现的字符种类和数量typedef struct node/ 静态三叉的哈夫曼树的定义intweight;/结点的权值intparent;/双亲的下标intLchild;/左孩子结点的下标intRchild;/ 右孩子结点的下标htnode,hnM+1;/ hn 是结构数组类型，0 号单元不用4. 总体设计功能函数模块划分void main()/主函数void jianliwenjian()/建立存

4、储原文的文件 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 bianmabaocun(Hcode hc,jilunode * jilu)/保存编码在文件 yiwen 中void yiwen(Hcode hc,jilunode *

5、 jilu)/ 读取 yiwen 中的编码，并将其翻译为原文void baocunyiwen()/将翻译的译文保存到文件textfile 中void duqubianma()/在编码文件 yiwen 中读取编码void duquyiwen()/从文件 textfile 中读取译文15. 详细设计5.1 主函数void main()开始Int tep=1;Ntep=1YNa=1YYNjianliwenjian();a=2NYa=3N luruyuanwen();Yc=1chuangjian(jilNNYu,humtree);a=4c=1tep=0;Ybianma(jilu,hYNtep=0; u

6、mtree,hc,jilua=5system(cls);yiwen(hc-tag);,jilu);YNsystem(cls);Bianmabaocduquyuanwen();a=6break;un(hc,jiolu); baocunyiwen();YNbreak;NNNduqubianma();a=7c=1c=1Yc=1Ytep=0; Ytep=0;YNduquyiwen();c=1Nsystem(cls);tep=0;a=8system(cls);YNtep=0; c=1break;system(cls);Ybreak;Ytep=0;break;system(cls);break;syste

7、m(cls);结束25.2 建立文件void jianliwenjian()首先，要建立一个文件来存储原文，在这里文件的名称按要求默认为 yuanwen，文件建立时有可能成功，有可能失败，建立失败时输出“ Cannot open file ”，成功后会提示：“文件已建立，名称为 yuanwen”。开始printf( 现在建立文件，以存储原文（文件名称默认为“ yuanwen”）n);N(fp=fopen(yuanwen,wb)=NULLYprintf(Cannot open filen);printf( 文件已建立 ,名称为： yuanwen);结束35.3 输入原文void luruyuan

8、wen()输入原文时首先要打开原文件，成功打开文件后逐个读取输入的字符存放到文件中，直到遇到结束标志 ，然后关闭文件。开始charch;(fp=fopen(yuanwen,wb)=NULLNYprintf(Cannot open filen);printf( 请输入原文（结束标志为： “ ”）n);ch=getchar();fputc(ch,fp)Ych!=Ngetchar();结束45.4 创建哈夫曼树void chuangjian()打开存储原文的文件 yuanwen，将字符逐个读出，然后统计字符的种类，类别和数量，最后建立静态的三叉链表来建立哈夫曼树，树中的叶子结点对应出现的个字符。开始

9、N打开文件 yuanwenYN文件未结束Y将文件中的字符逐个赋给数组CHi用栈 jilunode记录字符的种类、类别及数量关闭文件输出统计结果建立哈夫曼树结束55.5 编码void bianma()该函数实现对哈夫曼树的编码，先申请一个能存储字符编码的临时空间 cd，编码从哈夫曼树的叶子结点开始，寻找其父母结点，然后根据父母结点判断孩子结点的左右位置，左边置 1，右边置 0，并将 1,0 这样的字符从后往前逆序存放在 cd 中，每求得一个叶子结点的编码，就将其复制到存储哈夫曼编码的头指正数组中，找完叶子结点的编码后就释放临时空间cd。开始申请存放编码的字符空间cdN叶子结点的父母不为0Y对哈夫

10、曼树的叶子结点编码将叶子结点的编码存放在cd中将 cd中存放的编码复制到存储哈夫曼编码的头指针数组中释放 cd的空间结束65.6 对哈夫曼码译码void yiwen()打开文件 yiwen，打开成功后，逐个读取存放在里边的编码字符，并与先前的编码相匹配，直到找到编码对应的原字符，当找完编码后就关闭文件。开始N打开文件 yiwenYN文件未结束Y读取文件 yiwen 中的字符逐个读取字符后，将其与先前的编码相匹配N匹配成功Y将匹配的结果（即译文）保存到数组Yw中关闭文件结束75.7 保存译文void baocunyiwen()打开文件 textfile ，打开成功后，将译文保存到文件中，然后关闭

11、文件。开始N打开文件 textfileY将译文保存到textfile文件中关闭文件结束85.8 输出原文void duquyuanwen()打开文件 yuanwen，将里边的原文输出，以便查看。开始N打开文件 yuanwenY输出文件中的原文关闭文件结束95.9 输出原文编码void duqubianma()打开文件 yiwen ，打开成功后，将文件中存放的编码输出，然后关闭文件。开始N打开文件 yiwenY输出文件中的编码关闭文件结束105.10 输出译文void duquyiwen()打开文件 textfile ，打开成功后，输出里边的译文，然后关闭文件。开始N打开文件 textfileY

12、输出文件中的译文关闭文件结束116. 测试与调试程序调试采用 Microsoft Visual Studio2008，程序在调试过程中遇到了各种问题，首先在建立哈夫曼树时我是用静态三叉链表实现的，但里边的参数 parent， Lchild ，Rchild 定义为指针类型，在原理上是可行，但调试时总得不到正确结果，后来改为书中用基本类型整型后就很好的得到了满意结果，其它一些小错误在不断地调试，不断地改善后，基本达到可满意的效果。各模块的调试结果截屏如下：6.1 主函数菜单6.2 建立文件6.3 通过程序输入原文126.4 直接将原文存放到文件yuawen 中6.5 对原文编码1314156.6

13、对编码译码6.7 输出原文166.8 输出编码6.9 输出译文177. 源程序清单#include#include#include#define N 5000#define m 128/叶子结点个数，即字符总类数#define M 2*m-1 /哈夫曼树的节点数char CHN;/记录原文字符数组char YWN;/记录译文字符数组typedef char * Hcodem+1; / 存放哈夫曼字符编码串的头指针的数组 typedef structchar a;int num;dangenode; / 记录单个字符的类别和出现的次数 typedef structdangenode b129;i

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

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

16、t,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.weight&ht*tag2.Lchild!=0)s=(*tag1);/如果结点权值相

17、同，先出现的放在哈夫曼树的左边(*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)/以只读的方式打开文件19printf(Cannot open filen);exit(0);while(!feof(fp)/判断文件指示标志是否移动到了文件尾处ch=fgetc(fp);if(ch!=)/判断字符是否是结束标志+i;CHi=ch

18、;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+)s+;printf(%c的个数为 :%d,jilu-bi.a,jilu-bi.num);if(s%4=0)/每行放四个数据printf(n);printf(n);

19、for(i=1;itag)-1;i+)if(itag)hti.weight=jilu-bi.num; /初始化叶子结点权值hti.Lchild=0;/初始化叶子结点左孩子20hti.parent=0;/初始化叶子结点父母hti.Rchild=0;/初始化叶子结点右孩子elsehti.Lchild=0;/初始化非叶子结点左孩子hti.parent=0;/初始化非叶子结点父母hti.Rchild=0;/初始化非叶子结点右孩子hti.weight=0;/初始化非叶子结点权值for(i=jilu-tag+1;itag)-1;i+)min_2(ht,i-1,&tag1,&tag2);需找权值小的两个父母

20、为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,i,p,c;cd=(char *)malloc(n+1)*sizeof(char);/申请存储字符的临时空间cdn-1=0;/加结束标志for(i=1;ibi.a,&cdstart);hci=(char *)m

21、alloc(n-start)*sizeof(char); /为字符数组分配空间strcpy(hci,&cdstart);/将临时空间中的编码复制到字符数组中21free(cd);/释放临时空间void bianmabaocun(Hcode hc,jilunode * jilu)/将原文以编码的形式保存到文件 yiwen 中int i,j;FILE *fp;if(fp=fopen(yiwen,wb)=NULL)/以写的方式打开文件printf(Cannot open filen);exit(0);/文件打开失败退出for(i=0;i=N&CHi!=;i+)for(j=1;jtag;j+)if(C

22、Hi=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 *c;if(fp=fopen(yiwen,rb)=NULL)/以只读的方式打开文件printf(cannot open filen);exit(0);while(!feof(fp)tag1=1;/结束 for 循环的辅助标志ta

23、g2=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;/匹配成功后将字符保存到数组YW中22tag1=0;s+;free(c);/释放临时字符存储空间tag2=0;YWs=0;void baocunyiwen()/将翻译的译文保存到文件textfile中int i;FILE *fp;if(

24、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;FILE *fp;if(fp=fopen(textfile,rb)=NULL)/以只读的方式打开文件printf(cannot open filen);exit(0);while(!feof(fp)ch=fgetc(fp);/将文件中的字符赋给

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

26、(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;hn humtree;/定义用三叉链表方式实现的哈夫曼树Hcode hc;/定义存放哈夫曼字符编码串的头指针的数组jilunode ji;/定义存放字符种类数量的栈jilunode *jilu;jilu=&ji;/取指针jilu-tag=0;/字符种类数标志初始化while

27、(tep)printf( (*_*) 哈夫曼编码系统欢迎您 (*_*) n); printf(*n);printf(1创建存贮原文件的文件n);printf(2输入原文 n);printf(3对原文编码 n);printf(4对编码译码 n);24printf(5输出原文 n);printf(6输出译码 n);printf(7输出译文 n);printf(8退出 n);printf(注意：如果您未创建原文件原文操作，请不要进行后续项操作！n);printf(*n);printf(请输入服务选项（ -8 ）:);scanf(%d,&a);getchar();switch(a)case 1:jia

28、nliwenjian();/建立存储字符的文件printf(是否继续？（ .YES 2 ，NO ）： );scanf(%d,&c);getchar();if(c=1)tep=1;elsetep=0;system(cls);break;case 2:system(cls);luruyuanwen();/将原文录入到文件中printf(n 注意：原文件将保存在名称为“ yuanwen”的文件中！ n); printf( 是否继续？（ .YES 2 ， NO ）： );scanf(%d,&c);getchar();if(c=1)tep=1;elsetep=0;system(cls);break;ca

29、se 3:chuangjian(jilu,humtree);/创建哈夫曼树printf(n各字符编码结果为： n);bianma(jilu,humtree,hc,jilu-tag);/对哈夫曼树的叶子结点编码printf(原文的编码为： n);printf(* *n);bianmabaocun(hc,jilu);/保存编码printf(n*n);printf(n注意：原文的编码将保存在以名称为“yiwen ”的文件中！ n);25printf(是否继续？（ .YES 2 ，NO ）： );scanf(%d,&c);getchar();if(c=1)tep=1;elsetep=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;elsetep=0;system(cls);break;case 5:system(cls);printf(原文为： n);duquyuanwen();/