数据结构课程设计报告——哈夫曼编译器

1、 数据结构课程设计设计说明书（题目）哈夫曼编译器起止日期： 2011 年 6 月 20 日 至 2011 年 6 月 27 日学生姓名班级学号成绩指导教师(签字)计算机与通信学院2011年 6月 23 日一、课题任务与说明1编辑一个哈夫曼编译器系统程序2问题描述设某编码系统共有n个字符，使用频率分别为w1,w2,wn，设计一个不等长编码方案，使得该编码系统的空间效率最好。3.所具有的功能：(1) 为一字符文本编码功能：将一字符文本复制到指定的文本中，并保存到指定路径，让程序自动为它编码。(2) 为部分字符编码功能：输入部分字符与对应的字符频率，让程序为之编码（需注意输入格式）。(3) 保存输出

2、到文本功能：将编码结果输出到文本。(4) 输出保存文本信息功能：将功能3保存的文本信息输出到屏幕上，用于查看结果是否正确。4.设计要求（1）设计数据结构；（2）设计编码算法；（3）分析时间复杂度和空间复杂度。（4）字符和频度如下：字符 空格 a b c d e f g h i j k l m n o p q r s t u v w x y z频度 186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1 48 51 80 23 8 18 1 165.设计内容与步骤（1）选择合适的数据结构（2）结点结构的设计（3）算法设计与分析（4）程序设计、实现

3、、调试（5）课程设计说明书6.设计工作计划与进度安排（1）设计工作4学时（2）实现与调试16学时（3）课程设计说明书4学时二、算法设计huffman编码是一种可变长编码方式，是由美国数学家david huffman创立的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。huffman算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。三、程序的功能设计为实现系统功能，本程序主要分为五个模块。它们分别为：1.初始化功能模块 此功能模

4、块的功能为从键盘接收字符集大小n,以及n各字符和n个权值。 2.建立哈弗曼树的功能模块 此模块功能为使用1中或从一文本中得到的数据按照教材的构造哈夫曼树的算法构造哈夫曼树。 3.建立哈夫曼编码与译码的功能模块此模块功能为读入相关的字符信息进行哈夫曼编码，并将译码结果输出，在必要时也可保存到文件中。其中各个函数的功能分别如下：notesave函数用于保存输出的结果；hfmtree函数用于建立结点哈夫曼树并输出最终结果；readnote函数用于读取目标文本字符信息；4.流程图：界面main()exit()readnote()hfmtree() main()notesave()结束四、函数编码及调试

5、由于本人能力有限难免不会在编码与调试过程中遇到这样或那样的问题，但通过长时间的改正，查询资料与询问，终于能将出现一些致命错误得以修正。例如：在输入编码结果信息时由于少了一个很不明显的getchar（）的接收enter的函数，后面的就全乱了使程序出现了不能达到意料之中的效果。还有先是运行完一个函数后就跳出了整个运行程序不能再继续，后来通过查阅书籍，明白再主函数中加一个for语句就可以避免这一问题。第三个问题就是由于调用完一个函数后显示的信息还是留在运行界面，但它们的确有没什么用且占用界面，不美观，后来通过询问同学得知，在每个要调用的函数后加一个system(cls)语句就可达到清除上屏信息的功能

6、。五、总结该程序主要用于哈夫曼编码，并在必要时保存数据。做法主要是用一个主函数main，用它达到显示欢迎界面，提示选择操作与调用其它函数功能（用到switch函数），这样使得程序简单，易读，运行效果也好。但由于能力有限，该程序在时间与空间复杂度上有待作改正。参考文献：（1） 刘振鹏、张小莉等编著；数据结构（第二版）.中国铁道出版社。（2） 石强、罗文浩等编著；数据结果习题解答与实验指导（第二版）.中国铁道出版社。（3） 刘克成 主编；c语言程序设计.中国铁道出版社。附全部代码(正常运行vc+6.0)：#include#include#include#include#define maxleaf

7、 27#define maxnode maxleaf*2-1#define maxbit 25#define maxvalue 2000#define h tt =ntypedef structint parent;int weight;int lchild;int rchild;hfm_n;typedef structint bitmaxbit; int start;hfm_c;void notesave(int n,char a,hfm_c hfm_code)file *fp; int i=0,j;char c;if(fp=fopen(d:notesave.txt,w)=null)prin

8、tf(n cannot open file!n);getchar();exit(1);for(i=0;i,fp);for(j=hfm_codei.start+1;jn;j+)c=char(48+hfm_codei.bitj); fputc(c,fp);fputs( ,fp);if(i+1)%3=0) fputs(n,fp);fclose(fp);printf(n 保存成功!n);hfm_n *hfmtree(int n,char a,int s) hfm_n hfm_nodemaxnode; hfm_c hfm_codemaxleaf,cd; int i,j,m1,m2,x1,x2,c,p;c

9、har ch1;for(i=0;i2*n-1;i+) hfm_nodei.weight=0; hfm_nodei.parent=-1; hfm_nodei.lchild=-1; hfm_nodei.rchild=-1;for(i=0;in;i+)hfm_nodei.weight=si; for(i=0;in-1;i+) m1=m2=maxvalue; x1=x2=0; for(j=0;jn+i;j+) if(hfm_nodej.parent=-1&hfm_nodej.weightm1) m2=m1; x2=x1; m1=hfm_nodej.weight; x1=j; else if(hfm_n

10、odej.parent=-1&hfm_nodej.weightm2) m2=hfm_nodej.weight; x2=j; hfm_nodex1.parent=hfm_nodex2.parent=n+i; hfm_noden+i.weight=hfm_nodex1.weight+hfm_nodex2.weight; hfm_noden+i.lchild=x1; hfm_noden+i.rchild=x2; for(i=0;in;i+) cd.start=n-1; c=i; p=hfm_nodec.parent; while(p!=-1) if(hfm_nodep.lchild=c) cd.bi

11、tcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=hfm_nodec.parent; for(j=cd.start+1;jn;j+) hfm_codei.bitj=cd.bitj; hfm_codei.start=cd.start;printf(nn 所有编码:n );for(i=0;in;i+)printf(%c,ai);printf();for(i=0,c=0;in;i+)for(j=hfm_codei.start+1;jn;j+)printf(%d,hfm_codei.bitj);c+;if(c=48|(c-48)%78=0) p

12、rintf(n );printf(nn 各字符对应的编码:n); for(i=0;i,ai);for(j=hfm_codei.start+1;j路径d: notesave (y/n)?);ch1=getchar();getchar();if(ch1=y|ch1=y)notesave(n,a,hfm_code);return null;int readnote()file *fp;int i,j,b26,s26,k;char a26,ch,ch1=n;memset(b,0,sizeof(b);if(fp=fopen(d:note.txt,r)=null) printf(n cannot open

13、 the file of note!); printf(n please creat a new text!n); ch1=y;if(ch1=y) printf(n 此功能你要做的只是将要编码的字符文本复制到下面文本并将它命名为note并 n 保存到-d:. n 需注意的是一定要是字符文本且文本保存路径是d盘下.n ); system(notepad);printf(n 保存好文本后，请按任意键继续.); getchar(); if(fp=fopen(d:note.txt,r)=null) printf(n open files fail!); getchar(); exit(1); whil

14、e(ch=fgetc(fp)!=eof)if(sizeof(ch)!=1) break;k=int(ch);if(k=65&k=97&k=122) bk-97+;fclose(fp);printf(n 文本中各字符的频率为:n);for(i=0,j=0;i%d ,aj,sj); j+;if(j%6=0) printf(n);hfmtree(j,a,s);return 1;void main()int i,h,n=0,b26;char a26,c30,ch,ch1;for(;)printf(nnntt n);printf(tt =* * * * * * * * * * * * * *=n);pr

15、intf(tt =*欢迎使用本哈夫曼编码系统!*输入格式应为:字符+空格n =例如:a b c.n =对应的字符频率格式也应如此.n); doprintf(n 请输入叶子结点个数:);if(scanf(%d,&n)!=1|sizeof(n)!=4)ch=s;printf(n input worry!n please input again.n);else ch=n;getchar();while(ch=s); doprintf(n =请输入相应个字符:); for(i=0;in;i+)ai=getchar(); ch1=getchar();if(ch1!=n) gets(c); printf(n 请输入相应字符对应的频率:); for(i=0;in;i+) scanf(%d,&bi); ch1=getchar(); if(ch1!=n) gets(c); printf(n 确认所有数据无误后请按enter(否则按y); ch=getchar();while(ch=y|ch=y); hfmtree