《赫夫曼编译码器的实现数据结构课程设计报告》由会员分享，可在线阅读，更多相关《赫夫曼编译码器的实现数据结构课程设计报告（20页珍藏版）》请在金锄头文库上搜索。
1、1数据结构课程设计报告数据结构课程设计报告题 目：赫夫曼编/译码器的实现学生姓名： 学 号： 所在学院： 班 级： 指导教师： 职 称： 2010 年 6 月 25 日攀枝花学院本科学生课程设计任务书攀枝花学院本科学生课程设计任务书2题 目哈夫曼编译码器1、课程设计的目的 1)使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和 操作实现算法，以及它们在程序中的使用方法。 2)使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3） 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。2、课程设计的内容和要求（包括原始数据、
2、技术要求、工作要求等） 问题描述：哈夫曼编译码器基本要求： 1.初始化，键盘输入字符集大小 n，n 个字符和 n 个权植，建立哈夫曼树。2.编码，利用建好的 huffman 树生成 huffman 编码；3.输出编码；4.译码功能；5.字符和频度如下： 字符 空格 A B C D E F G H I J K L M N O P Q 频度 186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1 字符 R S T U V W X Y Z 频度 48 51 80 23 8 18 1 163、主要参考文献 1刘大有等， 数据结构 （C 语言版） ，高等
3、教育出版社 2严蔚敏等， 数据结构 （C 语言版） ，清华大学出版社 3William Ford，William Topp， Data Structure with C+清华大学出版社 4苏仕华等，数据结构课程设计，机械工业出版社4、课程设计工作进度计划 第 1 天 完成方案设计与程序框图 第 2、3 天 编写程序代码 第 4 天 程序调试分析和结果 第 5 天 课程设计报告和总结指导教师（签字）日期年 月 日教研室意见：年 月 日学生（签字）： 接受任务时间： 2010年 6 月 25 日3课程设计（论文）指导教师成绩评定表课程设计（论文）指导教师成绩评定表题目名称哈夫曼编译码器评分项目分
4、值得 分评价内涵01学习态度6遵守各项纪律，工作刻苦努力，具有良好的科学 工作态度。02科学实践、调研7通过实验、试验、查阅文献、深入生产实践等渠 道获取与课程设计有关的材料。工 作 表 现 20%03课题工作量7按期圆满完成规定的任务，工作量饱满。04综合运用知识的能力10能运用所学知识和技能去发现与解决实际问题， 能正确处理实验数据，能对课题进行理论分析， 得出有价值的结论。05应用文献的能力5能独立查阅相关文献和从事其他调研；能提出并 较好地论述课题的实施方案；有收集、加工各种 信息及获取新知识的能力。06设计（实验）能力，方案 的设计能力5能正确设计实验方案，独立进行装置安装、调试、
5、操作等实验工作，数据正确、可靠；研究思路清 晰、完整。07计算及计算机应用能力5具有较强的数据运算与处理能力；能运用计算机 进行资料搜集、加工、处理和辅助设计等。能 力 水 平 35%08对计算或实验结果的分析 能力（综合分析能力、技 术经济分析能力）10具有较强的数据收集、分析、处理、综合的能力。09插图（或图纸）质量、篇 幅、设计（论文）规范化 程度5符合本专业相关规范或规定要求；规范化符合本 文件第五条要求。10设计说明书（论文）质量30综述简练完整，有见解；立论正确，论述充分， 结论严谨合理；实验正确，分析处理科学。成 果 质 量 45%11创新10对前人工作有改进或突破，或有独特见解
6、。成绩指 导 教 师 评 语指导教师签名： 年 月 日4摘要摘要利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原） 。对于双工信道（即可以双向传输信息的信道） ，每端都需要一个完整的编/译码系统，试为这样的信息收发站写一个哈夫曼编译码系统。关键字：数据结构、哈夫曼编码5目录目录第一章第一章. 序言序言.1第二章问题分析与说明第二章问题分析与说明.1一功能分析一功能分析.1二问题描述与说明二问题描述与说明.1第第三三章章程程序序总总体体设设计计.2一设计思路及方案一设计思路
7、及方案.2二二. .设计的总体框架设计的总体框架.3第第四四章章 . .详详细细算算法法与与设设计计.5一一实实现现算算法法流流程程图图.5二哈夫曼编码的算法二哈夫曼编码的算法.6三文件的编码和解码三文件的编码和解码.8第第五五章章 . .程程序序调调试试与与运运行行结结果果.8第六章第六章. .课程设计总结课程设计总结.9第七章第七章. .参考文献参考文献.10第第八八章章 . .附附录录.111第一章第一章. 序言序言目的：目的：1、为了使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、为了使学生掌握软件设计的基本内容和
8、设计方法，并培养学生进行规化软件设计的能力。3、为了使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。意义：意义：通过数据结构课程设计，我掌握了赫夫曼编/译码器的实现所需要的各种知识，了解到了哈夫曼程序设计的基本原理和知识，我相信在以后的学习当中我会更加的喜欢计算机这门高新技术学科。第二章问题分析与说明第二章问题分析与说明一功能分析一功能分析利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一
9、个完整的编译码系统。因此为这样的信息收发站写一个哈夫曼码的编译码系统存在着相当大的必要。相关知识：数据结构、哈夫曼编码译码器、程序设计格式等。二问题描述与说明：二问题描述与说明：1.数据结构主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。2. 哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制
10、编码2称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。作为信息管理专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。3. 课程设计题目：哈夫曼编译码器任务和功能：（1）从终端读入字符
11、集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树的存储结构；（2）利用已经建好的哈夫曼树（如不在内存，则从文件 htmTree 中读入） ，对给定的 n 个字符正文进行编码，并输出结果。（3）利用已建好的哈夫曼树，对给定的一个哈夫曼编码进行译码，判断此编码对应的字符，并输出结果。4.问题分析该问题要求将输入的字符以及相应的权值建立哈夫曼树，并利用建好的哈夫曼树生成哈夫曼编码。把输入的字符按权值从小到大排序，挑出 2 个最小权值供哈夫曼编码调用，再将输入的字符以及他的权值，按照哈夫曼规则建立二叉树，从叶子到根逆向求编码，再使用循环,从根结点开始遍历输出。第第三三章章程程序序总总体体设设计
12、计一设计思路及方案一设计思路及方案1.哈弗曼树的构造根据哈夫曼树的定义，一棵二叉树要使其 WPL 值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。这种方法的基本思想是：（1）由给定的 n 个权值W1，W2，Wn构造 n 棵只有一个叶结点的二叉3树，从而得到一个二叉树的集合 FT1，T2，Tn；（2）在 F 中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；（3）在集合 F 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合 F 中；（4）重复（2） （3）两步，当 F 中只剩
13、下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。2.哈弗曼编码 设 S=d0,d1,d(n-1)为待编码的字符集，W=w0,w1,w(n-1)是S 中各字符在电文中出现的频率。现以 W 为权值，构造哈弗曼树。哈弗曼的每个叶子结点对应一个字符。在哈弗曼树的每个结点到其左孩子的边上标上 0，到其右孩子的边上标上 1。将从根的每个叶子的路径上的数码连接起来，就是该叶子所代表的字符编码。因此，设计电文总长最短的二进制前缀编码，就是以 n 种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。3.哈弗曼译码译码过程为：自左向右逐一扫描码文，并从哈弗曼树的根开始，将扫描得到的二进制位串中的相邻位于哈弗曼树上标的 0，1 相匹配，以确定一条从跟到叶子结点的路径，一但到达叶子，则译出了一个字符；再回到树根，从二进制的下一位开始继续译码4.该系统将实现以下几大功能：从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树的存储结构；利用已经建好的哈夫曼树（如不在内存，则从文件 htmTree 中读入） ，对给定的 n 个字符正文进行编码，
