哈弗曼树课程设计报告.doc

1、 课程设计（论文）摘要摘要1一 概述21.课程设计的目的22.课程设计的要求23.哈夫曼算法的实现2二 总体方案设计31.整体的设计思路32.算法的整体思路33.工作内容34.关键问题4三 详细设计51.总体设计流程图52.建立哈夫曼树53.编码功能64.译码功能6四 程序的调试与运行结果说明7五 课程设计总结10程序部分代码11参考文献14摘要随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础

2、。 算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效

3、率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。一 概述1.课程设计的目的1理解和掌握该课程中的有关基本概念，程序设计思想和方法。2培养综合运用所学知识独立完成课题的能力。3培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。4掌握

4、从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。2.课程设计的要求一个完整的系统至少具有以下功能：(1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。(2) E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。(3) D：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文

5、件Textfile中。3.哈夫曼算法的实现由哈夫曼树的构造过程可知，初始森林中共有n棵二叉树，每棵树中都仅有一个孤立的结点，它们既是根，又是叶子。然后将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新二叉树。每合并一次，森林中就减少一棵树。显然，要进行n-l次合并，才能使森林中的二叉树的数目，由n棵减少到剩下一棵最终的哈夫曼树。并且每次合并，都要产生一个新结点，合并n-l次共产生n-1个新结点，显然它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中共有2n-1个结点，其中n个叶结点是初始森林中的n个孤立结点，并且哈夫曼树中没有度为1的分支结点。因此，在构造哈夫曼树时，可以设置一

6、个大小为2n-1的数组ht保存哈夫曼树中各结点的信息。二 总体方案设计1.整体的设计思路利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输预先编码，在接收端将传来的数据进行译码。对于双工通道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。本课程设计实现这样的信息收发站，编写一个哈夫曼码的编/译码系统。系统共分为四个子系统：初始化哈夫曼树；编码；译码；打印哈夫曼树。输入相应的数字后按回车键即可进入相应的系统。在相应的系统内可完成相应的功能。各模块相对独立，每个模块用一个大型的函数来处理数据。2.算法的整体思路 本系

7、统能根据输入的字符数生成哈夫曼树，并自动输出各字符的哈夫曼编码。通过对单链表的结点查找，结点插入等一些算法建立一个根据头结点来插入数据的函数，通过对此函数的调用建立一个根据输入的数据来输入信息的函数。修改信息，排序，查找信息等模块的函数均用同样的方法处理。3.工作内容工作进程安排：系统设计，详细设计，编写代码，结果测试与分析。本人负责模块：译码功能。功能分析：译码（Decoding）。将codefile.txt文档中的编码以字符形式输出。译码原则：在完成Huffman编码后，我们利用其构建的哈夫曼编码树来进行译码。与编码过程不同，译码过程中，我们将用户输入的二进制代码串依次与字符集中的每个字符

8、的编码进行比较，从根结点出发，逐个读入电文中的二进制码；若代码为“0”，则走左子树的根结点，否则走向右子树的根结点；一旦到达叶子结点，便译出代码所对应的字符。然后又重新从根结点开始继续译码，直到二进制电文结束。实现代码：void Decoding() cout 下面对根目录下文件codefile.txt中的字符进行译码 endl; FILE *codef, *txtfile; if (txtfile = fopen(Textfile.txt, w) = NULL)/ w 只写 cout 不能打开文件 endl; if (codef = fopen(codefile.txt, r) = NULL

9、)/ r 只读 cout 不能打开文件 endl; char *work, *work2, i2; int i4 = 0, i, i3; unsigned long length = 10000; work = (char*)malloc(length *sizeof(char); fgets(work, length, codef); work2 = (char*)malloc(length *sizeof(char); i3 = 2 * n - 1; for (i = 0; *(work + i - 1) != 0; i+) i2 = *(work + i); if (HTi3.lchil

10、d = 0) *(work2 + i4) = *(z + i3 - 1); i4+; i3 = 2 * n - 1; i-; else if (i2 = 0) i3 = HTi3.lchild; else if (i2 = 1) i3 = HTi3.rchild; *(work2 + i4) = 0; fputs(work2, txtfile); cout 译码完成 endl 内容写入根目录下的文件txtfile.txt中 endl endl; cout work2endl; free(work); free(work2); fclose(txtfile); fclose(codef);4.关

11、键问题（1）哈夫曼树的构建，输入字符与权值后哈夫曼编码的生成。（2）编码（Encoding）。输入要编码的字符，存入text.txt文档中，通过编码程序，将字符以哈夫曼编码形式存在codefile.txt文档中。（3）将哈夫曼树以树型打印出来。三 详细设计1.总体设计流程图图3-1 主要功能流程图哈夫曼树编码建立哈夫曼树编码译码打印哈夫曼树打印哈夫曼树退出2.建立哈夫曼树功能：1.进入输入系统后选择需要进行的操作步骤。输入待编码的字符数，并且随即输入编码字符的权值。 建立哈夫曼树输入字符及权值对权值进行从小到大排序输出编码结束创建哈夫曼树，放入hfmTree.txt文件中图3-2 建立哈夫曼树

12、3.编码功能功能：输入需要编码的字符，编码后存入文档。再输出编码。编码输入需要编码的字符将字符放入ToBeTran.txt进行编码码值放入CodeFile.txt中从CodeFile.txt中读入编码，输出在终端结束图3-3 编码功能4.译码功能功能：选择译码步骤，将Codefile.txt中的编码进行译码。译码读入CodeFile.txt中的编码进行译码将译出来的字符放入Textfile.txt中结束图3-4 译码功能四 程序的调试与运行结果说明1.初始化哈夫曼树2.编码功能3.译码功能4.打印哈夫曼树5.调试分析5.1 调试过程中遇到的问题（1）文件的调用与写入。由于文件的内容学习得不够扎

13、实，在从tobetran.txt文档中读取已经输入的字符进行编码时出现了问题。程序首先能成功读取字符，并进行编码存入Codefile.txt文档中，但无法再从Codefile.txt文档中读出已经编码的值。解决方法：设置一个全局结构体变量来存放已经在文件中存放的哈夫曼树。（2）Huffman树的打印。由于在学习中并未留意数据如何类似图形输出，算法思想也不了解。因此这一模块无法成功完成。解决方案：由其他组员完成，但未完善解决，只是将内存中的哈夫曼树中各节点的值及其孩子输出。5.2 算法的时空分析算法的时间复杂度：Select(HuffmanTree HT,int end,int *s1,int

14、*s2) O(n)HuffmanCoding(Huffman Hfm) O(n2)InitHuffman(Huffman Hfm) O(n)Encoding(Huffman Hfm) O(n)Decoding(Huffman Hfm) O(n)Print(Huffman Hfm) O(n)五 课程设计总结通过为期半个月的课程设计，我们对数据结构这门课程有了更深一步的了解。它是计算机程序设计的重要理论技术基础，在我们计算机专业的学习中占据着十分重要的地位。同时也使我们知道，要学好这门课程，仅学习书本上的知识是不够的，还要有较强的实践能力。因为我们学习知识就是为了实践。而只有多实践，多编写程序，才

15、能更好的理解与掌握书本上的东西。我从实践中明白了C语言的模块化设计的理论。将一个大任务分成若干个较小的任务，较小的任务又细分为更小的任务，直到更小的任务功能较为单一，便于实现为止，每个小任务为一个模块。各个模块功能单一，独立编程，独立存放，单独调试，可以为多个程序所调用，并可以由不同的人实现。在以后的编程过程中，我会按照软件开发的方法，步骤，原则认真的完成软件开发。不断寻求最优的解决问题的办法，使自己开发出来的软件运行效率更高，功能更加完善。对于自己解决不了的问题可以在网上查找，找同学帮忙，复习教材相应的内容，并且不断地学习新知识，以使自己在软件开发方面跟上时代的发展。程序部分代码/ -求赫夫

16、曼编码-int min(HuffmanTree t, int i) int j, flag; int k = UINT_MAX; /k存最小权值，初值取整型最大值 for (j = 1; j = i; j+)/对于前i个结点,寻找第一最小值 if (tj.weight s2) j = s1; s1 = s2; s2 = j; / -构造赫夫曼树-void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) int m, i, s1, s2, start;/*m表示结点个数*/ int c, f; HuffmanTree

17、p; char *cd; if (n = 1)/叶子结点数不大于n return ; m = 2 * n - 1; /n个叶子结点的哈弗曼树共有m个结点 HT = (HuffmanTree)malloc(m + 1) *sizeof(HTNode); / 0号单元未用 for (p = HT + 1, i = 1; i weight = *w;/*赋权值*/ p-parent = 0;/*双亲域为空（是根结点）*/ p-lchild = 0;/*左右孩子为空（是叶子结点）*/ p-rchild = 0; for (; i parent=0; /*双亲域为空（是根结点）*/p-lchild=0;

18、 /*左右孩子为空（是叶子结点）*/p-rchild=0;*/ p-parent = 0; for (i = n + 1; i = m; +i) select(HT, i - 1, s1, s2); HTs1.parent = HTs2.parent = i;/*i号单元是s1和s2的双亲*/ HTi.lchild = s1;/*i号单元的左右孩子分别是s1和s2*/ HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; HC = (HuffmanCode)malloc(n + 1) *sizeof(char*); cd = (cha

19、r*)malloc(n *sizeof(char); / 分配求编码的工作空间 cdn - 1 = 0; / 编码结束符 for (i = 1; i = n; i+) start = n - 1; / 编码结束符位置 for (c = i, f = HTi.parent; f != 0; c = f, f = HTf.parent) if (HTf.lchild = c) /*c是其双亲的左孩子*/ cd-start = 0; else cd-start = 1; HCi = (char*)malloc(n - start) *sizeof(char); strcpy(HCi, &cdstar

20、t); / 从cd复制编码(串)到HC free(cd); / 释放工作空间/-打印赫夫曼树的函数-void coprint(HuffmanTree start, HuffmanTree HT) if (start != HT) FILE *TreePrint; if (TreePrint = fopen(TreePrint.txt, a) = NULL) cout 创建文件失败 rchild, HT); cout setw(5 *numb) weight weight); coprint(HT + start-lchild, HT); numb-; fclose(TreePrint); vo

21、id Tree_printing(HuffmanTree HT, int w) HuffmanTree p; p = HT + w; cout 下面打印赫夫曼树 endl; coprint(p, HT); cout 打印工作结束 endl;/-主函数-void main() char choice; while (choice != q) cout 哈夫曼编码解码系统 endl; cout 1.初始化哈夫曼树 2.编 码 功 能 endl; cout 3.译 码 功 能 4.打印哈夫曼树 endl; cout 5.退 出 系 统 endl; cout choice; switch (choic

22、e) case 1: Initialization(); break; case 2: InputCode(); Encoding();break; case 3: Decoding(); break; case 4: Tree_printing(HT, 2 *n - 1); break; case 5: default: cout input error endl; free(z); free(w); free(HT);参考文献1邓又明，数据结构（第一版），北京，地质出版社，2007年8月。2刘天印，C语言程序设计（第一版），北京，科学出版社，2007年3月。3严蔚敏，吴伟民编著，数据结构（

23、C语言版），北京；清华大学出版社，20054严蔚敏，陈文博编著，数据结构及应用算法教程，北京；清华大学出版社，20065谭浩强编著， C语言程序设计（第二版），北京；清华大学出版社，2003 课程设计成绩评定表1、课程设计答辩或质疑记录1）2）3）2、答辩情况a）未能完全理解题目，答辩情况较差 b）部分理解题目，答辩情况较差 c）理解题目较清楚，问题回答基本正确 d）理解题目透彻，问题回答流利 3、课程设计报告a）内容： 不完整 完整 详细 b）方案设计： 较 差 合理 非常合理 c）实现： 未实现 部分实现 全部实现 d）文档格式： 不规范 基本规范 规范 考勤成绩： ，占总成绩比例10%答辩成绩： ，占总成绩比例30%课程设计论文成绩： ，占总成绩比例60%课程设计总成绩： 指导教师签字： 年 月 日15