用c语言实现堆的建立和插入、删除操作,要完整代码
时间: 2024-02-18 20:03:27 浏览: 22
以下是用C语言实现堆的建立和插入、删除操作的完整代码,包括注释说明。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_HEAP_SIZE 100 // 堆的最大容量
// 定义堆结构体
typedef struct {
int* data; // 存储堆中的数据
int size; // 堆的大小
} Heap;
// 初始化堆
void initHeap(Heap* heap) {
heap->data = (int*)malloc(sizeof(int) * MAX_HEAP_SIZE); // 动态分配内存
heap->size = 0; // 初始大小为0
}
// 交换两个数的值
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 将堆中第i个结点的值向下调整
void adjustDown(Heap* heap, int i) {
int left = i * 2 + 1; // 左孩子结点的下标
int right = i * 2 + 2; // 右孩子结点的下标
int maxIndex = i; // 初始化最大值的下标为i
// 找到左右孩子结点中的最大值
if (left < heap->size && heap->data[left] > heap->data[maxIndex]) {
maxIndex = left;
}
if (right < heap->size && heap->data[right] > heap->data[maxIndex]) {
maxIndex = right;
}
// 如果最大值的下标不是i,则交换i和最大值结点的值,并继续向下调整
if (maxIndex != i) {
swap(&heap->data[i], &heap->data[maxIndex]);
adjustDown(heap, maxIndex);
}
}
// 将堆中的最后一个元素向上调整
void adjustUp(Heap* heap) {
int i = heap->size - 1; // 最后一个结点的下标
int parent = (i - 1) / 2; // 父结点的下标
// 如果父结点的值比最后一个结点的值小,则交换两个结点的值,并继续向上调整
while (i > 0 && heap->data[parent] < heap->data[i]) {
swap(&heap->data[parent], &heap->data[i]);
i = parent;
parent = (i - 1) / 2;
}
}
// 向堆中插入一个元素
void insert(Heap* heap, int val) {
if (heap->size >= MAX_HEAP_SIZE) { // 如果堆已满,则返回
return;
}
heap->data[heap->size] = val; // 将新元素放入堆的末尾
heap->size++; // 堆的大小加1
adjustUp(heap); // 将新元素向上调整
}
// 删除堆中的最大元素
void removeMax(Heap* heap) {
if (heap->size == 0) { // 如果堆为空,则返回
return;
}
heap->data[0] = heap->data[heap->size - 1]; // 将最后一个元素移到堆顶
heap->size--; // 堆的大小减1
adjustDown(heap, 0); // 将堆顶元素向下调整
}
// 打印堆中的元素
void printHeap(Heap* heap) {
int i;
for (i = 0; i < heap->size; i++) {
printf("%d ", heap->data[i]);
}
printf("\n");
}
int main() {
Heap heap;
initHeap(&heap); // 初始化堆
// 向堆中插入元素
insert(&heap, 2);
insert(&heap, 5);
insert(&heap, 7);
insert(&heap, 3);
insert(&heap, 9);
insert(&heap, 1);
printf("堆中的元素为:");
printHeap(&heap);
// 删除堆中的最大元素
removeMax(&heap);
printf("删除最大元素后,堆中的元素为:");
printHeap(&heap);
return 0;
}
```
以上代码实现了堆的建立和插入、删除操作,并且在删除最大元素后输出了堆中的元素。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)