C语言实现哈夫曼编码：字符统计、排序、构建哈夫曼树并输出编码

#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX_CODE_LEN 100

// 定义链表节点结构体 typedef struct ListNode { int c; // 存储字符（使用 int 类型，能够正确处理特殊字符） int frequency; // 存储字符出现频度 char *code; // 存储字符编码（在后续实现哈夫曼编码时使用） int order; // 存储节点插入先后顺序 struct ListNode *parent; struct ListNode *left; struct ListNode *right; struct ListNode *next; // 存储下一个节点指针 int frequencyCount; // 存储节点个数计数器 } ListNode, HuffmanTree;

// 将一个字符插入到链表中，如果已存在则更新频度 void insert(ListNode *head, int c) { ListNode *p = head; while (p->next != NULL) { if (p->next->c == c) { // 如果已存在该字符，则更新频度 p->next->frequency++; return; } p = p->next; } ListNode *newNode = (ListNode *) malloc(sizeof(ListNode)); // 新建一个节点 newNode->c = c; newNode->frequency = 1; newNode->code = NULL; newNode->next = NULL; newNode->order = ++head->frequencyCount; // 记录节点插入的先后顺序 p->next = newNode; // 将新节点插入到链表尾部 }

// 对链表进行选择排序，按照字符频度和插入先后顺序排序 void sort(ListNode *head) { ListNode *p, *q; int tmpc; // 定义临时变量存储字符 int tmpfrequency, tmporder; p = head->next; while(p != NULL) { q = p->next; while(q != NULL) { if(p->frequency < q->frequency || (p->frequency == q->frequency && p->order > q->order)) { // 根据频度和先后顺序进行比较 // 如果 p 节点的频度小于 q 节点的频度，或者 p 和 q 节点的频度相等但 p 的插入先后顺序大于 q 的，则交换两个节点的数据域和指针域 tmpc = q->c; q->c = p->c; p->c = tmpc; tmpfrequency = q->frequency; q->frequency = p->frequency; p->frequency = tmpfrequency; tmporder = q->order; q->order = p->order; p->order = tmporder; p->code += q->code - (q->code = p->code); } q = q->next; } p = p->next; } }

// 建立哈夫曼树 HuffmanTree *buildHuffmanTree(ListNode *head) { // 根据链表中的节点建立哈夫曼树 // 首先将链表中的节点转换为哈夫曼树的叶子节点 // 然后依次合并叶子节点和非叶子节点，直至合并成根节点 // 合并两个节点的过程中，将两个节点的频度之和作为新节点的频度 // 新节点的左子树为频度较小的节点，右子树为频度较大的节点

// 先将链表中的节点转换为哈夫曼树的叶子节点
int n = 0; // 统计叶子节点个数
ListNode *p = head->next;
while (p != NULL) {
    n++;
    p = p->next;
}
HuffmanTree **leaves = (HuffmanTree **) malloc(n * sizeof(HuffmanTree *)); // 动态分配叶子节点指针数组
p = head->next;
for (int i = 0; i < n; i++) {
    leaves[i] = (HuffmanTree *) malloc(sizeof(HuffmanTree)); // 新建一个叶子节点
    leaves[i]->c = p->c;
    leaves[i]->frequency = p->frequency;
    leaves[i]->code = NULL;
    leaves[i]->parent = NULL;
    leaves[i]->left = NULL;
    leaves[i]->right = NULL;
    p = p->next;
}

// 依次合并叶子节点和非叶子节点
for (int i = 0; i < n - 1; i++) {
    // 找到频度最小的两个节点
    int min1, min2;
    min1 = min2 = -1;
    for (int j = 0; j < n + i; j++) {
        if (leaves[j]->parent == NULL) { // 如果该节点还没有父节点，说明它还没有被合并过
            if (min1 == -1 || leaves[j]->frequency < leaves[min1]->frequency) {
                min2 = min1;
                min1 = j;
            } else if (min2 == -1 || leaves[j]->frequency < leaves[min2]->frequency) {
                min2 = j;
            }
        }
    }

    // 新建一个节点，将两个子节点合并到该节点中
    HuffmanTree *newNode = (HuffmanTree *) malloc(sizeof(HuffmanTree));
    newNode->frequency = leaves[min1]->frequency + leaves[min2]->frequency;
    newNode->code = NULL;
    newNode->parent = NULL;
    newNode->left = leaves[min1];
    newNode->right = leaves[min2];
    leaves[min1]->parent = newNode;
    leaves[min2]->parent = newNode;

    // 将新节点插入到叶子节点数组中
    leaves[n + i] = newNode;
}

// 最后一个节点即为根节点
return leaves[n * 2 - 2];

}

// 遍历哈夫曼树，获取叶子节点的哈夫曼编码 void traverseHuffmanTree(HuffmanTree *tree, char *code, int depth) { // tree：当前遍历的节点 // code：当前遍历的节点所对应的哈夫曼编码（字符串形式） // depth：当前遍历的节点的深度

// 如果遍历到了叶子节点，则将其对应的哈夫曼编码保存到节点中
if (tree->left == NULL && tree->right == NULL) {
    tree->code = (char *) malloc((depth + 1) * sizeof(char));
    strcpy(tree->code, code);
} else {
    // 遍历左子树
    code[depth] = '0';
    traverseHuffmanTree(tree->left, code, depth + 1);

    // 遍历右子树
    code[depth] = '1';
    traverseHuffmanTree(tree->right, code, depth + 1);
}

}

int main() { ListNode *head = (ListNode *) malloc(sizeof(ListNode)); head->next = NULL; head->frequency = 0; // 初始化节点计数器 int c; while ((c = getchar()) != EOF) { //使用 getchar() 函数读取输入字符流 insert(head, c); } sort(head); HuffmanTree *tree = buildHuffmanTree(head); // 建立哈夫曼树 char code[MAX_CODE_LEN]; // 用于存储哈夫曼编码的字符数组 traverseHuffmanTree(tree, code, 0); // 遍历哈夫曼树，获取叶子节点的哈夫曼编码

ListNode *p = head->next;
while (p != NULL) {
    if (p->c == '\n') { // 对换行符进行特殊处理
        printf(''\n' %d %s\n', p->frequency, p->parent->code);
    } else { // 其他字符按照 ASCII 码输出
        printf(''%c' %d %s\n', p->c, p->frequency, p->parent->code);
    }
    p = p->next;
}
printf("%d\n", tree->frequency); // 输出哈夫曼树的带权路径长度

return 0;