064.哈夫曼编码

#include <stdio.h>
#define MAX  1000
#define MAXSYMBS 30
#define MAXNODE 59

typedef struct
{
  int weight;
  int flag;
  int parent;
  int lchild;
  int rchild;
}huffnode;

typedef struct
{
  int bits[MAXSYMBS];
  int start;
}huffcode;

main()
{
	huffnode huff_node[MAXNODE];
    huffcode huff_code[MAXSYMBS],cd;
    int i,j,m1,m2,x1,x2,n,c,p;
/*    char symbs[MAXSYMBS],symb; */
    /*数组huff_node初始化*/
    clrscr();
	printf("please input the leaf num of tree:\n");
    scanf("%d",&n);
    for(i=0;i<2*n-1;i++)
	{
		huff_node[i].weight=0;
        huff_node[i].parent=0;
		huff_node[i].flag=0;
		huff_node[i].lchild=-1;
        huff_node[i].rchild=-1;
	}

	printf("please input the weight of every leaf\n");
    for(i=0;i<n;i++)
        scanf("%d",&huff_node[i].weight);
/*构造哈夫曼树*/
    for(i=0;i<n-1;i++)
	{
        m1=m2=MAX;
        x1=x2=0;
        for(j=0;j<n+i;j++)
		{
            if (huff_node[j].weight<m1&&huff_node[j].flag==0)
			{
			    m2=m1;
                x2=x1;
                m1=huff_node[j].weight;
                x1=j;
			}
            else if (huff_node[j].weight<m2&&huff_node[j].flag==0)
			{
			    m2=huff_node[j].weight;
                x2=j;
			}
		}
 
        huff_node[x1].parent=n+i;    /*将找出的两棵子树合并为一棵子树*/
        huff_node[x2].parent=n+i;
        huff_node[x1].flag=1;
        huff_node[x2].flag=1;
        huff_node[n+i].weight=huff_node[x1].weight+huff_node[x2].weight;
        huff_node[n+i].lchild=x1;
        huff_node[n+i].rchild=x2;
	}
/*求字符的哈夫曼编码*/

    for(i=0;i<n;i++)
	{
		cd.start=n;
        c=i;
        p=huff_node[c].parent;
        while(p!=0)
		{
			if(huff_node[p].lchild==c)
            
				cd.bits[cd.start]=0;
            else
				cd.bits[cd.start]=1;
            cd.start=cd.start-1;
            c=p;
            p=huff_node[p].parent;
		}
		cd.start++;
        for(j=cd.start;j<=n;j++)
			huff_code[i].bits[j]=cd.bits[j];
        huff_code[i].start=cd.start;
	}
        /*输出字符的哈夫曼编码*/
    puts("The Hafman code are:");    
    for(i=0;i<n;i++)
	{
		for(j=huff_code[i].start;j<=n;j++)
			printf("%10d",huff_code[i].bits[j]);
        printf("\n");                                                                                                                                                                                                                                                                                                                                                                                                                                      
		
	}
	puts("Press any key to quit...");
	getch();

}