哈夫曼编码译码报告.doc

烟台大学计算机与控制工程学院
课程设计
(数据结构与OOP)
设计题目:
班级
姓名
学号
指导教师
成绩
年月日
目录
1 题目 3
问题描述 3
基本要求 3
进一步完成 3
2 内容 3
基本需求 3
. 我的设计 4
3 算法设计 4
数据的存储结构 4
存放哈夫曼树的存储结构: 4
存放哈夫曼编码的存储结构: 4
存放哈夫曼树每个节点位置的存储结构: 5
生成哈弗曼树的算法 5
生成哈弗曼编码的算法 7
译码的算法 9
打印哈弗曼树的算法 10
其他算法 11
4 程序正确性验证 11
输入数据的控制 11
打印哈弗曼树 12
哈弗曼编码 12
哈弗曼译码 13
5 遇到的问题 13
6 课程设计的主要收获 13
7 对今后课程设计的建议 13
1 题目
问题描述
设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理项目,直到选择退出为止。
基本要求
1) 将权值数据存放在数据文件(,位于执行程序的当前目中
2) 分别采用动态和静态存储结构
3) 初始化:键盘输入字符集大小n、n个字符和n个权值,建立哈夫曼树
4) 编码:利用建好的哈夫曼树生成哈夫曼编码
5) 输出编码
6) 设字符集及频度如下表:
字符空格 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
进一步完成
1) 译码功能
2) 显示哈夫曼树
3) 界面设计的优化
2 内容
基本需求
编写一个哈夫曼编码/译码器,次编码/译码器有两大主要功能:一是对一段文本进行编码,比如在利用电报机发送信息时,需要将文字“DA”转换成类似“00110111001”这样的二进制组成的字符串;二是对一段密文进行译码,比如在接收电报后,需要对“0101110100101”这样的二进制密文通过某种标准译码成看得懂的文字信息。
另外还有一些辅助功能,比如可以打印一些简单的哈夫曼树的简图、有基本的
主菜单、简洁的操作界面、文件的读写。
. 我的设计
哈夫曼编码/译码器主要有五个功能:初步编码、文件编码、手动译码、文件译码、退出。
初步编码:实现基本的编码,打印简单的哈夫曼树。输入N个字符和N个权值,输出每个字符对应的编码并打印哈夫曼树。注意此功能只是对哈夫曼编码的初探,只完成了生成哈夫曼树和哈夫曼编码的功能并没有实现文件的编码。
文件编码:对一个特定的文件进行编码,。
手动译码:对手动输入的密文进行译码,译码标准可自定义或默认。
文件译码:对存放密文的文件进行译码,与手动译码的主要区别就是在密文的获取方法上。
退出:哈夫曼编码/译码器运行结束。
3 算法设计
数据的存储结构
存放哈夫曼树的存储结构:
typedef struct //存放树节点
{
char data; //节点代表的字符
int weight; //权值
int parent; //父节点
int lchild; //左孩子节点
int rchild; //右孩子节点
}HTNode;
存放哈夫曼编码的存储结构:
typedef struct //存放编码
{
char cd[60]; //
int start; //编码在数组中的开始下标
}HCode;
存放哈夫曼树每个节点位置的存储结构:
typedef struct //节点位置
{
char data;
int n;//在完全二叉树中的位置序号
}tree;
此存储结构的主要目的是记录哈弗曼树的每一个节点在完全二叉树上的位置序号,便于输出哈弗曼树的大致图形。
生成哈弗曼树的算法
算法思想:先将存有每个节点权值和数据的数组初始化,将每个节点的左右节点和父节点初始化为-1,保证每个节点都是独立的。假设有n 个节点,在建树时需要比较n-1次;在每一次的比较中,先找出两个权值最小的节点,将这两个节点作为孩子节点形成一个双亲节点并修改相应的属性值,形成的双亲节点的权值等于两孩子节点