【数据结构】C语言实现堆(附完整运行代码)
🦄个人主页:修修修也
🎏所属专栏:数据结构
⚙️操作环境:Visual Studio 2022
编辑
目录
一.了解项目功能
在本次项目中我们的目标是实现一个使用顺序结构存储的堆:
该堆使用动态内存分配空间,可以用来存储任意数量的同类型数据.
堆需要包含三个要素:存储数据的数组a,堆的当前存储容量capacity,堆当前的长度size.
堆结构的图示如下:
编辑
堆程序提供的功能有:
1. 堆的初始化.
2. 数据元素入堆.
3. 数据元素出堆.
4. 数据元素向上调整.
5. 数据元素向下调整.
6. 取堆顶元素.
7. 堆判空.
8. 打印大堆.
9. 堆的元素个数.
10. 堆销毁.
二.项目功能演示(以大堆为例)
要编写一个堆项目,首先要明确我们想要达到的效果是什么样，下面我将用vs2022 编译器来为大家演示一下堆程序运行时的样子：
堆程序演示
这是演示过程中程序生成的堆数组,我们将数组构建成堆验证一下:
编辑
编辑
编辑
编辑
编辑
编辑
可以看到,程序生成的大堆是符合堆的特性的.
三.逐步实现项目功能模块及其逻辑详解
通过第二部分对项目功能的介绍，我们已经对 的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！
！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。
1.实现堆程序主函数
由于我们要实现堆的功能可以反复使用的逻辑，且至少在一开始执行一次,因此我们选择do...while的循环语句来实现这一部分的逻辑.
该部分功能实现代码如下:
int main()
{
HP hp;
HeapInit(&hp);
int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件
do //使用do...while实现
{
HeapMenu();
scanf("%d", &swi);
switch (swi)
{
case 0:
// 释放堆内存
HeapDestory(&hp);
printf("您已退出程序:>\n");
break;
case 1:
printf("请输入要入堆的数据:>");
HPDataType push_data = 0;
scanf("%d", &push_data);
HeapPush(&hp, push_data);
printf("已成功入堆:>\n");
break;
case 2:
HeapPop(&hp);
printf("出堆成功:>\n");
break;
case 3:
printf("堆顶元素为:");
HPDataType e = HeapTop(&hp);
printf("%d\n", e);
break;
case 4:
if (!HeapEmpty(&hp))
{
printf("当前堆不为空:>\n");
}
else
{
printf("当前堆为空\n");
}
break;
case 5:
printf("当前堆长度为:");
int size = HeapSize(&hp);
printf("%d\n", size);
break;
case 6:
HeapPrint(&hp);
break;
default:
printf("输入错误,请重新输入\n");
break;
}
} while (swi);
return 0;
}2.创建堆结构
创建堆结构成员的结构体应该包括:存储数据的数组a,堆的当前存储容量capacity,堆当前的长度size.
因此我们创建Heap结构体类型时应由一个数组及两个整型组成.
堆结构图示如下:
编辑
这里的第一行使用的typedef类定义的作用是方便我们后续在使用堆时对存储的数据类型做更改,比如后续我们不想在堆中存储int类型数据了,就可以很方便的在这里对数组类型做更改.
实现代码逻辑如下:
typedef int HPDataType;
//堆的结构存储结构很像顺序表
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;3.堆的初始化
堆的初始化需要处理三个内容,分别是初始化:数组a,堆长度size,堆容量capacity.
编辑
初始化堆的逻辑不难,但代码编写的细节上可能会需要多注意一些:
首先在进入初始化函数后,我们应当对函数传进来的参数做一个检验,即检验php指针是否为空指针,如果该指针为空的话,那么指针变量就没有指向任何有效的内存地址，即指针变量的值为0或NULL。这时我们再进入下一步强行开辟内存空间就很可能会导致程序出现一些问题:
tips:
用空指针接收malloc函数返回值的危害是非常严重的，因为它会导致程序出现未定义的行为，甚至可能会导致程序崩溃。
当我们调用malloc函数时，它会在堆上分配一块指定大小的内存，并返回指向该内存的指针。如果我们用空指针来接收malloc函数返回的指针，那么就相当于没有为分配的内存分配任何指针变量，这意味着我们无法访问该内存块，也无法释放该内存块，因为我们没有指向它的指针。
这种情况下，如果我们试图访问该内存块，就会发生未定义的行为，也可能会导致程序崩溃。此外，如果我们忘记释放该内存块，就会导致内存泄漏，这会导致程序消耗大量的内存资源，最终导致程序崩溃或者系统变慢。
因此，我们应该始终使用有效的指针变量来接收malloc函数返回的指针，以确保我们能够正确地访问和释放动态分配的内存块。
因此,我们可以使用assert来对函数传进来的参数php进行检验,如果php为空,那么立刻终止程序,并抛出异常警告程序员.
【 C 语言】库宏 assert 简介及使用方法详解 
https://blog.csdn.net/weixin_72357342/article/details/133822893?spm=1001.2014.3001.5502
检验参数指针没有问题后,我们就可以开始进行初始化相关操作了:
1. 首先,我们为数组a动态开辟一块空间.
2. 然后,给size赋值为0
3. 最后,给capacity赋值为前面动态开辟的数组容量
至此,和顺序表初始化一模一样的堆初始化就完成了,该部分代码如下:
void HeapInit(HP* php)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
if (php->a == NULL)
{
perror("malloc fail::\n");
return;
}
php->size = 0;
php->capacity = 4;
}4.数据元素入堆
入堆的物理逻辑是:
• 先判断当前堆长度是否满了,如果满了要对堆的容量进行扩容.
• 然后的入堆逻辑和顺序表插入元素相同,都是直接按下标给堆尾赋值就行.
• 赋值结束后同样需要给堆长度+1.
• 随后将新入堆的元素向上调整.
入堆逻辑结构图示如下(大堆):
编辑
入堆的物理结构如下:
编辑
该部分代码实现如下:
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//查满扩容
if (php->size == php->capacity)
{
HPDataType*tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail::\n");
return;
}
php->a = tmp;
php->capacity *= 2;
}
//入数据
php->a[php->size] = x;
php->size++;
//向上调整建堆
AdjustUp(php->a, php->size - 1);
}5.数据元素向上调整
在入堆部分其实我们的逻辑还没有结束,因为堆和顺序表不同的点就在于,顺序表插入元素后就没有别的事了,但堆中元素入堆后需要进行向上调整,因为我们不能保证新入的元素一定完全符合堆定义的要求,为了防止新插入的元素破坏堆的性质,因此我们需要对新入堆的元素进行向上调整,直到调整到其满足堆排序的性质为止.
为了方便理解,我们拿刚才的大堆做一下演示,逻辑图示如下:
编辑
编辑
编辑
此时我们对于新入结点的向上调整就结束了,可以发现,在向上调整结束后,我们的堆就又重新符合大堆的特性了.
搞清楚逻辑结构,我们再来看一下在存储逻辑上这个调整是如何实现的:
首先,我们要知道顺序存储结构存储完全二叉树时双亲结点和左右孩子的下标关系:
• parent=(child-1)/2
• leftchild=parent*2+1
• rightchild=parent*2+2
通过这几个公式,我们就可以很方便的在堆里对双亲和孩子结点进行调整.
如图,在存储结构上,我们首先将数据元素进行入堆:
编辑
其次,我们找到当前入堆元素的双亲结点,并与之比较:
编辑
此时入堆元素仍大于双亲,我们继续交换:
编辑
直到调整到入堆元素比双亲结点小或入堆元素成为根节点时,我们结束向上调整:
编辑
综上,该部分实现代码如下:
//向上调整
void AdjustUp(HPDataType* a, int child)
{
int parent = ( child - 1 ) / 2;
//判断,如果孩子大于双亲,换,否则结束[正因此是大堆]
while (child > 0 && a[child] > a[parent])
{
//交换函数
Swap(&a[child], &a[parent]);
//移动下标,使入堆元素继续向上调整
child = parent;
parent = (child - 1) / 2;
}
}6.数据元素出堆
因为堆的特性使得堆顶元素一定为当前堆中最大/小的值,因此我们出堆操作往往需要出的是堆顶元素.
但是我们不能直接将堆顶元素删除,因为这样会导致堆中剩下的元素关系全部乱掉:
编辑
后面剩余的数据也完全不符合大堆/小堆的特性:
编辑
因此合理的操作是出堆顶就将堆顶元素和堆尾元素交换,然后将新堆顶元素向下调整到合适的位置上:
编辑
综上,出堆的逻辑为:
1. 判空,为空则无法再出堆
2. 交换堆顶元素与堆尾元素
3. 将交换后的堆尾元素删除
4. 将交换后的堆顶元素向下调整
//出堆
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
//先交换堆顶元素和堆尾元素
Swap(&php->a[0], &php->a[php->size-1]);
//删除交换后的堆尾元素(即原来的堆顶)
php->size--;
//将新堆顶元素向下调整
AdjustDown(php->a, php->size, 0);
}7.数据元素向下调整
为了方便理解向下调整,我们继续拿之前的大堆做一个演示:
首先是交换堆顶和堆尾元素:
编辑
其次将交换后的新堆顶元素和两个孩子做比较,如果是大堆,那么只要孩子比新堆顶元素大,二者就交换位置,如果两个孩子都比堆顶元素大,则堆顶元素和较大的那个孩子交换位置.
编辑
直到向下调整到叶子结点位置或交换到该堆顶元素比两个孩子结点都大时停止向下调整:
编辑
搞清楚逻辑结构,我们再来看一下在存储逻辑上这个向下调整是如何实现的:
首先,交换堆首和堆尾元素:
编辑
还是利用前面提到的两个公式来计算该结点的左孩子结点和右孩子结点,再进行比较:
编辑
直到调整到叶子结点或交换到该堆顶元素比两个孩子结点都大时停止向下调整:
编辑
注意:向上调整我们只需要将入堆元素与它的双亲结点比较,而向下调整时我们需要先比较出结点的两个孩子的大小,然后双亲结点与大的/小的(取决于大堆还是小堆)孩子交换位置,直到将该结点交换至叶子结点或比两个孩子结点都大/小为止.
该部分代码逻辑如下:
//向下调整建堆,左右子树必须是大堆或者小堆
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;//默认是左孩子
while (child < n)//孩子走到叶子就不走了
{
//选出左右孩子中大的那个
if (child + 1<n && a[child + 1] > a[child])//如果右孩子存在且大于左孩子
{
child++;
}
//向下调整重新使堆有序
if (a[child] > a[parent])
{
//交换两个元素
Swap(&a[child], &a[parent]);
//继续向后调整
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
8.取堆顶元素
取堆顶元素在物理结构上看就是访问数组的首元素:
编辑
因此该部分的逻辑就是直接访问数组首元素即可.
该部分代码逻辑如下:
HPDataType HeapTop(HP* php)
{
assert(php);
return php->a[0];
}
9.堆判空
因为我们在设计堆时有设置变量记录堆内的元素长度,因此在判空时我们只需要判断size是否等于0即可.
该部分代码逻辑如下:
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
10.堆的元素个数
和判空部分一样,直接访问size并返回即可.
该部分代码逻辑如下:
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
11.打印大堆
因为我们将堆存储在数组中,因此打印逻辑很简单,即遍历打印数组元素即可.
该部分代码实现如下:
void HeapPrint(HP* php)
{
assert(php);
//循环打印数组
int i = 0;
while (i < php->size)
{
printf("%d ", php->a[i]);
i++;
}
printf("\n");
}
12.堆销毁
在堆程序使用结束后,我们需要将之前动态开辟的内存还给操作系统,并将其指针置空,size,capacity置为0.
该部分代码如下:
void HeapDestory(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
四.项目完整代码
我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:
test.c文件
#include"Heap.h"
int main()
{
HP hp;
HeapInit(&hp);
int swi = 0;//创建变量swi作为do...while循环的终止条件,以及switch语句的运行条件
do //使用do...while实现
{
HeapMenu();
scanf("%d", &swi);
switch (swi)
{
case 0:
// 释放堆内存
HeapDestory(&hp);
printf("您已退出程序:>\n");
break;
case 1:
printf("请输入要入堆的数据:>");
HPDataType push_data = 0;
scanf("%d", &push_data);
HeapPush(&hp, push_data);
printf("已成功入堆:>\n");
break;
case 2:
HeapPop(&hp);
printf("出堆成功:>\n");
break;
case 3:
printf("堆顶元素为:");
HPDataType e = HeapTop(&hp);
printf("%d\n", e);
break;
case 4:
if (!HeapEmpty(&hp))
{
printf("当前堆不为空:>\n");
}
else
{
printf("当前堆为空\n");
}
break;
case 5:
printf("当前堆长度为:");
int size = HeapSize(&hp);
printf("%d\n", size);
break;
case 6:
HeapPrint(&hp);
break;
default:
printf("输入错误,请重新输入\n");
break;
}
} while (swi);
return 0;
}Heap.c 文件
#include"Heap.h"
void HeapInit(HP* php)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
if (php->a == NULL)
{
perror("malloc fail::\n");
return;
}
php->size = 0;
php->capacity = 4;
}
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, int child)
{
int parent = ( child - 1 ) / 2;
//判断,如果孩子大于双亲,换,否则结束[正因此是大堆]
while (child > 0 && a[child] > a[parent])
{
//交换函数
Swap(&a[child], &a[parent]);
//移动下标,使入堆元素继续向上调整
child = parent;
parent = (child - 1) / 2;
}
}
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//查满扩容
if (php->size == php->capacity)
{
HPDataType*tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail::\n");
return;
}
php->a = tmp;
php->capacity *= 2;
}
//入数据
php->a[php->size] = x;
php->size++;
//向上调整建堆
AdjustUp(php->a, php->size - 1);
}
//向下调整建堆,左右子树必须是大堆或者小堆
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;//默认是左孩子
while (child < n)//孩子走到叶子就不走了
{
//选出左右孩子中大的那个
if (child + 1<n && a[child + 1] > a[child])//如果右孩子存在且大于左孩子
{
child++;
}
//向下调整重新使堆有序
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//出堆
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
//先交换堆顶元素和堆尾元素
Swap(&php->a[0], &php->a[php->size-1]);
//删除交换后的堆尾元素(即原来的堆顶)
php->size--;
//将新堆顶元素向下调整
AdjustDown(php->a, php->size, 0);
}
HPDataType HeapTop(HP* php)
{
assert(php);
return php->a[0];
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
void HeapDestory(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
void HeapMenu()
{
printf("**********************************\n");
printf("******请选择要进行的操作 ******\n");
printf("******1.入堆 ******\n");
printf("******2.出堆 ******\n");
printf("******3.取堆顶元素 ******\n");
printf("******4.判断堆空 ******\n");
printf("******5.查询当前堆长度 ******\n");
printf("******6.打印大堆 ******\n");
printf("******0.退出堆程序 ******\n");
printf("**********************************\n");
printf("请选择:>");
}
void HeapPrint(HP* php)
{
assert(php);
//循环打印数组
int i = 0;
while (i < php->size)
{
printf("%d ", php->a[i]);
i++;
}
printf("\n");
}Heap.h文件
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
//堆的结构存储结构很像顺序表
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
//堆的初始化
void HeapInit(HP* php);
//数据元素入堆
void HeapPush(HP* php,HPDataType x);
//数据元素出堆
void HeapPop(HP* php);
//元素向上调整
void AdjustUp(HPDataType* a, int child);
//元素向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//取堆顶元素
HPDataType HeapTop(HP* php);
//堆判空
bool HeapEmpty(HP* php);
//堆元素个数
int HeapSize(HP* php);
//堆销毁
void HeapDestory(HP* php);
//堆菜单
void HeapMenu();
//堆打印
void HeapPrint(HP* php);结语
希望这篇堆的C语言实现详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.
学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!
相关文章推荐
【数据结构】 C 语言实现 顺序表万字 详解 ( 附完整运行代码 )
【数据结构】 C 语言实现单链表万字详解 ( 附完整运行代码 )
【数据结构】 C 语言实现带头双向循环链表万字详解 ( 附完整运行代码 )
【数据结构】用 C 语言实现顺序 栈 ( 附完整运行代码 )
【实用编程技巧】不想改 bug? 初学者必须学会使用的报错函数 assert!( 断言函数详解 )
编辑
- 点赞
- 收藏
- 关注作者
评论（0）