哈夫曼编码译码器课程设计.docVIP

学 年 设 计 报 告 设计题目 哈夫曼树的建立与实现 作者姓名 所学专业 网络工程 指导教师 2011年8月23日 学年设计任务书 课程设计题目 组长 学号 班级 别 专业 网络工程 组员 指导教师 设 计 目 的 设计所需环境 Windows XP VC++ 6.0 设计任务要求 ⑴ 收集有关的资料，对如何构建哈夫曼树有了更加清晰的认识，为哈夫曼树的编写提供了基本的框架。 ⑵ 将所输入的数据信息进行编码构造成哈夫曼树。 ⑶ 代码的编写和对每段的编码的解释使得源代码更具可读性。 学年设计工作进度计划 序号 起止日期 工 作 内 容 分工情况 1 2 2011年8月26日~ 2011年8月27日 查找资料对哈夫曼树相关的类型变量的定义 3 2011年8月27日~ 2011年8月28日 收集图片和生成哈夫曼树并写入文件 4 2011年8月28日~ 2011年8月29日 编写主函数以及修改文件的编辑 5 2011年8月29日~ 2011年8月29日 构建哈夫曼树和收集相关资料 6 2011年8月29日~ 2011年8月31日 编辑代码分配任务等其他相关事宜 指导教师签字： 年 月 日 教研室审核意见： 教研室主任签字： 年 月 日 目 录1 引 言 4 2 需求分析 4 3 概要设计 4 3.1 设计思路及方案 4 3.2 模块的设计及介绍 5 4 详细设计 8 4.1 主调函数 8 4.2 建立HuffmanTree 9 4.3生成Huffman树并写入文件 10 5 调试与操作说明 11 5.1读出文本 11 5.2输出哈夫曼树存储结构的初态 12 5.3输出哈夫曼树存储结构的终态 12 5.4输出哈夫曼树构成后的抽象图 14 6 学年设计总结与体会 14 7 参考文献 15 8 致谢 15 9 附录 15 学年设计的主要内容 1 引 言 随着当今信息技术的发展，为了方便和节省信息的存储和传递速度，人们便创建了哈夫曼编码。哈夫曼编码是将文件进行压缩的一种压缩方法。哈夫曼编码的最大的功能是能够用更少的内存空间来存储更多的信息。若要对文件进行编码则必须对其建立哈夫曼树，其次对这个哈夫曼树进行编码。本学年设计的主要目标就是对如何建立哈夫曼树和如何进行编码的一个详细介绍。 2 需求分析 问题描述：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它作为权值，对字符进行。 问题补充：⑴ 从硬盘的一个文件里读出一段英语文章； ⑵ 统计这篇文章中的每个字符出现的次数； ⑶ 以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储结构的初态和终态进行输出具体介绍：在E盘中预先建立一个filel.txt文档，在编辑一篇文章（大写）。然后运行程序，调用fileopen()函数读出该文章，显示在界面；再调用jsq()函数对该文章的字符种类进行统计，并对每个字符的出现次数进行统计，并且在界面上显示；然后以每个字符出现次数作为权值，调用ChuffmanTree()函数构建哈夫曼树并调用print1()和print2()函数将哈夫曼的存储结构的初态和终态进行输出 3 概要设计 3.1 设计思路及方案 假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为（W1*L1）+(W2*L2)+.......(Wi*Li)。若将此对应到二叉树上，Wi为叶结点，Li为根结点到叶结点的路径长度。那么，（W1*L1）+(W2*L2)+.......(Wi*Li) 恰好为二叉树上带权路径长度以n种字符出现的频率作权，构造一棵哈夫曼树。 该系统将实现以下几大功能：从硬盘读取字符串，建立哈夫曼树，输出哈夫曼树的存储结构的初态和终态。模块的设计及介绍 ⑴ 从硬盘读取字符串 ileopen(参数){ 实现命令； 打印输出；} ⑵ 建立HuffmanTree 通过三个函数来实现: void select(参数){初始化； for{ 接受命令； 处理命令； }说明：在ht[l.......k]中选择parent为0且权值最小的两个根结点的算法 int jsq（参数{