我的代码
#include<stdio.h>
#define max 100
typedef struct hufnode
{
int weight;
int parent;
int lchild;
int rchild;
char data;
}hnodetype;
void creathuff(hnodetype huftree[max], int n)
{
int min1, min2, pos1, pos2;
//初始化所有结点
for (int i = 0; i < 2 * n - 1; i++)
{
huftree[i].data = 0;
huftree[i].lchild = -1;
huftree[i].rchild = -1;
huftree[i].parent = -1;
huftree[i].weight = 0;
}
//输入权值和字符
printf("请输入字符以及它的权重:\n");
for (int i = 0; i < n; i++)
{
scanf("%c:%d", &huftree[i].data, &huftree[i].weight);
}
//寻找权值最小的两个合并
for (int i = 0; i < n; i++)
{
min1 = min2 = 999;
pos1 = pos2 = 0;
for (int j = 0; j < n; j++)
{
if (huftree[j].weight < min1 && huftree[j].parent == -1)
{
min1 = huftree[j].weight;
pos1 = j;
}
else if (huftree[j].weight < min2 && huftree[j].parent == -1)
{
min2 = huftree[j].weight;
pos2 = j;
}
}
huftree[min1].parent = n + i;
huftree[min2].parent = n + i;
huftree[n + i].lchild = pos1;
huftree[n + i].rchild = pos2;
huftree[n + i].parent = -1;
huftree[n + i].weight = min1 + min2;
}
}
void huffnode(hnodetype huftree[max],int n,int i)
{
int fa = 0;
int a = 0;
int b[100] = { 0 };
while (huftree[i].parent != -1)
{
fa = huftree[i].parent;
if (i == huftree[fa].lchild)
{
b[a] = 0;
a++;
}
else
{
b[a] = 1;
a++;
}
i = fa;
}
i--;
printf("%c的编码是:\n", huftree[i].data);
for (int k = i; k >= 0; k--)
{
printf("%d", b[k]);
}
}
int main()
{
hnodetype huftree[max];
int n;
printf("请输入你想创建的哈夫曼树的叶子结点数:\n");
scanf("%d", &n);
creathuff(&huftree[max], n);
char c;
printf("请输入你想要查询编码的字符:\n");
scanf("%c", &c);
for (int i = 0; i < n; i++)
{
if (c == huftree[i].data)
{
huffnode(&huftree[max], n, i);
}
else
{
break;
}
}
return 0;
}
题目
运行结果