haffman.h

huffman 算法 包含的主要个文件： minheap.h:初始化堆 haffman.cpp:具体实现huffman算法

#pragma once

#include"minheap.h"
#include "stdafx.h"

template <class Type> struct NodeData{
   Type symbol;//结点代表的符号
   int key;//记录频数
   char num;//结点编码
};
template <class Type> class ExtBinTree;
template <class Type> class Element{
friend class ExtBinTree<Type>;
friend class MinHeap<ExtBinTree<Type> >;
public:
   Element<Type>(Type na='^',int f=0,char n='0'){
       data.key=f;
       data.symbol=na;
       data.num=n;
       parent=leftChild=rightChild=NULL;
   }
private:
   NodeData<Type> data;
   Element<Type>*parent,*leftChild,*rightChild;
};
template <class Type> class ExtBinTree{
friend class MinHeap<ExtBinTree<Type> >;
public:
   ExtBinTree(int n=0,Type *s=NULL,Type *name=NULL,Element<Type> *l=NULL):
   root(l),num(n),str(s){
       na=new Type[n];
       na=name;
       fr=new int[n];
       for(int i=0;i<n;i++)fr[i]=0;
       if(str!=NULL)Fre();
   }
   void Modify(ExtBinTree<Type> *bt1,ExtBinTree<Type> *bt2){
       root->parent=NULL;
       root->leftChild=(*bt1).root;
       root->rightChild=(*bt2).root;
       (*bt1).root->parent=(*bt2).root->parent=root;
       (*bt1).root->data.num='0';
       (*bt2).root->data.num='1';
       root->data.key=(*bt1).root->data.key+(*bt2).root->data.key;
   }
   void HuffmanTree();//构造哈夫曼树
   Element<Type>* Find(Type item);//寻找结点的函数
   char* Coding(Type item);//编码函数
   void Fre();//计算字符频数的函数
   void DeCoding(char s[]);//译码函数
   int *GetFr(){return fr;}//返回字符出现的频数
  
private:
   Element<Type> *root;//扩充二叉树的根
   int num;//输入的字符种类数
   Type *str;//输入的字符串
   Type *na;//存放各种字符
   int *fr;//各种字符的频数
};
template <class Type> void ExtBinTree<Type>::HuffmanTree(){
   int n(0),*f=new int[num];
   char *s=new char[num];
   for(int i=0;i<num;i++){
       if(fr[i]!=0){
           f[n]=fr[i];
           s[n]=na[i];
           n++;
       }
   }
   ExtBinTree<Type> *Node=new ExtBinTree<Type>[n];
   for(int i=0;i<n;i++)
       Node[i].root=new Element<Type>(s[i],f[i]);
   MinHeap<ExtBinTree<Type> > hp(Node,n);
   ExtBinTree<Type> first,second;
   for(int i=0;i<n-1;i++){//建立霍夫曼树的过程，做n-1趟
       hp.RemoveMin(first);//选根权值最小的树
       hp.RemoveMin(second);//选根权值次小的树
       root=new Element<Type>;
       Modify(&first,&second);//建新的根结点
       hp.Insert(*this);//形成新树插入
   }
}
template <class Type> Element<Type>* ExtBinTree<Type>::Find(Type item){//寻找值为item的结点
   Element<Type>*p=root,**s=new Element<Type>*[num+1];
   int top=-1;
   while(!(p==NULL&&top==-1)){
       while(p!=NULL){
           s[++top]=p;
           p=p->leftChild;
       }
       if(top!=-1){
           p=s[top--];
           if(p->data.symbol==item)return p;
           p=p->rightChild;
       }
   }
   return NULL;
}
template <class Type> char* ExtBinTree<Type>::Coding(Type item){
   Element<Type>*p=Find(item);
   if(p==NULL){
       cerr<<"符号未找到！";
       return NULL;
   }
   char *s=new char[num];
   int i=-1;
   while(p!=root){
       s[++i]=p->data.num;
       p=p->parent;
   }
   char *c=new char[i+2];
   for(int j=0;j<=i;j++)
	   c[j]=s[i-j];
		 c[i+1]='\0';
   
   return c;
}
template <class Type> void ExtBinTree<Type>::DeCoding(char s[]){
   int i=0;
   Element<Type>*p=root;
   while(s[i]!='\0'){
       if(s[i]=='0'){
           p=p->leftChild;
           if(p->data.symbol!='^'){
               cout<<p->data.symbol;
               p=root;
           }
       }
       else{
           p=p->rightChild;
           if(p->data.symbol!='^'){
               cout<<p->data.symbol;
               p=root;
           }
       }
       i++;
   }
}
template <class Type> void ExtBinTree<Type>::Fre(){
   int i=0;
   while(*(str+i)!='\0'){
       for(int j=0;j<num;j++)
           if(*(str+i)==na[j])fr[j]++;
       i++;
   }
}
/*template <class Type> double ExtBinTree<Type>::Entropy(int m){
   double ent=0;
   int n(0);
   while(str[n]!='\0')n++;
   if(m==0){//计算符号序列熵        
       for(int i=0;i<num;i++)
           if(fr[i]!=0)
               ent+=-double(fr[i])/n*log(double(fr[i])/n)/log(2.0);
   }
   else if(m==1){//计算平均码长
       for(int i=0;i<num;i++)
           if(fr[i]!=0)
               ent+=double(fr[i])/n*strlen(Coding(na[i]));
   }
   else{
       cout<<"错误调用！\n";
       return 0;
   }
   return ent;
}*/