注册 登录
编程论坛 数据结构与算法

哈夫曼编码问题,求解

baolis 发布于 2021-11-26 19:26, 5888 次点击
请你构造出哈夫曼树,设计出哈夫曼编码,并译出该指令的汉语意思。
已知,每个字母的使用频率是:A 8.19 B 1.47 C 3.83 D 3.91 E 12.25 F 2.26 G 1.71  H 4.57  I 7.10 J 0.14  K 0.41  L 3.77  M 3.34  N 7.06  O 7.26  P 2.89  Q 0.09   R 6.85   S 6.36   T 9.41  U 2.58 V 1.09 W 1.59 X 0.21 Y 1.58 Z 0.08
6 回复
#2
diycai2021-11-27 17:30
指令呢?
#3
baolis2021-11-28 10:12
101100010111001010011111011111 10010100111101100101001100111111000
#4
baolis2021-11-28 10:15
我试着弄出来一段“IHERPAEATDRPRA”这玩楞
#5
diycai2021-11-28 22:57
程序代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _LETTER
{
    int weight;
    int index;
    char str[28];
} LETTER;
int compare(const void *a, const void *b)
{
    LETTER *p1, *p2;
    p1 = (LETTER *)a;
    p2 = (LETTER *)b;
    return p2->weight - p1->weight;
}
void main()
{
    LETTER let[52];
    int i, offset;
    for (i=0; i<26; i++)
    {
        scanf("%s%d", let[i].str, &let[i].weight);
        let[i].index = 0;
    }
    qsort(let, 26, sizeof(LETTER), compare);
    for (i=25; i>0; i--)
    {
        memcpy(&let[i*2+1], &let[i], sizeof(LETTER));
        memcpy(&let[i*2], &let[i-1], sizeof(LETTER));
        strcat(let[i-1].str, let[i*2+1].str);
        let[i-1].weight += let[i*2+1].weight;
        let[i-1].index = i*2;
        memset(&let[i], 0, sizeof(LETTER));
        qsort(let, i, sizeof(LETTER), compare);
    }
    char code[] = "10110001011100101001111101111110010100111101100101001100111111000";
    offset = 2;
    for (i=0; i<strlen(code); i++)
    {
        offset += '1' - code[i];
        if (strlen(let[offset].str) == 1)
        {
            printf("%c", let[offset].str[0]);
            offset = 2;
        }
        else
        {
            offset = let[offset].index;
        }
    }
    printf("\n");
    if (offset != 2)
    {
        printf("error\n");
    }
}

输入:
A 819
B 147
C 383
D 391
E 1225
F 226
G 171
H 457
I 710
J 14
K 41
L 377
M 334
N 706
O 726
P 289
Q 9
R 685
S 636
T 941
U 258
V 109
W 159
X 21
Y 158
Z 8
#6
baolis2021-11-28 23:20
我弄出来的也是IHERPAEATPDRPRAS 这个玩楞,翻译不出来啥意思
#7
baolis2021-11-28 23:22
怀疑是老师把指令改了,和字母出现率对应不上
1