中国科大高分哈夫曼树实验报告：Huffman编码和译码

数据结构 实验报告 中国科大 高分

哈夫曼树实验报告

2011.4.22

实验题目： 编码和译码。

实验目的：1、练习树和哈夫曼树的有关操作，和各个算法程序。

2、理解哈夫曼树的编码和译码

实验内容:

一、 抽象数据类型：

ADT {

数据对象 : D={带有各自实数W(D)的数据元素}

数据关系：(1) D=NULL 则 tree 不存在

//判断树是否存在

(2) D≠NULL R={H}.H为如下二元关系：

//如果存在，假设R为其元素名称，H为里边所有元素①D中存在唯一根数据元素root,这个元素无前驱。

//如果只有一个元素，则为根元素②D-{root} ≠NULL.则存在D-{root} ={D1，Dr}.且D1∧Dr=NULL

//如果除了根元素还有别的元素，那么会有D1和Dr两部分，并且两者的交集为空，也就是两者是独立的。③若D1 ≠NULL，则D1 中存在唯一元素xr,∈H

//如果D1部位空集，则会有一个元素xr，且存在Dr上关系Hr ∈H,H= {,< root, xr>,H1,Hr};④符合① ② ③的R的组合中，存在一个组合R’使D中所有结点到root长与其权值W(Di)相乘的和最小，此时的集合称为 tree.

基本操作：

void ( HT,int m,int *s1,int *s2)

//比较得到权最小的两棵树。用指针指向所在位置。

*void (char *HC)

//将哈弗曼编码逐个打印出来

void ( HT)

//将哈夫曼树前后的结构打印出来

void ( HT, w)//建立哈夫曼树

元素 存在 D1 数据 实验 哈夫曼