【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典)

这篇具有很好参考价值的文章主要介绍了【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典),数据解构和C++学习分享,数据结构,c语言,c++,启发式算法


一、前言:二叉树的顺序结构

普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。
 
现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段。

【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典),数据解构和C++学习分享,数据结构,c语言,c++,启发式算法


二、堆的概念及结构

堆是一种特殊的数据结构,可以将堆分为大顶堆和小顶堆两种形式。堆中的每个节点都有一个值,并且满足以下两个条件:
 
①:堆的父节点的值总是大于或等于其子节点的值(大顶堆)或者小于或等于其子节点的值(小顶堆)。
②:堆是完全二叉树,即除了最底层外,其他层的节点都是满的,并且最底层的节点都尽量靠左排列。

大(小)堆示意图:

【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典),数据解构和C++学习分享,数据结构,c语言,c++,启发式算法
【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典),数据解构和C++学习分享,数据结构,c语言,c++,启发式算法


三、堆的实现(本篇博客以实现小堆为例)

3.1 准备工作

由于堆是通过数组来实现的,所以我们也和顺序表一样,首先要创建一个结构体来存储:数组指针 + 容量 + 存储数据大小

代码实现:

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;//数组指针
	int size;//存储数据大小
	int capacity;//容量
}HP;

3.2 初始化

初始化有两种方式:
①:初始化时为数组开辟一定大小空间。②:直接将数组指针置为NULL,插入数据过程中在进一步处理。(本篇博客采用第二种)

代码实现:

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

3.3 堆的插入

【代码思路】:
①:在插入数据前,我们首先要判断是否要扩容的问题。由于前面初始化时我们直接置空,所以我们先判断容量是否为空。如果为空开4个空间,否则空间扩大到原来的2倍。(为空时,第一次具体开辟多少空间读者可自行选择,本篇博客开4)
②:接下来就是插入数据了!但有一个问题,直接插入数据可能会破坏堆的结构,所以我们采用了向上调整算法

代码:

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->size == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	
	//插入数据
	php->a[php->size] = x;
	php->size++;

	//向上调整
	AdjustUp(php->a, php->size - 1);
}

3.3.1 向上调整算法

【代码思路】:由于插入数据时,影响的只是插入数据到根节点间的关系。所以我们只需将插入数据通过双亲节点调到合适位置即可
 
Tips:父节点和子节点关系

  • leftchild = parent *2 + 1
  • rightchild = parent * 2 + 2
  • parent = (child - 1)/2

【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典),数据解构和C++学习分享,数据结构,c语言,c++,启发式算法
代码:

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

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

3.4 堆的删除

【代码思路】:堆的删除默认是头删。删除有两种思路:
 
①:将根节点删除,再将其余数据全部向前移动。但这样做会造成一个问题:挪动覆盖导致父子节点的关系全乱了,需要重新建堆。为了删个数据,重新建堆,得不偿失,所以我们采用下面这种方法。
 
②:将堆顶的1数据和最后一个数据交换,在删除最后一个数据。堆顶数据在通过向下调整算法调到合适位置即可

【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典),数据解构和C++学习分享,数据结构,c语言,c++,启发式算法

代码:

void HPPop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));//非空,还有数据可删。该接口后面实现
	
	Swap(&php->a[0], &php->a[php->size - 1]);//交换
	php->size--;//删除

	//向下调整
	AdjustDown(php->a, php->size, 0);
}

3.4.1 向下调整算法

【代码思路】:向下调整算法有一个前提:左右子树必须是一个堆,才能调整。同时还要注意是调大堆还是小堆。
调小堆:堆顶元素和孩子中最小的节点比较,如果父节点大于较小的子节点子,两者交换。不断向下调整到合适位置。(调大堆,和较大孩子比较)

【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典),数据解构和C++学习分享,数据结构,c语言,c++,启发式算法

代码

//这里博主在多说一句,为什么向下调整算法不直接传结构体指针,
//而是分别传数组指针和数据大小呢?
//这里是博主有意为之的,目的在于让向下调整算法通用性更强,在做其他题时,也可以直接调用此接口
void AdjustDown(HPDataType* a, int n, int parent)
{
	assert(a);
	int child = parent * 2 + 1;//假设左孩子更小
	while (child < n)
	{
		//如果右孩子存在,且右孩子更小,则左孩子加1移到右孩子
		if ((child + 1) < n && a[child] > a[child + 1])
		{
			child++;
		}

		if (a[parent] > a[child])//交换
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			//父节点小于较小的子节点,说明已经调到合适位置,此时break跳出
			break;
		}
	}
}

3.5 堆的判空(接下的过于简单直接给出代码)

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

3.6 取堆顶的数据

	assert(php);
	assert(!HPEmpty(php));//断言堆中还有元素
	return php->a[0];

3.7 堆的个数

int HPSize(HP* php)
{
	assert(php);
	return php->size;
}

3.8 堆的销毁

void HPDestory(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}

四、所有代码

Heap.h

#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 HPInit(HP* php);//初始化
void HPPush(HP* php, HPDataType x);//插入数据
void HPPop(HP* php);//删除数据
int HPTop(HP* php);//堆顶元素
bool HPEmpty(HP* php);//判空
int HPSize(HP* php);//数据个数
void HPDestory(HP* php);//销毁

Heap.c

#include "Heap.h"

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

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

void AdjustDown(HPDataType* a, int n, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child < n)
	{
		if ((child + 1) < n && a[child] > a[child + 1])
		{
			child++;
		}

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

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->size == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->size] = x;
	php->size++;

	//向上调整
	AdjustUp(php->a, php->size - 1);
}


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

void HPPop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));
	
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	//向下调整
	AdjustDown(php->a, php->size, 0);
}

int HPTop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));
	return php->a[0];
}

int HPSize(HP* php)
{
	assert(php);
	return php->size;
}

void HPDestory(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}

【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典),数据解构和C++学习分享,数据结构,c语言,c++,启发式算法
【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典),数据解构和C++学习分享,数据结构,c语言,c++,启发式算法文章来源地址https://www.toymoban.com/news/detail-663669.html

到了这里,关于【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构入门指南】单链表

     由于顺序表插入和删除元素需要移动大量数据,导致运行效率下降。因此引入了另一种数据结构 —— 链表 。链表又分为单链表和双链表。单链表结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在

    2024年02月14日
    浏览(45)
  • 数据结构入门指南:顺序表

    目录 文章目录 前言 顺序表 静态顺序表 动态顺序表 总结         今天我们正式进入对数据结构的学习,顺序表是数据结构中最简单的一种线性数据结构,也是数据结构入门的试金石,如果对于顺序表中内容理解过难,可以先填补一下C语言中结构体、动态内存管理及指针

    2024年02月15日
    浏览(51)
  • C语言笔记 | 数据结构入门指南

    文章目录 0x00 前言 0x01 百鸡百钱 0x1 题目描述 0x2 问题分析 0x3 代码设计 0x4 完整代码 0x5 运行效果 0x6 举一反三 [兔鸡百钱] 0x02 借书方案知多少 0x1 题目描述 0x2 问题分析 0x3 代码设计 0x4 完整代码 0x5 运行效果 0x6 举一反三 [领导小组方案] 0x03 打鱼还是晒网 0x1 题目描述 0x2 问题分

    2024年02月08日
    浏览(49)
  • 数据结构入门指南:单链表(附源码)

    目录 前言 尾删 头删 查找 位置前插入  位置后插入  位置删除  位置后删除  链表销毁 总结         前边关于链表的基础如果已经理解透彻,那么接下来就是对链表各功能的实现,同时也希望大家能把这部分内容熟练于心,这部分内容对有关链表部分的刷题很有帮助。废话

    2024年02月14日
    浏览(61)
  • Python基础数据结构入门必读指南

    作者主页:涛哥聊Python 个人网站:涛哥聊Python 大家好,我是涛哥,今天为大家分享的是Python中常见的数据结构。 含义:数组是一种有序的数据结构,其中的元素可以按照索引来访问。数组的大小通常是固定的,一旦创建就不能更改。 基本操作: 含义:列表是Python中内置的

    2024年02月07日
    浏览(56)
  • 数据结构入门指南:带头双向循环链表

    目录 文章目录 前言 1.结构与优势 2.链表实现       2.1 定义链表 2.2 创建头节点 2.3 尾插 2.4 输出链表 2.5 尾删 2.6 头插 2.7头删 2.8 节点个数 2.9 查找 2.10 位置插入 2.11 位置删除 2.12 销毁链表  3. 源码 总结         链表一共有8种结构,但最常用的就是无头单向链表、和带头

    2024年02月14日
    浏览(51)
  • 【数据结构】二叉树基础入门

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 一棵二叉树是结点的

    2024年02月09日
    浏览(41)
  • 数据结构入门 — 二叉树的概念、性质及结构

    本文属于数据结构专栏文章,适合数据结构入门者学习,涵盖数据结构基础的知识和内容体系,文章在介绍数据结构时会配合上 动图演示 ,方便初学者在学习数据结构时理解和学习,了解数据结构系列专栏点击下方链接。 博客主页:Duck Bro 博客主页 系列专栏:数据结构专栏

    2024年02月07日
    浏览(36)
  • 【Java--数据结构】提升你的编程段位:泛型入门指南,一看就会!

    泛型是一种编程概念,它允许我们编写可以适用于多种数据类型的代码。通过使用泛型,我们可以在编译时期将具体的 数据类型作为参数 传递给代码,从而实现代码 的复用和灵活性 。 在传统的编程中,我们通常需要为不同的数据类型编写不同的代码,这样会导致代码冗余

    2024年04月26日
    浏览(64)
  • 数据结构入门(C语言版)二叉树概念及结构(入门)

    1.1 树的概念 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 ☆有一个特殊的结点,称为根结点,根节点没有前驱结点 ☆除根节点外,其余结点被分成M

    2023年04月14日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包