文档介绍：数据结构课程设计
设计说明书
哈夫曼编码的实现
学生姓名
学号
班级
成绩
指导教师
计算机科学与技术系
2009年 3 月 2 日
数据结构课程设计评阅书
题目
哈夫曼编码的实现
学生姓名
学号
指导教师评语及成绩
成绩: 教师签名: 年月日
答辩教师评语及成绩
成绩: 教师签名: 年月日
教研室意见
总成绩: 室主任签名: 年月日
注:指导教师成绩60%,答辩成绩40%,总成绩合成后按五级制记入。
课程设计任务书
2008 —2009 学年第一学期
专业: 信息管理与信息系统学号: 姓名:
课程设计名称: 数据结构课程设计
设计题目: 哈夫曼编码的实现
完成期限:自 2009 年 2 月 23 日至 2009 年 3 月 6 日共 2 周
设计依据、要求及主要内容(可另加附页):
利用哈夫曼编码进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。
基本要求:
将权值数据存放在数据文件(,位于执行程序的当前目录中);
初始化:键盘输入字符集大小n、n个字符和n个权值,建立哈夫曼树;
编码:利用建好的哈夫曼树生成哈夫曼编码;
输出编码;
设字符集及频度如下表:
字符空格 A B C D E F G H I J K L M
频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20
字符 N O P Q R S T U V W X Y Z
频度 57 63 15 1 48 51 80 23 8 18 1 16 1
可以根据题目要求把程序划成不同的模块,设计成菜单方式,每次执行一个模块后返回菜单。作出本算法的流程图和主要模块。
指导教师(签字): 教研室主任(签字):
批准日期: 年月日
摘要
针对减少通信系统中字符编码所需要的二进制位长度,提出用于产生不定长的前缀编码算法,所谓前缀编码是指任一编码都不是其他编码的前缀。前缀编码算法的基本事项就是对于出现概率较大的字符采用短编码方式,而出现概率较小的字符采用长编码方式。在网络传输数据过程中个别数据出现的次数特别多,而有些则不怎么出现。如果对数据用同样的长度定义则会造成相当大的浪费,因而需要构建一种可根据数据出现频率生成长度不同但又不会在传输过程中出现混淆的编码。哈夫曼编码就是能完成这项工作的一种编码。而此次设计的哈夫曼树编码器,具有将输入的字符以及权值转换成对应哈夫曼编码的功能。本编码器采用C++作为软件开发环境,采用建立哈夫曼树来实现编码。提供了数据导入并完成编码、输出执行结果即哈夫曼编码这两个功能。
关键词:函数;树;哈夫曼;编码;文件
目录
1 课题描述 1
2 问题分析和任务定义 2
3 逻辑设计 3
4 详细设计 4
5 程序编码 6
6 程序调试与测试 10
7 结果分析 12
8 总结 14
参考文献 15
1 课题描述
哈夫曼树,又称最优树,是一类带权路径最短的树。
哈夫曼算法能够使得其构造出的二叉树的WPL值最小,从而保证在通信过程中,传输二进制位总长度最短。该算法主要是根据给定的不同字符的出现频率(频次)建立一颗最优二叉树。
由哈夫曼树设计电文总长最短的二进制前缀编码并以n种字符出现的频率作权即为哈夫曼编码。
所设计的哈夫曼编码器,具有从外部文件中读入任意数量的字符和权值(字符和权值的数量要匹配)并能对每个字符输出相应的哈夫曼编码的功能,目的在于将通讯时需要传输的字符通过该编译器转换成相应的二进制代码。利用哈夫曼编码进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。
2 问题分析和任务定义
求解n个字符的哈夫曼编码其实就是构建一颗有n个叶子结点的哈夫曼树,首先要确定的是哈夫曼树的结点结构问题。
自定义结点结构类型:
typedef struct // 结点数据结构
{
char elem; // 结点信息
int m_weight; // 存放权值
int parent,lchild,rchild; // 双亲结点,左孩子,右孩子
};
其次,根据哈夫曼树的特点可知,其中没有度为1的结点,所以当一颗哈夫曼树有n个结点时,推出总结点数为2*n-1个,可以用大小为2*n-1的一维数组来储存它。
程序主要算法:使用贪心算法构造最有前缀码的编码。
贪心算法采用的是逐步构造最优解的方法:在当前状态下一旦选定一个分量,就不再重试其他的可行性;它并不从整体最优上作出考虑,它的选择只是在贪心准则下的局部最优选择。
3 逻辑设计
图 哈夫曼编码流程图
4 详细设计
//哈夫曼编码伪代码