哈夫曼算法和哈夫曼树 .txt

哈夫曼算法以及哈夫曼树实现 c++实现 这个是编码的基础

哈夫曼算法和哈夫曼树 


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

#define NAMEMAX 20
#define CODEMAX 30

typedef unsigned int UINT;
typedef char NAME[NAMEMAX];
typedef char CODE[CODEMAX];

 typedef struct
{
      NAME name;
      CODE code;
      UINT weight;
      UINT parent,lchild,rchild;
}HTNode,*HuffmanTree; 

int minnode(HuffmanTree t,int i)
{
      int j,flag;
      unsigned int k=0xffffffff; 
      for(j=1;j<=i;j++)
            if(t[j].weight<k&&t[j].parent==0)
                  k=t[j].weight,flag=j;
      t[flag].parent=1; 
      return flag;
}

void select(HuffmanTree t,int i,int *s1,int *s2)
{ 
      int j;
      *s1=minnode(t,i);
      *s2=minnode(t,i);
      if(*s1>*s2)
      {
            j=*s1;
            *s1=*s2;
            *s2=j;
      }
}

void HuffmanCoding(HuffmanTree *HT,NAME *str,int *w,int n) 
{
      int i,s1,s2,start;
      unsigned c,f;
      HuffmanTree p;
      char *cd;
      if(n<=1||n>CODEMAX)return;
      *HT=(HuffmanTree)malloc(2*n*sizeof(HTNode)); 
      for(p=*HT+1,i=1;i<=n;++i,++p,++w)
      {
            strcpy((*p).name,str[i-1]);
            (*p).weight=*w;
            (*p).parent=0;
            (*p).lchild=0;
            (*p).rchild=0;
      }
      for(;i<=2*n-1;++i,++p)(*p).parent=0;

      for(i=n+1;i<2*n;++i)
      {
            select(*HT,i-1,&s1,&s2);
            (*HT)[s1].parent=(*HT)[s2].parent=i;
            (*HT)[i].lchild=s1;
            (*HT)[i].rchild=s2;
            (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
      }

      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';
            }
            strcpy((*HT)[i].code,&cd[start]);
      }
      free(cd);
}

int main()
{
      HuffmanTree HT;
      int *w,n,i;
      NAME *str;
      char temp[50];
      printf("请输入权值的个数(>1): ");
      scanf("%d",&n);
      w=(int*)malloc(n*sizeof(int));
      str=(NAME*)malloc(n*sizeof(NAME));
      printf("请依次输入%d个符号(回车分隔):\n",n);
      for(i=0;i<n;i++)scanf("%s",str[i]);
      printf("请依次输入%d个权值(整型):\n",n);
      for(i=0;i<n;i++)scanf("%d",w+i);
      HuffmanCoding(&HT,str,w,n);
      for(i=1;i<=n;i++)printf("%s---%s\n",HT[i].name,HT[i].code);
      printf("请输入你要查的字符\n");
      scanf("%s",temp);
      for(i=1;i<=n;i++)
            if(!strcmp(HT[i].name,temp))printf("%s\n",HT[i].code);
      printf("请输入你要查的编码\n");
      scanf("%s",temp);
      for(i=1;i<=n;i++)
            if(!strcmp(HT[i].code,temp))printf("%s\n",HT[i].name);
      for(i=0;i<2*n;i++)
      {
            free((&HT)[i]);
      }
      system("PAUSE");
      return 0;
}
/*运行结果
请输入权值的个数(>1): 5
请依次输入5个符号(回车分隔):
v1
v2
v3
v4
v5
请依次输入5个权值(整型):
2
6
10
3
16
v1---1110
v2---110
v3---10
v4---1111
v5---0
请输入你要查的字符
v3
10
请输入你要查的编码
110
v2
请按任意键继续. . .