哈夫曼编码译码系统实验报告数据结
构课程设计
2020年4月19日
1
[键入公司名称]
[键入文档标题]
[键入文档副标题]
姓名：鉏飞祥 学号：E21414018 专业：软件工程
完成日期 2016/7/4
计算机科学与技术学院
文档仅供参考
1 .需求分析 1.1问题描述
? 问题描述：利用哈夫曼编码进行通信能够大大提高信
道利用率，缩短信息传输时间，降低传输成本。可是，这要求在发送端经过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即能够双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。
1.2基本要求
(1) 输入的形式和输入值的范围； (2) 输出的形式；
(3) 程序所能达到的功能。 1.基本要求
（1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree；
（2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中；
（3）译码（Decoding）。利用已建好的哈夫曼树，对文件
1
2020年4月19日
文档仅供参考
CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中；
（4）输出（Output）。输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data及其原文Textfile.txt；
2. 概要设计
说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。
(1)
数据结构
哈夫曼树的节点 struct huff {
int weight; int parent; int l; int r; };
哈夫曼编码的存储 struct huff *hufftree;
(2)
程序模块
2
2020年4月19日
选择1到i-1中parent为0且权值最小的两个下标
文档仅供参考
void Select(struct huff *HT, int n, int &s1, int &s2)
构建哈夫曼树：
void huffmancoding(struct huff *ht,int *w,int n) 对原文进行编码： void code(char *c) 根据报文找到原文：
void decoding(char *zifu)
3. 详细设计
核心技术分析：
1：构建哈夫曼树及生成哈夫曼编码：
根据每个字符权值不同，根据最优二叉树的构建方法，递归生成哈夫曼树，而且用数组存放哈夫曼树。
再从每一叶子节点向树根遍历，求得编码 例如：
如图所示的四个节点v1，v2，v3，v4，她们的权值分别为7，11,4,5
7 11 4 5
VVVV第一步：选择两个权值最小的节点作为左右子孩子，建立一个二叉树，双亲权值为两个自孩子之和，如图
3
2020年4月19日
哈夫曼编码译码系统实验报告数据结构课程设计
