#include <stdio.h> #include <string.h> #include <malloc.h> #define N 20 #define M 2*N-1 typedef struct { int weight; int parent; int LChild; int RChild; } HTNode; typedef char *HuffmanCode; // 哈夫曼编码 void Select(HTNode *ht, int n, int *s1, int *s2) { int i, j; int min1, min2; min1 = min2 = 0; for (i = 1; i <= n; i++) { if (ht[i].parent == 0) { if (ht[i].weight < ht[min1].weight) { min2 = min1; min1 = i; } else if (ht[i].weight < ht[min2].weight) { min2 = i; } } } *s1 = min1; *s2 = min2; } void CreateHuffmanTree(HTNode *ht, int w[], int n) { int i, m; int s1, s2; m = 2 * n - 1; for (i = 1; i <= n; i++) { ht[i] = (HTNode) {w[i], 0, 0, 0}; } for (i = n + 1; i <= m; i++) { ht[i] = (HTNode) {0, 0, 0, 0}; } for (i = n + 1; i <= m; i++) { Select(ht, i - 1, &s1, &s2); ht[i].weight = ht[s1].weight + ht[s2].weight; ht[s1].parent = i; ht[s2].parent = i; ht[i].LChild = s1; ht[i].RChild = s2; } } void CreateHuffmanCode(HTNode *ht, HuffmanCode *hc, int n) { int i, m; int start, c, p; char *cd; m = 2 * n - 1; cd = (char *) malloc(sizeof(char) * n); cd[n - 1] = '\0'; for (i = 1; i <= n; i++) { start = n - 1; for (c = i, p = ht[i].parent; p != 0; c = p, p = ht[p].parent) { if (ht[p].LChild == c) { cd[--start] = '0'; } else { cd[--start] = '1'; } } hc[i] = (char *) malloc(sizeof(char) * (n - start)); strcpy(hc[i], &cd[start]); } free(cd); } int main() { int w[N] = {0, 5, 29, 7, 8, 14, 23, 3, 11}; HTNode ht[M]; HuffmanCode hc[N]; int n = 8; int i; CreateHuffmanTree(ht, w, n); CreateHuffmanCode(ht, hc, n); for (i = 1; i <= n; i++) { printf("%d : %s\n", w[i], hc[i]); } return 0; } 该代码无法正常输出结果 问题出在哪里

经过查看代码，发现程序中存在两个问题：

1. 在结构体 HTNode 中，使用了 C99 新增的特性——“柔性数组成员”，即在结构体中定义数组大小为可变量，但该特性只能用于动态内存分配的结构体中，而该程序中定义的是静态数组，因此应该将该特性改为明确的数组大小，例如将代码中的 `int weight;` 改为 `int weight[N];`。

2. 在函数 CreateHuffmanCode 中，定义了一个字符指针 cd，并在循环中对其进行了修改，但在最后并没有释放其动态分配的内存，因此应该在函数末尾添加 `free(cd);` 进行内存释放。

修改后的代码如下：

#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define N 20
#define M 2*N-1

typedef struct {
    int weight[N];
    int parent;
    int LChild;
    int RChild;
} HTNode;

typedef char *HuffmanCode; // 哈夫曼编码

void Select(HTNode *ht, int n, int *s1, int *s2) {
    int i, j;
    int min1, min2;
    min1 = min2 = 0;
    for (i = 1; i <= n; i++) {
        if (ht[i].parent == 0) {
            if (ht[i].weight < ht[min1].weight) {
                min2 = min1;
                min1 = i;
            } else if (ht[i].weight < ht[min2].weight) {
                min2 = i;
            }
        }
    }
    *s1 = min1;
    *s2 = min2;
}

void CreateHuffmanTree(HTNode *ht, int w[], int n) {
    int i, m;
    int s1, s2;
    m = 2 * n - 1;
    for (i = 1; i <= n; i++) {
        ht[i] = (HTNode) { {w[i]}, 0, 0, 0 };
    }
    for (i = n + 1; i <= m; i++) {
        ht[i] = (HTNode) { {0}, 0, 0, 0 };
    }
    for (i = n + 1; i <= m; i++) {
        Select(ht, i - 1, &s1, &s2);
        ht[i].weight[0] = ht[s1].weight[0] + ht[s2].weight[0];
        ht[s1].parent = i;
        ht[s2].parent = i;
        ht[i].LChild = s1;
        ht[i].RChild = s2;
    }
}

void CreateHuffmanCode(HTNode *ht, HuffmanCode *hc, int n) {
    int i, m;
    int start, c, p;
    char *cd;
    m = 2 * n - 1;
    cd = (char *) malloc(sizeof(char) * n);
    cd[n - 1] = '\0';
    for (i = 1; i <= n; i++) {
        start = n - 1;
        for (c = i, p = ht[i].parent; p != 0; c = p, p = ht[p].parent) {
            if (ht[p].LChild == c) {
                cd[--start] = '0';
            } else {
                cd[--start] = '1';
            }
        }
        hc[i] = (char *) malloc(sizeof(char) * (n - start));
        strcpy(hc[i], &cd[start]);
    }
    free(cd);
}

int main() {
    int w[N] = {0, 5, 29, 7, 8, 14, 23, 3, 11};
    HTNode ht[M];
    HuffmanCode hc[N];
    int n = 8;
    int i;
    CreateHuffmanTree(ht, w, n);
    CreateHuffmanCode(ht, hc, n);
    for (i = 1; i <= n; i++) {
        printf("%d : %s\n", w[i], hc[i]);
    }
    return 0;
}