(数据结构)哈夫曼编码实现（C语言）

一时失言乱红尘 2023-10-13 22:06 7阅读 0赞

### (数据结构)哈夫曼编码实现（C语言） ###

> 哈夫曼的编码:从一堆数组当中取出来最小的两个值，按照左下右大的进行绘制，将两个权值之和，放入队列当中，然后再进行取出两个小的，以此类推，直到全部结束，在根据图根节点，到叶子节点，每一个分支来得出编码，向左0，向右1，即可得到一个结果。

#include <stdio.h>
    #include <stdlib.h>
    
    // 定义哈夫曼树结点的结构
    struct Node {
        
        int frequency;
        char data;
        struct Node* left;
        struct Node* right;
    };
    
    // 创建一个新的哈夫曼树结点
    struct Node* newNode(int frequency, char data) {
        
        struct Node* node = (struct Node*)malloc(sizeof(struct Node));
        node->frequency = frequency;
        node->data = data;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    
    struct MinHeap {
        
        int size;
        int capacity;
        struct Node** array;
    };
    
    // 创建最小堆
    struct MinHeap* createMinHeap(int capacity) {
        
        struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
        minHeap->size = 0;
        minHeap->capacity = capacity;
        minHeap->array = (struct Node**)malloc(capacity * sizeof(struct Node*));
        return minHeap;
    }
    
    // 交换两个结点的位置
    void swapNode(struct Node** a, struct Node** b) {
        
        struct Node* temp = *a;
        *a = *b;
        *b = temp;
    }
    
    // 维护最小堆的性质
    void minHeapify(struct MinHeap* minHeap, int idx) {
        
        int smallest = idx;
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
    
        if (left < minHeap->size && minHeap->array[left]->frequency < minHeap->array[smallest]->frequency) {
        
            smallest = left;
        }
    
        if (right < minHeap->size && minHeap->array[right]->frequency < minHeap->array[smallest]->frequency) {
        
            smallest = right;
        }
    
        if (smallest != idx) {
        
            swapNode(&minHeap->array[smallest], &minHeap->array[idx]);
            minHeapify(minHeap, smallest);
        }
    }
    
    // 检查最小堆是否只有一个元素
    int isSizeOne(struct MinHeap* minHeap) {
        
        return minHeap->size == 1;
    }
    
    // 检查结点是否是叶子结点
    int isLeaf(struct Node* root) {
        
        return !(root->left) && !(root->right);
    }
    
    // 从最小堆中提取最小值（即频率最小的结点）
    struct Node* extractMin(struct MinHeap* minHeap) {
        
        struct Node* temp = minHeap->array[0];
        minHeap->array[0] = minHeap->array[minHeap->size - 1];
        --minHeap->size;
        minHeapify(minHeap, 0);
        return temp;
    }
    
    // 将结点插入最小堆
    void insertMinHeap(struct MinHeap* minHeap, struct Node* node) {
        
        ++minHeap->size;
        int i = minHeap->size - 1;
    
        while (i && node->frequency < minHeap->array[(i - 1) / 2]->frequency) {
        
            minHeap->array[i] = minHeap->array[(i - 1) / 2];
            i = (i - 1) / 2;
        }
    
        minHeap->array[i] = node;
    }
    
    // 构建哈夫曼树
    struct Node* buildHuffmanTree(char data[], int frequency[], int size) {
        
        struct Node *left, *right, *top;
        // 创建一个最小堆并初始化
        struct MinHeap* minHeap = createMinHeap(size);
    
        // 向最小堆中插入结点
        for (int i = 0; i < size; i++) {
        
            insertMinHeap(minHeap, newNode(frequency[i], data[i]));
        }
    
        // 构建哈夫曼树
        while (!isSizeOne(minHeap)) {
        
            // 从最小堆中取出最小的两个结点作为左子树和右子树
            left = extractMin(minHeap);
            right = extractMin(minHeap);
    
            // 创建一个新的结点作为父结点
            top = newNode(left->frequency + right->frequency, '-');
            top->left = left;
            top->right = right;
    
            // 将父结点插入最小堆中
            insertMinHeap(minHeap, top);
        }
    
        // 最后剩下的结点就是哈夫曼树的根结点
        return extractMin(minHeap);
    }
    
    // 打印哈夫曼编码
    void printHuffmanCodes(struct Node* root, int arr[], int top) {
        
        // 叶子结点是存有字符的结点
        if (root->left) {
        
            arr[top] = 0;
            printHuffmanCodes(root->left, arr, top + 1);
        }
    
        if (root->right) {
        
            arr[top] = 1;
            printHuffmanCodes(root->right, arr, top + 1);
        }
    
        // 如果是叶子结点（没有左右子结点），则打印编码
        if (!root->left && !root->right) {
        
            printf("%c: ", root->data);
            for (int i = 0; i < top; i++) {
        
                printf("%d", arr[i]);
            }
            printf("\n");
        }
    }
    
    int main() {
        
        char data[] = {
         'a', 'b', 'c', 'd', 'e' };
        int frequency[] = {
         5, 9, 12, 13, 16 };
        int size = sizeof(data) / sizeof(data[0]);
    
        struct Node* root = buildHuffmanTree(data, frequency, size);
    
        int arr[100], top = 0;
        printHuffmanCodes(root, arr, top);
    
        return 0;
    }