hafuman.cpp

从终端读入要编码的字符串

#include <stdio.h>
#include "stdlib.h"
#include "malloc.h"   
#include "iomanip.h"
#include "string.h"
typedef struct
{   
  char zifu;//不同的字符   
  unsigned int quanzhi;  
  unsigned int d;   
  char elem;//输入的字符   
  char *bianma;//各个字符的编码
  char  xx;   //存放译码字符
  int  weizhi;
  int  flag;
}Weight;
typedef struct
{
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}Htnode,*HuffmanTree;
typedef char **HuffmanCode;

void select(HuffmanTree HT,int n,int &s1,int &s2) 
{  //找权值最小的两个节点	
    int i,j;    
    for(i = 1;i <= n;i++)    
          if(!HT[i].parent)     //双亲为0表示未选
		  {s1 = i;
		  break;}    
    for(j = i+1;j <= n;j++)    
          if(!HT[j].parent)
		  {s2 = j;
		   break;}    
    for(i = 1;i <= n;i++)    
          if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))  //找权值更小的
          s1=i;    
    for(j = 1;j <= n;j++)    
          if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))
          s2=j;    
 //   printf("s1=%d,s2=%d\n",s1,s2);
	  if(s1>s2)
		  {i=s1;
		   s1=s2;
		   s2=i;
		  }

}

void HuffmanCoding(HuffmanTree &HT,Weight *w,int m)
{   //建立哈夫曼树
	int i;
	int s1,s2;
	HT=(HuffmanTree)malloc((2*m-1)*sizeof(Htnode));
	for(i=1;i<=2*m-1;i++)  //初始化
	{HT[i].parent=0;
	 HT[i].lchild=0;
	 HT[i].rchild=0;
	}
	for(i=1;i<=m;i++)
	{HT[i].weight=w[i].quanzhi;}  //初始化
	for(i=m+1;i<=2*m-1;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;
	}

}

void Yima(HuffmanTree HT,Weight *w,int m)
{  //译码
	int    i;
	int    k;
	int    y=1;
	char  p[30];
	int   j=0;
	unsigned int c,f;
	printf("请输入要编码的二进制数:");
_P:	scanf("%s",p);
	getchar();
	printf("\n");
	c=2*m-1;     
	for(k=0;*(p+k)!='\0';k++)
	{
		if(*(p+k)>='2'||*(p+k)<'0')
		{printf("含有非01字符!请重新输入:");
		goto _P;
		}
	}
	for(k=0;*(p+k)!='\0';k++); //求二进制数长度
	for(i=1,j=c;i<=k&&j>=1;i++)
	{ 
		if(i>k)
           break;
        c=j;
        while(HT[c].lchild&&HT[c].rchild)  
		{  
		if(*(p+i-1)=='1')  
			{
                  f=HT[c].rchild;  
				  c=f; 
			}
        else 
			if(*(p+i-1)=='0')  
			{  
                  f=HT[c].lchild; 
				  c=f;
			}
            else  
			{  
                  printf("\n输入的第%d个二进制数有误！\n",i);  
                  break;
			}         
            i++; 
            if(*(p+i-1)=='\0')  
            break;  
		}  
     if(HT[c].lchild==HT[c].rchild)  
	 {  
        printf("%c",w[c].zifu);   
        i=i-1;  
	 }  
	}
	if(*(p+i-1)!='\0')  printf("\n输入的第%d位有误!\n",i-2);
	printf("\n");

}

void bianma(HuffmanTree HT,HuffmanCode HC,Weight *w,int m,int n)
{ //对输入的字符串编码
	int i,t;
	t=m;
	for(i=1;i<=n;i++)
		w[i].bianma="qqq";
	for(i=1;i<=n;i++)
	{
		t=w[i].weizhi;
	    w[i].bianma=HC[t];
	}
	for(i=1;i<=n;i++) 
			printf("%s",w[i].bianma); 
    printf("\n"); 
}

void Huffmanbianma(HuffmanTree HT,HuffmanCode &HC,Weight *w,int m) 
{//对每个字符进行哈夫曼编码 
	unsigned int f; 
	unsigned int c; 
	int    start,i; 
	char       *cd; 
	cd=(char *)malloc(m*sizeof(char));                              
	cd[m-1]='\0'; 
	for(i=1;i<=m;i++)  { 
		start=m-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((m-start)*sizeof(char));
		strcpy(HC[i],&cd[start]);  //将编码存如HC中
	}
	for(i=1;i<=m;i++)
		w[i].bianma=HC[i];

}

int counting(Weight *w,char *c)
{       //频率统计
    int  i,j,n,k=0,m=1;
	for(i=0;*(c+i)!='\0';i++);
	n=i;
	for(i=1;i<=n;i++,k++)  //初始化
	{
       w[i].elem=*(c+k);
	   w[i].d=0;            //初始每个字符个数为0
	   w[i].flag=1;
	   w[i].weizhi=1;
	}
	for(i=1;i<=n;i++)
	{
		k=0;
		for(j=1;j<=n;j++)
		if(w[j].flag)
		   {
			if(w[i].elem==w[j].elem)
			{
				w[j].weizhi=m;
				w[j].flag=0; 
                k++;
			}
		  }
		if(k>0)
			m++;
	}

    for(i=1;i<=n;i++)   
	{  
     for(j=1;j<=n;j++) 
         if(w[i].elem==w[j].elem)   
		 {w[i].d=w[i].d+1; }   //统计各个字符的个数
	}  
    for(i=1;i<=n;i++)   
       for(j=i+1;j<=n;j++)   
           if(w[i].elem==w[j].elem&&w[i].d>=w[j].d&&w[j].d!=0)   
               w[j].d=0;          //除去相同字符
    for(i=1,m=1;i<=n;i++) 
	{   
        if(w[i].d!=0)              //放入权值
		{   
          w[m].zifu=w[i].elem;   
          w[m].quanzhi=w[i].d;    
          m++;   
		}   
	}  
	return m-1;
   
	
}

void Print()
{
	printf("1:察看各个字符权值\n");
	printf("2:察看各个字符编码\n");
	printf("3:查看哈夫蔓表\n");
	printf("4:对输入字符串编码\n");
	printf("5:对数字译码\n");
	printf("6:清屏 \n");
	printf("0:退出\n");
}

int choose()
{
	int flag=1;
	int    k;
	int    i;
	char   s[10];
	printf("请选择:");
	scanf("%s",s);
	getchar();
	printf("\n");
	for(i=0;s[i]!='\0';i++);
	if(i>1)  goto _F;
	if(s[0]>='0'&&s[0]<='9')
	{   k=s[0]-'0';
	    flag=0;
	}
_F:	while(flag)
	{
	 printf("输入错误,请重新选择:");
	 scanf("%s",s);
	 getchar();
	 printf("\n");
	 for(i=0;s[i]!='\0';i++);
	 if(i>1)  goto _F;
	 if(s[0]>='0'&&s[0]<='9')
	 {  k=s[0]-'0';
	    flag=0;
	 }
	}
	return k;
}
void main()
{
	char  *c;
	int    k=0;
	int    i;  
	int    m=1;  //不同字符的个数
	int    n;  //输入字符的个数
	HuffmanTree HT;
	Weight *w;
	c=(char *)malloc(30*sizeof(char));
_L:	printf("请输入字母:");
	gets(c);
	for(i=0;*(c+i)!='\0';i++);
	n=i; 
	if(n==0)
	{	
		printf("没有输入字符!\n");
		goto  _L;
	}
	printf("\n以下是对%s的操作:\n",c);
	Print();
	HuffmanCode HC;
	HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
	w=(Weight *)malloc((n+1)*sizeof(Weight));
	m=counting(w,c);
	HuffmanCoding(HT,w,m);
	Huffmanbianma(HT,HC,w,m);
	while((k=choose()))
	{
	switch(k)
	{
	case 1: 
		printf("字符     权值\n");
		for(i=1;i<=m;i++)
		{
			printf(" %c        %d\n",w[i].zifu,w[i].quanzhi);
		}
		break;
	case 2:
		for(i=1;i<=m;i++)
		printf("%c is %s\n",w[i].zifu,w[i].bianma);
		break;
	case 3:
		printf("位置   权值  双亲   左子   右子 \n"); 
		for(i=1;i<=2*m-1;i++)
        printf(" %d      %d      %d     %d      %d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
		break;
	case 4:
		printf("输入的字符串编码为:");
		bianma(HT,HC,w,m,n);
		printf("\n");
		break;
	case 5:
		Yima(HT,w,m);
		break;
	case 6:
		system("cls");
		printf("请输入字母:%s",c);
		printf("\n以下是对%s的操作:\n",c);
	    Print();
		break;

	case 0:
		exit(1);
	default :
		printf("选择错误!\n");

	}
	}
	
}