一段简易的霍夫曼编码c程序

好的，以下是一段简易的C语言程序实现霍夫曼编码的过程。假设有一个字符串需要进行编码，首先需要统计各个字符出现的频率，然后根据频率构建霍夫曼树，最后根据霍夫曼树生成编码表并对原始字符串进行编码。

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

#define MAX_CHAR 256

// 定义霍夫曼树节点结构体
typedef struct node {
    char ch;  // 字符
    int freq; // 出现频率
    struct node *left, *right; // 左右子节点指针
} Node;

// 定义堆结构体
typedef struct heap {
    Node **nodes; // 节点指针数组
    int size; // 堆的大小
} Heap;

// 创建一个节点
Node* createNode(char ch, int freq) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->ch = ch;
    node->freq = freq;
    node->left = NULL;
    node->right = NULL;
    return node;
}

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

// 堆化操作
void heapify(Heap *heap, int idx) {
    int smallest = idx;
    int left = 2*idx + 1;
    int right = 2*idx + 2;
    if (left < heap->size && heap->nodes[left]->freq < heap->nodes[smallest]->freq) {
        smallest = left;
    }
    if (right < heap->size && heap->nodes[right]->freq < heap->nodes[smallest]->freq) {
        smallest = right;
    }
    if (smallest != idx) {
        swap(&heap->nodes[idx], &heap->nodes[smallest]);
        heapify(heap, smallest);
    }
}

// 创建堆
Heap* createHeap() {
    Heap *heap = (Heap*) malloc(sizeof(Heap));
    heap->nodes = (Node**) malloc(MAX_CHAR * sizeof(Node*));
    heap->size = 0;
    return heap;
}

// 添加节点到堆中
void addToHeap(Heap *heap, Node *node) {
    heap->nodes[heap->size++] = node;
    int idx = heap->size - 1;
    while (idx > 0 && heap->nodes[idx]->freq < heap->nodes[(idx-1)/2]->freq) {
        swap(&heap->nodes[idx], &heap->nodes[(idx-1)/2]);
        idx = (idx-1)/2;
    }
}

// 从堆中取出最小的节点
Node* extractMinFromHeap(Heap *heap) {
    Node *minNode = heap->nodes[0];
    heap->nodes[0] = heap->nodes[--heap->size];
    heapify(heap, 0);
    return minNode;
}

// 构建霍夫曼树
Node* buildHuffmanTree(int *freq) {
    Heap *heap = createHeap();
    for (int i = 0; i < MAX_CHAR; i++) {
        if (freq[i] > 0) {
            Node *node = createNode((char) i, freq[i]);
            addToHeap(heap, node);
        }
    }
    while (heap->size > 1) {
        Node *left = extractMinFromHeap(heap);
        Node *right = extractMinFromHeap(heap);
        Node *parent = createNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        addToHeap(heap, parent);
    }
    Node *root = extractMinFromHeap(heap);
    free(heap->nodes);
    free(heap);
    return root;
}

// 生成编码表
void generateCodeTable(Node *root, char **codeTable, char *code, int index) {
    if (root == NULL) {
        return;
    }
    if (root->ch != '\0') {
        code[index] = '\0';
        codeTable[root->ch] = (char*) malloc(strlen(code) + 1);
        strcpy(codeTable[root->ch], code);
    }
    code[index] = '0';
    generateCodeTable(root->left, codeTable, code, index+1);
    code[index] = '1';
    generateCodeTable(root->right, codeTable, code, index+1);
}

// 对原始字符串进行编码
char* encodeString(char *str, char **codeTable) {
    int len = strlen(str);
    char *encoded = (char*) malloc(len * MAX_CHAR * sizeof(char));
    int index = 0;
    for (int i = 0; i < len; i++) {
        char *code = codeTable[str[i]];
        int codeLen = strlen(code);
        for (int j = 0; j < codeLen; j++) {
            encoded[index++] = code[j];
        }
    }
    encoded[index] = '\0';
    return encoded;
}

int main() {
    // 原始字符串
    char str[] = "hello world";

    // 统计字符出现的频率
    int freq[MAX_CHAR] = {0};
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        freq[(int) str[i]]++;
    }

    // 构建霍夫曼树
    Node *root = buildHuffmanTree(freq);

    // 生成编码表
    char **codeTable = (char**) malloc(MAX_CHAR * sizeof(char*));
    char *code = (char*) malloc(MAX_CHAR * sizeof(char));
    generateCodeTable(root, codeTable, code, 0);

    // 对原始字符串进行编码
    char *encoded = encodeString(str, codeTable);

    // 输出结果
    printf("原始字符串：%s\n", str);
    printf("编码结果：%s\n", encoded);

    // 释放内存
    free(code);
    for (int i = 0; i < MAX_CHAR; i++) {
        if (codeTable[i] != NULL) {
            free(codeTable[i]);
        }
    }
    free(codeTable);
    free(encoded);
    free(root);

    return 0;
}

在上面的程序中，首先使用一个数组freq来统计字符出现的频率，然后根据频率构建霍夫曼树，并使用一个数组codeTable来保存每个字符的编码。在编码的过程中，对于原始字符串中的每个字符，都在codeTable中查找对应的编码，并将其拼接到encoded字符串中。最后，将原始字符串和编码结果输出，并释放内存。