数据结构：哈夫曼树的应用

核心提示：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>a#include<graphics.h>#define MAXVALUE 200 /*权值的最大值*/#define

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>a
#include<graphics.h>
#define MAXVALUE 200　　　　　 /*权值的最大值*/
#define MAXB99v  30　　　　　　 /*最大的编码位数*/
#define MAXNODE 30　　　　　　 /*初始的最大的结点数*/
 strUCt haffnode
　　　　 {char data;
　 int weight;
　　　　　　　　　　　  int flag;
　　　　　　　　　　　  int parent;　　　 /*双亲结点的下标*/
　　　　　　　　　　　  int leftchild;　  /*左孩子下标*/
　　　　　　　　　　　  int rightchild;　 /*右孩子下标*/
　　　　 };
 struct haffcode
　　　　 {int bit[MAXNODE];
　　　　　　　　　　　  int start;　　　  /*编码的起始下标*/
　 char data;
　 int weight;　　　 /*字符权值*/
　　　　 };  
/*函数说明*/
/************************************************************************/
void pPRintf(struct haffcode haffcode[],int n);
/*输出函数*/
void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[]);
/*建立哈夫曼树*/
void haffmancode(struct haffnode hafftree[],int n,struct haffcode haffcode[]);
/*求哈夫曼编码*/
void test(struct haffcode haffcode[],int n);
/*测试函数*/
void end();
/*结束界面函数*/
/************************************************************************/  
void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[])
　  /*建立叶结点个数为n，权值数组为weight[]的哈夫曼树*/
　  {int i,j,m1,m2,x1,x2;
　　 /*哈夫曼树hafftree[]初始化，n个叶结点共有2n-1个结点*/
　　　　 for(i=0;i<2*n-1;i++)
　　　  {if(i<n)  {hafftree[i].data=data[i];
　　 hafftree[i].weight=weight[i];　 /*叶结点*/
　　　　　 }
　　　　 else　　 {hafftree[i].weight=0;　　　　　 /*非叶结点*/
　　 hafftree[i].data='\0';
　　 }
　　　　 hafftree[i].parent=0;　　　　　　　　　　 /*初始化没有双亲结点*/
　　　　　　　　　　　　　　  hafftree[i].flag=0;
　　　　 hafftree[i].leftchild=-1;
　　　　　　　　　　　　　　  hafftree[i].rightchild=-1;
　　　　　　　　　　　　　　 }
　 for(i=0;i<n-1;i++)　　　　　　　　　　　　　　  /*构造哈夫曼树n-1个非叶结点*/
　　　　　　　　　　　　　  {m1=m2=MAXVALUE;
　　　　　　　　　　　　　　 x1=x2=0;
　　　  for(j=0;j<n+i;j++)
　　 {if(hafftree[j].weight<m1&&hafftree[j].flag==0)
　　　　　　　　　　　　　　　　　　　　 {m2=m1;
　　　　　　　　　　　　　　　　　　　　  x2=x1;
　　　　　　　　　　　　　　　　　　　　  m1=hafftree[j].weight;
　　　　　　　　　　　　　　　　　　　　  x1=j;
　　　　　　　　　　　　　　　　　　　　 }
　　  else if(hafftree[j].weight<m2&&hafftree[j].flag==0)
　　　　　　　　　　　　　　　　　　　　　  {m2=hafftree[j].weight;
　　　　　　　　　　　　　　　　　　　　　　 x2=j;
　　　　　　　　　　　　　　　　　　　　　  }
　　　　　　　　　　　　　　　　  }
　　　　　　　　　　　　　　　　  hafftree[x1].parent=n+i;
　　　　　　　　　　　　　　　　  hafftree[x2].parent=n+i;