[已解决]该贴无效，请删除

小纸张二号

设字符集为10个字符，其出现频度如下表所示。先建哈夫曼树，输出对应字符的译码，再利用此树对报文“ADEC”进行编码和译码，输出对应
字符        A        B        C        D        E        F        G        H        I        J
频度        24     20        1        7        9        11        8        15    2        3

最佳答案

月排行榜 / 总排行榜

Croper

2019-12-20 20:19:58

//vs的调试功能太好用，我是在vs里写的代码，但其不支持C语言的部分功能,例如变长数组，例如直接使用strlen（即使在C环境下） \
所以使用宏定义#ifdef __cplusplus确保程序在传统C环境下也能运行；

//不使用数组代替二叉树，因为霍夫曼树可能非常“不完全”，其使用数组代替时占用空间可能过大；

#ifdef __cplusplus
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <malloc.h>
#include <memory.h>
#include <string.h>
#endif
#include <stdio.h>

#define _Out_
#ifndef NULL
#define NULL 0
#endif

typedef char string[128];  //单个字符编码长度不超过128；

//霍夫曼书的节点
typedef struct node_t {   
        struct node_t* left;
        struct node_t* right;
        struct node_t* parent;
        int freq;
        char code;
}node;


//删除树
void DestroyTree(node* root) {
        if (!root) return;
        DestroyTree(root->left);
        DestroyTree(root->right);
        free(root);
};


//生成编码
string* generateHuffmanCode(char ch[], int freq[], int N, string _Out_ *codelist) {
        int i, j, k;

#ifdef __cplusplus
        node *pool[128], *pool_backup[128];  //c++环境下不支持变长数组；
#else
        node *pool[N], *pool_backup[N];
#endif

        //为每个字符创建节点
        for (i = 0; i < N; ++i) {
                pool[i] = (node*)malloc(sizeof(node));
                pool[i]->freq = freq[i];
                pool[i]->left = NULL;
                pool[i]->right = NULL;
                pool[i]->parent = NULL;
        }
        //做一个备份
        memcpy(pool_backup, pool, sizeof(pool));

        //每次选取两个节点组合，共需组合N-1次
        for (i = 0; i < N - 1; ++i) {
                int min_freq[2]; //频次最低的两个节点的编号
                memset(min_freq, -1, sizeof(min_freq));
                for (j = 0; j < N - i; ++j) {
                        if (min_freq[0] == -1 || pool[j]->freq < pool[min_freq[0]]->freq) {
                                min_freq[1] = min_freq[0];
                                min_freq[0] = j;
                        }
                        else if (min_freq[1] == -1 || pool[j]->freq < pool[min_freq[1]]->freq) {
                                min_freq[1] = j;
                        }
                }

                //组合两个节点，新节点的频次是两个子节点之和
                node* sum = (node*)malloc(sizeof(node));
                sum->left = pool[min_freq[0]];
                sum->right = pool[min_freq[1]];
                sum->parent = NULL;

                sum->left->code = '0';
                sum->right->code = '1';
                sum->left->parent = sum;
                sum->right->parent = sum;
                sum->freq = sum->left->freq + sum->right->freq;

                //于节点池中，用新节点代替原有子节点，并移除另一个子节点
                pool[min_freq[0]] = sum;
                for (j = min_freq[1]; j + 1 < N - i; ++j) {
                        pool[j] = pool[j + 1];
                }
        }
        //霍夫曼树生成完毕

        
        pool[0]->code = 0;
        for (i = 0; i < 128; ++i) {
                codelist[i][0] = 0;
        }
        //对于每一个字符对应的节点（即叶节点），向上搜寻直到根节点，路径即为颠倒的编码；
        for (i = 0; i < N; ++i) {
                node* p = pool_backup[i];
                char *line = codelist[ch[i]];
                for (j = 0; p != NULL; ++j, p = p->parent) {
                        line[j] = p->code;
                }
                j--;

                //再将颠倒的编码回正
                for (k = 0; k < j / 2; ++k) {
                        char t = codelist[ch[i]][k];
                        line[k] = line[j - 1 - k];
                        line[j - 1 - k] = t;
                }
        }

        //删除霍夫曼树，释放空间
        DestroyTree(pool[0]);

        return codelist;
}

//根据编码表编码字符串
char* encode(char* sz, string codelist[], char* _Out_ szEncoded) {
        char* p = szEncoded;
        while (*sz) {
                int l = strlen(codelist[*sz]);
                strcpy(p, codelist[*sz]);
                p += l;
                sz++;
        }
        return szEncoded;
}

//解码字符串
char* decode(char* szEncoded, string codelist[], char* _Out_ szDecoded) {
        int i, j;

        //根据编码表重新生成树
        node* root = (node*)malloc(sizeof(node));
        root->left = NULL;
        root->right = NULL;
        for (i = 0; i < 128; ++i) {
                node* p;
                char* pch;
                for (p = root, pch = codelist[i]; *pch != 0; ++pch) {
                        if (*pch == '0') {
                                if (p->left == NULL) {
                                        p->left = (node*)malloc(sizeof(node));
                                        p->left->left = NULL;
                                        p->left->right = NULL;
                                }
                                p = p->left;
                        }
                        else if (*pch == '1') {
                                if (p->right == NULL) {
                                        p->right = (node*)malloc(sizeof(node));
                                        p->right->left = NULL;
                                        p->right->right = NULL;
                                }
                                p = p->right;
                        }
                }
                p->code = i;
        }


        //根据编码的0或1，进入当前节点的左子树或右子树，直到到达叶节点，并记录
        char* pch, *pret;
        node* p;
        for (p = root, pch = szEncoded, pret = szDecoded; *pch != 0; ++pch) {
                if (*pch == '0') {
                        p = p->left;
                }
                else {
                        p = p->right;
                }
                if (p->left == NULL) {
                        *pret++ = p->code;
                        p = root;
                }
        }

        //删除树，释放空间
        DestroyTree(root);
        *pret = '\0';
        return szDecoded;
}

int main() {
        string codelist[128];
        char sz[] = { 'A','B','C','D','E','F','G','H','I','J'};
        int freq[] = { 24,20,1,7,9,11,8,15,2,3};

        generateHuffmanCode(sz, freq, sizeof(sz), codelist);

        printf("========编码表================\n");
        unsigned char c;
        for (c = 0; c < 128; ++c) {
                if (codelist[c][0] == 0) continue;
                printf("%c:%s\n", c, codelist[c]);
        }

        char a[] = "ADEC";
        char code[1024];
        char b[10];
        encode(a, codelist, code);
        decode(code, codelist, b);
        printf("===================================\n");
        printf("%s 的编码结果为%s\n", a, code);
        printf("%s 的解码结果为%s\n", code, b);
#ifdef __cplusplus
        system("pause");
#endif
}

跳转到最佳答案楼层

Croper

//vs的调试功能太好用，我是在vs里写的代码，但其不支持C语言的部分功能,例如变长数组，例如直接使用strlen（即使在C环境下） \
所以使用宏定义#ifdef __cplusplus确保程序在传统C环境下也能运行；

//不使用数组代替二叉树，因为霍夫曼树可能非常“不完全”，其使用数组代替时占用空间可能过大；

#ifdef __cplusplus
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <malloc.h>
#include <memory.h>
#include <string.h>
#endif
#include <stdio.h>

#define _Out_
#ifndef NULL
#define NULL 0
#endif

typedef char string[128];  //单个字符编码长度不超过128；

//霍夫曼书的节点
typedef struct node_t {   
        struct node_t* left;
        struct node_t* right;
        struct node_t* parent;
        int freq;
        char code;
}node;


//删除树
void DestroyTree(node* root) {
        if (!root) return;
        DestroyTree(root->left);
        DestroyTree(root->right);
        free(root);
};


//生成编码
string* generateHuffmanCode(char ch[], int freq[], int N, string _Out_ *codelist) {
        int i, j, k;

#ifdef __cplusplus
        node *pool[128], *pool_backup[128];  //c++环境下不支持变长数组；
#else
        node *pool[N], *pool_backup[N];
#endif

        //为每个字符创建节点
        for (i = 0; i < N; ++i) {
                pool[i] = (node*)malloc(sizeof(node));
                pool[i]->freq = freq[i];
                pool[i]->left = NULL;
                pool[i]->right = NULL;
                pool[i]->parent = NULL;
        }
        //做一个备份
        memcpy(pool_backup, pool, sizeof(pool));

        //每次选取两个节点组合，共需组合N-1次
        for (i = 0; i < N - 1; ++i) {
                int min_freq[2]; //频次最低的两个节点的编号
                memset(min_freq, -1, sizeof(min_freq));
                for (j = 0; j < N - i; ++j) {
                        if (min_freq[0] == -1 || pool[j]->freq < pool[min_freq[0]]->freq) {
                                min_freq[1] = min_freq[0];
                                min_freq[0] = j;
                        }
                        else if (min_freq[1] == -1 || pool[j]->freq < pool[min_freq[1]]->freq) {
                                min_freq[1] = j;
                        }
                }

                //组合两个节点，新节点的频次是两个子节点之和
                node* sum = (node*)malloc(sizeof(node));
                sum->left = pool[min_freq[0]];
                sum->right = pool[min_freq[1]];
                sum->parent = NULL;

                sum->left->code = '0';
                sum->right->code = '1';
                sum->left->parent = sum;
                sum->right->parent = sum;
                sum->freq = sum->left->freq + sum->right->freq;

                //于节点池中，用新节点代替原有子节点，并移除另一个子节点
                pool[min_freq[0]] = sum;
                for (j = min_freq[1]; j + 1 < N - i; ++j) {
                        pool[j] = pool[j + 1];
                }
        }
        //霍夫曼树生成完毕

        
        pool[0]->code = 0;
        for (i = 0; i < 128; ++i) {
                codelist[i][0] = 0;
        }
        //对于每一个字符对应的节点（即叶节点），向上搜寻直到根节点，路径即为颠倒的编码；
        for (i = 0; i < N; ++i) {
                node* p = pool_backup[i];
                char *line = codelist[ch[i]];
                for (j = 0; p != NULL; ++j, p = p->parent) {
                        line[j] = p->code;
                }
                j--;

                //再将颠倒的编码回正
                for (k = 0; k < j / 2; ++k) {
                        char t = codelist[ch[i]][k];
                        line[k] = line[j - 1 - k];
                        line[j - 1 - k] = t;
                }
        }

        //删除霍夫曼树，释放空间
        DestroyTree(pool[0]);

        return codelist;
}

//根据编码表编码字符串
char* encode(char* sz, string codelist[], char* _Out_ szEncoded) {
        char* p = szEncoded;
        while (*sz) {
                int l = strlen(codelist[*sz]);
                strcpy(p, codelist[*sz]);
                p += l;
                sz++;
        }
        return szEncoded;
}

//解码字符串
char* decode(char* szEncoded, string codelist[], char* _Out_ szDecoded) {
        int i, j;

        //根据编码表重新生成树
        node* root = (node*)malloc(sizeof(node));
        root->left = NULL;
        root->right = NULL;
        for (i = 0; i < 128; ++i) {
                node* p;
                char* pch;
                for (p = root, pch = codelist[i]; *pch != 0; ++pch) {
                        if (*pch == '0') {
                                if (p->left == NULL) {
                                        p->left = (node*)malloc(sizeof(node));
                                        p->left->left = NULL;
                                        p->left->right = NULL;
                                }
                                p = p->left;
                        }
                        else if (*pch == '1') {
                                if (p->right == NULL) {
                                        p->right = (node*)malloc(sizeof(node));
                                        p->right->left = NULL;
                                        p->right->right = NULL;
                                }
                                p = p->right;
                        }
                }
                p->code = i;
        }


        //根据编码的0或1，进入当前节点的左子树或右子树，直到到达叶节点，并记录
        char* pch, *pret;
        node* p;
        for (p = root, pch = szEncoded, pret = szDecoded; *pch != 0; ++pch) {
                if (*pch == '0') {
                        p = p->left;
                }
                else {
                        p = p->right;
                }
                if (p->left == NULL) {
                        *pret++ = p->code;
                        p = root;
                }
        }

        //删除树，释放空间
        DestroyTree(root);
        *pret = '\0';
        return szDecoded;
}

int main() {
        string codelist[128];
        char sz[] = { 'A','B','C','D','E','F','G','H','I','J'};
        int freq[] = { 24,20,1,7,9,11,8,15,2,3};

        generateHuffmanCode(sz, freq, sizeof(sz), codelist);

        printf("========编码表================\n");
        unsigned char c;
        for (c = 0; c < 128; ++c) {
                if (codelist[c][0] == 0) continue;
                printf("%c:%s\n", c, codelist[c]);
        }

        char a[] = "ADEC";
        char code[1024];
        char b[10];
        encode(a, codelist, code);
        decode(code, codelist, b);
        printf("===================================\n");
        printf("%s 的编码结果为%s\n", a, code);
        printf("%s 的解码结果为%s\n", code, b);
#ifdef __cplusplus
        system("pause");
#endif
}