huffman编码c实现

题目里的数据来至于算法导论的huffman那章

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

#define N 20
#define M 2*N-1
#define Min 1000 /*最小值*/

typedef struct
{
  char ch; /*权值对应的字符*/
  int weight; /*权值*/
  int parent; /*双亲位置*/
  int Lchild; /*左孩子位置*/
  int Rchild; /*右孩子位置*/
}HTNode,Huffmantree[M+1];

char hc[N+1][N+1];

void OutputHuffmancode(Huffmantree ht, int n);
void CrtHuffmancode(Huffmantree ht, int n);
void OutputHuffmantree(Huffmantree ht,int n);

void select(Huffmantree ht,int a,int *s1,int *s2)
{
  int i;
  int c1=Min;
  int c2;

  for(i=1;i<=a;i++)
   {
    if (ht[i].parent==0&&ht[i].weight<c1)
     {
       *s1=i;
       c1=ht[i].weight;
      }
    }

  c2=Min;
  for(i=1;i<=a;i++)
   {
    if (ht[i].parent==0&&(*s1!=i)&&c2>ht[i].weight)
     {
       *s2=i;
       c2=ht[i].weight;
      }
    }
}

void CrtHuffmantree(Huffmantree ht,int w[],char elem[],int n)
{
  int i;
  int m;
  int s1,s2;

  m=2*n-1;
  
  ht=(HTNode *)malloc((m)*sizeof(HTNode));
  
  for(i=1;i<=n;i++)
   {
    ht[i].ch=elem[i-1];
    ht[i].weight=w[i-1];
    ht[i].parent=0;
    ht[i].Lchild=0;
    ht[i].Rchild=0;
   }

  for(i=n+1;i<=m;i++)
   {
    ht[i].ch='\0';
    ht[i].weight=0;
    ht[i].parent=0;
    ht[i].Lchild=0;
    ht[i].Rchild=0;
   }

  /*初始化完毕*/
  for(i=n+1;i<=m;i++)
  {
    select( ht,i-1,&s1,&s2); /*返回最小值和次小值的位置*/
    ht[i].weight=ht[s1].weight+ht[s2].weight;
    ht[s1].parent=i;
    ht[s2].parent=i;
    ht[i].Lchild=s1;
    ht[i].Rchild=s2;/*建立树完毕*/
  }

   OutputHuffmantree( ht,m);
   printf("now begin crthuffman code\n");
   CrtHuffmancode( ht, n);
   printf("crthuffman code end\n");
   OutputHuffmancode(ht, n);
}

void OutputHuffmantree(Huffmantree ht,int n)
 {
   int i;
   printf("\nnumber---weight---parent---Lchild---Rchild---huffman char\n \n");

   for(i=1;i<=n;i++)
     printf("%d\t%d\t%d\t%d\t%d\t%c\n",i,ht[i].weight,ht[i].parent,ht[i].Lchild,ht[i].Rchild,ht[i].ch);
}


void CrtHuffmancode(Huffmantree ht, int n) /*建立编码*/
 {
     int i,c,p;
     int start;
     char *cd;

     cd=(char *) malloc((n+1)*sizeof(char));
     memset(cd,'\0',sizeof(cd));
     
     for(i=1;i<=n;i++)
     {
        start=n;
        cd[start]='\0';
        
        c=i;
        p=ht[i].parent;
        while(p!=0)
         {
           start--;
           if(ht[p].Lchild==c)
             cd[start]='0';
           else
              cd[start]='1';
           
            c=p;
            p=ht[p].parent;
         }
      //cd[start] = '\0';

      printf("cd is %s\n start is %d\n", cd+start, start);
       sprintf(hc[i], "%s", cd+start); /*将已存在的编码复制到code中*/
      }

     free(cd);
}

void OutputHuffmancode(Huffmantree ht,int n)
{
  int i;
  printf("\nweight_char---weight---huffmancode\n \n");
  for(i=1;i<=n;i++)
    printf(" %c\t%4d\t%s\n",ht[i].ch,ht[i].weight,hc[i]);
}

int main()
{
  int n = 6;/*记录了权值个数*/
  Huffmantree hfm;
 
  int w[] = {45,13,12,16,9,5};
  char elem[] = {'a','b','c','d','e','f'};
  
  CrtHuffmantree( hfm, w,elem, n);
  return 0;
}