哈夫曼树

王小二°

#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);
}

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

很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. **编码的打印**：
   您需要在构建完哈夫曼树和编码后，打印出每个字符对应的编码。