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

中北大学数 据 结 构课 程 设 计 说 明 书学生姓名:学 号：10210109学 院:软件学院专 业:软件开发与测试题 目:哈夫曼编码/译码器指导教师康珺2011年12月20日目 录1 问题描述12 需求分析13 概要设计131抽象数据类型定义132总体框图以及功能描述24 详细设计241数据类型的定义242主要模块的算法描述35 测试分析46 课程设计总结6附录（源程序清单）7- 24 - 1 问题描述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（m0）。 （3）对应于D-root的划分，H-root，X1， 有唯一的一个划分H1，H2，Hm（m0）。基本操作：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 #include #include #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;in;i+)k=i;for(j=i+1;jn;j+)if (tree-nodej.weighttree-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;in;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;kn;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;inodei.parent=-1;tree-nodei.lchild=-1;tree-nodei.rchild=-1;tree-nodei.weight=0.0;for (i=tree-n;im;i+)/构建哈夫曼树small1=small2=MAXVAL;for (j=0;jnodej.parent=-1 & tree-nodej.weightnodej.weight;p1=j;for (j=0;jnodej.parent=-1 & tree-nodej.weightnodej.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;i128;i+)counti=0;/对源文件中各字符的个数统计ch=fgetc(textfile);while(!feof(textfile)for(i=0;i128;i+)if (ch=char(i)counti+;break;ch=fgetc(textfile);/将统计结果写入权值信息文件data.txt中，并构建哈夫曼树datafile=fopen(f:data.txt,w);for (i=0;inode=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree-n=n;printf(n源文件的字符集及其权值信息如下：n);for(i=0;inodej.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 (nnode=(hufmtreenode*)malloc(2*n-1)*sizeof(hufmtreenode);tree-n=n;m=2*n-1;for (i=0;inodei.parent=-1;tree-nodei.lchild=-1;tree-nodei.rchild=-1;tree-nodei.weight=0.0;fprintf(datafile,%dn,n);for (i=0;inodei.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;inodei.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;in;i+)if (ch=tree-nodei.data)for(j=codei.start+1;jn;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(de