第四次数据结构作业.docx

数据结构作业之
-----------------Huffman二叉树的使用
班级: 070921
姓名: 刘言明
学号: 07092030
报告名称: Huffman二叉树的使用
上机时间: 2010/10/22
报告时间: 2010/10/24
摘要
实验目的:
加深理解树及二叉树的逻辑结构、存储结构
掌握树及二叉树上基本运算的实现
学会使用Huffman编码对数据进行无损压缩的原理
理解Huffman二叉树的概念
一步理解和熟练掌握课本中所学的各种数据结构,学会如何把学到的知识用于解决实际问题
实验方法:
利用哈夫曼二叉树用关知识,和最优二叉树解法,综合考虑各种因素,定义结构体变量,和其它函数的综合运用来实现对输入的数字考虑权值用二叉树方法表示,并利用哈夫曼编码的知识,将其转化成为最优二叉树,求出编码表示数,输入字符将其转化为编码,并进行译码,并用函数输入最后结果。
实验结果:
读入输入字符的总数
分别读入每个结点的值和权值
构造最优二叉树,输出哈夫曼编码
读入一串字符,将字符转化成编码形式
再通过编码进行译码,得到翻译后的字符并比对
内容
问题重述
读入个一个ASCII文件
统计文档中字符出现的频度,并根据频度对每个字符生成Huffman编码
打印原始数据、每个字符对应的Huffman编码以及原文档的Huffman编码
按Huffman树对编码后的数据进行解码
验证解码的结果
输出一些统计数据:总编码长度、编码效率等
算法描述
首先,定义结构体变量,实现对哈夫曼二叉树的构造。
其次,构造其他函数,分别实现输入,输出,排序,转化等方法。
最后,通过函数和结构体的综合调用,实现题目的要求。
函数说明
结构体定义说明

typedef struct
{
int weight;
char ch;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef struct
{
char ch;
char *chs;
}HuffmanCode;

typedef struct
{
char ch;
int weight;
}sw;
typedef struct
{
HuffmanTree HT;
HuffmanCode *HC;
}huf;
其它函数说明
void select(HTNode * HT,int n,int *n1,int *n2)函数:
选择在给定权值的两个结点中选择最小的权值的结点,其中*n1和*n2分别用来储存两个结点
huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF)函数:
主要进行哈夫曼编码,其中w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC。
void transcode(HuffmanTree ht,char *chars2,char*chars3)函数:
进行译码的工作,将输入的字符根据哈夫曼编码进行译码
执行结果
input the