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

浙大数据结构第五周之05-树7 堆中的路径

题目详情:

将一系列给定数字依次插入一个初始为空的小顶堆H[]。随后对任意给定的下标i,打印从H[i]到根结点的路径。

输入格式:

每组测试第1行包含2个正整数N和M(≤1000),分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。

输出格式:

对输入中给出的每个下标i,在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔,行末不得有多余空格。

输入样例:

5 3
46 23 26 24 10
5 4 3

输出样例:

24 23 10
46 23 10
26 10

主要思路:

就是实现课本上小顶堆

第一次写错误:

插入过程循环条件里是根节点比要插入元素大,才要上滤

代码实现:

#include <stdio.h>
#include <windows.h>
#define MAX_SIZE 1005
#define MIN_NUM -10005
typedef struct MinHeap MinHeap;
struct MinHeap {int Data[MAX_SIZE];int Size;
};
void Init(MinHeap* heapName, int nodeNum) {for(int i = 0; i <= nodeNum; i++) {(*heapName).Data[i] = MIN_NUM;}(*heapName).Size = 0;return;
}
void Insert(MinHeap* heapName, int data) {int i = ++(*heapName).Size;for(; (*heapName).Data[i / 2] > data; i /= 2) {    //Data[0]设置为哨兵(最小),保证最后一定能退出循环(*heapName).Data[i] = (*heapName).Data[i / 2];    //之所以能这么复制不用担心覆盖后找不到下标为i的结构,因为一开始的i指向位置是空,所以相当于一位一位向下移,空出位置用于插入}(*heapName).Data[i] = data;return;
}
void PrintPath(MinHeap* heapName, int index) {for(int i = index; i > 0; i /= 2) {if(i != 1) {printf("%d ", (*heapName).Data[i]);}else {printf("%d", (*heapName).Data[1]);}}return;
}
int main() {int N, M;scanf("%d %d", &N, &M);MinHeap heap;Init(&heap, N);for(int i = 0; i < N; i++) {int data;scanf("%d", &data);Insert(&heap, data);}for(int i = 0; i < M; i++) {int index;scanf("%d", &index);PrintPath(&heap, index);if(i != M - 1) {printf("\n");}}system("pause");return 0;
}

相关文章:

浙大数据结构第五周之05-树7 堆中的路径

题目详情&#xff1a; 将一系列给定数字依次插入一个初始为空的小顶堆H[]。随后对任意给定的下标i&#xff0c;打印从H[i]到根结点的路径。 输入格式: 每组测试第1行包含2个正整数N和M(≤1000)&#xff0c;分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-1…...

C# Modbus TCP上位机测试

前面说了三菱和西门子PLC的上位机通信&#xff0c;实际在生产应用中&#xff0c;设备会有很多不同的厂家生产的PLC&#xff0c;那么&#xff0c;我们就需要一种通用的语言&#xff0c;进行设备之间的通信&#xff0c;工业上较为广泛使用的语言之一就是Modbus。 Modbus有多种连…...

instr字符查找函数(oracle用instr来代替like)

instr函数&#xff1a;字符查找函数。其功能是查找一个字符串在另一个字符串中首次出现的位置。 instr函数在Oracle/PLSQL中是返回要截取的字符串在源字符串中的位置。 语法 instr( string1, string2, start_position,nth_appearance ) 参数 string1&#xff1a;源字符串&am…...

trie树的一点理解

这个是最简单的数据结构&#xff1a;因为只需要记住两句话就能完美的写出简洁优雅的代码 1. 每次都是从根节点开始看(或者说从第零次插入的东西开始遍历&#xff0c;son[][]里面存的是第几次插入) 2每次遍历都是插入和查询的字符串 #include<iostream> using namespace …...

Linux CentOS监控系统的运行情况工具 - top/htop/glances/sar/nmon

在CentOS系统中&#xff0c;您可以使用以下工具来监控系统的运行情况&#xff1a; 1. top&#xff1a; top 是一个命令行工具&#xff0c;用于实时监控系统的进程、CPU、内存和负载情况。您可以使用以下命令来启动 top&#xff1a; top 输出 2. htop&#xff1a; htop 是一…...

Qt开发(2)——windows下调用外部程序

一、QProcess::start &#xff11;&#xff0e;阻塞性 start是非阻塞函数&#xff0c;但是这里的waitForFinished是阻塞的 2. 调用外部压缩程序7z // 目标压缩路径 QString zipFilePath destinationFolder "/" zipFileName; QStringList arguments{"a&qu…...

PostgreSQL查看数据库对象大小

PostgreSQL查看数据库对象大小 PostgreSQL查看数据库对象大小1、查看某个数据库大小2、查看多个数据库大小3、按顺序查看索引大小4、查看所有对象的大小 PostgreSQL查看数据库对象大小 1、查看某个数据库大小 select pg_size_pretty(pg_database_size(tzqdb));2、查看多个数据…...

给el-table实现列显隐

用过若依的都知道&#xff0c;在使用el-table 时候&#xff0c;实现列显隐效果是要给每个列加v-if 判断的&#xff0c;这种代码过于繁琐&#xff0c;于是翻看el-table包的代码&#xff0c;调试后发现内部的【插入】和【删除】两个方法可以达到我们要的效果。 项目不提供源码&a…...

为Android构建现代应用——应用架构

选择风格(Choosing a style) 我们将依照Google在《应用架构指南》中推荐的最佳实践和架构指南来构建OrderNow的架构。 这些定义包括通过各层定义组件的一些Clean Architecture原则。 层次的定义(Definition of the layers) 在应用程序中&#xff0c;我们将定义以下主要层次…...

49:字符串的新增方法

字符串的新增方法 String.fromCodePoint()String.raw()实例方法&#xff1a;codePointAt()实例方法&#xff1a;normalize()[实例方法&#xff1a;includes(), startsWith(), endsWith()](https://es6.ruanyifeng.com/#docs/string-methods#实例方法&#xff1a;includes(), s…...

Kaggle图表内容识别大赛TOP方案汇总

赛题名称&#xff1a;Benetech - Making Graphs Accessible 赛题链接&#xff1a;https://www.kaggle.com/competitions/benetech-making-graphs-accessible 赛题背景 数以百万计的学生有学习、身体或视力障碍&#xff0c;导致人们无法阅读传统印刷品。这些学生无法访问科学…...

DAY2,Qt(继续完善登录框,信号与槽的使用 )

1.继续完善登录框&#xff0c;当登录成功时&#xff0c;关闭登录界面&#xff0c;跳转到新的界面中&#xff0c;来回切换页面&#xff1b; ---mychat.h chatroom.h---两个页面头文件 #ifndef MYCHAT_H #define MYCHAT_H#include <QWidget> #include <QDebug> /…...

【设计模式】设计原则-开闭原则

单一职责原则 定义 当应用的需求改变时&#xff0c;在不修改软件实体的源代码或者二进制代码的前提下&#xff0c;可以扩展模块的功能&#xff0c;使其满足新的需求。作用 1、方便测试&#xff1b;测试时只需要对扩展的代码进行测试。 2、提高代码的可复用性&#xff1b;粒…...

【2500. 删除每行中的最大值】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个 m x n 大小的矩阵 grid &#xff0c;由若干正整数组成。 执行下述操作&#xff0c;直到 grid 变为空矩阵&#xff1a; 从每一行删除值最大的元素。如果存在多个这样的值&#xff0c;删除其…...

Superset部署

Superset部署 1、安装依赖 (superset) [hadoopnode1 ~]$ yum install -y python-setuptools (superset) [hadoopnode1 ~]$ yum install -y gcc gcc-c libffi-devel python-devel python-pip python-wheel openssl-devel2、安装Superset 2.1 安装&#xff08;更新&#xff09;…...

Python3 学习笔记 ~ 怎样打印字符串

Python中变量的打印方法_python打印变量_清欢依旧的博客-CSDN博客 a 9 b 2print(f"{a} / {b} {a/b}") print(a, "//", b, "", (a//b))a -9 print(f"{a} / {b} {a/b}") print(a, "//", b, "", (a//b))...

postgresql安装

安装postgresql Linux下载安装地址 https://www.postgresql.org/download/linux/redhat/ 指定对应版本&#xff0c;指定完成后会生成对应的安装语句 下载对应的包 yum –y install https://download.postgresql.org/pub/repos/yum/reporpms/EL-7-x86_64/pgdg-redhat-repo-l…...

ElasticSearch之IK分词器安装以及使用介绍

文章目录 一、IK 分词器简介1. 支持细粒度分词&#xff1a;2. 支持多种分词模式&#xff1a;3. 支持自定义词典&#xff1a;4. 支持拼音分词&#xff1a;5. 易于集成和使用&#xff1a; 二、安装步骤1、下载 IK 分词器插件&#xff1a;2、安装 IK 分词器插件&#xff1a;3. 安装…...

Linux系统安装部署Jenkins详细教程(图文讲解)

前言&#xff1a;最近需要使用Jenkins部署项目&#xff0c;所以想出一篇关于如何使用Linux系统安装部署Jenkins的相关教程&#xff0c;整体部署过程还是挺顺利的&#xff0c;特此分享一下&#xff01; 目录 一、安装JDK11和Tomcat11 二、准备Jenkins安装包 三、部署Jenkins…...

基于ChatGPT聊天的零样本信息提取7.25

基于ChatGPT聊天的零样本信息提取 摘要介绍ChatIE用于零样本IE的多轮 QA 实验总结 摘要 零样本信息提取&#xff08;IE&#xff09;旨在从未注释的文本中构建IE系统。由于很少涉及人类干预&#xff0c;因此具有挑战性。 零样本IE减少了数据标记所需的时间和工作量。最近对大型…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...