huffmantree..txt

来自「数据结构中的一个经典案例」· 文本 代码 · 共 171 行

# include <iostream.h>
# include "stdlib.h"
#include "string.h"
#define length 30
int m;//用来记录根结点的位置
struct Node
{
	  int weight;
	 int  parent,lchild, rchild;
};

 
class Huffman
{
public:
 	void BuiltTree(int w[],int n);
	void WriteNum(int l );
	void TranstlateNum();
	void  SelectNode( Node *HT,int n,int& s1);
   // int  pointNum(int w[]);
	void DisplayNum();
protected:
	
	//Node HtNode;
	Node *HT;
	char*HuffmanCode[length];
   
};

   
void Huffman::BuiltTree (int w[],int n)
{
	if(n<=1)
	{
		cout<<"n is a wrong value."<<endl;
	        return ;
	}
     int m,i;
	 m=2*n-1;
	 Node  *p;
	  HT=new Node[m+1];
       p=HT;
 	 for( i=1;i<=n;i++,w++) //构造一个空间用来存放数据,便于更改
	 {
		p[i].weight=*w ;
		p[i].parent =0;
		p[i].lchild=0;
		p[i].rchild=0;
  
	 }
        for(;i<=m;i++) //后半部用来存放新增的结点   
		 {
		p[i].weight=0;
		p[i].parent=0;
		p[i].lchild=0;
		p[i].rchild=0;
	   }
   int s1;
   int s2;
  	   for(i=n+1;i<=m;i++)
	   {    //建树
		   
//在HT[1.....i-1]选择parent为零的且weight最小的两个结点，其序号分别为s1和s2.
  		  int b=i;
		   SelectNode (HT,b-1,s1 );   //选点   该函数是引用返回
           SelectNode (HT,b-1,s2 );   //选点   该函数是引用返回
		   cout<<"输出所选择的点："<< s1<<"    "<< s2<<endl;
 		 HT[s1].parent= i  ;          //纪录s1 的parent
		 HT[s2].parent=  i ;          //纪录s2 的parent
 		 HT[i].lchild= s1 ;           //将较小点作为做孩子 
		 HT[i].rchild= s2;            //将次小点作为右孩子
		 HT[i].weight = HT[s1].weight+HT[s2].weight;//s1和s2的parent的权值
	   }
	   for(i=1;i<=m;i++)             //输出选点情况
	   {
	   cout<<"parent  "<<HT[i].parent <<endl
		   <<"weight   "<<HT[i].weight <<endl
		   <<"lchild  "<<HT[i].lchild <<endl
		   << "rchild   "<<HT[i].rchild <<endl;
	   }
 
}

void Huffman::SelectNode (Node *HT,int n,int& s1)
{   
 	int a, i=1;
     loop: 
			 {
				 if(HT[i].parent ==0)
				 {
					 a=HT[i].weight ;
				 }
       	    	 else
				 {
		    	   i++;
			       goto loop;
				 }
			 } 
 	 	for(i=1;i<=n;i++)
 	         if(a >= HT[i].weight&&HT[i].parent ==0)
			 {
				 s1=i;
				 a=HT[i].weight; 
			 }
          HT[s1].parent=1;
}
 
 

void Huffman::WriteNum (int l)//l为原数组有的结点个数
{  	
	int n ;
	n=2*l-1;//总共需要的存储单位
	cout<<"总共需要的存储单位："<<n<<endl;
 	int start,f,i,c;
 	 *HuffmanCode =new char [n];
 	char *cd; //cd为分配的编码工作空间
    cd=new char[n];
 	cd[n-1]='\0';//编码结束符
 
	for(i=1;i<=n;i++)//逐个字符求huffman编码
	{
      	start=n-1;//编码结束的位置	
  		
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码
			if(HT[f].lchild==c) 
				cd[--start]='0';
			else cd[--start]='1';
 	    HuffmanCode[i]=new char[n-start];//为第i个字符编码分配空间
  			strcpy(HuffmanCode[i],&cd[start]);//从cd 复制编码串到HuffmanCode 
			if (HT[i].parent ==0)
			{    
				cout<<"根结点为第"<<i<<"个结点:" ;
		       	HuffmanCode[i]=new char[n-start];
 				HuffmanCode[i]="头结点";
				cout<<HuffmanCode[i]<<endl;
			  m=i;
			}
	}
 	for(int g=1; g<=n;g++)
	{ 
		 
				cout<<HuffmanCode[g]<<endl;
	}
	cout<<"ok, 第一次输出完毕。"<<endl;
 	delete cd;//释放工作空间
}
	
void Huffman::DisplayNum ()
{
	
	for(int i=1; i<=m;i++)
	{
		cout<<"权值："<<HT[i].weight<<endl; 
	 
				cout<<" huffman编码："<<HuffmanCode[i]<<endl;
	}
}
 
  
void main ()
 {  
	 Huffman t;
      int w[]={2 ,4,7,12,78,45,69,45};
	  
      t.BuiltTree( w, sizeof(w)/sizeof(int) );
 	  
	  t.WriteNum (sizeof(w)/sizeof(int) );
	 t.DisplayNum ();
}