#include <stdio.h>
int s1, s2;
const int maxn = 101; //定义整型常量maxn，值为101
typedef struct //结构体
{
int weight; //定义权重
int leftchild, rightchild, parent; //定义左子结点，右子结点，父节点
}huffuman;
void select(huffuman tree[], int k); //找到权值最小的两个结点
void huffumantree(huffuman tree[], int w[], int n); //建立哈夫曼树
void huffumancode(huffuman tree[], int n); //完成哈夫曼树
int main() //定义主函数
{
int n;
int x;
int w[maxn];
char cha[maxn]; //定义最大值
huffuman tree[maxn];
printf ("-----来建立一棵huffumantree吧！！！-----\n");
while (1)
{
printf (" 1.建立哈夫曼树\n");
printf (" 2.输出哈夫曼树\n");
printf (" 3.退出\n");
printf ("请输入选项：");
scanf ("%d", &x);
// printf ("x = %d\n", x);
if (x == 1)
{
printf ("开始建树操作\n");
printf ("请输入带编码字符个数：");
scanf ("%d", &n);
getchar();
printf ("开始输入字符和对应的权值：\n");
for (int i=1; i<=n; i++) {
printf ("字符 对应的权值：\n");
scanf ("%c%d", &cha[i], &w[i]);
getchar(); //用输入的数据构建哈夫曼树
}
huffumantree(tree, w, n);
}
if (x == 2)
{
printf ("开始输出操作\n"); //执行huffmancode函数,打印结果
huffumancode(tree, n);
}
if (x == 3) //结束主函数运行,退出程序
{
return 0;
}
if (x != 1 && x != 2 && x!= 3) //输入错误
printf ("请输入正确的选项！！！\n");
}
return 0;
}
void select (huffuman tree[], int k) //选择权值最小的两个节点
{
int i; //定义变量i
for (i=1; i<=k && tree[i].parent != 0; i++); //遍历tree[i]数组
s1 = i; //将父节点的下标置0
for (i=1; i<=k; i++) //寻找左右子节点
{
if (tree[i].weight < tree[s1].weight && tree[i].parent ==0) //其中每棵二叉树tree[i]中只要一个权值为wi的根节点,其左右子树均空
s1 = i;
}
for (i=1; i<=k; i++)
if (i != s1 && tree[i].parent == 0)
break;
s2 = i;
for (i=1; i<=k; i++) //比较权重
{
if (i != s1 && tree[i].parent == 0)
if (tree[i].weight <tree[s2].weight)
s2 = i; //找到parent为0,且weight最小的两个结点,其序号分别是s1和s2。
}
}
void huffumantree(huffuman tree[], int w[], int n) //构建哈夫曼树
{
if (n <= 1) //若节点数小于等于1,直接结束
return;
int i;
int m = 2 * n - 1; //m表示哈夫曼树所有节点的个数
for (i=1; i<=n; i++) //将节点进行初始化
{
tree[i].weight = w[i]; //其中每棵二叉树tree[i]中只要一个权值为wi的根节点,其左右子树均空
tree[i].parent = 0;
tree[i].leftchild = 0;
tree[i].rightchild = 0;
}
for (i=n+1; i<=m; i++)
{
tree[i].weight = 0;
tree[i].parent = 0;
tree[i].leftchild = 0;
tree[i].rightchild = 0;
}
for (i=n+1; i<=m; i++)
{
select(tree, i-1); //调用select函数,将找到的两棵根结点的权值最小的树作为左右子树,即s1,s2
tree[s1].parent = i; //找到两个最小节点后,将这两个节点的父节点指向i
tree[s2].parent = i;
tree[i].leftchild = s1; //找到左子节点
tree[i].rightchild = s2; //找到右子节点
tree[i].weight = tree[s1].weight + tree[s2].weight; //新的二叉树的根结点的权值为其左右子树上根结点的权值之和，即父节点的权重
}
}
void huffumancode(huffuman tree[], int n) //完成哈夫曼编码
{
printf ("iweightparentleftchildrightchild\n"); //遍历输出哈夫曼树的weight,parent,leftchild,rightchild
for (int i=1; i<=2*n-1; i++) {
printf ("--%2d %6d %6d %9d %10d---\n", i, tree[i].weight,
tree[i].parent, tree[i].leftchild, tree[i].rightchild);
}
}
怎么加个输出哈夫曼编码
