C语言哈夫曼编码打印结果只有一位数

Question

求哈夫曼树和编码的代码如下，运行结果如图。疑似是求哈夫曼编码的函数模块出问题，请问为什么有这种错误？如何修改？

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {//哈夫曼树的每个叶子？结点的信息
    int weight;//权
    int parent, lchild, rchild;//该结点的父结点，左子结点，右子结点在数组中的编号
}HTNode, * Huffmantree;//结构体名
typedef char** HuffmanCode;
void Select(Huffmantree& HT, int i, int& s1, int& s2)//选择函数：用于从叶子结点开始构建哈夫曼树
{
    s1 = 0; s2 = 0;
    int min1 = 100; int min2 = 100;
    for (int k = 1; k <= i; k++)
    {
        if (HT[k].parent == 0)
        {
            if (HT[k].weight < min1)
            {
                min2 = min1;
                s2 = s1;
                min1 = HT[k].weight;
                s1 = k;
            }
            else if (HT[k].weight < min2)
            {
                min2 = HT[k].weight;
                s2 = k;
            }
        }
    }
}
void HuffmanCoding(Huffmantree& HT, HuffmanCode& HC, int* w, int n)//构建哈夫曼树并求哈夫曼编码
{
    if (n <= 1) return;
    int m = n * 2 - 1;//m为哈夫曼树的全部结点个数
    int i;//循环计数器
    Huffmantree p;
    HT = (Huffmantree)malloc((m + 1) * sizeof(HTNode));
    for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w)
    {
        p->weight = *w;
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }
    for (; i <= m; ++i, ++p)
    {
        p->weight = 0;
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }
    //建立哈夫曼树
    for (i = n + 1; i <= m; ++i)
    {
        int s1, s2;
        Select(HT, i - 1, s1, s2);
        HT[s1].parent = i;
        HT[s2].parent = i;
        HT[i].lchild = s1; HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
    //从叶子到根逆向求哈夫曼编码
    HC = (HuffmanCode)malloc(sizeof(char*)*(n+1));
    char* cd;
    cd = (char*)malloc(n * sizeof(char));//为cd申请n个存储空间
    cd[n - 1] = '\0';
    int c, f;
    for (i = 1; i <= n; ++i)
    {
        int start = n - 1;
        c = i;
        f = HT[c].parent;
        while (f)
        {
            if (HT[f].lchild == c)
                cd[--start] = '0';
            else
                cd[--start] = '1';
            c = f;
            f = HT[c].parent;
        }
        HC[i] = (char*)malloc((n - start) * sizeof(char));
        strcpy_s(HC[i], n - start + 1, &cd[start]);
    }
    free(cd);
}
int main(void)
{
    int n = 8;
    int w[8] = { 5,29,7,8,14,23,3,11 };
    Huffmantree HT;
    HuffmanCode HC;
    int j;
    HuffmanCoding(HT, HC, w, n);
    printf("初始化如下\n");
    printf("     weight  parent  lchild rchild\n");
    for (j = 1; j <= 15; j++)
    {
        printf("HT[%d] %6d%6d%6d%6d\n", j, HT[j].weight, HT[j].parent, HT[j].lchild, HT[j].rchild);
    }
    printf("\n");
    printf("编码如下\n");
    for (j = 1; j <= 15; j++)
    {
        printf("HT[%d] %c\n", j, *HC[j]);
    }
    printf("\n");
    return 0;
}

Answer 1

• 问题出在main函数的打印部分，你使用*HC[j]，这只会打印哈夫曼编码字符串的第一个字符。

• 你应该使用循环或者其他方法来打印整个字符串。这是修正后的打印编码的代码段：

printf("编码如下\n");
for (j = 1; j <= n; j++) // 注意这里应该是 j <= n，因为我们只对前n个元素进行了编码
{
    printf("HT[%d] %s\n", j, HC[j]);
}

用%s代替%c来格式化输出字符串，并且循环条件是j <= n而不是j <= 15，因为你的哈夫曼编码数组HC中只有n个编码字符串，从HC[1]到HC[n]