霍夫曼编码例题c语言,哈夫曼树及哈夫曼编码的C程序实现(数据结构题)问题描述〕输入一个有n个叶结点的权值构造一棵哈夫曼树；（例如：n＝8,权值为 5 29 7 8 14 23 3 11） 根据哈夫曼树...

好的，这是一个经典的哈夫曼编码问题。以下是C语言实现的代码：

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

#define MAX_N 100

typedef struct Node {
    int weight;
    int parent, lchild, rchild;
} Node;

void select_min(Node *nodes, int n, int *p1, int *p2) {
    int i, min1 = -1, min2 = -1;
    for (i = 0; i < n; i++) {
        if (nodes[i].parent == -1) {
            if (min1 == -1 || nodes[i].weight < nodes[min1].weight) {
                min2 = min1;
                min1 = i;
            } else if (min2 == -1 || nodes[i].weight < nodes[min2].weight) {
                min2 = i;
            }
        }
    }
    *p1 = min1;
    *p2 = min2;
}

void build_huffman_tree(Node *nodes, int n) {
    int i, p1, p2;
    for (i = 0; i < n * 2 - 1; i++) {
        nodes[i].parent = nodes[i].lchild = nodes[i].rchild = -1;
    }
    for (i = n; i < n * 2 - 1; i++) {
        select_min(nodes, i, &p1, &p2);
        nodes[i].weight = nodes[p1].weight + nodes[p2].weight;
        nodes[p1].parent = nodes[p2].parent = i;
        nodes[i].lchild = p1;
        nodes[i].rchild = p2;
    }
}

void huffman_encoding(Node *nodes, int n, char **encoding) {
    int i, j, p;
    char *code = (char *) malloc(sizeof(char) * (n + 1));
    code[n] = '\0';
    for (i = 0; i < n; i++) {
        p = i;
        j = n - 1;
        while (nodes[p].parent != -1) {
            if (nodes[nodes[p].parent].lchild == p) {
                code[--j] = '0';
            } else {
                code[--j] = '1';
            }
            p = nodes[p].parent;
        }
        encoding[i] = (char *) malloc(sizeof(char) * (n - j));
        strcpy(encoding[i], &code[j]);
    }
    free(code);
}

void print_huffman_encoding(Node *nodes, int n, char **encoding) {
    int i;
    printf("Huffman encoding:\n");
    for (i = 0; i < n; i++) {
        printf("%d: %s\n", nodes[i].weight, encoding[i]);
    }
}

int main() {
    int n, i;
    Node nodes[MAX_N * 2 - 1];
    char *encoding[MAX_N];
    printf("Enter the number of leaf nodes:\n");
    scanf("%d", &n);
    printf("Enter the weights of the leaf nodes:\n");
    for (i = 0; i < n; i++) {
        scanf("%d", &nodes[i].weight);
    }
    build_huffman_tree(nodes, n);
    huffman_encoding(nodes, n, encoding);
    print_huffman_encoding(nodes, n, encoding);
    return 0;
}

首先定义了一个`Node`结构体表示哈夫曼树的结点，包含权值、父结点、左子结点和右子结点。`select_min`函数用于在未被选中的结点中选择权值最小的两个结点，通过传入指针修改`p1`和`p2`的值。`build_huffman_tree`函数用于构建哈夫曼树，先将所有结点的父结点、左子结点和右子结点初始化为-1，然后循环n到2n-2次，每次选择权值最小的两个未被选中的结点，将它们合并成一个新结点，并将它们的父结点、左子结点和右子结点设置为新结点的下标。`huffman_encoding`函数用于对每个叶结点进行哈夫曼编码，遍历从叶结点到根结点的路径，每次将0或1加入编码字符串中，直到到达根结点。最后打印出每个叶结点的权值和对应的编码。

这个程序的时间复杂度是O(n^2)，可以通过优化`select_min`函数来达到O(nlogn)的时间复杂度。