哈夫曼树

王小二°

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 30
#define MAX 2*N-1

typedef struct HMtree
{
        double weight;
        char s;
        int parent, rchild, lchild;
}HMtree,HM[MAX+1];

void select(HM ht, int x, int* m1, int* m2)//找出森林中全职最小的两个
{
        double min1 = 999;
        double min2 = 999;
        int j;
        for (j = 1; j <= x; j++)
        {
                if (ht[j].weight < min1 && ht[j].parent == 0)
                {
                        min1 = ht[j].weight;
                        *m1 = j;
                }
        }
        int k;
        for (k = 1; k <= x; k++)
        {
                if (ht[k].weight < min2 && k != *m1 && ht[k].parent == 0)
                {
                        min2 = ht[k].weight;
                        *m2 = k;
                }
        }
}

//构建哈夫曼树
void CreatHM(HM ht, int n)
{
        int i;
        for(i=n+1;i<=2*n-1;i++)
        {
                int m1, m2;
                select(ht, i - 1, &m1, &m2);
                ht[i].weight = ht[m1].weight + ht[m2].weight;
                ht[i].lchild = m1;
                ht[i].rchild = m2;
                ht[i].parent = 0;
                ht[m1].parent = i;
                ht[m2].parent = i;
                
        }
}

//哈夫曼编码
void HMcoding(HM ht, char** hc, int n)
{
        char* cd = (char*)malloc(n * sizeof(char));
        cd[n - 1] = '\0';
        int now = 1;
        int p = 0;
        int start;
        int i = 0;
        while (i < n)
        {
                start = n - 1;
                now = i + 1;
                p = ht[now].parent;
                while (p != 0)
                {
                        start--;
                        if (ht[p].lchild == now)
                        {
                                cd[start] = '0';
                        }
                        else {
                                cd[start] = '1';
                        }
                        now = p;
                        p = ht[now].parent;
                        
                }
                hc[i + 1] = (char*)malloc((n - start) * sizeof(char));
                strcpy(hc[i + 1], &cd[start]);
                i++;
        }
        
}

//先序打印
void dayin(HM ht, char** hc, int index)
{
        if (index >= 1)
        {
                if (ht[index].lchild == 0 && ht[index].rchild)
                {
                        printf("%c:%s\n", ht[index].s, hc[index]);
                        return;
                        
                }
                dayin(ht, hc, ht[index].lchild);
                dayin(ht, hc, ht[index].rchild);
        }
}

//在生成的树里查找目标
void chaHM(HM ht, int n,char* pwd)
{
        printf("original:");
        int len = strlen(pwd);
        int i = 0;
        int node = 2 * n - 1;
        while (i < len)
        {
                if (pwd[i] == '0')
                {
                        node = ht[node].lchild;
                        i++;
                        if (ht[node].lchild == 0 && ht[node].rchild == 0)
                        {
                                printf("%c", ht[node].s);
                                node = 2 * n - 1;
                        }
                }
                if (pwd[i] == '1')
                {
                        node = ht[node].rchild;
                        i++;
                        if (ht[node].lchild == 0 && ht[node].rchild == 0)
                        {
                                printf("%c", ht[node].s);
                                node = 2 * n - 1;
                        }
                }
        }
}

int main()
{
        HM ht;
        int n;//字符个数
        scanf("%d", &n);
        getchar();
        char* hc[4 + 1];
        int i;
        for (i = 1; i <= n; i++)
        {
                scanf("%c%lf", &ht[i].s, &ht[i].weight);
                getchar();
                ht[i].lchild = 0;
                ht[i].rchild = 0;
                ht[i].parent = 0;
                
        }
        char pwd[99];
        scanf("%s", pwd);
        CreatHM(ht, n);
        HMcoding(ht,hc,n);
        dayin(ht, hc, 2 * n - 1);
        chaHM(ht, n, pwd);
}

我的问题是为什么没有对应每个字符的编码的输出，是函数哪里出问题了吗？

小甲鱼的二师兄

主要问题出在 dayin 函数的实现中。

在判断叶子节点时存在逻辑错误，导致没有正确打印字符的编码。

修复后的完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 30
#define MAX 2 * N - 1

typedef struct HMtree {
    double weight;
    char s;
    int parent, rchild, lchild;
} HMtree, HM[MAX + 1];

void selectMin(HM ht, int x, int* m1, int* m2) {
    double min1 = 999;
    double min2 = 999;
    int j;
    for (j = 1; j <= x; j++) {
        if (ht[j].weight < min1 && ht[j].parent == 0) {
            min1 = ht[j].weight;
            *m1 = j;
        }
    }
    int k;
    for (k = 1; k <= x; k++) {
        if (ht[k].weight < min2 && k != *m1 && ht[k].parent == 0) {
            min2 = ht[k].weight;
            *m2 = k;
        }
    }
}

// 构建哈夫曼树
void CreatHM(HM ht, int n) {
    int i;
    for (i = n + 1; i <= 2 * n - 1; i++) {
        int m1, m2;
        selectMin(ht, i - 1, &m1, &m2);
        ht[i].weight = ht[m1].weight + ht[m2].weight;
        ht[i].lchild = m1;
        ht[i].rchild = m2;
        ht[i].parent = 0;
        ht[m1].parent = i;
        ht[m2].parent = i;
    }
}

// 哈夫曼编码
void HMcoding(HM ht, char** hc, int n) {
    char* cd = (char*)malloc(n * sizeof(char));
    cd[n - 1] = '\0';
    int now = 1;
    int p = 0;
    int start;
    int i = 0;
    while (i < n) {
        start = n - 1;
        now = i + 1;
        p = ht[now].parent;
        while (p != 0) {
            start--;
            if (ht[p].lchild == now) {
                cd[start] = '0';
            } else {
                cd[start] = '1';
            }
            now = p;
            p = ht[now].parent;
        }
        hc[i] = (char*)malloc((n - start + 1) * sizeof(char)); // 改为从 0 开始
        strcpy(hc[i], &cd[start]);
        i++;
    }
    free(cd);
}

// 先序打印
void dayin(HM ht, char** hc, int index) {
    if (index >= 1) {
        if (ht[index].lchild == 0 && ht[index].rchild == 0) { // 叶子节点
            printf("%c:%s\n", ht[index].s, hc[index - 1]); // 索引从 0 开始
            return;
        }
        // 遍历左子树
        dayin(ht, hc, ht[index].lchild);
        // 遍历右子树
        dayin(ht, hc, ht[index].rchild);
    }
}

// 在生成的树里查找目标
void chaHM(HM ht, int n, char* pwd) {
    printf("original:");
    int len = strlen(pwd);
    int i = 0;
    int node = 2 * n - 1;
    while (i < len) {
        if (pwd[i] == '0') {
            node = ht[node].lchild;
            i++;
            if (ht[node].lchild == 0 && ht[node].rchild == 0) { // 到达叶子节点
                printf("%c", ht[node].s);
                node = 2 * n - 1;
            }
        } else if (pwd[i] == '1') {
            node = ht[node].rchild;
            i++;
            if (ht[node].lchild == 0 && ht[node].rchild == 0) { // 到达叶子节点
                printf("%c", ht[node].s);
                node = 2 * n - 1;
            }
        } else { // 非法输入
            printf("\nError: Invalid character in encoded string.\n");
            return;
        }
    }
    printf("\n");
}

int main() {
    HM ht;
    int n; // 字符个数
    printf("Enter the number of characters:\n");
    scanf("%d", &n);
    getchar();
    char* hc[N]; // 动态调整大小，索引从 0 开始
    int i;
    printf("Enter characters and their weights (format: <char> <weight>):\n");
    for (i = 1; i <= n; i++) {
        scanf("%c %lf", &ht[i].s, &ht[i].weight);
        getchar();
        ht[i].lchild = 0;
        ht[i].rchild = 0;
        ht[i].parent = 0;
    }
    char pwd[99];
    printf("Enter the encoded string:\n");
    scanf("%s", pwd);
    CreatHM(ht, n);
    HMcoding(ht, hc, n);
    printf("Huffman Codes:\n");
    dayin(ht, hc, 2 * n - 1);
    chaHM(ht, n, pwd);
    // 释放动态分配的内存
    for (i = 0; i < n; i++) {
        free(hc[i]);
    }
    return 0;
}

很cool的阳

您的代码中存在几个问题，可能导致没有对应每个字符的编码输出。以下是我发现的一些问题和相应的解决方案：

1. **`HMcoding`函数中的内存分配问题**：
   在`HMcoding`函数中，您为`cd`分配了`n * sizeof(char)`大小的内存，但实际需要的内存应该是`n + 1`，因为字符串的结尾需要一个空字符`'\0'`。

   ```c
   char* cd = (char*)malloc((n + 1) * sizeof(char)); // 修改这里
   ```

2. **`HMcoding`函数中的字符串复制问题**：
   在复制编码到`hc[i + 1]`时，您应该使用`strncpy`来确保正确复制字符串，并且要设置目标字符串的结束符。

   ```c
   strncpy(hc[i + 1], &cd[start], n - start);
   hc[i + 1][n - start] = '\0'; // 确保字符串正确结束
   ```

3. **`HMcoding`函数中的逻辑问题**：
   您的`HMcoding`函数逻辑似乎有误。您应该从叶子节点开始构建编码，而不是从根节点开始。此外，您需要为每个字符分配一个编码，而不是只分配一个。

4. **`dayin`函数的实现问题**：
   您的`dayin`函数似乎是想实现先序遍历打印哈夫曼树，但是实现有误。您需要一个递归函数来正确地打印每个节点的值和对应的编码。

5. **`chaHM`函数中的逻辑问题**：
   在`chaHM`函数中，当找到叶子节点时，您应该继续打印字符，直到遍历完整个密码串。

6. **`main`函数中的`hc`数组初始化问题**：
   您需要为`hc`数组的每个元素分配足够的内存，以存储可能的最长编码。

7. **`main`函数中的输入问题**：
   在读取字符和权重后，您使用了`getchar()`来消耗换行符，这在某些情况下可能会导致问题。确保输入格式正确，并且`getchar()`的使用是恰当的。

8. **编码的打印**：
   您需要在构建完哈夫曼树和编码后，打印出每个字符对应的编码。