数据结构与算法实验报告 姓名：孙瑞霜
一、实验目的
1、复习Huffman树及其创建等基本操作；
2、掌握最小堆的定义及其建立、插入删除等操作的实现。
3、掌握Huffman编码的方法。
二、实验要求：
1． 认真阅读和掌握教材上和本实验相关的内容和算法。
2． 上机将相关算法实现。
3． 实现上面实验目的要求的功能，并能进行简单的验证。
三、实验内容
1、 必做内容：Huffman树的创建
按照课本上最小堆（代码4.26，改成最小堆）及建立Huffman树的算法（代码4.27），编程实现Huffman树的建立。要求能够进行简单的输入输出验证，输出建好后的Huffman树的形态，比如输出其先序和中序遍历序列。
typedef struct TreeNode *HuffmanTree;
struct TreeNode{
int Weight;
HuffmanTree Left;
HuffmanTree Right;
};
2、 选做内容：实现Huffman编码，并进行简单输入输出验证，比如输入一些字符及其权值，输出每种字符的Huffman编码。可以查阅资料，结合程序进行分析,其存储结构及其操作上和建立Huffman树有何异同。
三、算法描述
首先我们应明确什么是哈夫曼树，假设有n个权值，构造有n个叶子结点的二叉树，每个叶子结点的权值是n个权值之一，其中带权路径长度最小的一棵就是哈夫曼树。在哈夫曼树的构造过程中，选取两棵根结点权值最小的树作为左、右子树，每次将权值最小的两棵树进行合并，构造成一棵新的二叉树，置新二叉树根结点的权值等于左、右子树根结点的权值之和。从集合中删除作为左、右子树的两棵二叉树，并将新构造的二叉树加入到集合中；重复操作，直到集合中只含一棵二叉树为止，这棵二叉树便是要建立的哈夫曼树。
四、详细设计
五、程序代码
#include<stdio.h>
#include<stdlib.h>
#define MinData -1
typedef struct TreeNode *HuffmanTree;//哈夫曼树类型
struct TreeNode{
int Weight; //结点权值
HuffmanTree Left;//指向左子树
HuffmanTree Right;//指向右子树
}HuffmanNode;//定义新的结构变量
typedef struct HeapStruct *MinHeap;
struct HeapStruct{
HuffmanTree *Data; //存储堆元素的数组 存储时从下标1开始
int Size; //堆的当前元素的个数
int Capacity; //堆的最大容量
};
HuffmanTree NewHuffmanNode();
//构造新的哈夫曼树
MinHeap CreateMinHeap(int MaxSize);
//创建容量为MaxSize的最小堆
bool Insert(MinHeap H,HuffmanTree item);
//将元素item插入到最小堆H中
HuffmanTree DeleteMin(MinHeap H);
//从最小堆H中取出权值为最小的元素，并删除一个结点
MinHeap BuildMinHeap(MinHeap H);
//将H->data[]按权值调整为最小堆
HuffmanTree Huffman(MinHeap H);
//最小堆构造哈夫曼树
void PreOrderTraversal(HuffmanTree BST);
//先序遍历哈夫曼树
int main()
{
int i,N;
MinHeap h;
HuffmanTree T,BT = NULL;
printf("输入叶子结点的个数:\n");
scanf("%d",&N);
h = CreateMinHeap(2*N); //创建最小堆
printf("输入%d个叶子结点对应的权值:\n",N);
for(i=1; i<=N; i++){/*最小堆元素赋值*/
T = NewHuffmanNode();
scanf("%d",&(T->Weight));
h->Data[++(h->Size)] = T;
}
BT = Huffman(h); //构造哈夫曼树
printf("先序遍历此哈夫曼树:\n");
PreOrderTraversal(BT); //先序遍历哈夫曼树
return 0;
}
/*哈夫曼树构造算法*/
HuffmanTree Huffman(MinHeap H)
{/*假设H->Size个权值已经存在H->data[]->Weight里*/
int i,n;
HuffmanTree T;
BuildMinHeap( H ); //将H->data[]按权值调整为最小堆
/*此处必须将H->Size的值交给num,因为后面做DeleteMin()和 Insert()函数会改变H->Size的值*/
n = H->Size;
for(i=1; i<n; i++){ //做 H->Size-1次合并
T = NewHuffmanNode(); //建立一个新的根结点
T->Left = DeleteMin(H); //从最小堆中删除一个节点，作为新T的左子结点
T->Right = DeleteMin(H); //从最小堆中删除一个节点，作为新T的右子结点
T->Weight = T->Left->Weight+T->Right->Weight; //计算新权值
Insert(H,T); //将新T插入到最小堆
}
T = DeleteMin(H);
return T;
}
//先序遍历哈夫曼树
void PreOrderTraversal(HuffmanTree BST)
{
if( BST ){
printf("%d ",BST->Weight); //先访问根节点
PreOrderTraversal(BST->Left); //再访问左子树
PreOrderTraversal(BST->Right); //最后访问右子树
}
}
HuffmanTree NewHuffmanNode()
{
HuffmanTree BST = (HuffmanTree)malloc(sizeof(HuffmanNode));
BST->Weight = 0;
BST->Left = BST->Right = NULL;
return BST;
}
MinHeap CreateMinHeap(int MaxSize)
{ /*创建容量为MaxSize的最小堆*/
MinHeap H = (MinHeap)malloc(sizeof(struct HeapStruct));
H->Data = (HuffmanTree *)malloc((MaxSize+1) * sizeof(HuffmanTree));
H->Size = 0;
H->Capacity = MaxSize;
HuffmanTree T = NewHuffmanNode();
T->Weight = MinData; /*定义哨兵-为小于堆中所有可能元素权值的值，便于以后更快操作*/
H->Data[0] = T;
return H;
}
//插入新增节点
bool IsFull(MinHeap H)
{
return (H->Size == H->Capacity);
}
bool IsEmpty(MinHeap H)
{
return (H->Size == 0);
}
bool Insert(MinHeap H,HuffmanTree item)
{ //将元素item插入到最小堆H中
int i;
if( IsFull(H) ){
printf("最小堆已满\n");
return false;
}
i = ++H->Size; //i指向插入后堆中的最后一个元素的位置
for(; H->Data[i/2]->Weight > item->Weight; i/=2) //无哨兵，则增加判决条件 i>1
H->Data[i] = H->Data[i/2]; //向下过滤结点
H->Data[i] = item; //将item插入
return true;
}
HuffmanTree DeleteMin(MinHeap H)
{/*从最小堆H中取出权值为最小的元素，并删除一个结点*/
int parent,child;
HuffmanTree MinItem,temp = NULL;
if( IsEmpty(H) ){
printf("最小堆为空\n");
return NULL;
}
MinItem = H->Data[1]; //取出根结点-最小的元素-记录下来
//用最小堆中的最后一个元素从根结点开始向上过滤下层结点
temp = H->Data[H->Size--]; //最小堆中最后一个元素，暂时将其视为放在了根结点
for(parent=1; parent*2<=H->Size; parent=child){
child = parent*2;
if((child != H->Size) && (H->Data[child]->Weight > H->Data[child+1]->Weight)){
/*有右儿子，并且左儿子权值大于右儿子*/
child++; //child指向左右儿子中较小者
}
if(temp->Weight > H->Data[child]->Weight){
H->Data[parent] = H->Data[child]; //向上过滤结点-temp存放位置下移到child位置
}else{
break; //找到了合适的位置
}
}
H->Data[parent] = temp; //temp存放到此处
return MinItem;
}
MinHeap BuildMinHeap(MinHeap H)
{
int i,parent,child;
HuffmanTree temp;
for(i=H->Size/2;i>0;i--){ //从最后一个父结点开始，直到根结点
temp = H->Data[i];
for(parent=i; parent*2<=H->Size; parent=child){
/*向下过滤*/
child = parent*2;
if((child != H->Size) && (H->Data[child]->Weight > H->Data[child+1]->Weight)){/*有右儿子，并且左儿子权值大于右儿子*/
child++; //child指向左右儿子中较小者
}
if(temp->Weight > H->Data[child]->Weight){
H->Data[parent] = H->Data[child]; //向上过滤结点-temp存放位置下移到child位置
}else{
break; //找到了合适的位置
}
}/*结束内部for循环对以H->data[i]为根的子树的调整*/
H->Data[parent] = temp; //temp存放到此处
}
return H;
}
六、测试和结果
测试用例：课本154页哈夫曼树的生成过程
七、用户手册
打开devC++，新建一个源程序，拷贝5部分的代码进去，点击运行，在出现的界面中按照提示输入数据，一步步按下回车键即可运行该程序，最后测试完毕，关闭界面。