广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言植物大战数据结构二叉树堆
  • 178

0
分享到

C语言植物大战数据结构二叉树堆

2024-04-02 19:04:59 178人浏览 薄情痞子
摘要

目录前言堆的概念创建结构体初始化结构体销毁结构体向堆中插入数据1.堆的物理结构和逻辑结构2.完全二叉树下标规律3.插入数据思路依次打印堆的值删除堆顶的值判断堆是否为空求堆中有几个元素

“竹杖芒鞋轻胜马，谁怕？一蓑烟雨任平生”

C语言朱武大战数据结构专栏

C语言植物大战数据结构快速排序图文示例

C语言植物大战数据结构希尔排序算法

C语言植物大战数据结构堆排序图文示例

C语言植物大战数据结构二叉树递归

前言

此篇详细实现二叉树中的一个顺序结构的实现——堆。并实现堆排序重点是堆的规律和堆的实现

堆的概念

堆：将一些元素按完全二叉树的顺序存储方式存储在一个一维数组中。这就是堆。完全二叉树：通俗讲就是只有最后一层的节点可以满，也可以不满。但是最后一层之前的节点要满，这就叫做完全二叉树。

在这里插入图片描述

小堆大堆：将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。（必须满足堆的性质）

堆的性质：

1.堆中某个节点的值总是不大于或不小于其父节点的值

2.堆总是一棵完全二叉树。

注意：

1.普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。

2.现实中我们通常把堆(一种特殊的二叉树)使用顺序结构的数组来存储。

3.需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

接下来我们用纯C实现小堆

创建结构体

因为完全二叉树更适合使用顺序结构存储。而堆就是完全二叉树，所以我们需要创建顺序表

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;//a指向只一个堆数组
	size_t size;//记录堆的大小
	size_t capacity;//堆的最大容量
}HP;

初始化结构体

这一步必须要有，相当于创建变量了。

//初始化结构体
void Heapinit(HP* PHP)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

销毁结构体

因为是动态版的顺序表，有动态开辟就需要动态内存释放，也就是free掉a所指向的空间。

//销毁结构体
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	//free掉及时置空，防止野指针
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

向堆中插入数据

在插入数据之前，我们需要先知道堆的一个技巧。

1.堆的物理结构和逻辑结构

前面的步骤打造了一个堆的轮廓，你说它是堆吧，其实本质就是一个物理结构在内存中连续的顺序表罢了。也就是数组。如图下标从0开始。

在这里插入图片描述

但是要用到它的逻辑结构，需要把它想象成一个完全二叉树，就是下面图片这个样子。

在这里插入图片描述

好了，现在我们要向堆中插入数据了，因为顺序表尾插效率高O(1),且尾插不会大幅度改变堆的结构。所以插入数据指的是尾插。

2.完全二叉树下标规律

注意：

1.尾插注意的是size的大小，size一直指向的是即将插入的那个空间。

2.和顺序表唯一不同的是尾插后需要向上调整数据，保持小堆的从上往下依次增大的结构

3.堆中的下标是有规律的。规律公式如下

在这里插入图片描述

这里需要强调的是对于父亲下标的计算。父亲的下标计算公式为：parent = (child - 1) / 2;举个例子。因为假如左子树是7，右子树是8。7-1初以2是3, 但8-1初以2是3.5。但是计算机计算的结果也是3。

结论：所以管他是左子树，还是右子树，都能计算出其父亲的下标。

3.插入数据思路

最重要的思路是向上调整思想

我们以向堆中插入一个8为例。

因为size指向的是顺序表中即将插入的位置，所以直接插入就好了，但要及时让size++。

注意：尾插后size还需要指向下一个即将插入的位置。如图

在这里插入图片描述

然后开始向上调整8的位置。

思路：

1.让child依次和其parent比较，假如child小的话就交换两者的数据，使child的值依次向上走。然后迭代执行child = parent;parent = (child - 1) / 2;用来迭代parent和child的位置，直到child等于0。结束循环。

2.我觉得思路不难，难在把思路转换为代码然后实现。

3.注意实参传递的实参分别是数组首元素的地址，和新插入元素的下标。

在这里插入图片描述

//交换
void HeapSwap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
		//因为需要多次用到交换算法，所以写成一个函数，方便调用。
			HeapSwap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//插入堆
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//除了AdjustUp
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		//注意realloc的用法
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)* newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	++php->size;
	//唯一不同于顺序表的地方，向上调整算法
	AdjustUp(php->a, php->size - 1);
}

依次打印堆的值

插入堆后，为了可视化，我们还是打印一下看看效果。

void HeapPrint(HP* php)
{
	assert(php);
	for (size_t i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

删除堆顶的值

删除也是一门艺术。今天的我是站在巨人的肩膀上学习堆的删除。

大佬们的算法思路是：

1.先让堆顶的值和堆尾的值交换O(1)，然后删除O(1)交换后堆尾的值。

2.再使用向下调整O(logN)算法，先比较left和right哪个小，谁小就让parent和谁交换，然后依次迭代，使堆顶的值向下调整。直到child大于size结束循环。

因为这样的时间复杂度是相当牛的。

注意：这里有几个地方代码技巧非常绝。

1.假设左子树就是最小的值。然后比较左右子树的大小后进行调整到底谁是最小的就OK了。这是非常的绝。因为你需要关注到底是左子树小还是右子树小！

//非常绝的一个思路
if (child+1 < size &&
 a[child + 1] < a[child])
{
	++child;
}

删除代码如下。

//向下调整
AdjustDown(HPDataType* a,size_t size, size_t root)
{
	 size_t parent= root;
	 size_t child= parent * 2 + 1;
	 while (child < size)
	 {
	 //判断哪个孩子小。
		 if (child+1 < size && a[child + 1] < a[child])
		 {
			 ++child;
		 }
		 //交换父亲和孩子的值
		 if (a[child] < a[parent])
		 {
			 HeapSwap(&a[parent], &a[child]);
			 //迭代
			 parent = child;
			 child = parent * 2 + 1;
		 }
		 else
		 {
			 break;
		 }
	 }	
}
//删除堆顶的值
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//交换堆顶和堆尾的值。然后删除堆尾的值
	HeapSwap(php->a, &php->a[php->size - 1]);
	--php->size;
	//向下调整
	AdjustDown(php->a, php->size, 0);
}

判断堆是否为空

当size为0时，堆即为空。

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

求堆中有几个元素

size标记的就是有几个元素。

//求堆中有几个元素
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

得到堆顶的值

需要注意的是size最少为1.当size为0时，就意味着堆已经为空。所以我们需要assert断言size不为0.

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

建堆

升序：建大堆

降序：建小堆（我们这里用的是建小堆）利用堆删除思想来进行排序

void HeapSort(HPDataType* a, int size)
{
	HP hp;
	HeapInit(&hp);
	//先创建一个小堆
	for (int i = 0; i < size; i++)
	{
		HeapPush(&hp, a[i]);
	}
	size_t j = 0;
	//利用堆删除思想来进行排序
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}
int main()
{
	//对a数组进行排序
	int a[] = { 4,2,7,8,5,1,0,6 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

时间复杂度分析：

时间复杂度为O(N*logN)。比冒泡排序上升了一个档次哦。

但是空间复杂度有待改进。

但是空间复杂度因为占用了一个数组所以是O(N)。

空间复杂度改进的话需要很多字来详解。下篇博文继续叙述。

总体代码

Heap.h

#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	size_t size;
	size_t capacity;
}HP;
//初始化结构体
void HeapInit(HP* php);
//销毁结构体
void HeapDestroy(HP* php);
//向堆里插入数据
void HeapPush(HP* php, HPDataType x);
//交换堆中父子
void HeapSwap(HPDataType* pa, HPDataType* pb);
//删除堆顶数据
void HeapPop(HP* php);
//按照下标打印堆
void HeapPrint(HP* php);
//判断堆是否为空
bool HeapEmpty(HP* php);
//求堆中有几个元素
size_t HeapSize(HP* php);
//得到堆顶的值
HPDataType HeapTop(HP* php);

Heap.c

#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
//初始化结构体
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
//销毁结构体
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
//交换
void HeapSwap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			HeapSwap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//插入堆
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)* newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	++php->size;
	//向上调整
	AdjustUp(php->a, php->size - 1);
}
//向下调整
AdjustDown(HPDataType* a,size_t size, size_t root)
{
	 size_t parent= root;
	 size_t child= parent * 2 + 1;
	 while (child < size)
	 {
		 if (child+1 < size && a[child + 1] < a[child])
		 {
			 ++child;
		 }
		 if (a[child] < a[parent])
		 {
			 HeapSwap(&a[parent], &a[child]);
			 parent = child;
			 child = parent * 2 + 1;
		 }
		 else
		 {
			 break;
		 }
	 }	
}
//删除堆的值
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//交换堆顶和堆尾的值。然后删除堆尾的值
	HeapSwap(php->a, &php->a[php->size - 1]);
	--php->size;
	//向下调整
	AdjustDown(php->a, php->size, 0);
}
//打印堆
void HeapPrint(HP* php)
{
	assert(php);
	for (size_t i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
//判断堆是否为空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
//求堆中有几个元素
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
//得到堆顶的值
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

Test.c

#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
void testHeap()
{
	HP hp;
	HeapInit(&hp);
	HeapPush(&hp, 5);
	HeapPush(&hp, 4);
	HeapPush(&hp, 3);
	HeapPush(&hp, 2);
	HeapPush(&hp, 1);
	HeapPrint(&hp);
	
	HeapDestroy(&hp);
}
void HeapSort(HPDataType* a, int size)
{
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < size; i++)
	{
		HeapPush(&hp, a[i]);
	}
	size_t j = 0;
	while (!HeapEmpty(&hp))
	{
		a[j] = HeapTop(&hp);
		j++;
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}
int main()
{
	
	int a[] = { 4,2,7,8,5,1,0,6 };
	HeapSort(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

以上就是C语言植物大战数据结构二叉树堆的详细内容，更多关于C语言二叉树堆的资料请关注编程网其它相关文章！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C语言植物大战数据结构二叉树堆

本文链接: https://www.lsjlt.com/news/148466.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档
去做题
猜你喜欢
  • C语言植物大战数据结构二叉树堆
    目录前言堆的概念创建结构体初始化结构体销毁结构体向堆中插入数据1.堆的物理结构和逻辑结构2.完全二叉树下标规律3.插入数据思路依次打印堆的值删除堆顶的值判断堆是否为空求堆中有几个元素...
    99+
    2022-11-13
  • C语言植物大战数据结构二叉树递归
    目录前言一、二叉树的遍历算法1.构造二叉树2.前序遍历(递归图是重点.)3.中序遍历4.后序遍历二、二叉树遍历算法的应用1.求节点个数3.求第k层节点个数4.查找值为x的节点5.二叉...
    99+
    2022-11-13
  • C语言植物大战数据结构堆排序图文示例
    目录TOP.堆排序前言一、向下调整堆排序1.向下调整建堆建堆的技巧建堆思路代码2.向下调整排序调整思路排序整体代码3.时间复杂度(难点)向下建堆O(N)向下调整(N*LogN)二、向...
    99+
    2022-11-13
  • C语言植物大战数据结构希尔排序算法
    目录前言一、插入排序1.排序思路2.单趟排序详细图解3.整体代码4.时间复杂度(1).最坏情况下(2).最好情况下(3).基本有序情况下(重点)5.算法特点二、希尔排序1.希尔从哪个...
    99+
    2022-11-13
  • C语言数据结构二叉树之堆的实现和堆排序详解
    目录一、本章重点二、堆2.1堆的介绍2.2堆的接口实现三、堆排序一、本章重点 堆的介绍堆的接口实现堆排序 二、堆 2.1堆的介绍 一般来说，堆在物理结构上是连续的数组结构，在逻辑结构...
    99+
    2022-11-13
  • C语言数据结构之二叉树详解
    目录1. 树概念及结构1.1树概念1.2树的表示2. 二叉树概念及结构2.1概念2.2数据结构中的二叉树2.3特殊的二叉树2.4二叉树的存储结构2.5二叉树的性质3. 二叉树顺序结构...
    99+
    2022-11-13
  • C语言数据结构之二叉链表创建二叉树
    目录一、思想（先序思想创建）二、创建二叉树(1)传一级参数方法(2)传二级参数方法一、思想（先序思想创建） 第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树，直到递归创建...
    99+
    2022-11-13
  • C语言堆与二叉树的顺序结构与实现
    目录一. 二叉树的顺序结构二. 堆的概念及结构三. 堆的实现四. 堆排序(具有缺陷型)一. 二叉树的顺序结构 普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全...
    99+
    2022-11-13
  • C语言植物大战数据结构快速排序图文示例
    目录快速排序一、经典1962年Hoare法1.单趟排序2.递归左半区间和右半区间3.代码实现二、填坑法(了解)1.单趟思路2.代码实现三、双指针法(最佳方法)1.单趟排序2.具体思路...
    99+
    2022-11-13
  • C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树
    链接：C语言数据结构系列之树的概念结构和常见表示方法 0x00 概念 定义：二叉树既然叫二叉树，顾名思义即度最大为2的树称为二叉树。 它的度可以为 1 也可...
    99+
    2022-11-13
  • C语言数据结构二叉树递归的方法
    本篇内容介绍了“C语言数据结构二叉树递归的方法”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！一、二叉树的遍历算法二叉树的精髓在于遍历。遍历掌...
    99+
    2023-06-30
  • C语言数据结构系列篇二叉树的遍历
    目录前言：Ⅰ.  定义二叉树0x00 二叉树的概念（回顾）0x00 定义二叉树0x01 手动创建二叉树Ⅱ.  二叉树的遍历...
    99+
    2022-11-13
  • C语言数据结构详细解析二叉树的操作
    目录二叉树分类二叉树性质性质的使用二叉树的遍历前序遍历中序遍历后序遍历层序遍历求二叉树的节点数求二叉树叶子结点个数求二叉树的最大深度二叉树的销毁二叉树分类 满二叉树 除最后一层无任何...
    99+
    2022-11-13
  • Go语言数据结构之二叉树可视化详解
    目录题目源代码做题思路扩展左右并列展示上下并列展示总结回顾题目 以图形展示任意二叉树，如下图，一个中缀表达式表示的二叉树：3.14*r²*h/3 源代码 package ...
    99+
    2022-11-11
  • 如何使用C语言实现平衡二叉树数据结构算法
    目录前言一、平衡二叉树实现原理二、平衡二叉树实现算法三、全部代码前言 对于一个二叉排序树而言 它们的结构都是根据了二叉树的特性从最左子树开始在回到该结点上继续往右结点走 ...
    99+
    2022-11-12
  • Go语言数据结构之二叉树必会知识点总结
    目录前言二叉树概念二叉树的性质创建二叉树树的遍历前序遍历(V-L-R)中序遍历(L-V-R)后序遍历(L-R-V)前言 如果你是一个开发人员，或多或少对树型结构都有一定的认识，我个人...
    99+
    2022-11-11
  • C语言数据结构二叉树先序、中序、后序及层次四种遍历
    目录一、图示展示（1）先序遍历（2）中序遍历（3）后序遍历（4）层次遍历（5）口诀二、代码展示一、图示展示 （1）先序遍历 先序遍历可以想象为，一个小人从一棵二叉树根节点为起点，沿着...
    99+
    2022-11-13
  • 编程语言中数据结构之二叉树递归与非递归的示例分析
    这篇文章主要为大家展示了“编程语言中数据结构之二叉树递归与非递归的示例分析”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“编程语言中数据结构之二叉树递归与非递归的示例分析”这篇文章吧。数据结构 二...
    99+
    2023-06-09
软考高级职称资格查询
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作