完整版哈夫曼编码译码器试验报告

1、中北大学数据结构课程设计说明书学生姓名：郝晨栋学号：1021010933学院：软件学院专 业：软件开发与测试题目：哈夫曼编码/译码器指导教师康理2021年12月20日1问题描述错误！未定义书签2需求分析错误！未定义书签3概要设计13. 1抽象数据类型定义 14. 2总体框图以及功能描述 24详细设计25. 1数据类型的定义24. 2主要模块的算法描述35测试分析46课程设计总结6附录源程序清单 71问题描述1 .设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下工程,直到选择退出为止.(1) 将权值数据存放在数据文件(文件名为data.txt ,位于当前目录中)；(2) 分别采用动态

2、和静态存储结构；初始化：键盘输入字符集大小n、n个字符 和n个权值,建立哈夫曼树；(3) 编码：利用建好的哈夫曼树生成哈夫曼编码；输出编码； 设计要求：(1)符合课题要求,实现相应功能；(2)要求界面友好美观,操作方便易行； (3)注意程序的实用性、平安性.2需求分析编写此软件是为了实现一个利用哈夫曼算法的编码和译码系统.比方,再 利用电报进行通讯时,需要将文字转换成由二进制的字符组成的字符串.比方需传送的电文为“ A B A C C D A 假设将A,B,C,D分别编码为00、01、10、11. 那么上述电文遍为0001001010110Q总长度为14位.但是在传送过程中,总希望 长度能够尽

3、可能的短,于是我们想采用长度不等的编码.但是这种编码必须遵循： 任何一个字符的编码都不是另一个字符编码的前缀.对此软件的要求：能够正确的使得对于输入的字符进行编码以及译码,并且是的在译码过程中不会出错,同时能够将编码以及译码的结果正确的存入文件当 中.3概要设计3. 1抽象数据类型定义ADT BinaryTree数据对象：D=ai|ai E ElemSet,i=1,2,.,n, n >0数据关系：假设D为空集,那么称为空树.假设D仅为一个数据元素,那么R为空集,否那么R=H, H是如下的二元关系： (1)再D中存在唯一的称为根的数据元素root ,它在关系H下无前驱. (2)假设 D-r

4、oot<> 空集,那么存在一个划分 D1, D2, , Dm(m>0. (3)对应于 D-root的划分,H-<root , X1, , <root , Xm> 有唯一的一个划分 H1, H2, , Hm(m>0.根本操作：InitTree(&T)操作结果：构造空树ToDestroyTree(&T)初始条件：树T已存在.操作结果：树T被销毁.ClearTree(&T)初始条件：树T已存在.操作结果：将树T清为空栈.TreeEmpty(T)初始条件：树T已存在.操作结果：假设树T为空,那么返回TRUE否那么FALSETreeDep

5、th(T)初始条件：树T已存在.操作结果：返回T的深度.Root (T)初始条件：树T已存在.操作结果：返回树T的根.3. 2总体框图以及功能描述4详细设计4. 1数据类型的定义(1)哈夫曼树节点类型struct hufmtreenode /char data;float weight;/int parent,lchild,rchild; /哈弗曼树结点数据类型结点权值父结点,左、右孩子结点;(2)哈夫曼树类型struct hufmtree/hufmtreenode*node;/int n;/;(3)哈夫曼编码数据类型struct Codetype/char *bits;/哈弗曼树数据类型结点

6、数组根据n的值动态分配叶子结点数哈弗曼编码数据类型编码流数组,int start;/编码实际在编码流数组里的开始位置4. 2主要模块的算法描述(1)主函数：void main()(printf("哈夫曼编码译码系统n");tree=CreateHuffmanTreeFromSourceFile();/ 读取文件建立哈树tree=CreateHuffmanTreeByInput(); /手动输入建立哈夫曼树HuffmanCode(tree);/打印字符集的哈夫曼编码tree=Encoding(tree);/对文本文件编码Decoding(tree);/对代码文件译码(2)构造

7、哈夫曼树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

8、(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)翻开源文件统计各字符及权值信息并存

9、入data.txt文件中一皿鑫* F:fitzBDebd gadsgea. ex eH不印文代出的建夫夫特哈哈码码 I冬的崔I 亶集笈请输入源文件所在路径;：source-txt源文件的字符集及其权值信息如下: £ 3意键继续. . .哈夫曼树建立完毕,已将权值信息保存至士(2)将统计出的权值信息进行哈夫曼编码请输入源文件所在路径f ： Xsoui'ce .txt源文件的原京如下Jaabcccddffaccdb字符集的哈夫曼编码如下一C 11a 01d 00 b 101 f 100编码成功,已将代码写入Cd de File-txt代码如F i01011011111110000

10、10010001111100101请接任竟键继续. . .(3)将编码内容存入CodeFile.txt 文件中| CodeFile.brt:一记事本文件旧现裁旧格式(0) S»(V) Wto(H)0101101111111000010010001111100101(4)将CodeFile.txt 文件中的内容译码-MMMMMMM请输入您的选择凶巧：5请输入代码文件所在路径：F： NCodef ilc,txt代码文件原文如下：0181181111100100011111 (Hl01译码成功,译文已伊存至眦心口deFic*txt 译文如下；aabcccddffaccdb请按任意键继续.

11、. .(5)成功译码把原字符信息存入 DeCodeFile.txt文件中'DesdeFil记事本a 1| 文用月褊后(E)1teC(O)帮助(H)aabcccddffaccdb(6)输入各字符及其权值II I第第第曼 人入人夫俞入您的选择【旧-SJ：2 志入学符数.312 3.才二日值E Z1次值H *2义值3已将权值信息保存至布6.J匕(7)将各字符的权值信息进行哈夫曼编码3但余分C请输入您的选择律一弓八多 c.K 11z 10请按任意键继续 . .(7)根据编码再进行译码工作Hr FHU/ 3d十 也" . 请输入代码文件所在路径: f：data.txt代码文件原文如下；

12、3E.1K.2c ,3请按任意键继续. 6课程设计总结课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问 题,锻炼实践水平的重要环节,是对学生实际工作水平的具体练习和考察过程.随 着科学技术开展的日新日异,当今计算机应用在生活中可以说得是无处不在. 因 此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的.只有回忆起此次课程设计,至今我仍感慨颇多,确实,自从拿到题目到完成 整个编程,从理论到实践,在整整一个星期的日子里,可以学到很多很多的的东 西,同时不仅可以稳固了以前所学过的知识, 而且学到了很多在书本上所没有学 到过的知识.通过这次课程设计使我懂得了理论与实际相结合是很重

13、要的,理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得 出结论,才能真正为社会效劳,从而提升自己的实际动手水平和独立思考的水平. 在设计的过程中遇到问题,这毕竟独立做的,难免会遇到过各种各样的问题,同 时在设计的过程中发现了自己的缺乏之处,对以前所学过的知识理解得不够深 刻,掌握得不够牢固,比方说结构体通过这次课程设计之后,一定把以前所学过的知识重新温故.这次课程设计终于顺利完成了,在设计中遇到了很多编程问题,最后在 谢老师的辛勤指导下,终于游逆而解.同时,在李玉蓉老师的?软件工程导论? 课上我学得到很多实用的知识,在次我表示感谢！同时,对给过我帮助的所有同 学和各位指导

14、老师再次表示忠心的感谢！附录源程序清单#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/

15、哈弗曼编码数据类型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

16、;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.dat

17、a);/打印字符信息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;

18、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;tre

19、e->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 &&t

20、ree->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* CreateHuffmanTreeFromSour

21、ceFile()/通过解析源文件建立哈夫曼树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

22、 找不到文件 %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

23、+)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);fp

24、rintf(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(da

25、tafile);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 ,同时进行哈夫曼树初始化print

26、f(" 请输入字符数：");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->nod

27、ei.weight=0.0;fprintf(datafile,"%dn",n);for (i=0;i<n;i+)(printf("n 输入第c字符及其权化",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);BuildH

28、uffmanTree(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(dataf

29、ile,"%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;

30、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中读取权值信息并建立

31、哈夫曼树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

32、=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;

33、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字符川在哈夫曼树中,不能正确编码.n",ch);fclose(codefile);return NULL;ch=fgetc(textfile);fclose(codefile);/提示成功信息并打印代码printf("n编码成功,已将

34、代码写入 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 *co

35、defile,*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 找不

36、到文件 %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(!fe

37、of(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(&q

38、uot;n编码与当前哈夫曼树结构不相符,不能正确译码n",ch);fclose(decodefile);return;)ch=fgetc(codefile);)if (tree->nodei.lchild>=0 && tree->nodei.rchild>=0)n",ch);/寻找叶子结点的过程中突然读到了文件尾printf("n代码文件编码内容不完整,不能完整译码fclose(decodefile);return;)fputc(tree->nodei.data,decodefile);)fclose(decodefi