写出“给定n个节点，每个节点的权重w(i)（1≤i≤n），构造一颗哈夫曼树，并输出带权路径长度”的C语言代码

在C语言中，我们可以使用优先队列（如二叉堆）和递归来构建哈夫曼树并计算带权路径长度。这里是一个简单的示例，假设我们有一个整数数组`weights`存储了节点的权重：

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

// 定义一个结构体表示二叉树节点
typedef struct Node {
    int weight;
    struct Node *left, *right;
} Node;

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

// 插入节点到最小堆
void insertMinHeap(Node** heap, int* heapSize, int weight) {
    Node* newNode = newNode(weight);
    *heapSize++;

    if (*heapSize == 1) {
        return;
    }

    int i = *heapSize - 1; // 当前插入位置
    while (i > 0 && newNode->weight < heap[i]->weight) { // 跳过比当前值大的节点
        heap[i] = heap[--i];
    }
    heap[i + 1] = newNode;
}

// 构建哈夫曼树并合并两个最小节点
Node* buildHuffmanTree(Node** heap, int size) {
    if (size <= 1) {
        return heap[0];
    }

    int left = 0, right = 1;
    Node* min1 = heap[left], *min2 = heap[right];

    Node* temp = newNode(min1->weight + min2->weight);
    temp->left = min1;
    temp->right = min2;

    // 合并后的节点加入堆
    insertMinHeap(heap, &size, temp->weight);

    return buildHuffmanTree(heap, size - 1);
}

// 计算带权路径长度
int calculateWPL(Node* root) {
    if (root == NULL) {
        return 0;
    } else {
        return root->weight + calculateWPL(root->left) + calculateWPL(root->right);
    }
}

// 主函数，读取输入并输出结果
int main() {
    int n, weights[n]; // 假设已读取n和权重到数组weights中
    Node** heap = (Node**)malloc(sizeof(Node*) * n);
    for (int i = 0; i < n; ++i) {
        insertMinHeap(heap, &n, weights[i]);
    }
    Node* huffmanRoot = buildHuffmanTree(heap, n);
    int wpl = calculateWPL(huffmanRoot);
    printf("带权路径长度: %d\n", wpl);

    free(heap);
    return 0;
}

这个程序首先将所有节点插入最小堆，然后每次从堆顶取出两个最小的节点合并成新的节点，直到只剩下一个节点。最后，通过递归的方式计算根节点的带权路径长度。