huffman.h

这是一个霍夫曼编码解码的源程序,可以用它高效实现霍夫曼解码编码,注释详细,可读性好.压缩包止包括源程序文件,再vc中运行.

#include<iostream.h>
#include<stdio.h>
const int DefaultSize=30;
class code
{
public:
	 char keymark;//编码字符
	 int key;//权值
};
class element
{
	friend class binTree;
public: 
	element():leftchild(NULL),rightchild(NULL),parent(NULL),mark(0){};
    code data;// 保存本结点的使用频度和其它数据。
	int mark;
    element *leftchild,*rightchild,*parent;
};
class binTree//单个元素的二叉树数
{
public:
	binTree(){ 	root=new element;}
    binTree(binTree &bt1,binTree &bt2)// 
    {
       root=new element;
       root->leftchild =bt1.root;
	   root->rightchild=bt2.root;
       root->data.key=bt1.root->data.key+bt2.root->data.key; 
	   bt1.root->parent=bt2.root->parent=root;  /**/
   }
   element *root;
}; 
class minHeap//最小堆的类声明，也即是排序二叉树（最小为根）
{
public:
	minHeap(){heap=NULL;};
	minHeap(int maxsize);
	void makeMinHeap(binTree a[],int n);
	~minHeap(){ delete[] heap;}
	int insert(binTree x);//插入堆中
	int removeMin(binTree &x);//删除堆顶的最小元素
	int isEmpty(){ return currentsize==0;};//判断是否为空
	int isFull(){return currentsize==maxheapsize;};//判断是否已满
	//void makeEmpty();//清空堆
private:
	binTree *heap;//存放堆中元素的数组
	int currentsize;//单前元素的个数
	int maxheapsize;//堆中元素的最大个数
	void filterDown(int start,int end);//从i到m自顶向下进行调整为最小堆
	void filterUp(int end);//从i到0自底向上进行调整为最小堆
};
minHeap::minHeap (int maxsize)//构造函数
{      
   maxheapsize=maxsize;
   heap=new binTree[maxheapsize];
   currentsize=0;
}
void  minHeap::makeMinHeap (binTree arr[],int n)
{  
   maxheapsize=n;
   heap =new binTree[maxheapsize];
   for(int i=0;i<n;i++)
   {
	   heap[i].root=arr[i].root;
   }
   currentsize=n;
   int currentPos =(currentsize-1)/2;//找最初调整位置：最后的分支结点
   while (currentPos>=0)
   {
       filterDown(currentPos,currentsize-1); //向下调整成最小堆
	   currentPos--;//再向前换一个分支结点
   } 
}
void  minHeap::filterDown(int start,int end)//指定开始、结尾，向下调整成最小堆
{   
   int i=start;
   int j=2*i+1;//左子女标号，i+1为有子女标号
   binTree temp=heap[i]; 
   while (j<=end)
   {   
	   if (j<end&&heap[j].root->data.key>heap[j+1].root->data.key) j++;//一次比较，让j指向两子女中的最小者
       if (temp.root->data.key<heap[j].root->data.key) break;     //二次比较
       else
	   { 
		   heap[i]=heap[j]; 
		   i =j;
		   j = 2*i+1;//并不马上将temp放入下层
	   }  // while end 
       heap[i]=temp;
   }
};
void minHeap::filterUp(int start)//指定开始向上调整成最小堆
{
	int j=start;
	int i=(j-1)/2;
	binTree temp=heap[j];
	while(j>0)
	{
		if(heap[i].root->data.key<=temp.root->data.key) break;
		else 
		{
			heap[j]=heap[i];
			j=i;
			i=(i-1)/2;
		}
		heap[j]=temp;
	}
}
int minHeap::insert(binTree x)//插入一棵二叉树
{
	if(currentsize==maxheapsize) 
	{
		cout<<"heap is full!"<<endl;
		return 0;
	}
	heap[currentsize]=x;
	filterUp(currentsize);//插入后，要调整
	currentsize++;
	return 1;
}
int minHeap::removeMin(binTree &x)//删除最小元素
{
	if(!currentsize)
	{
		cout<<"Heap is empty!"<<endl;
		return 0;
	}
	x=heap[0];
	heap[0]=heap[currentsize-1];//把最后的放到最前面来
	currentsize--;
	filterDown(0,currentsize-1);//然后调整
}
binTree * HuffmanTree ( code *fr,int n)//构造huffman树
{
    binTree *newtree=NULL; 
    binTree first, second;
    minHeap  hp;
    if(n>DefaultSize)
	{
		cerr<<"Size n"<<n<<"exceed the Boundary of Array"<<endl; 
		return NULL; 
	}
    binTree Node[DefaultSize];
    for(int i=0;i<n;i++)
	{ 
		 Node[i].root->data=fr[i]; 
         Node[i].root->leftchild=Node[i].root->rightchild=NULL; 
	}
    hp.makeMinHeap(Node,n);// 建立具有 n 个结点最小化堆。数组名为Node。
    for (i=0; i<n-1; i++ )
    { 
	  
      hp.removeMin(first); //从森林中找出根结点最小的两棵数
	  hp.removeMin(second);//合并成一棵新树，然后把两棵树从森林中去掉
      newtree=new binTree(first,second);
	  hp.insert (*newtree); //把新树插入森林中
	  
    }return newtree;  
}