(10)哈夫曼编码.cpp

一些数据结构算法的例子

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NUM 8;
typedef struct
{ unsigned int weight;
  unsigned int parent,lchild,rchild;
  unsigned char data;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;

unsigned int pop;

void select(HuffmanTree HT,int i,int &s1,int &s2)
{
  unsigned int temp;
  unsigned int min=100;
  for(temp=1;temp<=i;temp++)
	if((HT[temp].weight<min)&&(HT[temp].parent==0))
	{
		min=(HT+temp)->weight;
		s1=temp;
	}
   min=100;
   for(temp=1;temp<=i;temp++)
	if((HT[temp].weight<min)&&(HT[temp].parent==0)&&(temp!=s1))
	{
		min=(HT+temp)->weight;
		s2=temp;
	}
}

void GetCord(HuffmanCode HC,char *dm0,char *st,char *ch)
{
	int i=0;
	while(st[i]!=0)
	{
		strcat(dm0,HC[st[i]-0x60]);
		i++;
	}
	*ch=*ch;
}

void GetText(HuffmanTree HT,char *dm1,char *s)
{
	int Tree;
	int u;
	int c=0;
	while(*dm1)
	{
		Tree=pop-1;
		while(HT[Tree].lchild&&HT[Tree].rchild)
		{
			if(*dm1=='0')
				Tree=HT[Tree].lchild;
			else
				Tree=HT[Tree].rchild;
			dm1++;
		}
		s[c]=HT[Tree].data+1;
		c++;
	}
	s[c]=0;
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,char ch[])
{ int m,i,s1,s2,start,c,f;
int u;
  HuffmanTree p;
  char * cd;
  if(n<=1)return;
  m=2*n-1;
  HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
  for(u=1;u<9;u++)
	HT[u].data=95+u;
  for(p=HT+1,i=1;i<=n;++i,++p,++w)
   { (*p).weight=*w;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}
  for(;i<=m;++i,++p)
   { (*p).weight=0;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;}

  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;
	}
  pop=i;
 printf("%2d:%6d%6d%6d%6d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
  HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
  cd=(char *)malloc(n*sizeof(char));
  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';
	  HC[i]=(char*)malloc((n-start)*sizeof(char));
	  strcpy(HC[i],&cd[start]);
	  }
  printf(" char   weight   huffmancord \n");
  for(i=1;i<=n;++i)printf("%4c%10d%10s\n",ch[i],HT[i].weight,HC[i]);
}

void main()
{ int *w,*k,i,j,p,n;
  char ch[8+1];
  char dm1[256]="";
  char st[256]="";
  char dm0[256]="";
  char s[256];
  n=8;
  HuffmanTree HT;
  HuffmanCode HC;
  w=(int *)malloc(n*sizeof(int));
  for(i=1,k=w;i<=n;++i,++k)
   {ch[i]=96+i;printf("Enter the weight(%c):  ",ch[i]);scanf("%d",k);}
  HuffmanCoding(HT,HC,w,n,ch);
  printf("input the text :     ");
  scanf("%s",st);
  GetCord(HC,dm0,st,ch);
  printf("the cord is :%s \n",dm0);
  printf("Enter cord : ");
  scanf("%s",dm1);
  GetText(HT,dm1,s) ;
  printf("the decord text is : %s\n",s);
}