哈夫曼编码课程设计报告

1、课程设计(论文)任务书 软件 学院 软件+电气 专业 1 班 一、课程设计(论文)题目 哈夫曼树及其编码 二、课程设计(论文)工作自 2015年 1 月 5 日起至 2015年 1 月 9日止。三、课程设计(论文) 地点: 创新大楼303,305 四、课程设计(论文)内容要求：1课程设计的目的为了配合数据结构课程的教学，使学生能更深刻的领会数据结构课程的重要性，特开设此课程设计；编写一些在特定数据结构上的算法，通过上机调试，更好的掌握各种数据结构及其特点，培养学生综合运用所学理论知识解决复杂实际问题的实践能力、研究性学习能力和团队合作能力。2课程设计的任务及要求1）基本要求（1）课程设计前必须

2、选定课程设计题目，并认真进行需求分析与系统设计； （2）上机调试之前要认真准备实验程序及调试时所需的测试数据；（3）独立思考，独立完成，严禁抄袭，调试过程要规范，认真记录调试结果； （4）上机结束后认真规范撰写课设报告，对设计进行总结和讨论。2）课程设计论文编写要求（1）要按照书稿的规格撰写打印课设论文（2）论文包括任务书、目录、绪论、正文、总结、参考文献、附录等（3）正文中要有问题描述、抽象数据类型的定义、数据的存储结构、设计的求解算法、算法的实现、调试分析与测试结果（4）课设论文装订按学校的统一要求完成3）课设考核从以下几方面来考查：（1）考勤和态度； （2）任务的难易程度及设计思路；（3

3、）动手调试能力；（4）论文撰写的水平、格式的规范性。4）参考文献1 严蔚敏, 吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社, 2007年.2 严蔚敏, 吴伟民. 数据结构题集（C语言版）M. 北京：清华大学出版社, 2007年.3 谭浩强. C语言程序设计M. 北京：清华大学出版社，2006年.5）课程设计进度安排内容 天数地点构思及收集资料 1图书馆程序设计与调试 3计算机房撰写论文 1图书馆6）任务及具体要求初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；编码：利用建好的哈夫曼树生成哈夫曼编码； 输出其哈夫曼树及哈夫曼编码； 设字符集及频度如下表： 字符 空格

4、A B C D E F G H I J K L M 频度 197 64 13 22 32 103 21 15 47 57 5 1 20 32 字符 N O P Q R S T U V W X Y Z 频度 57 63 1 15 48 16 80 23 8 18 1 51 1 学生签名： 年 月 日课程设计(论文)评审意见（1）考勤和态度 ：优（）、良（）、中（）、一般（）、差（）（2）任务难易及设计思路 ：优（）、良（）、中（）、一般（）、差（）（3）动手调试能力评价 ：优（）、良（）、中（）、一般（）、差（）（4）论文撰写水平及规范性评价：优（ ）、良（ ）、中（）、一般（）、差（） 评阅人

5、： 职称： 讲师 年 月 日目 录1 设计任务12 需求分析13 概要设计13.1模块设计13.2系统子程序即功能设计14 详细设计25 编码实现35.1数据类型定义35.2哈夫曼编码模块设计35.3主程序模块66 调试分析77 课设总结9参考文献9附录9一 设计任务问题描述：设计一个利用哈夫曼算法的编码系统，重复地显示并处理以下项目，直到选择退出为止。基本要求：初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；编码：利用建好的哈夫曼树生成哈夫曼编码；输出其哈夫曼树及哈夫曼编码；设字符集及频度如下表：字符 空格 A B C D E F G H I J K L M频度 197 64

6、 13 22 32 103 21 15 47 57 5 1 20 32字符 N O P Q R S T U V W X Y Z 频度 57 63 1 15 48 16 80 23 8 18 1 51 1 二 需求分析（1）设计哈夫曼树。具体构造方法如下：以字符集（空格 A B C D E F G H I J K N O P Q R S T U V W X Y Z L M）作为叶子结点。以各字母出现的次数即频度（197 64 13 22 32 103 21 15 47 57 5 1 20 32 57 63 1 15 48 16 80 23 8 18 1 51 1）作为叶子结点的权值构造一棵哈夫曼

7、树。（2）设计哈哈夫曼。按照构造出来的哈夫曼树，规定哈夫曼树的左分支为0，右分支为1，则从根结点到每个叶子结点所经过的分支对应的0和1 组成的序列便为该结点对应字符的哈夫曼编码。三 概要设计3.1模块设计本程序包含3个模块：主程序模块，哈夫曼编码模块，和选择模块。其调用关系如下图所示。选择模块哈夫曼编码模块主程序模块3.2系统子程序即功能设计本程序共设置2个子程序，各子程序的函数名及各功能说明如（1）void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /构建赫夫曼树HT，并求出n个字符的赫夫曼编码HC（2）void Select(hfmtree &HT,

8、int a,int *p1,int *p2) /Select函数，选出HT树到a为止，权值最小且parent为0的2个节点四 详细设计 1问题分析哈夫曼树的定义1）哈夫曼树节点的数据类型定义为：typedef struc t/赫夫曼树的结构体 char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;2）所实现的功能函数如下1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼树，处理InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立2叉树

9、。此函数块调用了Select（）函数。2、void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函数，选出HT树到a为止，权值最小且parent为0的2个节点2、 int main() 主函数： 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt中读入）对文件中的正文进行编码，然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran.中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。3、Encoding 编码功能：对输入字符进行编码4、D

10、ecoding译码功能： 利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat 中。Print() 打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。5.主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。系统结构图（功能模块图）哈夫曼编码/译码器打印哈夫曼树打印编码译码编码初始化哈夫曼树五 编码实现5.1数据类型定义typedef struct /赫夫曼树的结构体char ch;int weight; /权值int

11、parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;5.2哈夫曼编码模块设计哈夫曼编码模块设计分为两步：首先构造哈夫曼树，然后完成哈夫曼编码。void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函数，选出HT树到a为止，权值最小且parent为0的2个节点int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i;

12、 /选出最小的节点for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;break;for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /构建赫夫曼树HT，并求出n个字符的赫夫曼编码HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;

13、+i) /初始化n个叶子结点printf(请输入第%d字符信息和权值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的结点HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立赫夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.pare

14、nt=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /给n个字符编码start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof

15、(char);strcpy(HCi,&cdstart);free(cd);5.3主程序模块详见源代码 六 调试分析字符ABCDEFGHIJKLM频度1976413223210321154757512032字符NOPQRSTUVWXYZ频度5763115481680238181151编码译码退出七 课设总结 通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自

16、己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。这次课程设计，体现出自己单独设计程序的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情。从中发现自己平时学习的不足和薄弱环节，从而加以弥补。通过这次课程设计，我对这种写程序的方法有了一定的了解，自己有一个很明确的思路去写程序，提高了效率。这种框架的程序写法，对我以后学习编程有进一步的提高。在此感谢我们的王玨老师.，老师严谨细致、一丝不苟的作风一直是我工作、学习中的榜样；老师循循善诱的教导和不拘一格的思路给予我无尽的启迪；而您开朗的个性和宽容的态度，帮助我能够很顺利的完成了这次课程设计。 同时感谢对我帮助

17、过的同学们，谢谢你们对我的帮助和支持，让我感受到同学的友谊。由于自己的设计能力有限，在设计过程中难免出现错误，恳请老师多多指教。我在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保存数据，对文件的操作也很生疏。在不断分析后明确并改正了错误和疏漏，我的程序有了更高的质量。参考文献严蔚敏,吴伟民. 数据结构(C语言版)M. 清华大学出版社. 2010.3 严蔚敏,吴伟民. 数据结构题集(C语言版)M.清华大学出版社. 1999.2何钦铭,冯燕等. 数据结构课程设计M. 浙江大学出版社. 2007.附录#include#include#include#include#includetype

18、def struct /赫夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函数，选出HT树到a为止，权值最小且parent为0的2个节点int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=

19、i; /选出最小的节点for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;break;for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /构建赫夫曼树HT，并求出n个字符的赫夫曼编码HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=

20、n;+i) /初始化n个叶子结点printf(请输入第%d字符信息和权值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的结点HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立赫夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.pa

21、rent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /给n个字符编码start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*size

22、of(char);strcpy(HCi,&cdstart);free(cd);int main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件输入输出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;coutn;cout 软件+电气（1）班 Q07620307 艾宁n;while(choice!=Q&choice!=q) /当choice的值不为q且不为Q时循环cout *赫夫曼编码/译码器*n; cout I.Init E.Encodin

23、g D.Decoding Q.Exitn; coutchoice; if(choice=I|choice=i) /初始化赫夫曼树coutn;hfmcoding(HT,HC,n);for(i=1;i=n;+i)coutHTi.ch:HCiendl;output_file.open(hfmTree.txt);if(!output_file)coutcant oen file!endl;return 1;for(i=1;i=n;i+)output_file(HTi.chHCi);output_file.close();cout赫夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!endl;

24、 else if(choice=E|choice=e) /进行编码，并将字符放入ToBeTran.txt，码值放入CodeFile.txt中printf(请输入字符：);gets(str);output_file.open(ToBeTran.txt);if(!output_file)coutcant oen file!endl;return 1;output_filestrendl;output_file.close();output_file.open(CodeFile.txt);if(!output_file)coutcant oen file!endl;return 1;for(i=0;istrlen(str);i+)for(j=0;j=n;+j)if(HTj.ch=stri)output_fileHCj;break;output_file.close();coutn;cout编码完毕，并且已经存