HUFFMAN编码 求解救
结点值ABCDE这个地方不知道为什么i第一个数输入不进去i是从第二个数输进去的
计算基本没问题
就是结点值输入出现了问题
调试后发现A是当i=1的时候输进去的
而非i=0的时候
求高手指点
如各个叶子值分别为A、B、C、D、E，各个权值分别为18，12，10，7，11。此部分信息由键盘一边输入，一边对数组初步赋值，结果如下：
数组下标 结点值 权值 左孩子 右孩子 双亲
0 A 18 -1 -1 -1
1 B 12 -1 -1 -1
2 C 10 -1 -1 -1
3 D 7 -1 -1 -1
4 E 11 -1 -1 -1
5
6
7
8
计算二叉树其余结点信息。
由于5个叶子结点，要合并4次。每次从还无双亲（无双亲代表还未合并过）的叶子结点中选择权值最小的两个叶子结点进行合并，新结点下标为这两个叶子的双亲，新结点的权值为这两个叶子权值之和，左孩子为最小结点下标，右孩子为次小结点下标，叶子值不需要，双亲为0。
如下为合并一次后的结果，如此循环4次即可：
数组下标 结点值 权值 左孩子 右孩子 双亲
0 A 18 -1 -1 -1
1 B 12 -1 -1 -1
2 C 10 -1 -1 5
3 D 7 -1 -1 5
4 E 11 -1 -1 -1
5 17 3 2 -1
6
7
8
以下是我写的程序
#include<stdio.h>
struct node
{
int weight;
int parent,lch,rch;
char yezi;
};
struct node Htree[80];
int n;
creat_huff(struct node Htree[])
{
int i,j,min1,min2,seat1,seat2;
char yezi;
printf("请输入叶子的个数(<10):");
scanf("%d",&n);
for(i=0;i<2*n-1;i++)
{
Htree[i].parent=-1;
Htree[i].lch=-1;
Htree[i].rch=-1;
}
printf("\n请输入各叶子的值：");
for(i=0;i<=n;i++)
{
scanf("%c",&Htree[i].yezi);
}
printf("\n请输入各叶子权值：");
for(i=0;i<n;i++)
{
scanf("%d",&Htree[i].weight);
}
for(i=n;i<2*n-1;i++)
{
min1=min2=1000;
seat1=seat2=0;
for(j=0;j<i;j++)
{
if(Htree[j].parent==-1)
if(Htree[j].weight<min1)
{
seat2=seat1;
min2=min1;
seat1=j;
min1=Htree[j].weight;
}
else if(Htree[j].weight<min2)
{
seat2=j;
min2=Htree[j].weight;
}
}
Htree[seat1].parent=Htree[seat2].parent=i;
Htree[i].weight=Htree[seat1].weight+Htree[seat2].weight;
Htree[i].lch=seat1;
Htree[i].rch=seat2;
}
Htree[2*n-2].parent=-1;
}
code_huff(struct node Htree[])
{
int i,j,seatyezi,fumu;
int code[80][80];
for(i=0;i<n;i++)
{
j=n-2;
seatyezi=i;
while(Htree[seatyezi].parent!=-1)
{
fumu=Htree[seatyezi].parent;
if(seatyezi==Htree[fumu].lch)
code[i][j]=0;
else code[i][j]=1;
j=j-1;
seatyezi=fumu;
}
code[i][n-1]=j+1;
}
printf("\n叶子的编码为：\n");
for(i=0;i<n;i++)
{
printf("%c:",Htree[i].yezi);
for(j=code[i][n-1];j<n-1;j++)
printf("%d",code[i][j]);
printf("\n");
}
}
out_huff(struct node Htree[])
{
int i;
printf("\nleave weight parent lch rch\n");
for(i=0;i<n;i++)
printf(" %c %2d %2d %2d %2d \n",Htree[i].yezi,Htree[i].weight,Htree[i].parent,Htree[i].lch,Htree[i].rch);
for(i=n;i<2*n-1;i++)
printf(" %2d %2d %2d %2d \n",Htree[i].weight,Htree[i].parent,Htree[i].lch,Htree[i].rch);
}
void main()
{
creat_huff(Htree);
out_huff(Htree);
code_huff(Htree);
}
