하프 만 트 리 생 성 및 인 코딩

codeblocks 에서 컴 파일 이 실 행 됩 니 다.

#include
#include
#include
typedef struct{
    int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;


int min1(HuffmanTree t,int i)
{//  VOID select  
   int j,flag;
   int k=10000;// K       
   for(j=1;j<=i;j++)
     if(t[j].weight*s2)
   {
       j=*s1;
      *s1=*s2;
      *s2=j;
   }
}

//      
void CreateHuffmanTree(HuffmanTree *HT,int *w,int n){
    int i,s1,s2,k,f;
    if(n<=1) printf("error");
    int m;
    m=2*n-1;
    HTNode *p;
    *HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    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;
    }

    // HT[1...i-1]   parent 0          ，     s1，s2；
    for(i=n+1;i<=m;i++){
    printf("1111111");
        Select(*HT,i-1,&s1,&s2);
    printf("222222");
        HT[s1]->parent = i;  printf("333333");HT[s2]->parent = i;
        HT[i]->lchild = s1;   HT[i]->rchild = s2;
        HT[i]->weight = HT[s1]->weight + HT[s2]->weight;
    }
}

//  Huffman  
void HuffmanTreeCode(HuffmanTree *HT,HuffmanCode *HC,int n){
   int start,c,i,f;
   char *cd;
   *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]);
   }
   free(cd);
   //       
   printf("number\t\tweight\t\tCode
");
   for(i=1;i<=n;i++){
    printf("%d\t\t%d\t\t%d
",i,HT[i]->weight,HC[i]);
   }
}

void ShowHuffmanTree(HuffmanTree HT,int n){
    int i;
    printf("      ：
");
    printf("number\t\tweight\t\tparent\t\tlchild\t\trchild
");
    for(i=1;i<=2*n-1;i++){
        printf("%d\t\t%d\t\t%d\t\t%d\t\t%d
",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
    }
}

void main(){
    int i,n;
    int *w;
    printf("       n(n>1):");
    scanf("%d",&n);
    w=(int *)malloc((n+1)*sizeof(int));
    w[0]=0;
    printf("        :");
    for(i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    HuffmanCode HC=NULL;
    HuffmanTree HT=NULL;
    CreateHuffmanTree(&HT,w,n);
    HuffmanTreeCode(&HT,&HC,n);
    ShowHuffmanTree(HT,n);
}