Question

3.给设定权值集w={5,4,7,9,2,6},分别代表｛a,b,c,d,e,f｝这六个字符出现的频率。

3.给设定权值集w={5,4,7,9,2,6},分别代表｛a,b,c,d,e,f｝这六个字符出现的频率。要求：构造关于这六个字符的哈夫曼树（左子树根结点的权不大于右子树根结点的权），并给出每个字符的哈夫曼编码（左分支为“0”，右分支为“1”）
【用C语言】

Answer 1

//huffman二叉树
#include<stdio.h>
#include<stdlib.h>
struct HTree
{
char c;
int parent,lChild,rChild,w,s;
};
struct stack
{
char Data[80];
int top;
};
typedef struct HTree HTree;
typedef struct stack stack;
//栈的相关操作，哈夫曼编码的时候会用到
stack *Initstack(int base)
{
stack *s;
s=(stack *)malloc(sizeof(stack)*base);
s->top=0;
return s;
}
void push(stack *S,char ch)
{
if(S==NULL)return;
S->Data[S->top]=ch;
S->top++;
}
char pop(stack *S)
{
char ch;
if(S==NULL)return ch;
S->top--;
ch=S->Data[S->top];
return S->Data[S->top];
}
int StackEmpty(stack *S)
{
if(S==NULL)return -1;
if(S->top==0)
return 1;
return 0;
}

int SeekMinNode(HTree T[],int N)//寻找最小结点
{
int i,n,w=100;
if(T==NULL||N<0)return -1;
for(i=0;i<N;i++)
{
if(T[i].w>0&&T[i].w<w&&T[i].s==0)
{
w=T[i].w;
n=i;
}
}
T[n].s=1;
return n;
}
//构造哈夫曼树
void CreateHuffman(HTree HT[],int n)
{
int i,min1,min2,N,s;
if(HT==NULL)return;
if(n<0)return;
N=2*n-1;
for(i=n;i<N;i++)
{
min1=SeekMinNode(HT,i);
min2=SeekMinNode(HT,i);
if(min1>=n&&min2>=n&&HT[min1].w+HT[min2].w<27)//最大权值为27,所以这个程序只适合这一组数据
{
s=min2;
min2=SeekMinNode(HT,i);
HT[s].s=0;

}
HT[i].w=HT[min1].w +HT[min2].w;
HT[i].lChild=min1;
HT[i].rChild=min2;
HT[min1].parent=i;
HT[min2].parent=i;
HT[i].parent=-1;
}
return;
}
//求哈夫曼码
void prtHuffmanCode(HTree *H,int n)
{
int i,lChild,rChild,p,c;
stack *s;
s=Initstack(100);
for(i=0;i<n;i++)
{
c=i;
while(H[c].w<27)
{
p=H[c].parent;
lChild=H[p].lChild;rChild=H[p].rChild;
if(lChild==c)push(s,'0');
if(rChild==c)push(s,'1');
c=p;
p=H[p].parent;
}
printf("%c: ",H[i].c);
while(!StackEmpty(s))
printf("%c",pop(s));
printf("\n");
}
}

main()
{
HTree Ht[11];
int i;
for(i=0;i<11;i++)
{
Ht[i].lChild=0;
Ht[i].rChild=0;
Ht[i].parent=0;
Ht[i].s=0;
if(i<6)
Ht[i].c=97+i;
if(i>=6)
Ht[i].c='x';
}
Ht[0].w=5;
Ht[1].w=4;
Ht[2].w=7;
Ht[3].w=9;
Ht[4].w=2;
Ht[5].w=6;
CreateHuffman(Ht,6);
printf("No\tData\tW\tparent\tlChild\trChild\n");
for(i=0;i<11;i++)
printf("%d\t %c\t%d\t %d\t %d\t %d\n",i,Ht[i].c,Ht[i].w,Ht[i].parent,Ht[i].lChild,Ht[i].rChild);
prtHuffmanCode(Ht,6);
}