课设哈弗曼编码/译码系统（数据结构）

哈弗曼编码/译码系统（数据结构）

一、 需求分析
1、 问题描述
利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，将信息还原成发送前的字符信息。
发送者的功能包括：
①输入待传送的字符信息；
②统计字符信息中出现的字符种类数和各字符出现的次数（频率
②根据字符的种类数和各自出现的次数建立哈夫曼树；
③利用以上哈夫曼树求出各字符的哈夫曼编码；
④将字符信息转换成对应的编码信息进行传送。
接受者的功能包括：
② 接收发送者传送来的编码信息；
②利用上述哈夫曼树对编码信息进行翻译， 即将编码信息还原成发送前的字符信息。
2、 输入输出形式及要求
2.1输入输出的范围
输入参数为一个密文，即一个字符串，和一个二进制编码，即密文。
输出格式按照题目要求进行输出，下面给出一个完整示例。

二 、概要设计
1、数据存储方式
typedef struct node
{
char letter; //字符
int weight; //权值
int parent; //父母结点
int lchild; //左孩子结点
int rchild; //右孩子结点
}HNodeType;
/字符编码类型/
typedef struct
{
char letter; // 字符
int bit[MAXBIT]; //数组，存放字符的哈夫曼编码
int start; //该编码在数组bit的开始位置
}HCodeType;
typedef struct
{
char s;
int num;
}Message;
2.程序函数
A．
函数名：HuffmanTree
功能：生成哈夫曼树
形参：HuffNode[]：哈夫曼树结点数组
n: 叶子结点个数(即有n种不同字符 ）
a[]: 字符串数组（是一个结构体数组），用来存储字符及其权值
返回值：void
B．
函数名：HuffmanCode
功能：生成哈夫曼编码并输出
形参：
n: 叶节点个数（即有n种不同字符）
a[]: 字符串数组（是一个结构体数组） ，用来存储字符及其权值
返回值：void
补充：用到的宏定义
#include<stdio.h>
#define use _CRT_SECURE_NO_WARNINGS//编译环境为VS2010
#define MAXVALUE 1000 //最大权值
#define MAXLEAF 30 //最大叶结点个数
#define MAXNODE MAXLEAF*2-1 //最大结点个数
#define MAXBIT 50
三 、详细设计
1、流程图
构造树
编码：
HuffmanCode函数
译码：
四 、测试与分析

五 、总结
在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码的应用很广泛，利用哈夫曼树求得用于通信的二进制编码称为哈夫曼编码。树中从根到每一个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各叶子对应的字符的编码，这就是哈夫曼编码。