《数据结构课程设计赫夫曼编译码器C》由会员分享，可在线阅读，更多相关《数据结构课程设计赫夫曼编译码器C（29页珍藏版）》请在金锄头文库上搜索。
1、赫夫曼编译码器摘要 本次课程设计过程中我主要根据课本中的实现思想及算法编写程序，表达以课本知识的应用为主，在学习了线性表、栈、队列、二叉树、树和图等结构的根底上，以能够更加熟练的应用所学知识，并能结合一些著名算法来实现对一些实际问题的应用，例如，赫夫曼树等，从而更为深刻理解数据结构的内涵，熟悉它们各自的应用场合及方法。有些在平时课程中并没有掌握的内容在这次课程设计中都是先通过看课本学懂了，然后再在课程设计中加深印象，实现算法的应用和扩展。这次课程设计的设计内容主要是通过实际的例子和程序来实现课本中所学习的算法的应用。程序设计设计语言采用C+,程序运行平台为Windows XP。赫夫曼编译码器的
2、主要功能是先建立赫夫曼树，然后利用建好的赫夫曼树生成哈夫曼编码后进行译码 。赫夫曼编译系统分为五个功能模块：原始数据载入，打印编码规那么、编码、译码。以二叉树的应用为根底，包括统计信息，并通过构建赫夫曼树、对信息进行赫夫曼编码，将编码信息等存入文档。关键字 数据结构 栈和队列 赫夫曼树 赫夫曼编码 目录1引言.1.1 .1.12需求分析.33 概要设计.43.1 设计思想43.2 函数间的关系444详细设计.6 4.1 赫夫曼的主要结构.65 调试分析.86 测试并列出测试结果.9 6.1 测试方式 9 6.2 测试结果.97 总结13致谢.14参考文献.14附录.151 引言当今社会，计算机
3、技术和通信技术已不断开展，处理和传输的数据量越来越庞大。如何采用有效的数据压缩技术引起了人们的极大重视。从而产生了哈夫曼编码，它是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据压缩20%至90%，通常我们将压缩技术称为编码，解压缩过程称为解码。树状结构简称为树，是一种以分支关系进行定义的层次结构，是十分重要的非线性数据结构，在计算机软件设计方面，有着广泛的应用。1.1 课程设计目的 本课程设计是为了让同学们了解数据结构的作用和意义。数据结构是计算机科学与技术专业、计算机信息管理与应用专业和电子商务的专业的根底课，是十分重要的课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结
4、构。因此，想要更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付当前众多复杂的课题，想要有效地使用计算机，充分发挥它的性能，还必须学习和掌握好数据结构的有关知识，打好数据结构这门课的扎实根底，对于学习计算机专业的其他课程，如操作系统、软件工程、编译原理、人工智能等十分有益。1.2 课程设计背景当今社会，计算机技术和通信技术已不断开展，处理和传输的数据量越来越庞大。如何采用有效的数据压缩技术引起了人们的极大重视。从而产生了哈夫曼编码，它是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据压缩20%至90%，通常我们将压缩技术称为编码，解压缩过程称为解码。树状结构简称为树
5、，是一种以分支关系进行定义的层次结构，是十分重要的非线性数据结构，在计算机软件设计方面，有着广泛的应用。在这信息量兴旺的时代，随着社会的进步，信息不断地增多和更新，为了使信息更加快速、准确有的传递。需要一个程序来完成。 1.3课程设计主要内容本课程设计要求完成发送端对待传送数据的编码和接收端对传送来的数据的译码。要实现五个功能:接受原始数据、编码、译码、打印编码规那么、将编码、译码存档。通过系统的提示要建立哈夫曼树并对载入的原文件进行编码，并保存到txtfile.txt文件中，同时输出到屏幕。最后将建立的赫夫曼树用某种树的储存方式储存后输出。2 需求分析一套完整的编码译码系统应该具有以下功能：
6、1I：初始化initialization。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树。并将他存于文件hfmtree.txt中。(2)E：编码encoding。利用已经建立好的赫夫曼树如不在内存，那么从文件hfmtree.txt中读入，对文件tobetree.txt中的正文进行编码。然后将结果存入文件codefile.txt文件中。(3)D：译码decoding。利用已经建立好的赫夫曼树将文件codefile.txt中的代码进行译码，将结果存入文件textfile.txt中。4P：印代码文件print。将文件codefile.txt以紧凑格式显示在终端上。每行50个代码。同时将
7、字符形式的编码文件写入到文件codeprin.txt中。3 概要设计3.1 设计思想赫夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。3.2 函数间的关系 函数间的关系如图3.1所示：主函数显示表头初始化树输入字符编码译码打印编码打印赫夫曼树选最小两个权值Select()图3.1 函数间的关系3.3 数据结构与算法设计赫夫曼编译码器的主要功能是先建立赫夫曼树，然后利用建好的赫夫曼树生成赫夫曼编码后进行译码 。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵赫夫曼树，规定赫夫曼树中的左分之代表0，右分支代表1，那么从根节点到每个叶子节点所经过的
8、路径分支组成的0和1的序列便为该节点对应字符的编码，称之为赫夫曼编码。最简单的二进制编码方式是等长编码。假设采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。赫夫曼树课用于构造使电文的编码总长最短的编码方案。其主要流程图如图3.2所示。开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I2*N?I+编码为1结束否否否右子是否为空是是否否是是是图3.2 赫夫曼树编译码器流程图4 详细设计赫夫曼树编、译码设
9、计功能如下：1赫夫曼树抽象数据类型定义ADT HuffmanCoding数据对象T：具有相同特性的数据元素的集合数据关系R：满足最优二叉树的关系根本操作P：Init&t操作结果：构造一个空赫夫曼树t。encode()操作结果：利用赫夫曼树进行编码Decode操作结果：利用赫夫曼树进行译码2. 主函数Void mian打印表头；While(选择项不为q)输入选择项；Switch(选择项)Case i： 初始化；break;Case w： 输入要编码的字符； break；Case e： 编码字符； break；Case d； 译码操作；break；Case p； 打印代码；break；Case t
10、； 打印赫夫曼树； break；Default：输入错误，重新选择；3. 求赫夫曼编码5 if(tj.weightk&tj.parent=0) k=tj.weight,flag=j; /flag为标志符，为不小于可能的值tflag.parent=1; 4. 建赫夫曼树 HTs1.parent=HTs2.parent=i;/将选好的两个结点设置成有同一个双亲结点 HTi.lchild=s1;/左孩子的权值 HTi.rchild=s2;/右孩子的权值 HTi.weight=HTs1.weight+HTs2.weight;/将两个权值相加作为新的权值 HC=(HuffmanCode)malloc(n
11、+1)*sizeof(char*);/为赫夫曼代码分配空间 5. 将赫夫曼编码写入文件用fputs(HCi,htmTree); fputs(r,htmTree);fclose(htmTree) 这些函数来实现编码写入文件; 6. 完成译码功能并将译码写入文件 因为赫夫曼树建好后是左孩子结点旁标上0，右孩子结点上标上1所以碰到1是用左孩子结点，2是用右孩子结点，可以用条件语句来实现。 if(i2=0) m=HTm.lchild; if(i2=1) m=HTm.rchild;fputs(outext,txtfile);/将译码写入文件5 调试分析1本程序要执行首先要初始化一个赫夫曼树，按照用户设定
12、的字符集大小，输入每个字符及其对应的出现概率即权值。分别存放在w和z这两个变量中。再利用这两个变量构造赫夫曼树。2执行输入字符命令时，程序将用户输入的字符存入文件tobetran.txt中。以便执行下一步编码操作时自己从文件调用。3编码时，程序直接从tobetran.txt中读取字符，依次和字符数组变量z中元素项比拟，找到之后，将编码表HC中对应编号的代码添加到分配的工作区间中，全部字符编码完成后将代码写入文件codefile.txt中。5打印编码操作，即从codefile.txt中读取代码，按要求输出到屏幕上。6 测试并列出测试结果6.1 测试方式 12程序运行后，出现的界面如图6.1所示：图6.1 界面图3首先须进行初始化，按“i执行，输入字符集数，对应的字符和权值，初始化赫夫曼树。然后才能进行后续的操作。4选择“w，输入要编码的字符。5选择“e，对刚输入的字符进行编码。6选择“d，对刚编码出的代码再译码回去。7选择“p，打印编码出的代码。8选择“t，代印赫夫曼树9选择“q，退出程序。6.2 测试结果6.1所示：表6.1 初始化的内容“ABCDEFG
