关于哈夫曼树的译码的问题!!一直解决不了…代码和我解决不了的问题在下面
代码和运行结果在这里!出现的问题是:编码是正确的 但是译码的时候输出的一直是两个烫字……我找了半天 没觉得我赋值有问题啊(况且有问题的话编码为什么对呢?)而且我也没发现我的访问位置有错……(真的找不出来了 …大神帮忙 (我是新手…谢谢各位了!#include<stdio.h>
#include<string.h>
#define MAX 100
typedef struct
{
char data;
double weight;
int parent;
int lchild;
int rchild;
}HTNode;
typedef struct //建立栈节点
{
int code[MAX];
int top;
}SeqStack;
void main()
{
void CreateHT(HTNode ht[],int n);
void HuffmanCode(HTNode ht[],SeqStack hc[],int n);
void HuffmanNode(HTNode ht[],int n);
HTNode ht[MAX];
SeqStack hc[MAX];
double f;
int i,n;
printf(" 哈夫曼树的构造及应用\n");
printf("请输入叶子数目 n:"); /*提示输出叶子结点个数*/
scanf("%d",&n);
printf("Please input data and weight:\n"); /*提示输出各叶子结点的权值*/
fflush(stdin);
for(i=0;i<n;i++)
{
scanf("%c",&ht[i].data);
getchar();
scanf("%lf",&f);
ht[i].weight=f;
getchar();
}
CreateHT(ht,n);
printf("哈弗曼编码为:\n");
HuffmanCode(ht,hc,n);
printf("哈夫曼译码为:\n");
HuffmanNode(ht,n);
}
void CreateHT(HTNode ht[],int n) /*ht保存哈夫曼树中各节点信息(可修改)
n为节点个数*/
{
int i,k,lnode,rnode;
double min1,min2;
for(i=0;i<=2*n-1;i++) // 所有节点相关域值初值为1
{
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
}
for(i=n;i<2*n-1;i++) //构造哈夫曼树
{
min1=min2=32767; //lnode和rnode为最小权重的两个节点位置
lnode=rnode=-1;
for(k=0;k<=i-1;k++)
if(ht[k].parent==-1) //只在尚未构造二叉树的节点中查找
{
if(ht[k].weight<min1)
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if(ht[k].weight<min2)
{
min2=ht[k].weight;rnode=k;
}
}
//将找出的两棵子树合并为一棵子树
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
ht[lnode].parent=ht[rnode].parent=i;
}
for(i=0;i<2*n-1;i++)
printf("%c,%f,%d,%d,%d\n",ht[i].data,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
}
void HuffmanCode(HTNode ht[],SeqStack hc[],int n)
{
int i,f,c;
for(i=0;i<n;i++)
{
hc[i].top=-1;
c=i;
while(ht[c].parent!=-1)
{
f=ht[c].parent;
if(ht[f].lchild==c)
{
hc[i].code[hc[i].top+1]=0;
hc[i].top++;
}
else if(ht[f].rchild==c)
{
hc[i].code[hc[i].top+1]=1;
hc[i].top++;
}
c=f;
}
printf("%c",ht[i].data);
printf("的编码为:");
for(;hc[i].top>=0;hc[i].top--)
printf("%d",hc[i].code[hc[i].top]);
printf("\n");
}
}
void HuffmanNode(HTNode ht[],int n)
{
int i,c=2*n-1,k;
int a[MAX];
printf("请输入密文长度:");
scanf("%d",&k);
printf("请输入密文:");
for(i=0;i<k;i++)
{
scanf("%d",&a[i]);
getchar();
}
for(i=0;i<k;i++)
{
c=2*n-1;
while(ht[c].lchild!=-1&&ht[c].rchild!=-1)
{
if(a[i]==0)
{
c=ht[c].lchild;
}
else if(a[i]==1)
{
c=ht[c].rchild;
}
i++;
}
printf("%c",ht[c].data);
}
}