哈夫曼树和编码

1.宏定义：

#include

#define N 100/*为不少于叶结点的个数*/ #define datatypepower int

2.结构体：

typedef struct { datatypepower weight; int parent; int lchild; int rchild;

}Huffmnode;/*哈夫曼结点*/ typedef struct { int bit[N];/*N为不少于叶结点的个数*/ int start;

}Huffmcode;/*哈夫曼编码*/

3.基本函数：

int Create_Huffmtree(Huffmnode HFMTree[],int n)

/*构造哈夫曼树函数1.先决条件:n为叶子结点的个数,HFMTree数组大少至少为(2*n-1);2.函数作用:构造哈夫曼树,构造的哈夫曼树存储于HFMTree[],成功返回1*/ { datatypepower x1,x2,middleweight; int m1,m2,middleindex; int i,j; for(i=0;i<2*n-1;i++) { HFMTree[i].weight=0; HFMTree[i].parent=-1; HFMTree[i].lchild=-1; HFMTree[i].rchild=-1; } printf(\"请分别输入%d个结点的权值:\\n\因情况可以删除此句*/ for(i=0;i if(HFMTree[j].parent==-1) { x1=HFMTree[j].weight; m1=j; break; } for(j=j+1;jreturn 1;

}

int Huffm_Code(Huffmnode HFMTree[],Huffmcode HFMCode[],int n)

/*哈夫曼编码函数1.先决条件:首先要求出哈夫曼树,其中n为叶子结点的个数,HFMCode数组大小至少为n,

HFMTree数组大少至少为(2*n-1);2.函数作用:求出每个叶结点的哈夫曼编码,保存到HFMCode[]数组里,成功返回1*/ { int i,c,p; for(i=0;i4.主函数

int main() { Huffmnode HFMTree[2*N-1]; Huffmcode HFMCode[N]; int i,j,number,choice; do{ printf(\"********************************************\\n\"); printf(\"1.构造哈夫曼树 2.哈夫曼编码 3.退出\\n\"); printf(\"********************************************\\n\"); printf(\"请输入选择(1~3):\"); scanf(\"%d\ getchar(); switch(choice) { case 1:printf(\"请输入结点的个数:\"); scanf(\"%d\

}

Create_Huffmtree(HFMTree,number); for(i=0;i<2*number-1;i++) printf(\"weight=%d parent=%d lchild=%d rchild=%d\\n\ break; case 2:Huffm_Code(HFMTree,HFMCode,number); for(i=0;icase 3:printf(\"谢谢使用!\\n\");break;

default :printf(\"输入错误，请重新输入!\\n\");break; }

}while(choice!=3); return 0;