哈夫曼编码课程设计报告.docx

《哈夫曼编码课程设计报告.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码课程设计报告.docx（23页珍藏版）》请在三一办公上搜索。

1、课程设计(论文)任务书软件一学院软件+电气专 业1班一、 课程设计(论文)题目哈夫曼树及其编码二、课程设计(论文)工作自2015年_X月室日起至2015年_X月_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个权值，建立哈夫曼树;编码：利用建好的哈夫曼树生成哈夫曼编码; 输出其哈夫曼树及哈夫曼编码:设字符集及频度如下表:字符空格A B CD EFG

4、HI J KLM频度19764 1322 32103211547 57 5 1 20 32字符N O PQRSTUVWXYZ频度57 63 115 4816 80238181511学生签名：年 月 日课程设计（论文）评审意见（1）考勤和态度:优（）、良（）、中（）、一般（）、差（）（2）任务难易及设计思路:优（）、良（）、中（）、一般（）、差（）（3）动手调试能力评价:优（）、良（）、中（）、一般（）、差（）（4）论文撰写水平及规范性评价：优（）、良（）、中（）、一般（）、差（）评阅人：_-职称：-讲师年月 日1设计任务12需求分析13概要设计13.1模块设计13.2系统子程序即功能设计14详

5、细设计25编码实现35.1数据类型定义35.2哈夫曼编码模块设计35.3主程序模块66调试分析77课设总结9参考文献9附录10一设计任务问题描述：设计一个利用哈夫曼算法的编码系统，重复地显示并处理以下项目， 直到选择退出为止。基本要求：初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫 曼树；编码：利用建好的哈夫曼树生成哈夫曼编码；输出其哈夫曼树 及哈夫曼编码；设字符集及频度如下表： 字符空格ABCDEFGH IJ KLM频度19764132232103211547 575 12032字符N OPQRSTUVWX YZ频度57 63115 4816 80238181 51 1二需求分析

6、(1) 设计哈夫曼树。具体构造方法如下：以字符集(空格ABCDE 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)作为叶子结点的权值构造一棵哈夫 曼树。(2) 设计哈哈夫曼。按照构造出来的哈夫曼树，规定哈夫曼树的左 分支为0，右分支为1，则从根结点到每个叶子结点所经过的分支对应的 0和1组成的序列便为该结点对应字符的哈夫曼编码。三概要设计:n,23.1模块设计本程序

7、包含3个模块：主程序模块，哈夫曼编码模块，和选择模块。 其调用关系如下图所示。3.2系统子程序即功能设计本程序共设置2个子程序，各子程序的函数名及各功能说明如(1) void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /构建赫夫曼 树HT,并求出n个字符的赫夫曼编码HC(2) void Select(hfmtree &HT,int a,int *p1,int *p2) /Select 函 数，选出HT树到a为止，权值最小且parent为0的2个节点四详细设计1问题分析哈夫曼树的定义1) 哈夫曼树节点的数据类型定义为：typedef struc t/赫夫曼

8、树的结构体( char ch;int weight;权值int parent,lchild,rchild;htnode,*hfmtree;2) 所实现的功能函数如下1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼树， 处理InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立 2叉树。此函数块调用了 Select()函数。2、void Select(hfmtree &HT,int a,int *p1,int *p2) /Select 函 数，选出HT树到a为止，权值最小且parent为0的2个节点2、int

9、 main()主函数：利用已建好的哈夫曼树(如不在内存，则从文 件hfmtree.txt中读入)对文件中的正文进行编码，然后将结果存入文件 codefile.txt中。如果正文中没有要编码的字符，则键盘读入并存储到 ToBeTran.中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码 存储到CodeFile中。3、Encoding编码功能：对输入字符进行编码4、Decoding译码功能：利用已建好的哈夫曼树将文件codefile.txt中 的代码进行译码，结果存入文件textfile.dat中Print()打印功能函 数：输出哈夫曼树，字符，权值，以及它对应的编码。5、主函数的简要

10、说明，主函数主要设计的是一个分支语句，让用户挑选所 实现的功能。使用链树存储，然后分别调用统计频数函数，排序函数，建 立哈夫曼函数，编码函数，译码函数来实现功能。系统结构图(功能模块图)五编码实现5.1数据类型定义typedef struct(/赫夫曼树的结构体char ch;int weight;权值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;5.2哈夫曼编码模块设计哈夫曼编码模块设计分为两步:首先构造哈夫曼树，然后完成哈夫曼编码。 void Select(hfmtree &HT,int a,int *p1,i

11、nt *p2) /Selec t 函数，选 出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;选出最小的节点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(hfm

12、tree &HT,hfmcode &HC,int n) /构建赫夫曼树 HT,并求出n个字符的赫夫曼编码HC(int 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;+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

13、=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.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*siz

14、eof(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;else(cd-start=1;HCi = (char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);53主程序模块详见源代码六调试分析字符ABCDEFGHIJKLM频度1976413223210321154757512032字符NOPQRSTUVWXYZ频度57631154

15、81680238181151编码E:MICROSOFT VISUAL STUDIOCOMIVIONMSDEV98BINDebLigdg.p 1Q 15 R 48 S 16T 80U 23U 8U 18X 1 51 Z 15一！E青青青青青青青青青至UmXAAAAAAAAA已经放入玷mT典e . t xt文件中?译码XJXJXXJXXJHXJHJXXJXXJHXJ 畤赤三*?号 M扁用马/1.羊 fl 马 W詈 XXXXXXXXXXHJXHJHJOHJXHJXH I.InitE.EncodingD.DecodingQ.Exit喜g翳操勤的步骤：E编码完毕，并且已经存入CodeFile.txt文件

16、！编码码值为：1H0KXXXJCXJCXXXXKXHXHXKXKXXXJC X 击赤= 名扁石马/j.宰而马XXJCXXXXKXKXHXKXKXKXXXJCXXXI.InitE.EncodingD.DecodingQ.Exit清输入您要操作的步骤：DA隔码结束，字符已经存入TextFile .txt文件中！退出I.InitE.EncodingD.DecodingQ-Exit请输入您要操作的步骤：QPress 己ny key to continue七课设总结通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫 曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关

17、于哈 夫曼编码的知识，真正学会一种算法了。当求解一个算法时，不是拿到问题就不加思 索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无 论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。 这次课程设计，体现出自己单独设计程序的能力以及综合运用知识的能力， 体会了学以致用、突出自己劳动成果的喜悦心情。从中发现自己平时学习 的不足和薄弱环节，从而加以弥补。通过这次课程设计，我对这种写程序 的方法有了一定的了解，自己有一个很明确的思路去写程序，提高了效率。 这种框架的程序写法，对我以后学习编程有进一步的提高。在此感谢我们 的王珏老师.，老师严谨细致、一丝不

18、苟的作风一直是我工作、学习中的 榜样；老师循循善诱的教导和不拘一格的思路给予我无尽的启迪；而您开 朗的个性和宽容的态度，帮助我能够很顺利的完成了这次课程设计。同 时感谢对我帮助过的同学们，谢谢你们对我的帮助和支持，让我感受到同 学的友谊。由于自己的设计能力有限，在设计过程中难免出现错误，恳请 老师多多指教。我在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保存数据，对 文件的操作也很生疏。在不断分析后明确并改正了错误和疏漏，我的程序有了更高 的质量。参考文献严蔚敏，吴伟民.数据结构（C语言版）M.清华大学出版社.2010.3严蔚敏，吴伟民.数据结构题集（C语言版）M.清华大学出版社.

19、1999.2何钦铭，冯燕等.数据结构课程设计:M.浙江大学出版社.2007.附录#include#include#include#include#includetypedef 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;

20、+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)(if(HTi.weightHTx.weight&HTi.parent=0)x=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个字符的赫夫曼编码HC(int i,start,c,f,m,w;

21、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;+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;H

22、Ti.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i)/建立赫夫曼树(Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent二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;

23、f!=0;c=f,f=HTf.parent)(if(HTf.lchild=c)(cd-start=0;else(cd-start=1;HCi = (char*)malloc(n-start)*sizeof(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)班

24、Q07620307艾宁n；while(choice!=Q&choice!=q)/当 choice 的值不为 q且不为Q时循环(cout* 赫夫曼编码 /译码器 *n；coutI.InitE.EncodingD.DecodingQ.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

25、;for(i=1;i=n;i+)(output_file(HTi.chHCi)；output_file.close();cout赫夫曼树已经创建完毕，并且已经放入hfmTree.txt 文件中！endl;else if(choice=E|choice=e)/进行编码，并将字符放入ToBeTran.txt，码值放入CodeFile.txt中(printf(请输入字符：)；gets(str);output_file.openCToBeTran.txt);if(!output_file)(coutcant oen file!endl;return 1;output_filestrendl;outpu

26、t_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编码完毕，并且已经存入CodeFile.txt文件！ n;input_file.open(CodeFile.txt)；/ 从CodeFile.txt中读入编码，输出在终端if(!input_fil

27、e)(coutcant oen file!code;cout编码码值为：codeendl;input_file.close();else if(choice=D|choice=d)/ 读 入CodeFile.txt中的编码进行译码，将译出来的字符放入Textfile.txt中(input_file.open(CodeFile.txt)；if(!input_file)coutcant oen file!h;input_file.close();output_file.open(Textfile.txt)；if(!output_file)(coutcant oen file!endl;return

28、 1;k=0;while(hk!=0)/先用编码中的前几个和字符的编码相比较，然后往后移(for(i=1;i=n;i+)l=k;for(j=0;jstrlen(HCi);j+,l+)hlj=hl;hlj=0;if(strcmp(HCi,hl)=0)(output_fileHTi.ch;k=k+strlen(HCi);break;output_file.close();input_file.open(Textfile.txt)；if(!input_file)coutcant oen file!h;couthendl;input_file.close();cout译码结束，字符已经存入 Textfile.txt文件中！ endl;else if(choice=Q|choice=q)退出程序(exit(0);else如果选了选项之外的就让用户重新选择(cout您没有输入正确的步骤，请重新输入！ endl;coutendl;return 0;