追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构

这篇具有很好参考价值的文章主要介绍了追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构

   
😎博客昵称:博客小梦
😊最喜欢的座右铭:全神贯注的上吧!!!
😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主!

😘博主小留言:哈喽!😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不多说,文章推上!欢迎大家在评论区唠嗑指正,觉得好的话别忘了一键三连哦!😘
追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构

前言🙌

    哈喽各位友友们😊,我今天又学到了很多有趣的知识现在迫不及待的想和大家分享一下!😘我仅已此文,手把手带领大家追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构~ 都是精华内容,可不要错过哟!!!😍😍😍

什么是堆?

堆的概念及结构

如果有一个关键码的集合K = { , , ,…, },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:

  1. 父结点的值都大于孩子结点的值,则称为大堆;
  2. 父结点的值都小于孩子结点的值,则称为小堆;
    大堆也称为大根堆,小堆也叫做小根堆。

堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。
    追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构

追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构

堆的实现

堆向下调整算法

现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整

画图分析:

追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构
追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构

堆向下调整算法源代码分享:
向下调整建小堆
//向下调整--建小堆
void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}

		if (a[child] < a[parent])
		{
			Swap(&(a[parent]), &(a[child]));
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


向下调整建大堆
//建大堆
void AdjustDown(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] > a[child])
		{
			child++;
		}

		if (a[child] > a[parent])
		{
			Swap(&(a[parent]), &(a[child]));
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

堆向上调整算法源代码分享:
画图分析:

追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构

追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构

向上调整建小堆
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (a[child] < a[parent])
		{
			Swap(&(a[child]), &(a[parent]));
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
向上调整建大堆
//向上调整建大堆
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (a[child] > a[parent])
		{
			Swap(&(a[child]), &(a[parent]));
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

C语言整体实现堆数据结构源代码分享

堆的插入:

先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。
追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//扩容
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tem = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tem == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tem;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	//向上调整--建小堆
	if(php->size > 0)
		AdjustUp(php->a, php->size);
	php->size++;	
}

堆的删除:

删除堆是删除堆顶的数据,将堆顶的数据和最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法。

画图分析:

追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&(php->a[0]), &(php->a[php->size - 1]));
	php->size--;
	AdjustDwon(php->a, php->size,0);
}

头文件(Heap.h)编写:

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int HPDataType;


typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
void Swap(HPDataType* p1, HPDataType* p2);
// O(logN)
void AdjustDwon(HPDataType* a, int size, int parent);
void AdjustUp(HPDataType* a, int child);

void HeapPrint(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

功能文件(Heap.c)编写:

#define _CRT_SECURE_NO_WARNINGS 1

#include"Heap.h"

void Swap(HPDataType* p1, HPDataType* p2)
{
	int tem = *p1;
	*p1 = *p2;
	*p2 = tem;
}
// O(logN)
//建小堆
void AdjustDwon(HPDataType* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < size)
	{
		//选出最小的那个
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		if (a[child] < a[parent] )
		{
			Swap(&(a[parent]), &(a[child]));
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (a[child] < a[parent])
		{
			Swap(&(a[child]), &(a[parent]));
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPrint(HP* php)
{
	assert(php);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//扩容
	if (php->capacity == php->size)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tem = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tem == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tem;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	//向上调整--建小堆
	if(php->size > 0)
		AdjustUp(php->a, php->size);
	php->size++;
	
}

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&(php->a[0]), &(php->a[php->size - 1]));
	php->size--;
	AdjustDwon(php->a, php->size,0);
}
	
	
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

测试文件(test.c)编写:

#define _CRT_SECURE_NO_WARNINGS 1

#include"Heap.h"



void HeapTest1()
{
	HP h;
	HeapInit(&h);
	HeapPush(&h, 15);
	HeapPush(&h, 18);
	HeapPush(&h, 19);
	HeapPush(&h, 25);
	HeapPush(&h, 28);
	HeapPush(&h, 34);
	HeapPush(&h, 65);
	HeapPush(&h, 49);
	HeapPush(&h, 27);
	HeapPush(&h, 37);
	HeapPush(&h, 10);
	printf("%d\n", HeapSize(&h));
	HeapPrint(&h);

	for (int i = 0; i < 8; i++)
	{
		printf("%d ", HeapTop(&h));
		HeapPop(&h);
	}
	printf("\n");
	HeapDestroy(&h);
	printf("%d ", HeapTop(&h));
	HeapPop(&h);
}

int main()
{

	HeapTest1();
	return 0;
}

运行结果测试截图:

追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构

总结撒花💞

   本篇文章旨在分享详解小白如何使用C语言实现堆数据结构。希望大家通过阅读此文有所收获
   😘如果我写的有什么不好之处,请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘文章来源地址https://www.toymoban.com/news/detail-416574.html

到了这里,关于追梦之旅【数据结构篇】——详解小白如何使用C语言实现堆数据结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++算法之旅、05 基础篇 | 第二章 数据结构

    常用代码模板2——数据结构 - AcWing 使用结构体指针,new Node() 非常慢,创建10万个节点就超时了,做笔试题不会用这种方式(优化是提前初始化好数组,但这样跟数组模拟没区别了,而且代码量很长) 使用两个数组,e存储val,ne存储next。空节点next用-1表示 826. 单链表 - AcWi

    2024年02月10日
    浏览(58)
  • 【追梦之旅】—— 手“C”二叉树~

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2024年02月06日
    浏览(32)
  • 数据结构之单链表非常详细介绍(适合小白)

    之前有一篇文章介绍完顺序表,可以点击(顺序表文章)即可看到顺序表的知识后,我们就要开始学习链表了,链表的种类有很多,比如说 单链表 、 双向链表 、 循环或者非循环链表 以及 带头或者不带头链表等 ,那么链表和顺序表有哪些不同呢,相较于顺序表,链表做了哪些

    2024年02月06日
    浏览(42)
  • 【数据结构】C--单链表(小白入门基础知识)

    前段时间写了一篇关于顺序表的博客,http://t.csdn.cn/0gCRp 顺序表在某些时候存在着一些不可避免的缺点: 问题: 1. 中间 / 头部的插入删除,时间复杂度为 O(N) 2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 3. 增容一般是呈 2 倍的增长,势必会有一定的空间

    2024年02月16日
    浏览(51)
  • 【数据结构】带头双向循环链表(小白入门必备知识)

    前言: 💥🎈个人主页:​​​​​​Dream_Chaser~ 🎈💥 ✨✨专栏:http://t.csdn.cn/oXkBa ⛳⛳本篇内容:c语言数据结构--带头双向循环链表 目录 一.带头双向循环链表  A.带头双向循环链表概念 B.带头双向循环链表的实现 1.带头双向循环链表的结构 2.动态申请节点函数 3.链表的初始化

    2024年02月12日
    浏览(36)
  • 【数据结构】——单链表超详细介绍(小白必看!!!)

     c语言中的小小白-CSDN博客 c语言中的小小白关注算法,c++,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域. https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343 给大家分享一句我很喜欢我话: 知不足而奋进,望远山而前行!!! 铁铁们,成功的路上必然是孤

    2024年04月11日
    浏览(68)
  • 【数据结构】顺序表---C语言版(数据结构开篇小菜,全网最详细!小白看一遍就学会!!!)

    停更了一个月限时返场啦😍从本篇文章开始就进入了我们数据结构的学习喽!本篇文章也是《数据结构与算法》 专栏的第一篇文章,本篇的内容是顺序表的学习,也是数据结构的开胃小菜,希望烙铁们可以理解消化哦🥰!!! 在我们学习 顺序表 之前呢,我们大家肯定会有

    2024年02月06日
    浏览(46)
  • 【数据结构】——单链表超详细介绍(独家介绍,小白必看!!!)

    被滑走别滑走 ,我这 一万字 的文章,写的真的很痛苦的,希望能得到 一点点支持 !!! 重点内容 和 易错点 都用 彩笔 标注了,干货满满,耐心看完,我真的真的有在 认真更新o(╥﹏╥)o 上一篇文章介绍完顺序表后,我们就要开始学习链表了,链表的种类有很多,比如说

    2024年02月02日
    浏览(41)
  • 【数据结构】带头双向循环链表(小白作品,如果有误,请大佬指点)

    带头双向循环链表(Doubly Circular Linked List with a Head)是一种链表数据结构,它具有以下特点: 头节点(哨兵位):带头双向循环链表包含一个头节点,它位于链表的起始位置,并且不存储实际数据。头节点的前驱指针指向尾节点,头节点的后继指针指向第一个实际数据节点。

    2024年04月28日
    浏览(29)
  • 【追梦之旅】——栈居然还能这样玩?!+ 力扣 - 有效括号

        😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话不

    2024年02月05日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包