3.cpp

哈弗曼编码的编译和解码 还能打印哈弗曼树

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "ctype.h"
char a[27]={' ','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
int b[27]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};
typedef struct{
    char         letter;
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode, *HuffmanTree;
typedef struct{
    char letter;
    char code[16];
}HTCode, *HuffmanCode;

void select(int,int *,int *);
void encoding();
void decoding();
void HuffmanCoding();
void treeprint();

HuffmanTree HT;
HuffmanCode HC;
int n;

void main()
{
    char c;
  

    HuffmanCoding();
    while(1)
    {
        printf("\n请选择(1:初始化,2:打印树,3:编码,4:译码):");
        do{
            c=getchar();
        }while(c<'1'||c>'5');
        switch(c){
        case '1':HuffmanCoding();break;
        case '2':treeprint();break;
        case '3':encoding();break;
        case '4':decoding();break;
       
        }
        
    }
}

void HuffmanCoding()
{
   HuffmanTree p;
   int m,i,j,s1,s2,temp,start,c,f;
   char tmp,*cd;

   printf("请输入读入字符集的大小:");
   //scanf("%d",&n);
   n=27;
   printf("%d\n",n);
   m=2*n-1;
   HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
   for(p=HT+1,i=1;i<=n;++i,++p)/*输入哈夫曼树的n的字符及其权值,0号单元未用*/
   {

/*inp:   getchar();
       printf("请输入一个字符和它的权值:");
       tmp=getchar();
       p->letter=tmp;
       scanf("%d",&temp);
       p->weight=temp;
	   for(j=i-1;j>=1;j--)
		   if(tmp==HT[j].letter) 
		   {printf("%c 已经输入过了!",tmp);
		   goto inp;
		   }*/
	   printf("请输入一个字符和它的权值:");
     p->letter=a[i-1];
	 p->weight=b[i-1];
	 printf("%c%4d\n",a[i-1],b[i-1]);
		   p->parent=0;
           p->lchild=0;
           p->rchild=0;
}
   for(i=n+1;i<=m;++i,++p)
   {p->letter='\0';p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}
   for(i=n+1;i<=m;++i)
   {
       select(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;
   }
   /*求每个字符的Huffman编码*/
   HC=(HuffmanCode)malloc((n+1)*sizeof(HTCode));
   cd=(char *)malloc(n*sizeof(char));
   cd[n-1]='\0';
   for(i=1;i<=n;++i)
   {
       start=n-1;
       HC[i].letter=HT[i].letter;
       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';
       strcpy(HC[i].code,&cd[start]);
   }
   for(i=1;i<=n;i++)
       printf("%c  %s\n",HC[i].letter,HC[i].code);
   free(cd);
}

void select(int num,int *s11,int *s22)
{
   
	    int i,min=65535;

    for(i=1;i<=num;i++)
        if (!HT[i].parent&&HT[i].weight<min)
        {
            min=HT[i].weight;
            *s11=i;
        }
    min=65535;
    for(i=1;i<=num;i++)
	{if(i==*s11) continue;
        else if (!HT[i].parent&&HT[i].weight<min)
        {
            min=HT[i].weight;
            *s22=i;
        }
	}
	if(*s11>*s22)
	{
		int tmp1,tmp2;
		tmp1=*s11;
		tmp2=HT[*s11].weight;
		*s11=*s22;
		HT[*s11].weight=HT[*s22].weight;
		*s22=tmp1;
		HT[*s22].weight=tmp2;
	}

}

void encoding()
{
    char str[80],*st=str,*s;
    int i,len,j;


    for(i=1;i<=n;i++)
       printf("%c  %s\n",HC[i].letter,HC[i].code);
    getchar();
    printf("请输入要编码的内容:\n");
    gets(st);
    len=strlen(st);
    s=(char *)malloc((len)*sizeof(char));
    strcpy(s,st);
    for(i=0;i<=len;i++)
    for(j=1;j<n+1;j++)
    {
    if(s[i]==HC[j].letter)
        printf("%s",HC[j].code);
    }
}

void decoding()
{
    char str[80],*st=str,*s;
    int i,len,m,x;

    for(i=1;i<=n;i++)
       printf("%c  %s\n",HC[i].letter,HC[i].code);
    getchar();
ini:
    printf("\n输入的哈弗曼编码只允许0—1:\n");
    gets(st);
    len=strlen(st);
    s=(char *)malloc((len)*sizeof(char));
    strcpy(s,st);
    for(i=0;s[i]!='\0';i++)
       if(s[i]!='1'&&s[i]!='0') {printf("输入错误，只有0-1 才允许!\n");free(s);goto ini;}
    m=2*n-1;
    x=m;
    for(i=0;s[i]!='\0';i++)
    {
    if(s[i]=='0') x=HT[x].lchild;
        else x=HT[x].rchild;
    if(HT[x].lchild==0||HT[x].rchild==0) {printf("%c",HT[x].letter);x=m;}
    }
}

void treeprint()
{
    int m,i;

    m=2*n-1;
    printf("|NO.|name|weight|parent|lchild|rchild|\n");
    for(i=1;i<=m;i++)
   printf(" %-3d %-4c %-6d %-6d %-6d %-6d \n",i,HT[i].letter,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
}