精品归纳
哈夫曼编码译码系统实验报告-数据结构课程设
计
[键入文档副标题]
姓名：鉏飞祥
学号：E
专业：软件工程
完成日期
2016/7/4
计算机科学与技术学院
1 .需求分析
问题描述
•问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。
基本要求
(1) 输入的形式和输入值的范围；
(2) 输出的形式；
(3) 程序所能达到的功能。
1.基本要求
（1）初始化（Initialzation）。从数据文件中读入字符及每个字符的权值，建立哈夫曼树HuffTree；
（2）编码（EnCoding）。用已建好的哈夫曼树，对文件中的文本进行编码形成报文，将报文写在文件中；
（3）译码（Decoding）。利用已建好的哈夫曼树，对文件中的代码进行解码形成原文，结果存入文件中；
（4）输出（Output）。输出中出现的字符以及各字符出现的频度（或概率）；输出及其报文；输出及其原文；
2. 概要设计
说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。
(1)数据结构
哈夫曼树的节点
struct huff
{
int weight;
int parent;
int l;
int r;
};
哈夫曼编码的存储
struct huff *hufftree;
(2)程序模块
选择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 9
重复第一步：
11 16
27
重复第一步：
16
则此时建立的是优有二叉树，约定定左子树边编码为1，右子树编码为0，则可以对次二叉树进行编码，如图：
1 0
1 0
则各顶点的编码为：
V1 01
V2 1
V3 001
V4 000
2：将原文编码：
逐个从文件读入字符，根据已经建立好的哈夫曼树，找到每一字符对应的编码
3：将报文译码：
步骤一：
先读入一个字符，存入匹配字符串
步骤二：
根据匹配串找所有的哈夫曼编码，如果找到对应的编码，则输入该编码所对应的字符，如果找不到，则读入两个字符存入匹配串，重复步骤二，找到为止。
步骤三：
把剩下的字符重复步骤一二
4. 测试与分析
调试过程，不可能错的分配空间的语句却莫名的让整个程序崩溃，关于编译原理和内存分配的各种问题太欠缺。学了计算机组成原理与体系结构也不知道
比如在自定义函数中：
Char **c;
C=(char **)malloc(4*sizoef(char *));
C[2]=(char *)malloc(4*sizeof(char));
这样竟然会让程序这执行到这一句时崩溃，本来不可能有错误的。
而这句如果写在主函数中，就不会有问题。
分配的空间不大，不可能是内存不够用。
解决的方法是分开，把
C=(char **)malloc(4*sizoef(char *));
放在主函数中，另外一句不变依然在自定义函数中。
malloc和free尽量配对使用，注意：malloc后通常要对返回值进行判断，避免发生不必要的错误。
注意，最好再p 被free掉后，加上p=NULL这句
“野指针”不是NULL指针，是指向“垃圾”内存（不可用内存）的指针。人们一般不会错用NULL指针，因为用if语句很容易判断。但是“野指针”是很危险的，if无法判断一个指针是正常指针还是“野指针”。有个良好的编程习惯是避免“野指针”的唯一方法。
指针p被free或者delete之后，没有置为NULL，让人误以为p 是个合法的指针。别看free和delete的名字（尤其是delete），
它们只是把指针所指的内存给释放掉，但并没有把指针本身干掉。此时指针指向的就是“垃圾”内存。释放后的指针应立即将指针置为NULL，防止产生“野指针”
malloc函数动态申请的内存空间是在堆里(而一般局部变量存于栈里)，并且该段内存不会被初始化，与全局变量不一样，如果不采
用手动free()加以释放，则该段内存一直存在，直到程序退出才被
系统，所以为了合理使用内存，在不适用该段内存时，应该调用free()。另外，如果在一个函数里面使用过malloc，最好要配对使用free，
否则容易造成内存泄露（没有将内存还给自由存储区）。
但是，往往会在free的时候发生段错误.
