赫夫曼树.cpp

是一些串操作、赫夫曼树、我的最小生成树的源码希望能帮助大家希望站长能够支持我

//*******************赫夫曼树和赫夫曼编码的存储表示************************

# include<iostream.h>
# include<stdlib.h>
# include<string.h>

# define OVERFLOW  -2
typedef struct{
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;      //动态分配数组存储赫夫曼树
typedef char **HuffmanCode;    //动态分配数组存储赫夫曼树编码表

void HuffmanCoding(HuffmanTree &,HuffmanCode &,int *,int );
void Select(HuffmanTree ,int ,int &,int & );

//******************************主函数*****************************************
void main(void)
{
	HuffmanTree HT;
	HuffmanCode HC;
	int i,n,*w;
	char *ch;

	cout<<"******************************************************"<<endl;
	cout<<"*         本程序的作用是求字符的赫夫曼编码!          *"<<endl;
	cout<<"******************************************************"<<endl;

	cout<<endl<<"请输入你要转换的字符的个数:  ";
	cin>>n;
	if(!(ch=(char *)malloc(n*sizeof(char))))
	{ cout<<endl<<"存储空间分配失败!"<<endl;
	exit(OVERFLOW);}//if
    
	if(!(w=(int *)malloc(n*sizeof(int))))
	{ cout<<endl<<"存储空间分配失败!"<<endl;
	exit(OVERFLOW);}//if
	
	for(i=1;i<=n;i++)
	{cout<<"请输入第个"<<i<<"字符和它的权值: ";
	 cin>>ch[i-1]>>w[i-1];
	}
	cout<<endl<<"你的输入完毕!"<<endl;
	HuffmanCoding(HT,HC,w,n);

	for(i=1;i<=n;i++)
	{
      cout<<"第 "<<i<<" 个字符 "<<ch[i-1]<<" 它的权值是 "<<w[i-1];
	  cout<<" 赫夫曼编码是 "<<HC[i]<<endl;
	}//for

	cout<<endl<<"程序结束!"<<endl;
}//main

//*************************huffmanCoding()*************************************

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
	//w存储n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。
	
    HuffmanTree p;
	int i,c,f,m,start,S1,S2;
	char *cd;

	if(n<=1) return;
	m=2*n-1;
	if(!(HT=(HuffmanTree) malloc((m+1) * sizeof(HTNode)))) //0号单元未用
	{ cout<<endl<<"存储空间分配失败!"<<endl;
	exit(OVERFLOW);}//if

	for(p=HT+1,i=1;i<=n;++i,++p,++w) 
	{(*p).weight=*w;
	 (*p).parent=0;
	 (*p).lchild=0;
	 (*p).rchild=0;
	}//for

	for(;i<=m;++i,++p) 
	{(*p).weight=0;
	 (*p).parent=0;
	 (*p).lchild=0;
	 (*p).rchild=0;
	}//for
	for(i=n+1;i<=m;i++){
		Select(HT,i-1,S1,S2);
		HT[S1].parent=i; HT[S2].parent=i;
		HT[i].lchild=S1; HT[i].rchild=S2;
		HT[i].weight=HT[S1].weight + HT[S2].weight;
	}//for

	//------------从叶子到根逆向求每个字符的赫夫曼编码
	if(!(HC=(HuffmanCode) malloc((n+1) * sizeof(char *))))
	{ cout<<endl<<"存储空间分配失败!"<<endl;
	exit(OVERFLOW);}//if
	if(!(cd=(char *) malloc(n*sizeof(char))))
    { cout<<endl<<"存储空间分配失败!"<<endl;
	exit(OVERFLOW);}//if
    cd[n-1]='\0';
	for(i=1;i<=n;i++){
		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';
			if(!(HC[i]=(char *)malloc((n-start)*sizeof(char))))
             { cout<<endl<<"存储空间分配失败!"<<endl;
            	exit(OVERFLOW);}//if
			  strcpy(HC[i],&cd[start]);
	}//for
	free(cd);
}//HuffmanCoding

//***************************函数Select()**************************************

void Select(HuffmanTree HT,int n,int &s1,int &s2){

	int start,i;
	for(i=1;i<=n;i++)
		if(HT[i].parent==0) {start=i;break;}//if
    s1=start;
	for(i=start;i<=n;i++)
		if(HT[i].parent==0 && HT[s1].weight>HT[i].weight)
			s1=i;

    for(i=1;i<=n;i++)
		if(HT[i].parent==0 && i!=s1) {start=i;break;}
		s2=start;
	for(i=start;i<=n;i++)
	    if(HT[i].parent==0 && HT[s2].weight>HT[i].weight && i!=s1)
			s2=i;
	if(s1>s2)
	{s1=s1+s2;s2=s1-s2;s1=s1-s2;}
}//Select()

//*********************************程序至此结束********************************