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

1、数据结构课程设计设计说明书（题目）哈夫曼编译器起止日期：2011年6 月20 日至2011年6月27 日学 生 姓 名班级学号成绩指导教师（签字）计算机与通信学院2011年6月23日一、课题任务与说明1 .编辑一个哈夫曼编译器系统程序2问题描述设某编码系统共有n个字符，使用频率分别为Wl,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 VW X Y Z频度 186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 151 48 51 80 23 8 18 1 165. 设计内容与步骤（1）选择合适的数据结构（2）结点结构的设计（3）算法设计与分析（4）程序设计、实现、调试（5）

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

4、们分别为：1. 初始化功能模块此功能模块的功能为从键盘接收字符集大小n,以及n各字符和n个权值。2. 建立哈弗曼树的功能模块此模块功能为使用1中或从一文本中得到的数据按照教材 的构造哈夫曼树的算法构造哈夫曼树。3. 建立哈夫曼编码与译码的功能模块此模块功能为读入相关的字符信息进行哈夫曼编码，并将译 码结果输出，在必要时也可保存到文件中。其中各个函数的功能分别如下：notesave函数用于保存输出的结果； hfmtree函数用于建立结点哈夫曼树并输出最终结果； read note函数用于读取目标文本字符信息；4. 流程图：四、函数编码及调试由于本人能力有限难免不会在编码与调试过程中遇到这样或 那

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

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

7、oni o.h>#include<string.h>#include<stdlib.h>#define MAXLEAF 27#define MAXNODE MAXLEAF*2-1#define MAXBIT 25#define MAXVALUE 2000n"#define H "tttypedef structint parent;int weight;int lchild;int rchild;hfm_n;typedef structint bitMAXBIT;int start;hfm_c;void notesave(int n,char

8、a,hfm_c hfm_code)FILE *fp;int i=0,j;char c;if(fp=fopen("d:notesave.txt","w")=NULL) printf("n Cannot open file!n"); getchar();exit(1);for(i=0;i<n;i+)fputc(ai,fp);fputs("->",fp);for(j=hfm_codei.start+1;j<n;j+)c=char(48+hfm_codei.bitj);fputc(c,fp);fputs(

9、" ",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;char ch1;for(i=0;i<2*n-1;i+)hfm_nodei.weight=0;hfm_nodei.parent=-1;hfm_nodei.lchild=-1;hfm_node

10、i.rchild=-1;for(i=0;i<n;i+)hfm_nodei.weight=si;for(i=0;i<n-1;i+)m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<n+i;j+)if(hfm_nodej.parent=-1&&hfm_nodej.weight<m1)m2=m1;x2=x1;m1=hfm_nodej.weight;x1=j;elseif(hfm_nodej.parent=-1&&hfm_nodej.weight<m2)m2=hfm_nodej.weight;x2=j;hfm_nodex1.

11、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;i<n;i+)cd.start=n-1;c=i;p=hfm_nodec.parent;while(p!=-1)if(hfm_nodep.lchild=c) cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=hfm_nodec.parent; for(j=cd.st

12、art+1;j<n;j+) hfm_codei.bitj=cd.bitj; hfm_codei.start=cd.start;printf("nn 所有编码 :n "); for(i=0;i<n;i+)printf("%c",ai);printf("<=>");for(i=0,c=0;i<n;i+)for(j=hfm_codei.start+1;j<n;j+)printf("%d",hfm_codei.bitj);c+; if(c=48|(c-48)%78=0) printf(&

13、quot;n ");printf("nn 各字符对应的编码 :n"); for(i=0;i<n;i+)printf(" ");printf("%c->",ai);for(j=hfm_codei.start+1;j<n;j+) printf("%d",hfm_codei.bitj);printf(" ");if(i+1)%5=0) printf("n");printf("nn 是否将结果保存到 -> 路径 D: notesave (y

14、/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 the file of note!"

15、;);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&quo

16、t;,"r")=NULL)printf("n Open files fail!");getchar();exit(1);while(ch=fgetc(fp)!=EOF)if(sizeof(ch)!=1) break;k=int(ch); if(k>=65&&k<=90)bk-65+;if(k>=97&&k<=122)bk-97+;fclose(fp);printf("n 文本中各字符的频率为 :n");for(i=0,j=0;i<26;i+)if(bi!=0)ch=char

17、(i+65); aj=ch;sj=bi;printf(" %c->%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 <<-1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1->>n");printf("tt一一 一一一一一* *n");printf(&

18、quot;tt =>>*欢迎使用本哈夫曼编码系统 !*<<=n");printf("tt*=n");printf("tt = |功能选项 !_ _ _ _|=n");printf("tt/ =n");printf("tt = |printf("tt = | 1.| =n");为一字符文本编码 . | =n");printf("tt = | =n");printf("tt = | 2.输入部分字符与相应频率为之编码 .| =n&quo

19、t;);printf("tt = |printf("tt = | 3.| =n");退出程序 . | =n");printf("tt = | =n");printf("tt = | 4. 打开保存的文本 . | =n");printf("tt = | =n");printf("tt = =n");printf(H);printf("ntt 请选择某功能选项 (14):");scanf("%d",&h);getchar();swi

20、tch(h)case 1: system("cls");printf("n 功能 1: 为一字符文本编码!n" );read no te();break;case 2: system("cls");printf("n功能 2: 输入部分字符与相应频率为之编码!n");printf("n =>输入格式应为 : 字符 +空格 n => 例如 :a b cn => 对应的字符频率格式也应如此 .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 => 请输入相应个字符 :"