用c语言写算法求哈夫曼编码

哈夫曼编码是一种用于数据压缩的编码方式，它将数据中出现频率较高的字符用较短的编码表示，而将出现频率较低的字符用较长的编码表示。以下是使用C语言实现哈夫曼编码的基本步骤：

1. 定义哈夫曼树的结构体

typedef struct _HuffmanNode {
    char ch;
    int freq;
    struct _HuffmanNode *left;
    struct _HuffmanNode *right;
} HuffmanNode;

typedef struct _HuffmanTree {
    HuffmanNode *root;
} HuffmanTree;

2. 构建哈夫曼树

void buildHuffmanTree(char *str, int len, HuffmanTree *tree) {
    // 统计字符出现频率
    int freq[256] = {0};
    for (int i = 0; i < len; i++) {
        freq[str[i]]++;
    }
    
    // 构建哈夫曼树
    PriorityQueue *queue = createPriorityQueue();
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            HuffmanNode *node = (HuffmanNode *) malloc(sizeof(HuffmanNode));
            node->ch = (char) i;
            node->freq = freq[i];
            node->left = NULL;
            node->right = NULL;
            enqueue(queue, node, freq[i]);
        }
    }
    
    while (queue->size > 1) {
        HuffmanNode *node1 = (HuffmanNode *) dequeue(queue);
        HuffmanNode *node2 = (HuffmanNode *) dequeue(queue);
        HuffmanNode *parent = (HuffmanNode *) malloc(sizeof(HuffmanNode));
        parent->ch = '\0';
        parent->freq = node1->freq + node2->freq;
        parent->left = node1;
        parent->right = node2;
        enqueue(queue, parent, parent->freq);
    }
    
    tree->root = (HuffmanNode *) dequeue(queue);
}

3. 生成哈夫曼编码

void generateHuffmanCode(HuffmanNode *node, char *code, int codeLen, char **codes) {
    if (node == NULL) {
        return;
    }
    
    if (node->left == NULL && node->right == NULL) {
        code[codeLen] = '\0';
        codes[node->ch] = (char *) malloc(sizeof(char) * (codeLen + 1));
        strcpy(codes[node->ch], code);
    } else {
        code[codeLen] = '0';
        generateHuffmanCode(node->left, code, codeLen + 1, codes);
        code[codeLen] = '1';
        generateHuffmanCode(node->right, code, codeLen + 1, codes);
    }
}

void getHuffmanCodes(HuffmanTree *tree, char **codes) {
    char code[256] = {0};
    generateHuffmanCode(tree->root, code, 0, codes);
}

完整代码如下：

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

typedef struct _HuffmanNode {
    char ch;
    int freq;
    struct _HuffmanNode *left;
    struct _HuffmanNode *right;
} HuffmanNode;

typedef struct _HuffmanTree {
    HuffmanNode *root;
} HuffmanTree;

typedef struct _Node {
    void *data;
    int priority;
    struct _Node *next;
} Node;

typedef struct _PriorityQueue {
    Node *front;
    int size;
} PriorityQueue;

PriorityQueue *createPriorityQueue() {
    PriorityQueue *queue = (PriorityQueue *) malloc(sizeof(PriorityQueue));
    queue->front = NULL;
    queue->size = 0;
    return queue;
}

void enqueue(PriorityQueue *queue, void *data, int priority) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = data;
    node->priority = priority;
    node->next = NULL;
    
    if (queue->front == NULL) {
        queue->front = node;
    } else if (queue->front->priority > priority) {
        node->next = queue->front;
        queue->front = node;
    } else {
        Node *current = queue->front;
        while (current->next != NULL && current->next->priority <= priority) {
            current = current->next;
        }
        node->next = current->next;
        current->next = node;
    }
    
    queue->size++;
}

void *dequeue(PriorityQueue *queue) {
    if (queue->front == NULL) {
        return NULL;
    }
    
    Node *node = queue->front;
    void *data = node->data;
    queue->front = node->next;
    free(node);
    queue->size--;
    
    return data;
}

void destroyPriorityQueue(PriorityQueue *queue) {
    while (queue->front != NULL) {
        Node *node = queue->front;
        queue->front = node->next;
        free(node);
    }
    free(queue);
}

void buildHuffmanTree(char *str, int len, HuffmanTree *tree) {
    // 统计字符出现频率
    int freq[256] = {0};
    for (int i = 0; i < len; i++) {
        freq[str[i]]++;
    }
    
    // 构建哈夫曼树
    PriorityQueue *queue = createPriorityQueue();
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            HuffmanNode *node = (HuffmanNode *) malloc(sizeof(HuffmanNode));
            node->ch = (char) i;
            node->freq = freq[i];
            node->left = NULL;
            node->right = NULL;
            enqueue(queue, node, freq[i]);
        }
    }
    
    while (queue->size > 1) {
        HuffmanNode *node1 = (HuffmanNode *) dequeue(queue);
        HuffmanNode *node2 = (HuffmanNode *) dequeue(queue);
        HuffmanNode *parent = (HuffmanNode *) malloc(sizeof(HuffmanNode));
        parent->ch = '\0';
        parent->freq = node1->freq + node2->freq;
        parent->left = node1;
        parent->right = node2;
        enqueue(queue, parent, parent->freq);
    }
    
    tree->root = (HuffmanNode *) dequeue(queue);
    destroyPriorityQueue(queue);
}

void generateHuffmanCode(HuffmanNode *node, char *code, int codeLen, char **codes) {
    if (node == NULL) {
        return;
    }
    
    if (node->left == NULL && node->right == NULL) {
        code[codeLen] = '\0';
        codes[node->ch] = (char *) malloc(sizeof(char) * (codeLen + 1));
        strcpy(codes[node->ch], code);
    } else {
        code[codeLen] = '0';
        generateHuffmanCode(node->left, code, codeLen + 1, codes);
        code[codeLen] = '1';
        generateHuffmanCode(node->right, code, codeLen + 1, codes);
    }
}

void getHuffmanCodes(HuffmanTree *tree, char **codes) {
    char code[256] = {0};
    generateHuffmanCode(tree->root, code, 0, codes);
}

void destroyHuffmanTree(HuffmanNode *node) {
    if (node != NULL) {
        destroyHuffmanTree(node->left);
        destroyHuffmanTree(node->right);
        free(node);
    }
}

int main() {
    char str[] = "hello world";
    int len = strlen(str);
    
    HuffmanTree tree;
    buildHuffmanTree(str, len, &tree);
    
    char *codes[256] = {NULL};
    getHuffmanCodes(&tree, codes);
    
    printf("Huffman Codes:\n");
    for (int i = 0; i < 256; i++) {
        if (codes[i] != NULL) {
            printf("%c: %s\n", i, codes[i]);
        }
    }
    
    for (int i = 0; i < 256; i++) {
        if (codes[i] != NULL) {
            free(codes[i]);
        }
    }
    
    destroyHuffmanTree(tree.root);
    
    return 0;
}