哈夫曼树的建立和编译器的实现
//哈夫曼树的建立和编译器的实现
#include
#include
#include
#define MaxSize 50
typedef struct{
char c; //代码;
int w; //代码权值;
char code[MaxSize]; //代码的Huffman编码;
}HuffCode[MaxSize];
typedef struct{
int Weight; //权值;
int LChild,RChild,Parent; //左孩子，右孩子，双亲；
}HTNode,HuffTree[MaxSize];
//================================================================================
void HuffmanTree(HuffTree HT,int length,HuffCode hc); //生成哈夫曼树
void SelectHTNode(HuffTree HT,int n,int *min1,int *min2); //查找最小和次小序号;
void HuffmanCode(HuffTree HT,int len,HuffCode hc); //生成Huffman编码;
//================================================================================
int main(void)
{
HuffTree HT; //Huffman树;
HuffCode HC; //Huffman编码;
int i,len;
while(1){//设置挡板过滤不符合要求的输入
printf("\n输入代码数量（请输入1到50整型数）：");
scanf("%d",&len);//输入代码数量
if(len>0&&len<=50) break;
printf("Input number error!!!");
}
system("cls"); //执行DOS下的清屏命令。
printf("代码数量：%2d\n\n",len);
printf("输入代码（要求为大小写的单个字母）及权值（权值为正，要求在整型范围内），输完一组请按回车键 )：\n"); //输入代码及其权值
for(i=1;i <= len;i++)
{
while(getchar() != '\n') NULL;
printf("No.%2d： ",i);
HC[i].c = getchar(); //输入代码
scanf("%d",&HC[i].w); //输入权值
}
HuffmanTree(HT,len,HC);// 生成哈夫曼树
HuffmanCode(HT,len,HC); //生成Huffman编码;
printf("\n输出Huffman编码：\n");
for(i = 1;i<=len;i++) //输出Huffman编码
{
printf("\n %c :",HC[i].c);
puts(HC[i].code);
}
//测试Huffman树结构，打印存储结构图；
printf("\n\n输出Huffman树结构：");
system("pause");//等待用户按一个键，然后返回
printf("\nHT[i]:\t权值\t双亲\t左孩子\t右孩子\n");
for(i = 1;i<2*len;i++) //共打印（2*len-1）组
{
if(i <= len) printf("(%c)",HC[i].c); //打印代码
printf("%2d:\t %2d;\t%2d,\t %2d,\t %2d.\n",i,HT[i].Weight,HT[i].Parent,HT[i].LChild,HT[i].RChild); //打印相应代码的权值，双亲，左孩子，右孩子；
}
return 0;
}
//================================================================================
void HuffmanTree(HuffTree HT,int length,HuffCode hc) //Huffman树初始化;
{
int i,min1,min2;
HT[0].Weight = 65535; //0号不做比较
for(i = 1;i <= length;i++) //代码赋权值并将双亲，左孩子，右孩子清空；
{
HT[i].Weight = hc[i].w; //代码
赋权值
HT[i].LChild = HT[i].RChild = HT[i].Parent = 0; //将双亲，左孩子，右孩子清空；
}
for(;i < 2*length;i++) //i初值 = length+1;
{
HT[i].LChild = HT[i].RChild = HT[i].Parent = 0; //length+1到2*length-1号的双亲，左孩子，右孩子清空；
}
for(i = length+1;i < 2*length;i++) //在选择Parent为0且权值最小的两个结点，其序号分别为min1,min2;
{
SelectHTNode(HT,i,&min1,&min2); //查找最小和次小序号;
HT[min1].Parent = i;
HT[min2].Parent = i;
HT[i].LChild = min1;
HT[i].RChild = min2;
HT[i].Weight = HT[min1].Weight + HT[min2].Weight; //i号代码的权值是两项权值的和；
}
}
//================================================================================
void SelectHTNode(HuffTree HT,int n,int *min1,int *min2) //查找最小和次小序号;
{
int i;
*min1 = *min2 = 0;// 初始化min1,min2;
for(i = 1;i < n;i++)
{
if(HT[i].Parent == 0) //代码双亲清零
{
if(HT[*min1].Weight >= HT[i].Weight) //i的权值比*min1小，保存i;
{
*min2 = *min1;
*min1 = i;
}
else if(HT[*min2].Weight > HT[i].Weight) *min2 = i; //i的权值比*min2小，保存i；
}
}
}
//================================================================================
void HuffmanCode(HuffTree HT,int len,HuffCode hc) //生成Huffman编码;
{
int i,j,tc,Stack[MaxSize],top = 0;
char flag[MaxSize]; //flag用来标记是左孩子还是右孩子
HTNode th;
for(i = 1;i <= len;i++)
{
top = 0; //栈初始化;
j = 0; //hc[i].code串首位置偏移;
th = HT[i]; //当前结点th;
tc = i; //当前结点标记tc;
while(th.Parent !=0)
{ //当前结点th双亲P入栈,由P的孩子是th,确定flag;确定下次结点标记tc;
Stack[++top] = th.Parent; //++top实现逐个字符求哈夫曼编码；
if(HT[th.Parent].LChild == tc) {flag[top] = 'L'; tc = th.Parent;} //当前结点是否为其双亲的左孩子；
if(HT[th.Parent].RChild == tc) {flag[top] = 'R'; tc = th.Parent;} //当前结点是否为其双亲的右孩子；
th = HT[Stack[top]]; //下一结点;
}
while(top != 0)
{
if(flag[top] == 'L') hc[i].code[j++] ='0';//字符0表示左孩子；
else hc[i].code[j++] ='1'; //字符1表示右孩子；
Stack[top--]; //出栈;
}
hc[i].code[j] ='\0'; //当前串结束;
159********
075877
}
}
//
================================================================================