当前位置： 首页 > article >正文

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

article 2024/11/13 6:58:06

详解小白如何使用C语言实现堆数据结构 + “痛”撕堆排序~😎

  • 前言🙌
  • 什么是堆？
    • 堆的概念及结构
  • 堆的性质：
    • 堆的实现
      • 堆向下调整算法
      • 画图分析：
        • 堆向下调整算法源代码分享：
          • 向下调整建小堆
          • 向下调整建大堆
        • 堆向上调整算法源代码分享：
        • 画图分析：
          • 向上调整建小堆
          • 向上调整建大堆
    • C语言整体实现堆数据结构源代码分享
      • 堆的插入：
      • 堆的删除：
        • 画图分析：
      • 头文件(Heap.h)编写：
      • 功能文件（Heap.c）编写：
      • 测试文件（test.c）编写：
      • 运行结果测试截图：
  • 总结撒花💞

追梦之旅，你我同行

   
😎博客昵称：博客小梦
😊最喜欢的座右铭：全神贯注的上吧！！！
😊作者简介：一名热爱C/C++，算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主！
😘博主小留言：哈喽！😄各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！😘
在这里插入图片描述

前言🙌

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

什么是堆？

堆的概念及结构

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

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

堆的性质：

  • 堆中某个节点的值总是不大于或不小于其父节点的值；
  • 堆总是一棵完全二叉树。
    在这里插入图片描述

在这里插入图片描述

堆的实现

堆向下调整算法

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

画图分析：

在这里插入图片描述
在这里插入图片描述

堆向下调整算法源代码分享：

向下调整建小堆
//向下调整--建小堆
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;
		}
	}
}

堆向上调整算法源代码分享：

画图分析：

在这里插入图片描述

在这里插入图片描述

向上调整建小堆
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到数组的尾上，再进行向上调整算法，直到满足堆。
在这里插入图片描述

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);
}

头文件(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语言实现堆数据结构。希望大家通过阅读此文有所收获！
   😘如果我写的有什么不好之处，请在文章下方给出你宝贵的意见😊。如果觉得我写的好的话请点个赞赞和关注哦~😘😘😘


http://www.kler.cn/a/11920.html

相关文章：

  • Day 63 || 拓扑排序、dijkstra
  • Vue中优雅的使用Echarts的三种方式
  • 通过脚本，发起分支合并请求和打tag
  • 线性表-数组描述补充 迭代器（C++）
  • 小程序中引入下载到本地的iconfont字体图标加载不出来问题解决
  • LeetCode【0016】最接近的三数之和
  • [架构之路-160]-《软考-系统分析师》-10-系统分析-7-数据与数据流程分析、需求规格说明书
  • GPT-4工具是软件工程师工作效率的倍增器
  • 前端解析Excel中的数据进行操作
  • 线性代数——矩阵
  • CTR-GCN 论文解读
  • 游戏运营专员的职责有哪些？提高游戏收入的关键是什么？
  • C语言实现惯导更新算法（机械编排）
  • DPDK入门（环境搭建以及小demo）
  • 2022国赛30：windows脚本题解析
  • python入门：cl.exe‘ failed with exit status 2错误通用解决方案
  • 【负荷预测】基于VMD-SSA-LSTM光伏功率预测【可以换数据变为其他负荷等预测】（Matlab代码实现）
  • 优橙内推河南专场——5G网络优化（中高级）工程师
  • mycat读写分离
  • C结构体中末尾的data[0]
  • Java-类的知识进阶
  • yocto 任务
  • 如何构建敏捷项目管理团队？
  • XML与JSON知识学习
  • 防火墙iptables
  • JavaSE学习进阶day03_01 多态