当前位置: 首页 > news >正文

二叉树顺序结构堆实现

目录

Test.c测试代码

test1

test2

test3

🎇Test.c总代码 

Heap.h头文件&函数声明

头文件

函数声明

🎇Heap.h总代码

Heap.c函数实现 

☁HeapInit初始化

☁HeapDestroy销毁

☁HeapPush插入数据

【1】插入数据

【2】向上调整Adjustup❗

数据交换Swap

☁HeapPop删除数据

【1】交换数据

【2】删除数据

【3】向下调整Adjustdown❗

假设法找Child 

数据交换Swap

☁HeapTop堆顶元素

☁HeapSize堆元素个数

☁HeapEmpty判断为空否

🎇Heap.c总代码 


拖了很久的【堆】,本周主要学习就是【数据结构】。本章【堆】是以【小堆】为例子。

  •  堆表面是数组,内核是完全二叉树/满二叉树
  • ❗HeapPush
  • ❗HeapPop
  • 函数如果需要多次复用才会提取出来
  • free会对NULL进行检查 
  • 用循环写起来很方便的代码就不要使用递归
  • do while循环用于无论循环条件如何,循环都会执行一次
  • 步骤--注意事项--循环结束条件--时间复杂度(下篇重点讲)

Test.c测试代码

#include"Heap.h"
int main()
{HP php;//HP*ph=&php//test1(&php);test2(&php);test3(&php);return 0;
}

test1

//建堆
void test1(HP* ph)
{int a[] = { 4,5,3,7,8,2,1,9,10 };HeapInit(ph);int i = 0;for (i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(ph, a[i]);}
}

test2

//找出堆的前K个数字
void test2(HP* ph)
{int a[] = { 4,5,3,7,8,2,1,9,10 };HeapInit(ph);int i = 0;int k = 5;for (i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(ph, a[i]);}while (k--){printf("%d ", HeapTop(ph));HeapPop(ph);}printf("\n");
}

 

test3

//排序--升序
void test3(HP* ph)
{int a[] = { 4,5,3,7,8,2,1,9,10 };HeapInit(ph);int i = 0;for (i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(ph, a[i]);}while (HeapEmpty(ph))//为NULLflase{printf("%d ", HeapTop(ph));HeapPop(ph);}
}

🎇Test.c总代码 

#include"Heap.h"
//建堆
void test1(HP* ph)
{int a[] = { 4,5,3,7,8,2,1,9,10 };HeapInit(ph);int i = 0;for (i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(ph, a[i]);}
}//找出堆的前K个数字
void test2(HP* ph)
{int a[] = { 4,5,3,7,8,2,1,9,10 };HeapInit(ph);int i = 0;int k = 5;for (i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(ph, a[i]);}while (k--){printf("%d ", HeapTop(ph));HeapPop(ph);}printf("\n");
}void test3(HP* ph)
{int a[] = { 4,5,3,7,8,2,1,9,10 };HeapInit(ph);int i = 0;for (i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(ph, a[i]);}while (HeapEmpty(ph))//为NULLflase{printf("%d ", HeapTop(ph));HeapPop(ph);}
}int main()
{HP php;//HP*ph=&php//test1(&php);test2(&php);test3(&php);return 0;
}

Heap.h头文件&函数声明

头文件

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HpDataType;//定义堆结构体
typedef struct Heap
{HpDataType* a;int size;int capacity;
}HP;

函数声明

//常用接口
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php,HpDataType x);
void HeapPop(HP* php);
HpDataType HeapTop(HP* php);
int HeapSize(HP* php);
bool HeapEmpty(HP* php);

🎇Heap.h总代码

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int HpDataType;//定义堆结构体
typedef struct Heap
{HpDataType* a;int size;int capacity;
}HP;//常用接口
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php,HpDataType x);
void HeapPop(HP* php);
HpDataType HeapTop(HP* php);
int HeapSize(HP* php);
bool HeapEmpty(HP* php);

Heap.c函数实现 

☁HeapInit初始化

#include"Heap.h"
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}

☁HeapDestroy销毁

void HeapDestroy(HP* php)
{assert(php);free(php->a);//不用担心为NULL,free会对NULL做检查php->size = php->capacity = 0;
}

☁HeapPush插入数据

 先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。

【1】插入数据

void HeapPush(HP* php, HpDataType x)
{assert(php);//扩容if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HpDataType* tmp = (HpDataType*)realloc(php->a, newcapacity * sizeof(HpDataType));if (tmp == NULL){printf("fail realloc");return;}php->capacity = newcapacity;php->a = tmp;}//插入数据php->a[php->size] = x;php->size++;//向上调整//数组,调整元素下标AdjustUp(php->a, php->size - 1);
}

【2】向上调整Adjustup❗

//向上调整算法
void AdjustUp(HpDataType* a, int child)
{int parent = (child - 1) / 2;while ( child > 0 )//此刻parent已经数组越界{if (a[child] < a[parent]){//交换Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else//child>=parent{break;}}
}
数据交换Swap
//交换
void Swap(HpDataType* H1, HpDataType* H2)
{HpDataType tmp = *H1;*H1 = *H2;*H2 = tmp;
}

☁HeapPop删除数据

删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法。

//删除
void HeapPop(HP* php)
{assert(php);assert(php->size);//1.交换Swap(&php->a[0], &php->a[php->size - 1]);//2.删除php->size--;//3.向下调整--数组,结束条件size有关,调整的位置parentAdjustdown(php->a, php->size, 0);
}

【1】交换数据

	//1.交换Swap(&php->a[0], &php->a[php->size - 1]);

【2】删除数据

	//2.删除php->size--;

【3】向下调整Adjustdown❗

//3.向下调整--数组,结束条件size有关,调整的位置parent
Adjustdown(php->a, php->size, 0);
//向下调整
void Adjustdown(HpDataType* a, int size, int parent)
{//假设法int child = parent * 2 + 1;while (child < size )//why child < size && child+1<size{if (child + 1 < size && a[child + 1] < a[child]){child++;}//比较if (a[child] < a[parent]){//交换Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else//>={break;}}
}
假设法找Child 
	int child = parent * 2 + 1;if (a[child + 1] < a[child]){child++;}
数据交换Swap
//交换
void Swap(HpDataType* H1, HpDataType* H2)
{HpDataType tmp = *H1;*H1 = *H2;*H2 = tmp;
}

☁HeapTop堆顶元素

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

☁HeapSize堆元素个数

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

☁HeapEmpty判断为空否

bool HeapEmpty(HP* php)
{assert(php);return php->size != 0;//!=0是true不为NULL执行   ==0 flase 不执行
}

🎇Heap.c总代码 

#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);//不用担心为NULL,free会对NULL做检查php->size = php->capacity = 0;
}
//交换
void Swap(HpDataType* H1, HpDataType* H2)
{HpDataType tmp = *H1;*H1 = *H2;*H2 = tmp;
}//向上调整算法
void AdjustUp(HpDataType* a, int child)
{int parent = (child - 1) / 2;while ( child > 0 )//此刻parent已经数组越界{if (a[child] < a[parent]){//交换Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else//child>=parent{break;}}
}void HeapPush(HP* php, HpDataType x)
{assert(php);//扩容if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HpDataType* tmp = (HpDataType*)realloc(php->a, newcapacity * sizeof(HpDataType));if (tmp == NULL){printf("fail realloc");return;}php->capacity = newcapacity;php->a = tmp;}//插入数据php->a[php->size] = x;php->size++;//向上调整//数组,调整元素下标AdjustUp(php->a, php->size - 1);
}//向下调整
void Adjustdown(HpDataType* a, int size, int parent)
{//假设法int child = parent * 2 + 1;while (child < size )//why child < size && child+1<size{if (child + 1 < size && a[child + 1] < a[child]){child++;}//比较if (a[child] < a[parent]){//交换Swap(&a[child], &a[parent]);parent = child;child = child * 2 + 1;}else//>={break;}}
}
//删除
void HeapPop(HP* php)
{assert(php);assert(php->size);//1.交换Swap(&php->a[0], &php->a[php->size - 1]);//2.删除php->size--;//3.向下调整--数组,结束条件size有关,调整的位置parentAdjustdown(php->a, php->size, 0);
}HpDataType HeapTop(HP* php)
{assert(php);assert(php->size);return php->a[0];
}int HeapSize(HP* php)
{assert(php);return php->size;
}bool HeapEmpty(HP* php)
{assert(php);return php->size != 0;//!=0是true不为NULL执行   ==0 flase 不执行
}

当然,【大堆】只要改变大小符号即可,如果你不想要改变,可以使用【回调函数】!! 

🙂感谢大家的阅读,若有错误和不足,欢迎指正!希望本周可以结束【初阶数据结构】

相关文章:

二叉树顺序结构堆实现

目录 Test.c测试代码 test1 test2 test3 &#x1f387;Test.c总代码 Heap.h头文件&函数声明 头文件 函数声明 &#x1f387;Heap.h总代码 Heap.c函数实现 ☁HeapInit初始化 ☁HeapDestroy销毁 ☁HeapPush插入数据 【1】插入数据 【2】向上调整Adjustup❗ …...

正则表达式 与文本三剑客(sed grep awk)

一&#xff0c;正则表达式 &#xff08;一&#xff09;正则表达式相关定义 1&#xff0c;正则表达式含义 REGEXP&#xff1a; Regular Expressions&#xff0c;由一类特殊字符及文本字符所编写的模式&#xff0c;其中有些字符&#xff08;元字符&#xff09;不表示字符字面意…...

【XR806开发板试用】全志 XR806 OpenHarmony 鸿蒙系统固件烧录

大家好&#xff0c;我是极智视界&#xff0c;本教程详细记录了全志 XR806 OpenHarmony 鸿蒙系统固件烧录的方法。 在上一篇文章《【嵌入式AI】全志 XR806 OpenHarmony 鸿蒙系统固件编译》中咱们已经编译生成了系统镜像&#xff0c;这里把这个编译出来的镜像烧录到 XR806 板子里…...

linux环境安装git、maven、jenkins等

重启 jenkins的命令&#xff1a; systemctl start jenkins 如果没有vim 命令 可以使用 yum install vim 安装 vim git 下载包地址 https://www.kernel.org/pub/software/scm/git/git-2.28.0.tar.gz 1.安装依赖环境&#xff1a; yum install -y curl-devel expat-devel ge…...

RabbitMQ快速上手

首先他的需求实在什么地方。我美哟明显的感受到。 它给我的最大感受就是脱裤子放屁——多此一举&#xff0c;的感觉。 他将信息发送给服务端中间件。在由MQ服务器发送消息。 服务器会监听消息。 但是它不仅仅局限于削峰填谷和稳定发送信息的功能&#xff0c;它还有其他重要…...

SpringBoot activemq收发消息、配置及原理

SpringBoot集成消息处理框架 Spring framework提供了对JMS和AMQP消息框架的无缝集成&#xff0c;为Spring项目使用消息处理框架提供了极大的便利。 与Spring framework相比&#xff0c;Spring Boot更近了一步&#xff0c;通过auto-configuration机制实现了对jms及amqp主流框架…...

视频智能识别安全帽佩戴系统-工地安全帽佩戴识别算法---豌豆云

视频智能识别安全帽佩戴系统能够从繁杂的工地、煤矿、车间等场景下同时对多个目标是否戴安全帽穿反光衣进行实时识别。 当视频智能识别安全帽佩戴系统发现作业人员没有戴安全帽、穿反光衣或者戴安全带&#xff0c;系统会及时报警提醒&#xff0c;并抓拍存档。 视频智能识别安…...

指针的深入理解(三)

这一节主要使用复习回调函数&#xff0c; 利用冒泡模拟实现qsort函数。 qsort 排序使用冒泡排序&#xff0c;主要难点在于运用元素个数和字节数以及基地址控制元素的比较&#xff1a; if里面使用了一个判断函数&#xff0c;qsort可以排序任意的数据&#xff0c;原因就是因为可…...

【Linux C | 网络编程】详细介绍 “三次握手(建立连接)、四次挥手(终止连接)、TCP状态”

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…...

主从数据库MySQL服务重启步骤与注意事项

主从数据库MySQL服务重启步骤与注意事项 实验环境&#xff1a; 172.20.26.34 &#xff08;主应用服务器&#xff09; 172.20.26.26 &#xff08;备应用服务器&#xff09; 172.20.26.37 &#xff08;主库服务器&#xff09; 172.20.26.38 &#xff08;从库服务器&…...

netlink学习

netlink是什么 netlink是Linux内核中的一种进程间通信&#xff08;IPC&#xff09;机制。它允许内核空间与用户空间之间&#xff0c;以及用户空间进程之间进行双向通信。 内核里的很多子系统使用netlink通信&#xff0c;包括网络管理&#xff08;Routing&#xff0c;Netfilt…...

地理空间分析10——空间数据分析中的地理编码与Python

目录 写在开头1. 地理编码基础1.1 地理编码的基本原理1.1.1 坐标系统1.1.2 地名解析1.1.3 编码算法1.2 Python中使用地理编码的基础知识1.2.1 百度地图API1.2.2 高德地图API1.2.3 腾讯地图API1.3 Python中实现代码2. 逆地理编码2.1 利用Python进行逆地理编码2.1.1 获取高德地图…...

使用“快速开始”将数据传输到新的 iPhone 或 iPad

使用“快速开始”将数据传输到新的 iPhone 或 iPad 使用 iPhone 或 iPad 自动设置你的新 iOS 设备。 使用“快速开始”的过程会同时占用两台设备&#xff0c;因此请务必选择在几分钟内都不需要使用当前设备的时候进行设置。 确保你当前的设备已连接到无线局域网&#xff0c;并…...

计算机网络(第六版)复习提纲13

前同步码&#xff0c;七位1010交替出现&#xff0c;帧开始码&#xff1a;10101011 为什么没有帧结束&#xff1f;曼彻斯特码传播完成后&#xff0c;维持高电平&#xff0c;不再跳变&#xff0c;因此不必要设置帧结束。 3.无效的MAC帧 i.数据字段的长度与长度字段的值不一致&…...

[office] excel2010双向条形图制作 #经验分享#微信

excel2010双向条形图制作 本教程为大家介绍一下excel2010中excel2010双向条形图制作方法。 1.选中工作区域 2.点击插入-->图表,选择条形图 3.为美观可将中间竖线可去掉 4.方法是选中竖线,右击-->删除 5.接下来将图例靠上,选中图例,右击-->设置图例格式-->图例选项…...

优雅管理多线程异步任务 - 永动异步任务

引言 在现代应用程序中,经常需要处理长时间运行的异步任务,如消息推送、定时任务等。为了确保这些异步任务能够安全可靠地执行,我们需要一种优雅的管理方式。本文将介绍一种基于线程池的多线程异步任务管理方案,并详细讨论任务的优雅关闭。 1. 多线程异步任务管理的需求 …...

软考笔记--分布式数据库

分布式数据库系统是数据库技术与网络技术相结合的产物&#xff0c;其基本思想是将传统的集中式数据库中的数据分布于网络上的多台计算机中。分布式数据库系统通常使用较小的计算机系统&#xff0c;每台计算机可单独放在一个地方&#xff0c;每台计算机中都有DBMS的一份完整的复…...

vue项目中路由懒加载的三种方式

1 . vue异步组件技术 异步加载 vue-router配置路由 , 使用vue的异步组件技术 , 可以实现按需加载 . 但是,这种情况下一个组件生成一个js文件 /* vue异步组件技术 */ { path: /home, name: home, component: resolve > require([/components/home],resolve) }, { path…...

【制作100个unity游戏之23】实现类似七日杀、森林一样的生存游戏6(附项目源码)

本节最终效果演示 文章目录 本节最终效果演示系列目录前言生命 食物 水简单绘制UI玩家状态脚本生命值控制饱食度控制水分控制 源码完结 系列目录 前言 欢迎来到【制作100个Unity游戏】系列&#xff01;本系列将引导您一步步学习如何使用Unity开发各种类型的游戏。在这第23篇中…...

Cache Lab:Part A【模拟出使用LRU策略的高速缓存存储器组织结构】

目录 任务描述 知识回顾 实验内容 测试结果 Cache Lab 对应《CS:APP》6.3节至第六章结束的内容。 任务描述 Your job for Part A is to fill in the csim.c file so that it takes the same command line arguments and produces the identical output as the reference …...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...