堆的实现--数据结构

目录

主程序（test.c）

头文件（heap.h）

调用函数（heap.c）

主程序（test.c）

#define _CRT_SECURE_NO_WARNINGS 1#include "heap.h"int main()
{//大堆Heap heap;//初始化HeapInit(&heap);//堆的插入HeapPush(&heap, 5);HeapPush(&heap, 1);HeapPush(&heap, 7);HeapPush(&heap, 10);HeapPush(&heap, 6);HeapPush(&heap, 8);HeapPush(&heap, 12);//堆的删除HeapPop(&heap);HeapPush(&heap, 48);//取堆顶数据HPDataType n = HeapTop(&heap);printf("堆顶的数据为:%d\n", n);HeapPop(&heap);n = HeapTop(&heap);printf("堆顶数据为%d\n", n);HeapPop(&heap);n = HeapTop(&heap);printf("堆顶的数据为:%d\n", n);HeapPop(&heap);HeapPop(&heap);HeapPop(&heap);printf("堆的数据个数为：%d\n", HeapSize(&heap));//判空int a = HeapSize(&heap);if (a == 0){printf("堆为空 \n");}elseprintf("堆不为空 \n");//销毁堆HeapDestory(&heap);return 0;
}

头文件（heap.h）

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;//堆初始化
void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
int HeapSize(Heap* php);
// 堆的判空
int HeapEmpty(Heap* php);
//向下调整
void Adjust_down(HPDataType* a, int father, int n);
//向上调整
void Adjust_up(HPDataType* a, int child);

调用函数（heap.c）

#define _CRT_SECURE_NO_WARNINGS 1
#include "heap.h"//堆初始化
void HeapInit(Heap* php)
{assert(php);php->capacity = 4;HPDataType* ph = (HPDataType*)malloc(sizeof(HPDataType)* php->capacity );if (ph == NULL){perror("malloc file:");return;}php->a = ph;php->size = 0;
}// 堆的销毁
void HeapDestory(Heap* php)
{assert(php);free(php->a);php->capacity = php->size = 0;
}void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}//向上调整
void Adjust_up(HPDataType* a, int child)
{assert(a);int father = (child - 1) / 2;while (child > 0){if (a[child] > a[father]){swap(&a[child], &a[father]);child = father;father = (child - 1) / 2;//当child = 0 时，father = 0;father是整形}else{break;}}
}//向下调整
void Adjust_down(HPDataType* a, int father,int n)
{assert(a);int child = father * 2 + 1;while (child < n ){if (child + 1 < n && a[child + 1] > a[child]){child = child + 1;}if (a[child] > a[father]){swap(&a[child], &a[father]);father = child;child = father * 2 + 1;}else{break;}}
}// 堆的插入
void HeapPush(Heap* php, HPDataType x)
{assert(php);//向上调整if (php->size == php->capacity){php->capacity *= 2;HPDataType* new = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity);if (new == NULL){perror("realloc file:");return;}php->a = new;}php->a[php->size] = x;php->size++;//向上调整Adjust_up(php->a, php->size-1);
}// 堆的删除
void HeapPop(Heap* php)
{assert(php);if (php->size == 0){return;}//删除数据的逻辑是，先把头和尾交换位置，再向下调整swap(&php->a[0], &php->a[php->size - 1]);php->size--;Adjust_down(php->a, 0, php->size);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* php)
{assert(php);if (php->size == 0){return NULL;}return php->a[0];
}
// 堆的数据个数
int HeapSize(Heap* php)
{assert(php);return php->size;
}
// 堆的判空
int HeapEmpty(Heap* php)
{assert(php);if (php->size > 0){return 1;}elsereturn 0;
}