用贪心算法解哈夫曼编码问题c语言代码实现

在C语言中，贪心算法可以用来构建哈夫曼树并生成哈夫曼编码，这是通过每次选择两棵权值最小的树合并成新的树，并将这两棵树的权值作为新树的权值来实现的。以下是一个简单的C语言代码示例：

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

// 结点结构体
typedef struct {
    int weight; // 权值
    char symbol; // 符号
    struct Node* left, *right; // 左右子节点
} Node;

// 创建新结点
Node* newNode(int weight, char symbol) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->weight = weight;
    node->symbol = symbol;
    node->left = node->right = NULL;
    return node;
}

// 贪心合并函数
Node* mergeTrees(Node* t1, Node* t2) {
    if (!t1 || !t2)
        return t1 ? t1 : t2;
    if (t1->weight < t2->weight) {
        t1->right = mergeTrees(t1->right, t2);
        return t1;
    } else {
        t2->left = mergeTrees(t1, t2->left);
        return t2;
    }
}

// 构建哈夫曼树
Node* buildHuffmanTree(int weights[], int n) {
    Node** heap = (Node**)malloc(n * sizeof(Node*));
    for (int i = 0; i < n; ++i) {
        heap[i] = newNode(weights[i], i + 'A');
    }

    while (heap[0]) {
        int minIndex1 = 0, minIndex2 = 0;
        for (int i = 1; i < n; ++i) {
            if (heap[minIndex1]->weight > heap[i]->weight) {
                minIndex1 = i;
            }
        }
        for (int j = 1; j < n; ++j) {
            if (heap[j] != heap[minIndex1] && heap[j]->weight < heap[minIndex2]->weight) {
                minIndex2 = j;
            }
        }

        Node* temp = mergeTrees(heap[minIndex1], heap[minIndex2]);
        heap[minIndex1] = heap[minIndex2] = NULL;
        heap[n++] = temp;
    }

    return heap[0];
}

// 打印哈夫曼编码
void printCodes(Node* root, int symbolToCode[]) {
    if (!root)
        return;
    if (!root->left && !root->right)
        symbolToCode[root->symbol - 'A'] = '0';
    else {
        printCodes(root->left, symbolToCode);
        printCodes(root->right, symbolToCode);
    }
}

int main() {
    int weights[] = {5, 3, 4, 6}; // 示例权重数组
    int n = sizeof(weights) / sizeof(weights[0]);

    Node* huffTree = buildHuffmanTree(weights, n);
    int symbolToCode[26] = {0};

    printf("Huffman Tree:\n");
    printCodes(huffTree, symbolToCode);

    return 0;
}

这个代码首先创建了一个堆，然后不断从堆中取出两个权值最小的结点合并，直到只剩下一个结点。最后，它会递归地生成每个字符的哈夫曼编码。