C语言字符串压缩算法

基于哈夫曼编码的字符串压缩算法是一种常见的字符串压缩算法，下面是C语言实现的步骤和代码示例：

1. 定义结构体Node，用于构建哈夫曼树：

typedef struct Node {
    char ch; // 字符
    int freq; // 字符出现的频率
    struct Node *left, *right; // 左右子节点
} Node;

2. 定义函数getFreq()，用于统计字符串中每个字符出现的频率：

int *getFreq(char *str) {
    int *freq = (int *) calloc(256, sizeof(int)); // 初始化为0
    while (*str) {
        freq[(int) *str++]++;
    }
    return freq;
}

3. 定义函数createNode()，用于创建一个新的节点：

Node *createNode(char ch, int freq) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->ch = ch;
    node->freq = freq;
    node->left = node->right = NULL;
    return node;
}

4. 定义函数getMinNode()，用于从节点数组中找到频率最小的两个节点：

void getMinNode(Node **nodes, int n, int *min1, int *min2) {
    *min1 = *min2 = -1;
    for (int i = 0; i < n; i++) {
        if (nodes[i] == NULL) continue;
        if (*min1 == -1 || nodes[i]->freq < nodes[*min1]->freq) {
            *min2 = *min1;
            *min1 = i;
        } else if (*min2 == -1 || nodes[i]->freq < nodes[*min2]->freq) {
            *min2 = i;
        }
    }
}

5. 定义函数buildTree()，用于构建哈夫曼树：

Node *buildTree(char *str) {
    int *freq = getFreq(str);
    Node **nodes = (Node **) malloc(sizeof(Node *) * 256);
    int n = 0;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            nodes[n++] = createNode((char) i, freq[i]);
        }
    }
    while (n > 1) {
        int min1, min2;
        getMinNode(nodes, n, &min1, &min2);
        Node *node = createNode('\0', nodes[min1]->freq + nodes[min2]->freq);
        node->left = nodes[min1];
        node->right = nodes[min2];
        nodes[min1] = node;
        nodes[min2] = NULL;
        n--;
    }
    Node *root = nodes[0];
    free(freq);
    free(nodes);
    return root;
}

6. 定义函数getCode()，用于获取每个字符的哈夫曼编码：

void getCode(Node *node, char *code, int len) {
    if (node == NULL) return;
    if (node->left == NULL && node->right == NULL) {
        printf("%c: %s\n", node->ch, code);
        return;
    }
    code[len] = '0';
    getCode(node->left, code, len + 1);
    code[len] = '1';
    getCode(node->right, code, len + 1);
}

7. 定义函数compress()，用于压缩字符串：

char *compress(char *str, Node *root) {
    char *result = (char *) malloc(sizeof(char) * strlen(str) * 8 + 1);
    int len = 0;
    while (*str) {
        Node *node = root;
        while (node->left != NULL && node->right != NULL) {
            if (*str == '0') {
                node = node->left;
            } else {
                node = node->right;
            }
            str++;
        }
        result[len++] = node->ch;
    }
    result[len] = '\0';
    return result;
}

8. 编写main()函数进行测试：

int main() {
    char *str = "hello,world!";
    Node *root = buildTree(str);
    getCode(root, (char *) malloc(sizeof(char) * 100), 0);
    char *result = compress(str, root);
    printf("Original string: %s\n", str);
    printf("Compressed string: %s\n", result);
    return 0;
}