哈夫曼压缩算法c语言代码

哈夫曼压缩算法是一种常用的数据压缩算法，其原理是基于将频率较高的字符映射为较短的编码，从而减小数据的存储空间。以下是一个简单的使用C语言实现的哈夫曼压缩算法代码示例：

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

// 定义字符节点结构
typedef struct {
    char data;  // 字符
    int freq;   // 频率
    struct Node *leftChild, *rightChild;
} Node;

// 定义哈夫曼树节点结构
typedef struct {
    int size;
    Node **nodes;
} Tree;

// 创建一个新的哈夫曼树节点
Node *newNode(char data, int freq) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->freq = freq;
    node->leftChild = node->rightChild = NULL;
    return node;
}

// 创建一个新的哈夫曼树
Tree *newTree(int size) {
    Tree *tree = (Tree *)malloc(sizeof(Tree));
    tree->size = size;
    tree->nodes = (Node **)malloc(size * sizeof(Node *));
    return tree;
}

// 交换两个哈夫曼树节点
void swap(Node **a, Node **b) {
    Node *temp = *a;
    *a = *b;
    *b = temp;
}

// 构建哈夫曼树
void buildHuffmanTree(Tree *tree) {
    int n = tree->size;
    Node **nodes = tree->nodes;
    for (int i = 0; i < n - 1; i++) {
        int min1 = i;
        int min2 = i + 1;
        for (int j = i + 2; j < n; j++) {
            if (nodes[j]->freq < nodes[min1]->freq) {
                min2 = min1;
                min1 = j;
            } else if (nodes[j]->freq < nodes[min2]->freq) {
                min2 = j;
            }
        }
        Node *newNode = malloc(sizeof(Node));
        newNode->freq = nodes[min1]->freq + nodes[min2]->freq;
        newNode->leftChild = nodes[min1];
        newNode->rightChild = nodes[min2];
        nodes[min1] = newNode;
        nodes[min2] = nodes[i + 2];
        for (int j = i + 2; j < n - 1; j++) {
            if (nodes[j]->freq > nodes[j + 1]->freq) {
                swap(&nodes[j], &nodes[j + 1]);
            }
        }
    }
}

// 打印哈夫曼编码
void printHuffmanCodes(Node *root, int arr[], int top) {
    if (root->leftChild) {
        arr[top] = 0;
        printHuffmanCodes(root->leftChild, arr, top + 1);
    }
    if (root->rightChild) {
        arr[top] = 1;
        printHuffmanCodes(root->rightChild, arr, top + 1);
    }
    if (!(root->leftChild) && !(root->rightChild)) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; i++) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

int main() {
    int n;
    printf("请输入字符的数量: ");
    scanf("%d", &n);

    Tree *tree = newTree(n);
    for (int i = 0; i < n; i++) {
        char data;
        int freq;
        printf("请输入第%d个字符和频率: ", i + 1);
        scanf(" %c %d", &data, &freq);  // 注意空格避免读取上个输入的残留字符
        Node *node = newNode(data, freq);
        tree->nodes[i] = node;
    }

    buildHuffmanTree(tree);

    int arr[100];
    printf("哈夫曼编码结果：\n");
    printHuffmanCodes(tree->nodes[0], arr, 0);

    return 0;
}

通过以上的代码示例，我们可以实现使用哈夫曼压缩算法对字符数据进行编码和压缩。