huffmantree3.cpp

创建静态

#define SWAP(x, y) (t)=(x);(x)=(y);(y)=(t)  //一切都为了效率


typedef struct node3
{
	int weight;
	struct node3 *lchil,*rchil,*paren;
}node3,*link3;

typedef struct
{
	int data;
	int tag;
}elem;//一个放权重值，一个放标志

elem weigh[30];
link3 t[20],r[20];//t[1]~t[k-1]分别指向不只一个结点的树  k为权重值个数
                //r[1]~r[k-1]分别指向权重值由小到大的只有根结点


void sort(elem **p,int n)//把K个权值由大到小排序，函数结果使指针pstr排序，而非elem
{
	int i,j;
	elem *t;
	for(i=0;i<n-1;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if((**(p+i)).data<(**(p+j)).data)
			{
				
				SWAP(*(p+i),*(p+j));
				
			}
		}
	}
}


void print(link3 T,int n)//DRL
{
	int i;
	if(T)
	{
		for(i=0;i<n;i++)
			cout<<"\t";
		cout<<T->weight<<endl;
		print(T->rchil,n+1);
		print(T->lchil,n+1);
		
	}
}

int yima(char *h,int k);

void huffmantree3()
{
	char *cd,** hc;
	elem **s;
	elem *pstr[20];
	int n,i,j,k,x1,x2,start;
	link3 p1,p2,p;
	
	cout<<"请输入权的个数"<<endl
		<<"例如 ：8 回车"<<endl;
	cin>>n;
	cout<<"分别输入"<<endl
		<<"例如 ：5 29 7 8 14 23 3 11 回车"<<endl;
	
	for(i=0;i<n;i++)
	{
		cin>>weigh[i].data;
		weigh[i].tag=0;//先全部置为0
		pstr[i]=&weigh[i];//一一对应指向 经过sort函数后则按由大到小顺序指向
	}
	
	k=n;//下文n会改变，因为每次拿出两个数，再放进去一个数
	s=pstr;


	for(i=1,j=0;i<k;i++)//刚好生成k-1结点时结束
	{	
		sort(s,n);
		x1=(*pstr[--n]).data;//取出最小的一个数
		if(! (*pstr[n]).tag)//如果不是生成的结点,tag==0;
		{
			r[j++]=p1=(link3)malloc(sizeof(node3));
			p1->weight=x1;
			p1->lchil=p1->rchil=NULL;
		}
		else p1=t[(*pstr[n]).tag];
		
		x2=(*pstr[--n]).data;//取出倒数第二小的数
		if(!(*pstr[n]).tag)
		{
			r[j++]=p2=(link3)malloc(sizeof(node3));
			p2->weight=x2;
			p2->lchil=p2->rchil=NULL;
		}
		else p2=t[(*pstr[n]).tag];
		
		p=(link3)malloc(sizeof(node3));//生成结点
		p->weight=x1+x2;
		p1->paren=p;
		p2->paren=p;
		p->lchil=p1;
		p->rchil=p2;
		(*pstr[n]).data=x1+x2;//把生成的结点放回结构体数组
		(*pstr[n++]).tag=i;//生成的结点tag!=0;
		p->paren=p;//指针回指，似乎没多大作用，但作为对单个权值编码时是否为结束的依据
		t[i]=p;//为了能在排序后，根据权值把对应的生成结点找出来
		
		
	}//利用了霍夫曼树的性质 生成的结点只有k-1个,虽然输入不同权重值时t[1]~t[k-2]值不同，但t[k-1]一定指向霍夫曼树的根
	
	
	cout<<"*************  huffmantree  is  as  follows   ************"<<endl;
	print(t[k-1],2);

	//////////////////////////////////////////////////////////////////////编码
	hc=(char**)malloc((k+1)*sizeof(char*));
	cd = (char *)malloc(k*sizeof(char));  
	cd[k-1] = '\0';                         
	for (i=1,j=0; i<=k; i++,j++) 
	{                  
		start = k-1;                          
		for (p1=r[j],p=r[j]->paren;p!=p1;p1=p,p=p1->paren) //因为指针回指，p==p1则表明结束
			if (p->lchil==p1) 
				cd[--start] = '0';
			else cd[--start] = '1';
			hc[i] = (char *)malloc((k-start)*sizeof(char)); 
			strcpy(hc[i], &cd[start]);   
	}
	free(cd); 
	
	
	
	cout<<"***********************赫夫曼编码为**********************"<<endl;
	for(i=1,j=0;i<=k;i++,j++)
		cout<<"\t\t"<<r[j]->weight<<(char)45<<(char)45<<(char)16<<"\t"<<hc[i]<<"\t\t译码为 :"<<yima(hc[i],k)<<endl<<endl;
	
} 


int yima(char *h,int k)//译码
{
    int i;
	link3 p=t[k-1];
	for(i=0;h[i]!='\0';i++)
	{
		if(h[i]=='0')
			p=p->lchil;
		else 
			p=p->rchil;
	}
	return p->weight;
}