哈夫曼编码译码器实验报告.doc

中北大学数 据 结 构课 程 设 计 说 明 书   学生姓名: 学 号：10210109 学 院:软件学院专 业:软件开发与测试 题 目:哈夫曼编码/译码器指导教师康珺    2011年12月20日目 录1 问题描述12 需求分析13 概要设计131抽象数据类型定义132总体框图以及功能描述24 详细设计241数据类型的定义242主要模块的算法描述35 测试分析46 课程设计总结6附录（源程序清单）71 问题描述1. 设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。(1) 将权值数据存放在数据文件(文件名为data.txt，位于当前目录中)；(2) 分别采用动态和静态存储结构; 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树;(3) 编码：利用建好的哈夫曼树生成哈夫曼编码；输出编码；设计要求：(1) 符合课题要求，实现相应功能；(2) 要求界面友好美观，操作方便易行；(3) 注意程序的实用性、安全性。2 需求分析 编写此软件是为了实现一个利用哈夫曼算法的编码和译码系统。比如，再利用电报进行通讯时，需要将文字转换成由二进制的字符组成的字符串。比如需传送的电文为“A B A C C D A”假设将A,B,C,D分别编码为00、01、10、11.则上述电文遍为00010010101100，总长度为14位。但是在传送过程中，总希望长度能够尽可能的短，于是我们想采用长度不等的编码。但是这种编码必须遵循：任何一个字符的编码都不是另一个字符编码的前缀。对此软件的要求：能够正确的使得对于输入的字符进行编码以及译码，并且是的在译码过程中不会出错，同时能够将编码以及译码的结果正确的存入文件当中。3 概要设计31抽象数据类型定义ADT BinaryTree数据对象：D=ai|aiElemSet,i=1,2,.,n, n0数据关系：若D为空集，则称为空树。若D仅为一个数据元素，则R为空集，否则R=H，H是如下的二元关系： （1）再D中存在唯一的称为根的数据元素root，它在关系H下无前驱。 （2）若D-root<>空集，则存在一个划分D1，D2，···，Dm（m>0）。 （3）对应于D-root的划分，H-<root，X1，···，<root，Xm> 有唯一的一个划分H1，H2，···，Hm（m>0）。基本操作：InitTree(&T)操作结果：构造空树T。DestroyTree(&T)初始条件：树T已存在。操作结果：树T被销毁。ClearTree(&T)初始条件：树T已存在。操作结果：将树T清为空栈。TreeEmpty(T)初始条件：树T已存在。操作结果：若树T为空，则返回TRUE，否则FALSE。TreeDepth(T)初始条件:树T已存在。操作结果：返回T的深度。Root（T）初始条件：树T已存在。操作结果：返回树T的根。32总体框图以及功能描述4 详细设计41数据类型的定义（1）哈夫曼树节点类型 struct hufmtreenode /哈弗曼树结点数据类型 char data; float weight; /结点权值 int parent,lchild,rchild; /父结点，左、右孩子结点 ;（2）哈夫曼树类型 struct hufmtree /哈弗曼树数据类型 hufmtreenode *node; /结点数组（根据n的值动态分配） int n; /叶子结点数;（3)哈夫曼编码数据类型 struct Codetype /哈弗曼编码数据类型 char *bits; /编码流数组， int start;/编码实际在编码流数组里的开始位置42主要模块的算法描述（1) 主函数： void main() printf("哈夫曼编码译码系统n"); tree=CreateHuffmanTreeFromSourceFile();/读取文件建立哈树tree=CreateHuffmanTreeByInput(); /手动输入建立哈夫曼树HuffmanCode(tree); /打印字符集的哈夫曼编码tree=Encoding(tree); /对文本文件编码Decoding(tree); /对代码文件译码 （2）构造哈夫曼树 hufmtree* BuildHuffmanTree(hufmtree *tree)/构建叶子结点已初始化的哈夫曼树For(p=HT,i=1;i<=n;+i,+p,+w) *p=0,0,0,0; For(;i<=m;+i,+p) *p=0,0,0,0); For(i=n+1;i<=m;i+) Select(HT,i-1,s1,s2); HTs1.parent=i; HTs2.parent=i; HTs1.parent=s1; HTs1.parent=s2; HTi.weight=HTs1.weight+HTs2.weight; （3）利用哈夫曼编码算法哈夫曼编码HuffmanCode(tree) hc=(HuffmanCode)malloc(n+1*sizeof(char *) cd=(char *)malloc(n*sizeof(char); cdn-1="0" for(c=i;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' HCi=(car *)malloc(n-start)*sizeof(char); Strcpy(HCi,&cdstart); 5 测试分析 (1)打开源文件统计各字符及权值信息并存入data.txt文件中 (2)将统计出的权值信息进行哈夫曼编码（3） 将编码内容存入CodeFile.txt文件中（4） 将CodeFile.txt文件中的内容译码（5) 成功译码把原字符信息存入DeCodeFile.txt文件中（6）输入各字符及其权值（7） 将各字符的权值信息进行哈夫曼编码（7） 根据编码再进行译码工作6 课程设计总结课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.随着科学技术发展的日新日异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。回顾起此次课程设计，至今我仍感慨颇多，的确，自从拿到题目到完成整个编程，从理论到实践，在整整一个星期的日子里，可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，这毕竟独立做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体通过这次课程设计之后，一定把以前所学过的知识重新温故。这次课程设计终于顺利完成了，在设计中遇到了很多编程问题，最后在谢老师的辛勤指导下，终于游逆而解。同时，在李玉蓉老师的软件工程导论课上我学得到很多实用的知识，在次我表示感谢！同时，对给过我帮助的所有同学和各位指导老师再次表示忠心的感谢！附录（源程序清单）#include <stdio.h>#include <conio.h>#include <stdlib.h>#define MAXVAL 10000.0struct hufmtreenode/哈弗曼树结点数据类型char data;double weight;/结点权值int parent,lchild,rchild;/父结点，左、右孩子结点;struct hufmtree/哈弗曼树数据类型hufmtreenode *node;/结点数组（根据n的值动态分配）int n;/叶子结点数;struct Codetype/哈弗曼编码数据类型char *bits;/编码流数组，n为为哈夫曼树中叶子结点的数目，编码的长度不可能超过nint start;/编码实际在编码流数组里的开始位置;void SortHufmtree(hufmtree *tree)/将哈夫曼树n个叶子结点由大到小排序int i,j,k;hufmtreenode temp;if (tree=NULL)return;for (i=0;i<tree->n;i+)k=i;for(j=i+1;j<tree->n;j+)if (tree->nodej.weight>tree->nodek.weight)k=j;if (k!=i)temp=tree->nodei;tree->nodei=tree->nodek;tree->nodek=temp;Codetype* HuffmanCode(hufmtree *tree)/哈弗曼编码的生成int i,j,p,k;Codetype *code;if (tree=NULL)return NULL;code=(Codetype*)malloc(tree->n*sizeof(Codetype);for (i=0;i<tree->n;i+)printf("%c ",tree->nodei.data);/打印字符信息codei.bits=(char*)malloc(tree->n*sizeof(char);codei.start=tree->n-1;j=i;p=tree->nodei.parent;while(p!=-1)if (tree->nodep.lchild=j)codei.bitscodei.start='0'elsecodei.bitscodei.start='1'codei.start-;j=p;p=tree->nodep.parent;for (k=codei.start+1;k<tree->n;k+)/打印字符编码printf("%c",codei.bitsk);printf("n");return code;hufmtree* BuildHuffmanTree(hufmtree *tree)/构建叶子结点已初始化的哈夫曼树/tree中所有叶子结点已初始化int i,j,p1,p2,m;float small1,small2;m=2*(tree->n)-1;for (i=tree->n;i<m;i+)/初始化所有非叶子结点tree->nodei.parent=-1;tree->nodei.lchild=-1;tree->nodei.rchild=-1;tree->nodei.weight=0.0;for (i=tree->n;i<m;i+)/构建哈夫曼树small1=small2=MAXVAL;for (j=0;j<=i-1;j+)if (tree->nodej.parent=-1 && tree->nodej.weight<=small1)small1=tree->nodej.weight;p1=j;for (j=0;j<=i-1;j+)if (tree->nodej.parent=-1 && tree->nodej.weight<=small2 && (j!=p1)small2=tree->nodej.weight;p2=j;tree->nodep1.parent=tree->nodep2.parent=i;tree->nodei.weight=tree->nodep1.weight+tree->nodep2.weight;tree->nodei.lchild=p1;tree->nodei.rchild=p2;return tree;hufmtree* CreateHuffmanTreeFromSourceFile()/通过解析源文件建立哈夫曼树FILE *textfile,*datafile;char ch,sourcefilename100;int i,j=0,n=0;float count128; /用于统计字符在源文件中出现的次数，27表示26个英文字母和1个空格字符hufmtree *tree;/打开一个源文件printf("n请输入源文件所在路径:n");scanf("%s",sourcefilename);if (textfile=fopen(sourcefilename,"r")=NULL)printf("n找不到文件%sn",sourcefilename);return NULL;for(i=0;i<128;i+)counti=0;/对源文件中各字符的个数统计ch=fgetc(textfile);while(!feof(textfile)for(i=0;i<128;i+)if (ch=char(i)counti+;break;ch=fgetc(textfile);/将统计结果写入权值信息文件data.txt中，并构建哈夫曼树datafile=fopen("f:data.txt","w");for (i=0;i<128;i+)if (counti!=0)n+;fprintf(datafile,"%dn",n);tree=(hufmtree*)malloc(sizeof(hufmtree); tree->node=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree->n=n;printf("n源文件的字符集及其权值信息如下：n");for(i=0;i<128;i+)if (counti!=0)/fprintf(datafile,"%c%fn",char(i),counti); fprintf(datafile,"%c %.0fn",char(i),counti); printf("%c %.0fn",char(i),counti);tree->nodej.data=char(i);tree->nodej.weight=counti;tree->nodej.parent=-1;tree->nodej.lchild=-1;tree->nodej.rchild=-1;j+;SortHufmtree(tree);BuildHuffmanTree(tree);fclose(textfile);fclose(datafile);printf("n哈夫曼树建立完毕，已将权值信息保存至data.txtn");return tree;hufmtree* CreateHuffmanTreeByInput()/通过用户输入建立哈夫曼树int n;hufmtree *tree;int i,m;FILE *datafile;tree=(hufmtree*)malloc(sizeof(hufmtree);datafile=fopen("f:data.txt","w");/由用户输入字符与权值信息并将其写入data.txt，同时进行哈夫曼树初始化printf("请输入字符数：");scanf("%d",&n);if (n<=0)printf("n您的输入有误。n");return NULL;tree->node=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree->n=n;m=2*n-1;for (i=0;i<n;i+)tree->nodei.parent=-1;tree->nodei.lchild=-1;tree->nodei.rchild=-1;tree->nodei.weight=0.0;fprintf(datafile,"%dn",n);for (i=0;i<n;i+)printf("n输入第%d个字符及其权值：",i+1);tree->nodei.data=getche();tree->nodei.weight=getche();fprintf(datafile,"%c,%.0fn",tree->nodei.data,tree->nodei.weight-48);fclose(datafile);/哈夫曼树构建SortHufmtree(tree);BuildHuffmanTree(tree);printf("n哈夫曼树建立完毕，已将权值信息保存至data.txtn");return tree;hufmtree* CreateHuffmanTreeFromDataFile()/通过读取权值信息文件建立哈夫曼树FILE *datafile;int i,n;hufmtree *tree;if (datafile=fopen("f:data.txt","r")=NULL)printf("n哈夫曼树尚未建立n");return NULL;/哈夫曼树初始化fscanf(datafile,"%d",&n);fgetc(datafile);tree=(hufmtree*)malloc(sizeof(hufmtree);tree->node=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree->n=n;for (i=0;i<n;i+)tree->nodei.data=fgetc(datafile);fscanf(datafile,"%fn",&tree->nodei.weight);tree->nodei.parent=-1;tree->nodei.lchild=-1;tree->nodei.rchild=-1;fclose(datafile);/哈夫曼树构建SortHufmtree(tree);BuildHuffmanTree(tree);return tree;hufmtree* Encoding(hufmtree *tree)/对源文件进行编码并将其输出至新文件FILE *textfile,*codefile;char ch,sourcefilename50;int i,j;Codetype *code;if (tree=NULL)/如果内存中尚未建立哈夫曼树/试从data.txt中读取权值信息并建立哈夫曼树tree=CreateHuffmanTreeFromDataFile();if (tree=NULL)return NULL;/读取源文件printf("n请输入源文件所在路径:n");scanf("%s",sourcefilename);if (textfile=fopen(sourcefilename,"r")=NULL)printf("n找不到文件%sn",sourcefilename);return NULL;/打印源文件内容printf("n源文件的原文如下：n");ch=fgetc(textfile);while(!feof(textfile)printf("%c",ch);ch=fgetc(textfile);/编码printf("n字符集的哈夫曼编码如下：n");code=HuffmanCode(tree);/将源文件中各字符编码并写入codefilecodefile=fopen("f:CodeFile.txt","w");fseek(textfile,0,SEEK_SET);ch=fgetc(textfile);while (!feof(textfile)for(i=0;i<tree->n;i+)if (ch=tree->nodei.data)for(j=codei.start+1;j<tree->n;j+)fputc(codei.bitsj,codefile);break;if (i=tree->n)/在哈夫曼树树中找不到与文本内容里对应的字符printf("n字符%c不在哈夫曼树中，不能正确编码。n",ch);fclose(codefile);return NULL;ch=fgetc(textfile);fclose(codefile);/提示成功信息并打印代码printf("n编码成功,已将代码写入CodeFile.txt,代码如下：n");codefile=fopen("f:CodeFile.txt","r");ch=fgetc(codefile);while(!feof(codefile)printf("%c",ch);ch=fgetc(codefile);printf("n");fclose(textfile);fclose(codefile);return tree;void Decoding(hufmtree *tree)/对编码文件进行译码并将其输出至新文件FILE *codefile,*decodefile;char ch,codefilename100;int i;if (tree=NULL)/如果尚未建立哈夫曼树/试从data.txt中读取权值信息并建立哈夫曼树tree=CreateHuffmanTreeFromDataFile();if (tree=NULL)return ;/打开编码文件printf("n请输入代码文件所在路径:n");scanf("%s",codefilename);if (codefile=fopen(codefilename,"r")=NULL)printf("n找不到文件%sn",codefilename);return;/打印编码文件的正文printf("n代码文件原文如下：n");ch=fgetc(codefile);while(!feof(codefile)printf("%c",ch);ch=fgetc(codefile);/进行译码并将译文写入DecodeFiledecodefile=fopen("f:DecodeFile.txt","w");fseek(codefile,0,SEEK_SET);ch=fgetc(codefile); while(!feof(codefile)for(i=2*tree->n-2;tree->nodei.lchild>=0 && tree->nodei.rchild>=0 && ch!=EOF;)if(ch='0')i = tree->nodei.lchild;else if(ch='1')i = tree->nodei.rchild;else/printf("n存在异常字符%c，不能正确译码。n",ch);return ;if (i=-1)/在哈夫曼树中找不到对应叶子结点printf("n编码与当前哈夫曼树结构不相符，不能正确译码。n",ch);fclose(decodefile);return;ch=fgetc(codefile);if (tree->nodei.lchild>=0 && tree->nodei.rchild>=0)/寻找叶子结点的过程中突然读到了文件尾printf("n代码文件编码内容不完整，不能完整译码。n",ch);fclose(decodefile);return;fputc(tree->nodei.data,decodefile);fclose(decodefile);/提示成功信息并打印译文printf("nn译码成功，译文已保存至DecodeFile.txtn");printf("译文如下：n");decodefile=fopen("f:DecodeFile.txt","r");ch=fgetc(decodefile);while(!feof(decodefile)printf("%c",ch);ch=fgetc(decodefile);printf("n");fclose(codefile);fclose(decodefile);void main()hufmtree *tree=NULL;char choice;do system("cls"); printf("-n");printf(" 欢迎进入n");printf("哈夫曼编码译码系统n");printf("-*-*-*-*-*-*-*-*-*n");printf("(1)-读取解析源文件建立哈夫曼树n");printf("(2)-手动输入建立哈夫曼树n");printf("(3)-打印字符集的哈夫曼编码n");printf("(4)-对文本文件编码n");printf("(5)-对代码文件译码n");printf("(0)-退出系统n");printf("-*-*-*-*-*-*-*-*-*n");printf("请输入您的选择0-5:");choice=getche();printf("n");switch (choice)case '1':tree=CreateHuffmanTreeFromSourceFile();break;case '2':tree=CreateHuffmanTreeByInput();break;case '3':if (tree=NULL)tree=CreateHuffmanTreeFromDataFile();HuffmanCode(tree);break;case '4':tree=Encoding(tree);break;case '5':Decoding(tree);break;case '0':exit(0);break;default:printf("无效的选项。n");printf("n");system("pause");while (choice!='0');