haffman.txt

哈夫曼树的建立,haffman 编码,在turbo c 下运行

 #include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#define maxvalue 10000 /*设定权值的最大值*/
#define maxbst 10  /*设定的最大编码位数*/
#define maxn 100 /*设定的最大结点数*/
typedef struct HaffNode_name{
int weight,flag; /*权值和标记*/
int parent; /*双亲结点下标*/
int leftchild,rightchild; /*左右孩子的下标*/
}HaffNode; /*哈夫曼树的结点结构*/
 typedef struct code_name{
 int bit[maxn]; /*数组*/
 int start,weight; /*编码的起始下标，字符的权值*/
  }Code; /*哈夫曼树的结构*/
void Haffman(int weight[],int n, HaffNode hafftree[])
/*建立叶结点，个数为N权值数组为weight的哈夫曼树hafftree*/
 {  
    int i,j,m1,m2,x1,x2;
    /*哈夫曼树的始初化n个叶结点的二叉树共有2*n-1个结点*/
    for(i=0;i<2*n-1;i++)
    {
       if(i<n)
       hafftree[i].weight=weight[i];/*把i的权值付给哈夫曼树的权值*/
       else 
       hafftree[i].weight=0; /*权值初始化为0*/
       hafftree[i].parent=-1; /*3个指针域初始化为-1*/
       hafftree[i].flag=0;
       hafftree[i].leftchild=-1;
       hafftree[i].rightchild=-1; 
	}
    /*构造哈夫曼树hafftree的n-1个非叶结点*/
    for(i=0;i<n-1;i++)   /*读入n个结点的权值*/
    {
       m1=m2=maxvalue; /*设置权值变量为最大权值*/
       x1=x2=0; /*设置最小和次小权值结点位置为下标0处*/
       for(j=0;j<n+i;j++) /*控制一趟中找出最小的两个权值*/
       {
          if(hafftree[j].weight<m1&&hafftree[j].flag==0)
          {
             m2=m1;x2=x1;/*若j的权值小于当前最小的m1改为次小*/
             m1=hafftree[j].weight;/**/
             x1=j; } /*记下当前最小权值及位置*/
         else if(hafftree[j].weight<m2&&hafftree[j].flag==0)
         {
            m2=hafftree[j].weight;x2=j;}
        } /*否则若小于当前次小m2则更新m2及其位置*/
      /*将找出两棵权值最小的子树合并为一棵树*/
      hafftree[x1].parent=n+i; /*修改最小权值结点的双亲为刚生成的新结点*/
      hafftree[x2].parent=n+i;  /*修改次小权值结点的双亲为刚生成的新结点*/
      hafftree[x1].flag=1;
      hafftree[x2].flag=1;
      hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight; /*填新生成的结点的权*/
      hafftree[n+i].leftchild=x1;  /*把亲生成结点的左孩子指针指向x1*/
      hafftree[n+i].rightchild=x2; /*把亲生成结点的右孩子指针指向x2*/
 }
   }
   void HaffmanCode(HaffNode hafftree[],int n,Code haffcode[])
   {  /*由N个结点的哈夫曼树构造哈夫曼编码*/
   Code *cd=(Code *)malloc(sizeof(Code));
   int j,i,child,parent; /*定义局部变量*/
   /*求N个结节点的哈夫曼树编码*/
   for(i=0;i<n;i++) /*对n个编码逐个求编码*/
   {
      cd->start=n-1; /*不等长编码最后一位为n-1*/
      cd->weight=hafftree[i].weight; /*取得编码对应的权值*/
      child=i;
      parent=hafftree[child].parent;
      /*由叶结点向上直到根结点*/
      while(parent!=-1) 
      {
         if(hafftree[parent].leftchild==child)
         cd->bit[cd->start]=0;/*左孩子分支编码为0*/
         else
         cd->bit[cd->start]=1;/*右孩子分支编码为1*/
         cd->start--;
         child = parent;
         parent=hafftree[child].parent;
       }
      for(j=cd->start+1;j<n;j++)
      haffcode[i].bit[j]=cd->bit[j];
      /*保存每个叶结点的编码*/
      haffcode[i].start=cd->start+1;
      haffcode[i].weight=cd->weight;/*保存编码对应的权值*/
     }
   }
int _tmain(int argc, _TCHAR* argv[])
{
    int i,j,n=4;
    int weight[]={1,3,5,7};
    HaffNode *myHafftree=(HaffNode *)malloc(sizeof(HaffNode)*(2*n+1)); /*申请haffnode空间*/
    Code *myHaffCode =(Code *)malloc(sizeof(Code) *n);/*申请编码的空间*/
    if(n>maxn)
    {
       printf("给同的n越界修改maxn值！\n");
       exit(0);
     }
    Haffman(weight,n,myHafftree);
    HaffmanCode(myHafftree,n,myHaffCode);
    /*输出每个叶结点的哈呋曼树编码*/
    for(i=0;i<n;i++)
    {
       printf("weight=%d Code= ",myHaffCode[i].weight);
       for(j=myHaffCode[i].start;j<n;j++)
       printf("%d",myHaffCode[i].bit[j]);
       printf("\n");
      }
	return 0;
}