鱼C论坛

 找回密码
 立即注册
查看: 266|回复: 0

[C\C++] 哈夫曼树

[复制链接]
发表于 2024-6-26 09:59:19 | 显示全部楼层 |阅读模式
60鱼币
#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);
}
我的问题是为什么没有对应每个字符的编码的输出,是函数哪里出问题了吗?

屏幕截图 2024-06-25 214948.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-7-17 03:15

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表