(2023)n个不等长的非空表，n-1次两两合并合成一表，设计一种方案，使总比较次数T最小并求出T的值。如 a b c合并，a和b 比较x次，ab和c比较y次，则T=x+y
审题
- 容易想到每次比较最小的两个表，再递增比较后面的，即使用哈夫曼树（Huffman Tree）的思想。
- 哈夫曼树是一种最优二叉树，用于数据压缩和编码中，其目的是通过合并频率最低的两个节点来构建树，从而减少整体的比较次数。
思路
- 将所有表的长度存储在一个数组中。
- 使用优先队列（最小堆）来存储这些长度，以便每次可以快速找到最小的两个元素进行合并。
- 重复以下步骤直到堆中只剩下一个元素：
- 从堆中取出两个最小的元素（即两个最短的表）。
- 将这两个表合并，并将合并后的表的长度重新插入到堆中。
- 记录这次合并过程中的比较次数。
- 累加所有合并过程中的比较次数，得到总比较次数T。
1. 结构体定义
#include <stdio.h>
#include <stdlib.h>
// 定义一个结构体表示堆中的节点
typedef struct {
int length; // 表的长度
} Node;
// 定义一个结构体表示最小堆
typedef struct {
Node *data; // 存储堆元素的数组
int size; // 当前堆的大小
int capacity; // 堆的最大容量
} MinHeap;
Node结构体：表示堆中的一个节点，包含一个整数length，表示表的长度。MinHeap结构体：表示最小堆，包含一个动态数组data来存储堆元素，size表示当前堆的大小，capacity表示堆的最大容量。
2. 初始化最小堆
MinHeap* createMinHeap(int capacity) {
MinHeap *heap = (MinHeap *)malloc(sizeof(MinHeap));
heap->data = (Node *)malloc(capacity * sizeof(Node));
heap->size = 0;
heap->capacity = capacity;
return heap;
}
createMinHeap函数：创建一个指定容量的最小堆。malloc：动态分配内存。- 初始化
size为 0，capacity为传入的容量值。
3. 交换两个节点
void swap(Node *a, Node *b) {
Node temp = *a;
*a = *b;
*b = temp;
}
swap函数：交换两个节点的值。
4. 向上调整堆
void siftUp(MinHeap *heap, int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (heap->data[parent].length <= heap->data[index].length) break;
swap(&heap->data[parent], &heap->data[index]);
index = parent;
}
}
siftUp函数：从下往上调整堆，使堆保持最小堆性质。parent：计算父节点的索引。- 如果父节点的值小于等于当前节点的值，则停止调整；否则，交换它们的位置并继续向上调整。
5. 向下调整堆
void siftDown(MinHeap *heap, int index) {
int leftChild, rightChild, smallest;
while (index * 2 + 1 < heap->size) {
leftChild = index * 2 + 1;
rightChild = index * 2 + 2;
smallest = index;
if (leftChild < heap->size && heap->data[leftChild].length < heap->data[smallest].length) {
smallest = leftChild;
}
if (rightChild < heap->size && heap->data[rightChild].length < heap->data[smallest].length) {
smallest = rightChild;
}
if (smallest == index) break;
swap(&heap->data[smallest], &heap->data[index]);
index = smallest;
}
}
siftDown函数：从上往下调整堆，使堆保持最小堆性质。leftChild和rightChild：计算左右子节点的索引。- 找到三个节点中最小的那个，如果最小节点不是当前节点，则交换它们的位置并继续向下调整。
6. 向堆中插入元素
void insert(MinHeap *heap, int length) {
if (heap->size >= heap->capacity) return;
heap->data[heap->size].length = length;
siftUp(heap, heap->size);
heap->size++;
}
insert函数：向堆中插入一个新元素。- 如果堆已满，直接返回。
- 将新元素插入到堆的末尾，然后调用
siftUp函数进行调整。
7. 从堆中取出最小元素
Node extractMin(MinHeap *heap) {
Node minElement = heap->data[0];
heap->data[0] = heap->data[--heap->size];
siftDown(heap, 0);
return minElement;
}
extractMin函数：从堆中取出最小元素。- 将堆顶元素与最后一个元素交换，然后调用
siftDown函数进行调整。 - 返回最小元素。
8. 计算总比较次数T
int calculateTotalComparisons(int *lengths, int n) {
MinHeap *heap = createMinHeap(n);
for (int i = 0; i < n; i++) {
insert(heap, lengths[i]);
}
int totalComparisons = 0;
while (heap->size > 1) {
Node first = extractMin(heap);
Node second = extractMin(heap);
int combinedLength = first.length + second.length;
totalComparisons += combinedLength;
insert(heap, combinedLength);
}
free(heap->data);
free(heap);
return totalComparisons;
}
calculateTotalComparisons函数：计算合并所有表的总比较次数。- 创建一个最小堆并将所有表的长度插入到堆中。
- 不断从堆中取出两个最小的元素进行合并，并记录合并过程中的比较次数。
- 最后返回总比较次数。
9. 主函数
int main() {
int n;
printf("输入表的数量: ");
scanf("%d", &n);
int lengths[n];
printf("输入每个表的长度: ");
for (int i = 0; i < n; i++) {
scanf("%d", &lengths[i]);
}
int totalComparisons = calculateTotalComparisons(lengths, n);
printf("总比较次数T: %d\n", totalComparisons);
return 0;
}
main函数：程序入口。- 读取用户输入的表的数量和每个表的长度。
- 调用
calculateTotalComparisons函数计算总比较次数并输出结果。
/*完整代码*/
************************************************************
#include <stdio.h>
#include <stdlib.h>
// 定义一个结构体表示堆中的节点
typedef struct {
int length; // 表的长度
} Node;
// 定义一个结构体表示最小堆
typedef struct {
Node *data; // 存储堆元素的数组
int size; // 当前堆的大小
int capacity; // 堆的最大容量
} MinHeap;
// 初始化最小堆
MinHeap* createMinHeap(int capacity) {
MinHeap *heap = (MinHeap *)malloc(sizeof(MinHeap));
heap->data = (Node *)malloc(capacity * sizeof(Node));
heap->size = 0;
heap->capacity = capacity;
return heap;
}
// 交换两个节点
void swap(Node *a, Node *b) {
Node temp = *a;
*a = *b;
*b = temp;
}
// 向上调整堆
void siftUp(MinHeap *heap, int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (heap->data[parent].length <= heap->data[index].length) break;
swap(&heap->data[parent], &heap->data[index]);
index = parent;
}
}
// 向下调整堆
void siftDown(MinHeap *heap, int index) {
int leftChild, rightChild, smallest;
while (index * 2 + 1 < heap->size) {
leftChild = index * 2 + 1;
rightChild = index * 2 + 2;
smallest = index;
if (leftChild < heap->size && heap->data[leftChild].length < heap->data[smallest].length) {
smallest = leftChild;
}
if (rightChild < heap->size && heap->data[rightChild].length < heap->data[smallest].length) {
smallest = rightChild;
}
if (smallest == index) break;
swap(&heap->data[smallest], &heap->data[index]);
index = smallest;
}
}
// 向堆中插入元素
void insert(MinHeap *heap, int length) {
if (heap->size >= heap->capacity) return;
heap->data[heap->size].length = length;
siftUp(heap, heap->size);
heap->size++;
}
// 从堆中取出最小元素
Node extractMin(MinHeap *heap) {
Node minElement = heap->data[0];
heap->data[0] = heap->data[--heap->size];
siftDown(heap, 0);
return minElement;
}
// 计算总比较次数T
int calculateTotalComparisons(int *lengths, int n) {
MinHeap *heap = createMinHeap(n);
for (int i = 0; i < n; i++) {
insert(heap, lengths[i]);
}
int totalComparisons = 0;
while (heap->size > 1) {
Node first = extractMin(heap);
Node second = extractMin(heap);
int combinedLength = first.length + second.length;
totalComparisons += combinedLength;
insert(heap, combinedLength);
}
free(heap->data);
free(heap);
return totalComparisons;
}
int main() {
int n;
printf("输入表的数量: ");
scanf("%d", &n);
int lengths[n];
printf("输入每个表的长度: ");
for (int i = 0; i < n; i++) {
scanf("%d", &lengths[i]);
}
int totalComparisons = calculateTotalComparisons(lengths, n);
printf("总比较次数T: %d\n", totalComparisons);
return 0;
}