堆和二叉树的动态实现(C语言实现)

请添加图片描述

✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌟🌟 追风赶月莫停留 🌟🌟
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
🌟🌟 平芜尽处是春山🌟🌟
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅

🍋堆和队二叉树

  • 🍑二叉树
    • 🍍二叉树的含义
    • 🍍二叉树的结构
    • 🍍二叉树的存储结构
  • 🍑堆
    • 🍍堆的含义
    • 🍍堆的结构
    • 🍍堆的实现
      • 🍌补充条件
      • 🍌堆的初始化
      • 🍌堆的销毁
      • 🍌堆的插入
      • 🍌 堆的删除
      • 🍌取堆顶的数据
      • 🍌堆的数据个数
      • 🍌堆的判空
      • 🍌堆的整体代码实现

🍑二叉树

🍍二叉树的含义

二叉树是一种树形结构,其特点是每个节点最多有两个子树。

二叉树是一种有序树,这意味着它的子树按照一定的顺序排列,通常左子树出现在右子树之前。二叉树的递归定义可以描述为:二叉树可以是空的,也可以由一个根节点和两个互不相交的子树组成,这两个子树分别称为左子树和右子树。左子树和右子树自身也构成二叉树。

🍍二叉树的结构

在这里插入图片描述

在这里插入图片描述
现实中的二叉树:
在这里插入图片描述

在这里插入图片描述

现实中的树,就是我们学过的二叉树倒过来的样子,大家可以把手机屏幕倒过来看试试。

🍍二叉树的存储结构

二叉树分为顺序存储和链式存储

在这里插入图片描述

顺序存储:类似于数组的存储形式,但只有完全二叉树才会用顺序存储,这样才不会造成空间的浪费

在这里插入图片描述

链式存储:利用了链表的性质。每个节点都存储了上个树和下个树的位置,这也就是带头指针的双链表结构

🍑堆

🍍堆的含义

堆是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:
(1)堆中某个结点的值总是不大于或不小于其父结点的值;
(2)堆总是一棵完全二叉树。
(3)将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。常见的堆有 二叉堆、斐波那契堆等。
(4)堆的物理结构本质上是顺序存储的,是线性的。但在逻辑上不是线性的,是完全二叉树的这种逻辑储存结构。 堆的这个数据结构,里面的成员包括一维数组,数组的容量,数组元素的个数,有两个直接后继。

🍍堆的结构

在这里插入图片描述

堆的结构就是特殊的二叉树结构,也就是上图中完全二叉树的样子

🍍堆的实现

在这里插入图片描述

堆的实现又分为大堆和小堆
大堆:任何父节点都大于等于子节点。
小堆:任何父节点都小于等于子节点。
两个子节点之间的大小没有明确规定

🍌补充条件

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int HPDatetype;
typedef struct Heap
{HPDatetype* a;int catacity;int size;
}HP;void Swap(HPDatetype *a1, HPDatetype *a2)
{HPDatetype cur = *a1;*a1 = *a2;*a2 = cur;
}

Swap()函数是交换两个数的作用,是利用结构体形式创建的堆

🍌堆的初始化

void HeapInia(HP* ps)
{assert(ps);//防止堆为空ps->a = NULL;ps->size = ps->catacity = 0;
}

🍌堆的销毁

void HeapDestroy(HP* ps)
{assert(ps);//防止堆为空free(ps->a);ps->a = NULL;ps->size = 0;ps->catacity = 0;
}

🍌堆的插入

void AdjustUp(HPDatetype* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}void HeapPush(HP* ps, HPDatetype x)
{assert(ps);//防止堆为空if (ps->catacity == ps->size){if (ps->catacity == 0){ps->catacity = 2;}else{ps->catacity *= 2;}int newcatacity = ps->catacity;HPDatetype* cur = (HPDatetype*)realloc(ps->a, sizeof(HPDatetype) * newcatacity);if (cur == NULL){perror("realloc fail");exit(-1);}ps->a = cur;ps->catacity = newcatacity;}ps->a[ps->size] = x;(ps->size)++;AdjustUp(ps->a, ps->size - 1);
}

AdjustUp()函数是把子节点向上调整的作用,因为我们利用数组形式建立堆,只能分为大堆和小堆,所以需要重新设计一个函数来调整子节点的位置。在这里我们是创建小堆。关于怎么向上找父节点,是利用了数组的位置特性。数组是从0开始,大家就可以找规律,以父节点找子节点就是需要加1再除以2,以子节点找父节点就是减1除以2。

🍌 堆的删除

void AdjustLown(HPDatetype* a, int n, int parent)//向下调整
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] > a[child + 1]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPop(HP* ps)
{assert(ps);assert(ps->size > 0);Swap(&(ps->a[0]), &(ps->a[ps->size - 1]));(ps->size)--;AdjustLown(ps->a, ps->size, 0);//向下调整}

堆的删除,在这里我们是删除的堆顶数据。
首先我们是先把堆顶数据和堆尾数据交换,然后再删除堆顶数据,最后利用函数AdjustLown()进行向下调整就行。
如果是小堆,取出来的数据就是依次变大,相反是大堆,取出来的数据就是依次变小。
堆在这里还有一个应用,就是堆排序。小堆就是升序,大堆就是降序。

🍌取堆顶的数据

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

返回堆顶数据即可

🍌堆的数据个数

int HeapSize(HP* ps)
{return ps->size;
}

直接返回ps->size即可

🍌堆的判空

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

注意,这里判空用到bool需要头文件名#include<stdbool.h>

🍌堆的整体代码实现

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int HPDatetype;
typedef struct Heap
{HPDatetype* a;int catacity;int size;
}HP;void HeapInia(HP* ps)
{assert(ps);ps->a = NULL;ps->catacity = ps->size = 0;
}void HeapDestroy(HP* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = ps->catacity;
}void Swap(HPDatetype* a1, HPDatetype* a2)
{HPDatetype cur = *a1;*a1 = *a2;*a2 = cur;
}void AdjustUp(HPDatetype* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}void HeapPush(HP* ps, HPDatetype x)
{assert(ps);if (ps->size == ps->catacity){if (ps->catacity == 0)ps->catacity = 2;elseps->catacity *= 2;int newcatacity = ps->catacity;HPDatetype* cur = (HPDatetype*)realloc(ps->a, sizeof(HPDatetype) * newcatacity);if (cur == NULL){perror("realloc fail");exit(-1);}ps->a = cur;ps->catacity = newcatacity;}ps->a[ps->size] = x;(ps->size)++;AdjustUp(ps->a, ps->size - 1);}void AdjustLown(HPDatetype* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] > a[child + 1]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPop(HP* ps)
{assert(ps);assert(ps->size > 0);Swap(&(ps->a[0]), &(ps->a[ps->size - 1]));(ps->size)--;AdjustLown(ps->a, ps->size, 0);}HPDatetype HeapTop(HP* ps)
{assert(ps);assert(ps->size > 0);return ps->a[0];
}int HeapSize(HP* ps)
{return ps->size;
}bool HeapEmpty(HP* ps)
{assert(ps);return ps->size == 0;
}void HeapPrint(HP *ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}int main()
{int a[] = { 65,100,70,32,50,60 };int size = sizeof(a) / sizeof(a[0]);HP ps;HeapInia(&ps);for (int i = 0; i < size; i++){HeapPush(&ps, a[i]);}HeapPrint(&ps);int net = HeapSize(&ps);//堆排序while (!HeapEmpty(&ps)){printf("%d ", HeapTop(&ps));HeapPop(&ps);}printf("%d ", net);HeapDestroy(&ps);return 0;
}

上面我也不充了堆排序,大家有兴趣可以试试,由于我这里是建的小堆,所以排出来的序是升序。

有不足的地方欢迎大家指正,谢谢!!!

请添加图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/269607.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

解锁AI大模型秘籍:未来科技的前沿探索

在当今这个技术高速发展的时代&#xff0c;人工智能&#xff08;AI&#xff09;已经成为了我们生活中不可或缺的一部分。从简单的个人助手到复杂的数据分析和决策制定&#xff0c;AI的应用范围日益扩大&#xff0c;其目的是为了让我们的生活变得更加智能化。本文旨在探讨AI如何…

C++ 基础知识

一. 预备知识 1. C的编程方式 过程性语言 (结构化、自顶向下)、面向对象语言、泛型编程 (创建独立于类型的代码) 2. 创建源代码文件的技巧 扩展名&#xff1a;.cpp 二. 第一个程序 - HelloWorld main() 入口点 返回 int 标准库 iostream std: 标准库的缩写 Statement…

苹果电脑免费释放磁盘空间软件CleanMyMac X2024

CleanMyMac X通过以下方式帮助用户释放磁盘空间&#xff1a; 智能扫描和清理&#xff1a;CleanMyMac X拥有强大的智能扫描功能&#xff0c;可以深入系统底层&#xff0c;快速识别并清理各类无用文件和垃圾&#xff0c;如缓存、日志、临时文件等。这些文件通常会占用大量的磁盘…

C语言回顾学习

一、数据类型 1.常量 2.float浮点表示 3.字符型 4.char&#xff08;大小写&#xff09; #include <stdio.h> //根据数字输出字符--int值可以直接输出为char int main() {int value;while (1){scanf("%d",&value);if(value<65||value>122){printf(&…

STM32CubeIDE基础学习-新建STM32CubeIDE基础工程

STM32CubeIDE基础学习-新建STM32CubeIDE基础工程 前言 有开发过程序的朋友都清楚&#xff0c;后面开发是不需要再新建工程的&#xff0c;一般都是在初学时或者有特殊需要的时候才需要新建项目工程的。 后面开发都是可以在这种已有的工程上添加相关功能就行&#xff0c;只要前…

构造pop链

反序列化视频笔记 第一步&#xff1a;找到目标触发echo调用$flag 第二步&#xff1a;触发_invoke函数调用appeng函数$varflag.php&#xff08;把对象当成函数&#xff09; 第三步&#xff1a;给$p赋值为对象&#xff0c;即function成为对象Modifier却被当成函数调用&#xff…

Stable Diffusion 模型分享:CG texture light and shadow(CG纹理光影)

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八 下载地址 模型介绍 一个拥有cg质感和光影的融合模型&#xff0c;偏2.5D 条目内容类型大模型基础模型SD 1.5来…

java 正则表达式介绍

Java正则表达式是一种强大的文本处理工具&#xff0c;它允许你进行模式匹配、搜索和文本操作。正则表达式提供了一种简洁、灵活的方式来处理字符串&#xff0c;可以用于各种应用场景&#xff0c;如数据验证、文本解析、搜索和替换等。 正则表达式的基础知识 正则表达式…

[HackMyVM] 靶场 Wave

kali:192.168.56.104 主机发现 arp-scan -l # arp-scan -l Interface: eth0, type: EN10MB, MAC: 00:0c:29:d2:e0:49, IPv4: 192.168.56.104 Starting arp-scan 1.10.0 with 256 hosts (https://github.com/royhills/arp-scan) 192.168.56.1 0a:00:27:00:00:05 (Un…

2024最新软件测试面试题(带答案)

1. 请自我介绍一下(需简单清楚的表述自已的基本情况&#xff0c;在这过程中要展现出自信&#xff0c;对工作有激情&#xff0c;上进&#xff0c;好学) 面试官您好&#xff0c;我叫###&#xff0c;今年26岁&#xff0c;来自江西九江&#xff0c;就读专业是电子商务&#xff0c;毕…

平衡搜索二叉树—AVL树

一、定义&#xff1a; 为了避免搜索二叉树的高度增长过快&#xff0c;降低二叉树的性能&#xff0c;规定在插入和删除二叉树的结点的时候&#xff0c;任何结点左右子树的高度差绝对值不超过1&#xff0c;这样的二叉树被称为平衡二叉树&#xff08;balanced Binary Tree&#xf…

Java并发编程-进程和线程

一、进程和线程 1. 进程 什么是进程&#xff1f; 简单来说&#xff0c;进程就是程序的一次启动和执行。进程是操作系统中的一个概念&#xff0c;它代表正在运行的程序的实例。每个进程都有自己的内存空间、代码和数据&#xff0c;以及其他操作系统资源&#xff0c;如文件和设备…

Python:关于数据服务中的Web API的设计

搭建类似joinquant、tushare类似的私有数据服务应用&#xff0c;有以下一些点需要注意&#xff1a; 需要说明的是&#xff0c;这里讨论的是web api前后端&#xff0c;当然还有其它方案&#xff0c;thrift&#xff0c;grpc等。因为要考虑到一鱼两吃&#xff0c;本文只探讨web ap…

FreeRTOS学习笔记-基于stm32f103(1)基础知识

一、裸机与RTOS 我们使用的32板子是裸机&#xff0c;又称前后台系统。裸机有如下缺点&#xff1a; 1、实时性差。只能一步一步执行任务&#xff0c;比如在一个while循环中&#xff0c;要想执行上一个任务&#xff0c;就必须把下面的任务执行完&#xff0c;循环一遍后才能执行…

服务器后端是学习java还是php

没有绝对的"最好"语言&#xff0c;每种后端语言都有其适用的场景和特点。以下是几种常用的后端语言&#xff1a; 1. Java&#xff1a;Java是一种通用且强大的语言&#xff0c;广泛用于企业级应用和大型系统。它有很好的性能和可靠性&#xff0c;并且具有优秀的生态系…

C++面试干货---带你梳理常考的面试题(二)

顾得泉&#xff1a;个人主页 个人专栏&#xff1a;《Linux操作系统》 《C从入门到精通》 《LeedCode刷题》 键盘敲烂&#xff0c;年薪百万&#xff01; 1.struct 和 class 区别 1.默认访问权限&#xff1a;struct中的成员默认为public&#xff0c;而class中的成员默认为priv…

Python打发无聊时光:13.用pywin32库制作电脑本地快捷应用

第一步&#xff1a;新建一个simple_app.py 装pywin32库 pip install pywin32 新建一个simple_app.py&#xff0c;复制下面代码&#xff0c;或者可以自己设计内容 import tkinter as tkclass AnimatedGUI:def __init__(self, root):self.root rootself.root.title("玩…

初学arp欺骗

首先准备一台靶机这里用虚拟机的win10 已知网关与ip地址&#xff08;怕误伤&#xff09; 现在返回kali从头开始 首先探测自己的网关 然后扫内网存活的ip 发现有3台 用nmap扫一下是哪几台 成功发现我们虚拟机的ip 现在虚拟机可以正常访问网络 接下来直接开梭 ip网关 返回虚拟机…

day03_登录注销(前端接入登录,异常处理, 图片验证码,获取用户信息接口,退出功能)

文章目录 1. 前端接入登录1.1 修改前端代码1.2 跨域请求1.2.1 跨域请求简介1.2.2 COSR概述CORS简介CORS原理 1.2.3 CORS解决跨域 2. 异常处理2.1 提示空消息分析2.2 系统异常分类2.3 异常处理2.2.1 方案一2.2.2 方案二 3. 图片验证码3.1 图片验证码意义3.2 实现思路3.3 后端接口…

【学习心得】响应数据加密的原理与逆向思路

一、什么是响应数据加密&#xff1f; 响应数据加密是常见的反爬手段的一种&#xff0c;它是指服务器返回的不是明文数据&#xff0c;而是加密后的数据。这种密文数据可以被JS解密进而渲染在浏览器中让人们看到。 它的原理和过程图如下&#xff1a; 二、响应数据加密的逆向思路 …