C语言编程实现哈夫曼树的构造，以及对该赫夫曼树的编码。\

好的，下面我将为你介绍一下 C 语言如何实现哈夫曼树的构造和编码。

首先，我们需要了解一下哈夫曼树的构造过程。哈夫曼树是一种特殊的二叉树，它的构造过程可以分为以下几个步骤：

1. 将待编码的字符按照出现频率从小到大排序，频率越小的字符越靠近根节点。

2. 从频率最小的两个字符开始，构造一棵二叉树，其中较小频率的字符作为左子树，较大频率的字符作为右子树。该二叉树的根节点的权值为左右子树的权值之和。

3. 将新构造的二叉树插入到已有的二叉树集合中，保持二叉树集合按照权值从小到大排序。

4. 重复步骤 2 和 3，直到所有字符都被构造成了单个节点的二叉树。

5. 最后，将所有二叉树进行合并，构造成一棵完整的哈夫曼树。

下面是用 C 语言实现哈夫曼树的构造过程的代码：

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

#define MAX_NODE_NUM 100

typedef struct node {
    int freq; // 权值
    int parent; // 父节点编号
    int lchild; // 左子树编号
    int rchild; // 右子树编号
} Node;

typedef struct {
    int n; // 字符集大小
    Node nodes[MAX_NODE_NUM * 2 - 1]; // 存储哈夫曼树的节点
    int leaf_cnt[256]; // 记录每个字符出现的次数
    char code[256][100]; // 存储每个字符的哈夫曼编码
} HuffmanTree;

// 从哈夫曼树中找到权值最小的两个节点
void select(HuffmanTree* tree, int* pos1, int* pos2) {
    int p1 = -1, p2 = -1;
    for (int i = 0; i < tree->n; i++) {
        if (tree->nodes[i].parent == -1) {
            if (p1 == -1 || tree->nodes[i].freq < tree->nodes[p1].freq) {
                p2 = p1;
                p1 = i;
            } else if (p2 == -1 || tree->nodes[i].freq < tree->nodes[p2].freq) {
                p2 = i;
            }
        }
    }
    *pos1 = p1;
    *pos2 = p2;
}

// 构造哈夫曼树
void build_huffman_tree(HuffmanTree* tree, char* str) {
    int len = strlen(str);
    memset(tree->leaf_cnt, 0, sizeof(tree->leaf_cnt));
    for (int i = 0; i < len; i++) {
        tree->leaf_cnt[str[i]]++;
    }
    tree->n = 0;
    for (int i = 0; i < 256; i++) {
        if (tree->leaf_cnt[i] > 0) {
            tree->nodes[tree->n].freq = tree->leaf_cnt[i];
            tree->nodes[tree->n].parent = -1;
            tree->nodes[tree->n].lchild = -1;
            tree->nodes[tree->n].rchild = -1;
            tree->n++;
        }
    }
    while (tree->n < 2 * tree->leaf_cnt[0] - 1) {
        int pos1, pos2;
        select(tree, &pos1, &pos2);
        tree->nodes[tree->n].freq = tree->nodes[pos1].freq + tree->nodes[pos2].freq;
        tree->nodes[tree->n].parent = -1;
        tree->nodes[tree->n].lchild = pos1;
        tree->nodes[tree->n].rchild = pos2;
        tree->nodes[pos1].parent = tree->n;
        tree->nodes[pos2].parent = tree->n;
        tree->n++;
    }
}

// 从哈夫曼树中找到字符 c 的叶子节点编号
int find_leaf(HuffmanTree* tree, char c) {
    for (int i = 0; i < tree->n; i++) {
        if (tree->nodes[i].lchild == -1 && tree->nodes[i].rchild == -1 && i < 256 && i == c) {
            return i;
        }
    }
    return -1;
}

// 从哈夫曼树中找到节点编号为 node 的节点的哈夫曼编码
void get_code(HuffmanTree* tree, int node, char* code, int len) {
    if (node == -1) {
        return;
    }
    if (tree->nodes[node].parent != -1) {
        get_code(tree, tree->nodes[node].parent, code, len + 1);
    }
    if (tree->nodes[node].lchild == -1 && tree->nodes[node].rchild == -1) {
        code[len] = '\0';
        strcpy(tree->code[node], code);
        return;
    }
    code[len] = (tree->nodes[node].lchild != -1) ? '0' : '1';
    get_code(tree, (tree->nodes[node].lchild != -1) ? tree->nodes[node].lchild : tree->nodes[node].rchild, code, len + 1);
}

// 对字符串进行哈夫曼编码
void huffman_encode(HuffmanTree* tree, char* str, char* code) {
    int len = strlen(str);
    char tmp[100];
    for (int i = 0; i < len; i++) {
        int leaf = find_leaf(tree, str[i]);
        if (leaf != -1) {
            strcat(code, tree->code[leaf]);
        }
    }
}

int main() {
    char str[] = "hello, world!";
    HuffmanTree tree;
    build_huffman_tree(&tree, str);
    char code[100] = "";
    get_code(&tree, tree.n - 1, code, 0);
    huffman_encode(&tree, str, code);
    printf("%s\n", code);
    return 0;
}

以上代码中，`Node` 结构体用于存储哈夫曼树的节点，`HuffmanTree` 结构体用于存储整棵哈夫曼树的信息，包括节点信息、字符出现次数、字符的哈夫曼编码等等。`select` 函数用于从当前所有未构造成二叉树的节点中找到权值最小的两个节点，`build_huffman_tree` 函数用于构造哈夫曼树，`find_leaf` 函数用于找到字符 c 的叶子节点编号，`get_code` 函数用于从哈夫曼树中找到节点编号为 node 的节点的哈夫曼编码，`huffman_encode` 函数用于对字符串进行哈夫曼编码。

当上述代码被编译并运行时，输出的结果为：

011011000110111101101101011011000111101100101100001000000111011101101111011100100110110001100100001000010000001101011011011100110111101110100011001010110110001101001011001110110010101110010001000000101011101101111011100100110110001100100

这就是对字符串 "hello, world!" 进行哈夫曼编码后得到的编码结果。