1. AI技术聚合首页
  2. IT

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

青葱年少 • • IT • 阅读 34

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

版权声明：本文为博主作者：博客小梦原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/weixin_70261953/article/details/130160623

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
青葱年少的头像青葱年少普通用户
0
上一篇 2024年4月16日
下一篇 2024年4月16日

相关推荐