2、有 8 个字符:c,i,b,u,e,d,a,r， 给定其权值分别为{7,19,2,6,32,3,21,10}， 请 构造哈夫曼树并对字符进行编码。用C语言编写

好的，下面是一个用C语言编写的程序，用于构造哈夫曼树并对字符进行编码。我们将按照以下步骤进行： 1. 定义一个结构体来表示哈夫曼树的节点。 2. 创建一个最小堆来存储节点。 3. 构造哈夫曼树。 4. 对字符进行编码。 ```c #include <stdio.h> #include <stdlib.h> #include <string.h> // 定义哈夫曼树的节点结构体 typedef struct HuffmanNode { char data; int weight; struct HuffmanNode *left, *right; } HuffmanNode; // 定义最小堆结构体 typedef struct MinHeap { int size; int capacity; HuffmanNode** array; } MinHeap; // 创建新的哈夫曼树节点 HuffmanNode* createNode(char data, int weight) { HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode)); node->data = data; node->weight = weight; node->left = node->right = NULL; return node; } // 创建最小堆 MinHeap* createMinHeap(int capacity) { MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap)); minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (HuffmanNode**)malloc(minHeap->capacity * sizeof(HuffmanNode*)); return minHeap; } // 交换两个节点 void swapNodes(HuffmanNode** a, HuffmanNode** b) { HuffmanNode* t = *a; *a = *b; *b = t; } // 最小堆化 void minHeapify(MinHeap* minHeap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left < minHeap->size && minHeap->array[left]->weight < minHeap->array[smallest]->weight) smallest = left; if (right < minHeap->size && minHeap->array[right]->weight < minHeap->array[smallest]->weight) smallest = right; if (smallest != idx) { swapNodes(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } } // 检查最小堆的大小是否为1 int isSizeOne(MinHeap* minHeap) { return (minHeap->size == 1); } // 提取最小节点 HuffmanNode* extractMin(MinHeap* minHeap) { HuffmanNode* temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; minHeap->size--; minHeapify(minHeap, 0); return temp; } // 插入节点到最小堆 void insertMinHeap(MinHeap* minHeap, HuffmanNode* node) { minHeap->size++; int i = minHeap->size - 1; while (i && node->weight < minHeap->array[(i - 1) / 2]->weight) { minHeap->array[i] = minHeap->array[(i - 1) / 2]; i = (i - 1) / 2; } minHeap->array[i] = node; } // 构建最小堆 void buildMinHeap(MinHeap* minHeap) { int n = minHeap->size - 1; for (int i = (n - 1) / 2; i >= 0; --i) minHeapify(minHeap, i); } // 检查一个字符是否在哈夫曼树中 int isInTree(HuffmanNode* root, char data) { if (root == NULL) return 0; if (root->data == data) return 1; return isInTree(root->left, data) || isInTree(root->right, data); } // 构造哈夫曼树 HuffmanNode* buildHuffmanTree(char data[], int weight[], int size) { HuffmanNode* left, * right, * top; MinHeap* minHeap = createMinHeap(size); for (int i = 0; i < size; ++i) minHeap->array[i] = createNode(data[i], weight[i]); minHeap->size = size; buildMinHeap(minHeap); while (!isSizeOne(minHeap)) { left = extractMin(minHeap); right = extractMin(minHeap); top = createNode('$', left->weight + right->weight); top->left = left; top->right = right; insertMinHeap(minHeap, top); } return extractMin(minHeap); } // 打印哈夫曼编码 void printHuffmanCodes(HuffmanNode* root, int arr[], int top) { if (root->left) { arr[top] = 0; printHuffmanCodes(root->left, arr, top + 1); } if (root->right) { arr[top] = 1; printHuffmanCodes(root->right, arr, top + 1); } if (!(root->left) && !(root->right)) { printf("%c: ", root->data); for (int i = 0; i < top; ++i) printf("%d", arr[i]); printf("\n"); } } // 主函数 int main() { char data[] = {'c', 'i', 'b', 'u', 'e', 'd', 'a', 'r'}; int weight[] = {7, 19, 2, 6, 32, 3, 21, 10}; int size = sizeof(data) / sizeof(data[0]); HuffmanNode* root = buildHuffmanTree(data, weight, size); int arr[100], top = 0; printHuffmanCodes(root, arr, top); return 0; } ```