C语言实现哈夫曼树 代码

Question

C语言实现哈夫曼树要代码
编程这些的东西，有没有知道的人啊
求大家告知，带带我

Answer 1

上午好☀️☀️☀️️
本答案参考ChatGPT-3.5

C语言实现哈夫曼树需要进行以下步骤：

1. 定义结构体Node，表示哈夫曼树中的节点，包含权值和左右子节点指针。

2. 定义哈夫曼树的数据结构HuffmanTree，包含一个Node类型的指针数组nodes和一个int类型的变量size，表示节点数量。

3. 实现一个比较函数，用于在构建哈夫曼树时按权值比较节点大小。

4. 实现一个创建节点的函数createNode，用于根据权值创建一个节点。

5. 实现一个构建哈夫曼树函数buildHuffmanTree，用于根据给定的权值数组构建哈夫曼树。

6. 实现一个编码函数encodeHuffman，将指定的字符编码成哈夫曼编码。

7. 实现一个解码函数decodeHuffman，将指定的哈夫曼编码解码成字符。

以下是C语言实现哈夫曼树的代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CODE_LEN 256

// 结构体Node，表示哈夫曼树中的节点
typedef struct {
    int weight;   // 节点权值
    int parent;   // 父节点下标
    int left;     // 左子节点下标
    int right;    // 右子节点下标
} Node;

// 哈夫曼树的数据结构HuffmanTree
typedef struct {
    Node *nodes;  // 节点数组
    int size;     // 节点数量
} HuffmanTree;

// 比较函数，用于按权值比较节点大小
int compareNode(const void *a, const void *b) {
    int aw = ((Node *)a)->weight;
    int bw = ((Node *)b)->weight;
    return aw - bw;
}

// 创建节点的函数
Node *createNode(int weight, int parent, int left, int right) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->weight = weight;
    node->parent = parent;
    node->left = left;
    node->right = right;
    return node;
}

// 构建哈夫曼树的函数
void buildHuffmanTree(HuffmanTree *tree, int *weights, int size) {
    int i, j, k, m1, m2;
    Node *nodes = (Node *)malloc(sizeof(Node) * size * 2);
    for (i = 0; i < size; i++) {
        nodes[i] = *createNode(weights[i], -1, -1, -1);
    }
    for (i = size; i < size * 2 - 1; i++) {
        m1 = m2 = size;
        for (j = 0; j < i; j++) {
            if (nodes[j].parent == -1) {
                if (nodes[j].weight < nodes[m1].weight) {
                    m2 = m1;
                    m1 = j;
                } else if (nodes[j].weight < nodes[m2].weight) {
                    m2 = j;
                }
            }
        }
        nodes[m1].parent = i;
        nodes[m2].parent = i;
        nodes[i] = *createNode(nodes[m1].weight + nodes[m2].weight, -1, m1, m2);
    }
    tree->nodes = nodes;
    tree->size = size;
}

// 编码函数，将指定的字符编码成哈夫曼编码
void encodeHuffman(HuffmanTree *tree, char *codeTable[MAX_CODE_LEN], char *str, char *code) {
    int i, j, k;
    int len = strlen(str);
    for (i = 0; i < len; i++) {
        for (j = 0; j < tree->size; j++) {
            if (tree->nodes[j].weight == str[i]) {
                k = j;
                while (tree->nodes[k].parent != -1) {
                    code[strlen(code)] = k == tree->nodes[tree->nodes[k].parent].left ? '0' : '1';
                    k = tree->nodes[k].parent;
                }
                for (j = strlen(code) - 1; j >= 0; j--) {
                    codeTable[str[i]][strlen(codeTable[str[i]])] = code[j];
                }
                code[strlen(code)] = 0;
                break;
            }
        }
    }
}

// 解码函数，将指定的哈夫曼编码解码成字符
void decodeHuffman(HuffmanTree *tree, char *codeTable[MAX_CODE_LEN], char *code, char *str) {
    int i, j, k, len;
    len = strlen(code);
    k = tree->size * 2 - 2;
    for (i = 0; i < len; i++) {
        if (code[i] == '0') {
            k = tree->nodes[k].left;
        } else {
            k = tree->nodes[k].right;
        }
        if (tree->nodes[k].left == -1 && tree->nodes[k].right == -1) {
            str[strlen(str)] = tree->nodes[k].weight;
            k = tree->size * 2 - 2;
        }
    }
}

int main() {
    int weights[] = {5, 6, 7, 8, 9, 10};
    HuffmanTree tree;
    buildHuffmanTree(&tree, weights, sizeof(weights) / sizeof(weights[0]));
    char *codeTable[MAX_CODE_LEN] = {0};
    int i, len;
    char code[MAX_CODE_LEN] = {0};
    char str[MAX_CODE_LEN] = "hello world";
    for (i = 0; i < MAX_CODE_LEN; i++) {
        codeTable[i] = (char *)malloc(sizeof(char) * MAX_CODE_LEN);
        codeTable[i][0] = 0;
    }
    encodeHuffman(&tree, codeTable, str, code);
    printf("Huffman Encoding:\n");
    for (i = 0; i < MAX_CODE_LEN; i++) {
        if (codeTable[i][0] != 0) {
            printf("%c:%s\n", i, codeTable[i]);
        }
    }
    char *encoded = (char *)malloc(sizeof(char) * MAX_CODE_LEN * strlen(str));
    encoded[0] = 0;
    len = strlen(str);
    for (i = 0; i < len; i++) {
        strcat(encoded, codeTable[str[i]]);
    }
    printf("Encoded String: %s\n", encoded);
    char *decoded = (char *)malloc(sizeof(char) * MAX_CODE_LEN);
    decoded[0] = 0;
    decodeHuffman(&tree, codeTable, encoded, decoded);
    printf("Decoded String: %s\n", decoded);
    return 0;
}

注：以上代码仅为示例，实际使用时需要进行一定的修改和适应。