huffmancode.cpp

霍夫曼编码前缀编码Huffman Coding

//----------------TreeNode.cpp---------------
#include "TreeNode.h"

//构造函数
template<class T>
TreeNode<T>::TreeNode()
{
}

//带参数的构造函数
template<class T>
TreeNode<T>::TreeNode(T& data, int weight, TreeNode<T> *pRight, TreeNode<T> *pLeft,
        TreeNode<T> *pParent):data(data),weight(weight),rchild(pLeft),
        lchild(pRight),parent(pParent)
{
}

//析构函数
template<class T>
TreeNode<T>::~TreeNode()
{
}

//访问结点的操作
template<class T>
TreeNode<T>* TreeNode<T>::Lchild()
{
return lchild;
}
template<class T>
TreeNode<T>* TreeNode<T>::Rchild()
{
return rchild;
}
template<class T>
TreeNode<T>* TreeNode<T>::Parent()
{
return parent;
}

//----------main----------
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <string.h>

#include "TreeNode.h"
#include "TreeNode.cpp"

template<class T>
TreeNode<T> *HuffmanTree(T data[], int weight[], int n);

//找出最小的元素
template<class T>
int FindMin(TreeNode<T> *Ht[], int n);

//显示Huffman树
template<class T>
void PrintTree(TreeNode<T> *Ht, int level);
void IndentBlanks(int num);

//Huffman编码
template<class T>
void HuffmanCode(TreeNode<T> *Ht[], int n);

struct hcodetype
{
     int bit[10];
     int start;
     char leaf;
};

void main()
{
char ch[8] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
int weight[8] = {1,2,3,4,5,6,7,8};
//生成Huffman树
TreeNode<char> *root = HuffmanTree(ch, weight, 8);
//显示Huffman树
PrintTree(root, 0);
}

//生成Huffman树 并返回树的根结点
template<class T>
TreeNode<T> *HuffmanTree(T data[], int weight[], int n)
{

TreeNode<T> *Ht[512]; //指向结点类的指针数组 0号位置不用
int sort[256];    //整型数组用于排序 用来存放指针数组的序列号
int i;      //循环变量
int m = 2*n-1;    //结点总数

memset(sort, 0, 4*256); //初始化排序数组
//初始化指针数组
if(n<=1) return NULL;
for(i=1; i<=m; i++)
{
   Ht[i] = new TreeNode<T>();
   Ht[i]->lchild = NULL;
   Ht[i]->rchild = NULL;
   Ht[i]->parent = NULL;
}
for(i=1; i<=n; i++)
{
   Ht[i]->data = data[i-1];
   Ht[i]->weight = weight[i-1];
   Ht[i]->flag = 0; //表示是否已经排过序
}

//按照Ht[]数组中weight的值进行排序 由小到大
for(i=0; i<n; i++)
   sort[i] = FindMin(Ht, n);

//-------------构造Huffman树的核心部分------------------//
int x=n;   //x表示新生成结点的位置 从Ht数组的n+1开始有n-1个新结点
while(n != 1) //当数组中仅有一个元素的时候结束循环
{
   //存放新结点的位置后移一个位置
   x++;
   //取sort数组中的前2个作为左右孩子初始化新结点
   Ht[x]->lchild = Ht[sort[0]]; 
   Ht[x]->rchild = Ht[sort[1]];
   Ht[sort[0]]->parent = Ht[x];
   Ht[sort[1]]->parent = Ht[x];
   Ht[x]->weight = Ht[sort[0]]->weight + Ht[sort[1]]->weight;
  
   //------将生成的新结点的序列号插入到排序数组中的正确位置-----//
  
   //将所有数据前移2个位置
   if(n != 2) 
    memmove(sort, sort+2, (n-2)*4);

   //除了最小和次小结点仅有一个结点的情况
   if(n == 2)
    sort[0] = x;
   for(i=0; i<n-2; i++)
   {
    //查找正确位置并将从该位置起的数据均后移一个位置将新结点序列号插入空出的正确位置
    if(Ht[sort[i]]->weight > Ht[x]->weight)
    {
     //把i后边的位置都向后移动一个单位
     memmove(sort+(i+1), sort+i, (n-i)*4);
     sort[i] = x;
     //移动一次后进应该跳出for循环因为数组本来是有序的
     break;
    }
    else
     //说明新结点是最大的插入到数组最后
     sort[n-2] = x;
   }
   //将数组大小减1
   n--; 
}
HuffmanCode(Ht, (x+1)/2);
return Ht[sort[0]];   //返回生成的Huffman树的根结点
}

//找出最小的元素
template<class T>
int FindMin(TreeNode<T> *Ht[], int n)
{
int i = 2;
int min = 65537; //定义最小值为一个较大的数
int j = 1;
for(i=1; i<=n; i++)
{
   if(Ht[i]->flag == 0 && min>Ht[i]->weight)
   {
    min = Ht[i]->weight;
    j = i;
   }
}
Ht[j]->flag = 1;
return j;
}

template<class T>
void PrintTree(TreeNode<T> *Ht, int level)
{
//当t!=NULL时，输出以t为根的树
if(Ht != NULL)
{
   //输出树的右半部分
   PrintTree(Ht->rchild, level+1);
   //缩进到当前层，输出结点的数据
   IndentBlanks(6 * level);
   cout<<Ht->data<<" "<<Ht->weight<<endl;
   //输出树的左半部分
   PrintTree(Ht->lchild, level+1);
}
}

void IndentBlanks(int num)
{
for(int i=0; i<num; i++)
   cout<<"   ";
}

template<class T>
void HuffmanCode(TreeNode<T> *Ht[], int n)
{
int i,j,c;
TreeNode<T> *p;
//Huffman编码
hcodetype *HuffCode=new hcodetype[n],cd;
for(i=1;i<=n;i++)
{
   cout<<Ht[i]->data<<": ";
   cd.start=n-1;
   c=i;
   p=Ht[c]->parent;
   while(p != NULL)
   {
    if(p->lchild == Ht[c])
     cd.bit[cd.start]=0;
    else
     cd.bit[cd.start]=1;
    cd.start--;
    Ht[c]=p;   //此处改变了data的值
    p=Ht[c]->parent;
   }
   for(j=cd.start+1;j<n;j++)
   {
    HuffCode[i].bit[j]=cd.bit[j];
    cout<<cd.bit[j];
   }
   cout<<endl;
   HuffCode[i].start=cd.start;
     }
}