哈夫曼编码

以下代码：首先统计了输入字符序列中每个字符出现的次数，然后基于这些统计结果构建了哈夫曼树，并生成了相应的哈夫曼编码和权重

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

#define MAX_CHARACTERS 256

struct Node {
    char data; // 节点存储的数据
    int frequency; // 节点的频率
    struct Node* left, * right; // 左子节点和右子节点的指针
};

struct MinTree {
    int size; // MinTree中存储的节点数
    int capacity; // MinTree的容量
    struct Node** array; // 存储节点的指针数组
};

// 创建一个新的节点
struct Node* newNode(char data, int frequency) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node)); // 为节点分配内存空间
    node->left = node->right = NULL; // 初始化左子节点和右子节点指针为空
    node->data = data; // 设置节点存储的数据
    node->frequency = frequency; // 设置节点的频率
    return node; // 返回创建的节点指针
}

// 创建一个新的MinTree
// capacity: MinTree的容量
struct MinTree* createMinTree(int capacity) {
    struct MinTree* minTree = (struct MinTree*)malloc(sizeof(struct MinTree)); // 为MinTree分配内存空间
    minTree->size = 0; // 初始化MinTree的节点数为0
    minTree->capacity = capacity; // 设置MinTree的容量
    minTree->array = (struct Node**)malloc(capacity * sizeof(struct Node*)); // 为存储节点的指针数组分配内存空间
    return minTree; // 返回创建的MinTree的指针
}

// 交换两个节点的指针
void swapNode(struct Node** a, struct Node** b) {
    struct Node* t = *a; // 临时变量保存第一个节点的指针指向的节点
    *a = *b; // 将第二个节点的指针赋值给第一个节点的指针
    *b = t; // 将临时变量保存的第一个节点的指针赋值给第二个节点的指针
}

// 将最小树中以指定索引为根节点的子树变成最小堆
// minTree: 最小树的指针
// idx: 子树的根节点索引
void minTreeify(struct MinTree* minTree, int idx) {
    int smallest = idx; // 假设根节点的值最小
    int left = 2 * idx + 1; // 左子节点的索引
    int right = 2 * idx + 2; // 右子节点的索引
    // 如果左子节点存在且频率比当前最小节点小，则更新最小节点索引
    if (left < minTree->size && minTree->array[left]->frequency < minTree->array[smallest]->frequency)
        smallest = left;
    // 如果右子节点存在且频率比当前最小节点小，则更新最小节点索引
    if (right < minTree->size && minTree->array[right]->frequency < minTree->array[smallest]->frequency)
        smallest = right;
    // 如果最小节点不是根节点，则交换最小节点和根节点，并对交换后的子树进行调整
    if (smallest != idx) {
        swapNode(&minTree->array[smallest], &minTree->array[idx]);
        minTreeify(minTree, smallest);
    }
}

// 判断MinTree是否只有一个节点
// minTree: MinTree指针
int isSizeOne(struct MinTree* minTree) {
    return (minTree->size == 1);
}

// 从MinTree中提取最小节点
struct Node* extractMin(struct MinTree* minTree) {
    struct Node* temp = minTree->array[0]; // 保存需要提取的最小节点
    minTree->array[0] = minTree->array[minTree->size - 1]; // 将最后一个节点移到根节点位置
    --minTree->size; // MinTree大小减1
    minTreeify(minTree, 0); // 重新调整MinTree的堆序性质
    return temp; // 返回被提取的最小节点
}

// 向MinTree中插入一个节点
void insertMinTree(struct MinTree* minTree, struct Node* node) {
    ++minTree->size; // MinTree大小增加1
    int i = minTree->size - 1;
    while (i && node->frequency < minTree->array[(i - 1) / 2]->frequency) {
        minTree->array[i] = minTree->array[(i - 1) / 2]; // 将父节点移到当前位置
        i = (i - 1) / 2; // 更新位置到父节点的位置
    }
    minTree->array[i] = node; // 将新节点插入到对应位置
}

// 以给定的数据和频率构建哈夫曼树
struct Node* buildHuffmanTree(char data[], int frequency[], int size) {
    struct Node* left, * right, * top;
    struct MinTree* minTree = createMinTree(size); // 创建一个最小堆，用于构建哈夫曼树

    for (int i = 0; i < size; ++i) {
        if (frequency[i] > 0) {
            minTree->array[minTree->size++] = newNode(data[i], frequency[i]); // 将节点插入最小堆中
        }
    }

    // 最小堆化，使堆顶元素为最小值
    for (int i = minTree->size / 2 - 1; i >= 0; --i) {
        minTreeify(minTree, i);
    }

    // 通过不断取出堆顶和次堆顶的方式，构建哈夫曼树
    while (!isSizeOne(minTree)) {
        left = extractMin(minTree); // 取出最小的节点作为左子树
        right = extractMin(minTree); // 取出次小的节点作为右子树
        top = newNode('$', left->frequency + right->frequency); // 创建一个新的节点作为父节点
        top->left = left; // 左子节点
        top->right = right; // 右子节点
        insertMinTree(minTree, top); // 将新节点插入最小堆中
    }

    return extractMin(minTree); // 最后返回哈夫曼树的根节点
}

// 递归打印哈夫曼编码
void printCodes(struct Node* root, int arr[], int top) {
    static int first = 1; // 用于控制输出格式
    if (!(root->left) && !(root->right)) { // 当前节点为叶子节点
        printf("Character: %c, Weight: %u, Huffman Code: ", root->data, root->frequency); // 输出字符、频率和编码
        for (int i = 0; i < top; ++i) {
            printf("%d", arr[i]); // 遍历路径数组，打印编码
        }
        printf("\n");
        if (first) { // 第一次打印该编码时，在最后不需要加换行符
            first = 0;
            return;
        }
    }
    if (root->left) { // 遍历左子树，将路径加入数组，并递归遍历子树
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) { // 遍历右子树，将路径加入数组，并递归遍历子树
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
}

int main() {
    char characters[MAX_CHARACTERS];
    int frequencies[MAX_CHARACTERS] = { 0 };
    int n;

    printf("Enter the number of characters: ");
    scanf("%d", &n);

    printf("Enter %d characters: ", n);
    for (int i = 0; i < n; ++i) {
        scanf(" %c", &characters[i]);
        frequencies[(int)characters[i]]++;
    }

    int L_chars = 0;
    for (int i = 0; i < MAX_CHARACTERS; ++i) {
        if (frequencies[i] > 0) {
            L_chars++;
        }
    }

    char L_characters[100];
    int L_frequencies[100];
    int index = 0;

    for (int i = 0; i < MAX_CHARACTERS; ++i) {
        if (frequencies[i] > 0) {
            L_characters[index] = (char)i;
            L_frequencies[index] = frequencies[i];
            index++;
        }
    }

    struct Node* root = buildHuffmanTree(L_characters, L_frequencies, L_chars);

    int arr[MAX_CHARACTERS], top_index = 0;
    printCodes(root, arr, top_index);

    return 0;
}