2015-11-05 11:16

# 一个程序，哈夫曼树的构造遍历打印，编码解码，缺少遍历和打印

#include
#include /* 数组头文件 /
#include
#define MAX 999 /

typedef struct{ /

char data;
int weight; /

int parent;
int lchild;
int rchild;
}huffmannode;
typedef struct{ /

char bits[50];
int start;
}huffmancode ;
void main()
{
huffmannode ht[100]; /

huffmancode cd[100];
char string[100]; /

char hcd[100];
int i,j,x,y,s1,s2,m1,m2,n,c,f,k;
printf("please input the n ="); /

scanf("%d",&n);
printf("\n============================\n");
for(i=0;i<n;i++)
{

getchar(); /

scanf("%c",&ht[i].data); /

scanf("%d",&ht[i].weight);
}
printf("\n=============================\n");
for(i=0;i<2*n-1;i++)
{
ht[i].parent=ht[i].lchild=ht[i].rchild=-1; /

}
for (i=n;i<2*n-1;i++)
{
s1=s2=0; /

m1=m2=MAX;
for (j=0;j<i;j++)
{
if (ht[j].weight<m1 &&ht[j].parent==-1) /

{
m2=m1;
s2=s1;
m1=ht[j].weight;
s1=j; /

}
else if(ht[j].weight<m2 &&ht[j].parent==-1) /

{
m2=ht[j].weight;
s2=j;
} /

}
ht[s1].parent=i; /
s1的父结点为i /
ht[s2].parent=i;
ht[i].weight=m1+m2; /

ht[i].lchild=s1; /
i的左子为s1 /
ht[i].rchild=s2; /
i的右子为s2 /
}
for(i=0;i<n;i++)
{
cd[i].start=n;
x=i;
y=ht[x].parent; /

while (y!=-1)
{
if (ht[y].lchild==x)
cd[i].bits[cd[i].start]='0'; /

else
cd[i].bits[cd[i].start]='1'; /

cd[i].start--;
x=y;
y=ht[y].parent;
}
}
printf("\cout the huffmancode:\n");
for (i=0;i<n;i++)
{
printf("%c:",ht[i].data); /

for(j=cd[i].start;j<=n;j++){
printf("%c",cd[i].bits[j]); /

}
printf("\n");
}
printf("\n=============================\n");
scanf("%s",string); /

for(i=0;string[i]!='0';i++)
{
for(c=0;c<=n;c++)
if(string[i]==ht[c].data) /

{
for(j=cd[c].start;j<=n;j++)
printf("%c",cd[c].bits[j]); /

break;
}
}
printf("\n=============================\n");
scanf("%s",hcd); /

f=2*n-2;
for(i=0;hcd[i]!='\0';i++)
{
if(hcd[i]=='0') /

f=ht[f].lchild;
else if(hcd[i]=='1')
f=ht[f].rchild; /

if(f<n)
{
printf("%c",ht[f].data); /

f=2*n-2;
}
}
printf("\n");
getch();

}

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享
• 邀请回答