数据结构完整的课程设计报告哈夫曼编译码器.doc

《数据结构完整的课程设计报告哈夫曼编译码器.doc》由会员分享，可在线阅读，更多相关《数据结构完整的课程设计报告哈夫曼编译码器.doc（26页珍藏版）》请在三一办公上搜索。

1、课 程 设 计 任 务 书课程名称 数据结构课程设计 课 题 赫夫曼编译码器 专业班级 网络工程* 学生姓名 * 学 号 * 指导老师 审 批 任务书下达日期： 2011 年 6 月 26 日任务完成日期： 2011 年 7 月 15 日一、设计内容1）问题描述对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。2）基本要求a.初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。b.编码，利用建好的huffman树生成huffman编码；c.输出编码；d.译码功能；e.字符和频度如下： 字符ABCDEFGHIJKLM频度1866413223210

2、3211547571232字符NOPQRSTUVWXYZ频度20576315148518023818116二设计要求：l 课程设计报告1)需求分析a.程序的功能。1. 初始化，键盘输入字符集大小n，n个字符和n个权植，建立哈夫曼树。2. 编码，利用建好的huffman树生成huffman编码；3. 输出编码；4. 译码功能；b.输入输出的要求。2)概要设计a. 程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。i. void main()ii. void tohuffmancode(int n)/编码部分iii. void decode(char ch,huftree

3、 tree,int n)/译码iv. void huffman(huftree tree,int *w,int n) /生成huffman树v. void select(huftree tree,int k) /找寻parent为0,权最小的两个节点vi. void huffmancode(huftree tree,char code,int n)/输出huffman编码其流程图如下：main()Initialization（）初始化函数Input()输入待编码字符函数Encoding（）编码函数Decoding（）译码函数Code_inting()打印编码函数inting()打印哈夫曼树主函

4、数main 调用其他函数： tohuffmancode(int n)decode(char ch,huftree tree,int n) huffman(huftree tree,int *w,int n) select(huftree tree,int k) huffmancode(huftree tree,char code,int n)其主流程图如下：进行相应的操作输出结果结束一构造哈夫曼树四程序结束退出三对编码串译码二对字符串编码开始进行相应的操作(3)主要模块程序流程图下面介绍三个主要的程序模块流程图： 函数流程图： 结束统计字符种类及频率字符总数num建立哈夫曼树哈夫曼编码哈夫曼译

5、码打开文件？开始否是 流程图注释：该图比较简单，主要是调用各个函数模块，首先代开已经存在的文件，然后统计总的字符数以及出现的各个字符和频率。然后才开始建立哈夫曼树，接着在哈夫曼树的基础上对其进行编码，编码之后才是译码。最后输出结束。构造哈夫曼树：开始结束第i个结点权值i=num?创建哈夫曼树输出字符统计情况第i个根结点i=2*num-1?i=num?否是否是否是 流程图注释：该图是表示构造哈夫曼树的过程。首先输入num个叶结点的权值，当i=num是循环结束。然后进行哈夫曼树的构建，当i=2*num-1是循环结束。最后输出所得到的字符统计情况。哈夫曼编码：结束开始Tp.lchlid=c?i=nu

6、m?Cd-start=0,start=numCd-start=0Cd-start=1否否是是 流程图解释：该流程图表四哈夫曼编码情况。首先初始化，Cd-start=0,start=num。然后进行编码，使用了一个三目运算符。cd-start=(Tp.lchild=c) ? 0 : 1，即当cd-start=Tp.lchild= =c时，cd-start=0；当cd-start=Tp.lchild！= =c时，cd-start=1。这个编码循环一直到i=num时结束。b. 课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。 有线性结构、树形结构等等。

7、3)详细设计a.采用C语言定义相关的数据类型。Char int 还有数据体结构 链表结构 等等。c. 写出各模块的类C码算法。1. void main()/主函数int i=0,n=0;int *w,weightMAX;char codeMAX;huftree treeMAX;char in;while (in!=5)cout -哈夫曼编码-endlendl;cout1 建立初始化哈夫曼树 2 输出哈夫曼编码 3 编码 4 译码 5 退出endlendl;coutin;coutendl;switch (in)case 1: coutn; cout请输入字符及对应权值:endl; for(i=1

8、;i=n;i+) cout; cinchaiweighti; huffman(tree,w,n); break; case 2:huffmancode(tree,code,n);break;case 3:tohuffmancode(n);break;case 4:decode(cha,tree,n);break;2. void tohuffmancode(int n)/编码部分 int i=0,j; char anychar9999; cout请输入你要编码的字符串:endl; cinanychar; cout编码为:; for (;anychari!=0;i+) j=0; for(;anyc

9、hari!=chaj&j=n;) j+; if (j=n) couthcj; coutendl;3. void decode(char ch,huftree tree,int n)/译码int i,j,m;char b;m=2*n-1;i=m;cout请输入编码:endl;cinb;cout译码为:;while(b!=10) if(b=0)i=treei.lchild;else i=treei.rchild;if(treei.lchild=0)coutchi; j=i,i=m;cin.get(b);if(treej.lchild!=0)coutendlERRORendl;coutendlend

10、l;4. void huffman(huftree tree,int *w,int n) /生成huffman树 int m,i; if (n=1) return; m=2*n-1;for (i=1;i=n;i+) treei.weight=wi; treei.parent=0; treei.lchild=0; treei.rchild=0; for (i=n+1;i=m;i+) treei.weight=0; treei.parent=0; treei.lchild=0; treei.rchild=0; for (i=n+1;i=m;i+) select(tree, i-1); trees1

11、.parent=i; trees2.parent=i; treei.lchild=s1; treei.rchild=s2; treei.weight =trees1. weight+ trees2.weight; 5. void select(huftree tree,int k) /找寻parent为0,权最小的两个节点 int i;for (i=1;i=k & treei.parent!=0 ;i+); s1=i; for (i=1;i=k;i+) if (treei.parent=0 & treei.weighttrees1.weight) s1=i; for (i=1; i=k ; i

12、+) if (treei.parent=0 & i!=s1) break; s2=i;for (i=1;i=k;i+) if ( treei.parent=0 & i!=s1 & treei.weighttrees2.weight) s2=i;6. void huffmancode(huftree tree,char code,int n) /输出huffman编码int start,c,i,f;cout哈夫曼树：endl;/输出hufftree for(i=1;i=2*n-1;i+) coutsetw(5)i setw(5)treei.weight setw(5)treei.parent s

13、etw(5)treei.lchild setw(5)treei.rchild endl;coden-1=0;/cout哈夫曼编码:endl;for(i=1;i=n;i+)start=n-1;for(c=i,f=treei.parent;f!=0;c=f,f=treef.parent)/if(treef.lchild=c)code-start=0;else code-start=1;strcpy(hci,&codestart);coutchaihciendl; 4)调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。1. 输入字符和

14、权值(测试数据): 2.输出地赫夫曼编码为： 3.对其进行编码为：例如：a为111. T为0011 Y为0110010104.对其进行译码为：例如：输入编码0011. 输入编码011001010 b.课程设计过程经验教训、心得体会。通过两周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。首先我谈谈我在设计期间我遇到的难点。开始的时候，代码中有许多的错误，特别是有一个“无法找到文件”的错误让我束手无策，最后还是屏蔽了定义的四个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现文章的读入时，由于对文件不是太熟悉，只好翻开C语言

15、书本仿照其模式编写，但后来进入了死循环，最后的解决方式是把main函数里的一个dowhile循环去掉。在程序中，我还另外加了一个功能-输出哈夫曼树的存储结构的初态和终态。这使得我更加的明白了哈夫曼到底是怎么存储信息的。许多的错误让我明白了一个道理-细心是非常重要的。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要，因为毕竟我们是新手，对于某些问题很难弄清楚。而且，某些错误对于我们来说有时候想半天都弄不来，但老师几下下就搞好了，这样就更加有效地节约了时间。这次课程设计不但让我学得了一些编程知识，还学会了系统的做一份课程设计报告，学

16、会了如何截图，学会了如何更好的画流程图，明白了做事情只有认真，才能真正做得更好！这段时间里，可谓是酸甜苦辣都尝过。有时，为了一个错误而焦头烂额；有时，编程熬夜到凌晨两点；有时，连吃饭都是匆匆了事；但一旦程序运行成功，总会让我兴奋不已。通过这次课程设计，我看清楚了自己的编程功底和动手能力还不如人意，这主要是平时实践太少的缘故。我想，在未来的暑假中，我会努力尝试编写一些程序。虽然我们信息管理专业的学生，但现在编程的能力太差了，毕竟多精通一门技术总是好事。在这个程序中，还有许多地方值得完善。比如，读出文本只能是大写的文档，空格和小写不能识别，更不用说是任意的ASC码字符了。由于时间问题，暂时不能实现

17、了。我想在暑假里好好研究这个问题。作为信息管理专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强

18、了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样，我们的综合素质才会有好的提高。5)使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。A. 说明：1) 在运行哈夫曼编码过程中，若字母

19、A，B，Z，C出现的概率为：0.75,0.54,0.28,0.43；则相应的权值为：75，54，28，43。构造好哈夫曼树后，就可根据哈夫曼树进行编码。例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。即译码功能的实现。2) 本设计中，代码很简短，实现了四项主要功能，用户可以根据所给的提示，一一实现。在调试过程中，主要是，在生成哈夫曼树时，须花费一定的时间输入字符以及权值的大小。本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性，特别是文件操作方面，如果可能的话，可以把文件读入、读

20、出分别写成一个函数（就是把文件名作为参数），然后就可以直接调用了。 此处我将编码结果存入了一个文件，译码时直接从文件读取逐一译码。 3.本设计，功能简单明了，且程序代码可运行好，其中用到了数组，字符串，二叉树等知识以实现程序。 4.时间复杂度与空间复杂度。在程序开头部分，就定义了一个长度为99的字符数组，用来存放用户输入的字符，空间上造成了一定的浪费，若能实现动态的存储空间，就可以有效的利用好空间。与之相同的还有解码的时候，同样申请了一个长度为9999的字符数组。所以有效的利用好空间时很好的。在运行第一步，也就时构造哈夫曼树时，字符与权值大小的输入可能会造成时间上的浪费，另外就是在译码时没能实

21、用二进制流文件对相关知识没能融会贯通，所以需耐心完成。 B程序的使用：1. 首先，找到已有的程序，双击！2.出现如图：3.在进行选择：输入“1” 如图：4.输入字符个数，并输入字符及相应的权值，如下图： 5.输入好后，就对其进行编码和译码，分别如下图：最后我们就完成了用哈夫曼编译码器对其进行的初始化还有编码和译码。6)附录a.参考书目1 苏仕华数据结构课程设计北京：机械工业出版社，20052陈慧南数据结构C+语言描述北京：人民邮电出版社，2005033严蔚敏，吴伟民数据结构北京：清华大学出版社，19974王成端, 徐翠霞数据结构上机实验与习题解析 北京-中国电力出版社，20065Adam Dr

22、ozdek数据结构与算法，北京：清华大学出版社，20066李春葆，金晶数据结构教程北京：清华大学出版社，20067Mark Allen Weiss。Data structures and algorithm analysis in C+北京：Posts & Telecom Press，20068王红梅, 胡明, 王涛数据结构 (C+版) 学习辅导与实验指导北京：清华大学出版社，20059胡元义数据结构(C语言)实践教程西安：西安电子科技大学出版社，200210朱战立数据结构使用C+语言西安：西安电子科技大学出版社，200111周云静数据结构习题解析与上机指导北京：冶金工业出版社，200412徐

23、孝凯数据结构实验北京：中央广播电视大学出版社，200113宁正元数据结构习题解析与上机实验指导北京：中国水利水电出版社，20009b.源程序清单（带注释）#include#include#include#define MAX 99char chaMAX;char hcMAX-1MAX;int s1,s2; /设置全局变量，以便在方法(函数)select中返回两个变量typedef struct /huffman树存储结构unsigned int weight;/权值int lchild,rchild,parent;huftree;void select(huftree tree,int k)

24、/找寻parent为0,权最小的两个节点int i;for (i=1;i=k & treei.parent!=0 ;i+); s1=i;/初始化s1for (i=1;i=k;i+) if (treei.parent=0 & treei.weighttrees1.weight) s1=i;/把最小值赋给s1for (i=1; i=k ; i+) if (treei.parent=0 & i!=s1) break; s2=i;/初始化s2for (i=1;i=k;i+) if ( treei.parent=0 & i!=s1 & treei.weighttrees2.weight) s2=i;/把

25、最小值赋给s2void huffman(huftree tree,int *w,int n) /生成huffman树 int m,i; if (n=1) return; m=2*n-1;for (i=1;i=n;i+)/给tree中每个结点权值赋值，且分别给左右孩子及双亲初始化 treei.weight=wi; treei.parent=0; treei.lchild=0; treei.rchild=0; for (i=n+1;i=m;i+)/给除了叶子结点下的其它结点初始化 treei.weight=0; treei.parent=0; treei.lchild=0; treei.rchil

26、d=0; for (i=n+1;i=m;i+)/最终结果 select(tree, i-1); trees1.parent=i; trees2.parent=i; treei.lchild=s1; treei.rchild=s2; treei.weight =trees1. weight+ trees2.weight; void huffmancode(huftree tree,char code,int n)/输出huffman编码int start,c,i,f;cout哈夫曼树：endl;/输出hufftree for(i=1;i=2*n-1;i+) coutsetw(5)i setw(5

27、)treei.weight setw(5)treei.parent setw(5)treei.lchild setw(5)treei.rchild endl;coden-1=0;/cout哈夫曼编码:endl;for(i=1;i=n;i+)start=n-1;for(c=i,f=treei.parent;f!=0;c=f,f=treef.parent)/输出huffman编码if(treef.lchild=c)code-start=0;/把编码存入codeelse code-start=1;strcpy(hci,&codestart);/把code分别复制给hccoutchaihciendl;

28、/分别输出编码 for是满足条件进入void tohuffmancode(int n)/编码部分 int i=0,j; char anychar9999; cout请输入你要编码的字符串:endl; cinanychar; cout编码为:; for (;anychari!=0;i+) j=0; for(;anychari!=chaj&j=n;) j+; if (j=n) couthcj; coutendl;void decode(char ch,huftree tree,int n)/译码int i,j,m;char b;m=2*n-1;i=m;cout请输入编码:endl;cinb;cou

29、t译码为:;while(b!=10) /遇到回车时，结束if(b=0)i=treei.lchild;else i=treei.rchild;if(treei.lchild=0)coutchi; j=i,i=m;cin.get(b);if(treej.lchild!=0)coutendlERRORendl;coutendlendl;void main()int i=0,n=0;int *w,weightMAX;char codeMAX;huftree treeMAX;w=weight;char in;while (in!=5)cout -哈夫曼编码-endlendl;cout1 建立初始化哈夫曼

30、树 2 输出哈夫曼编码 3 编码 4 译码 5 退出endlendl;coutin;coutendl;switch (in)case 1: coutn; cout请输入字符及对应权值:endl; for(i=1;i=n;i+) cout; cinchaiweighti; huffman(tree,w,n); break; /生成huffman树case 2:huffmancode(tree,code,n);break;case 3:tohuffmancode(n);break;case 4:decode(cha,tree,n);break;l 考核方式指导老师负责验收程序的运行结果，并结合学生

31、的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分： 平时出勤 （占10%） 系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%） 程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%） 设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。 独立完成情况（占10%）。l 课程验收要求 运行所设计的系统。 回答有关问题。 提交课程设计报告。 提交电子文档（源程序、设计报告文档）。 依内容的创新程度，完善程序情况及对程序讲解情况打

32、分。二、进度安排第19周星期一星期二星期三星期四星期五上午8：0012：00下午13：3017：30晚上18：0020：00第20周星期一星期二星期三星期四星期五上午8：0012：00下午13：3017：30晚上18：0020：00附：课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在5000字以上（不含程序原代码）。计算机与通信学院课程设计评分表课题名称： 赫夫曼编译码器 项 目评 价设计方案的合理性与创造性设计与调试结果设计说明书的质量答辩陈述与回答问题情况课程设计周表现情况综合成绩 教师签名： 日 期：