SDUT 数据结构实验之栈六:下一较大值(二)

2024-02-18 03:18

本文主要是介绍SDUT 数据结构实验之栈六:下一较大值(二),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

对于包含n(1<=n<=100000)个整数的序列,对于序列中的每一元素,在序列中查找其位置之后第一个大于它的值,如果找到,输出所找到的值,否则,输出-1。

输入

输入有多组,第一行输入t(1<=t<=10),表示输入的组数;

以后是 t 组输入:每组先输入n,表示本组序列的元素个数,之后依次输入本组的n个元素。

输出

输出有多组,每组之间输出一个空行(最后一组之后没有);

每组输出按照本序列元素的顺序,依次逐行输出当前元素及其查找结果,两者之间以-->间隔。

示例输入

2
4 12 20 15 18
5 20 15 25 30 6 

示例输出

12-->20
20-->-1
15-->18
18-->-1
 
20-->25
15-->25
25-->30
30-->-1
6-->-1

提示

本题数据量大、限时要求高,须借助栈来完成。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define N 100100
using namespace std;struct node//运用结构体来记录数据
{int num,id,next;
};
struct node a[N];
int main()
{int t;scanf("%d",&t);stack <struct node > p;//定义结构体的栈for(int i=1; i<=t; i++){while(!p.empty())//对栈进行清空{p.pop();}int n;if(i>1)//用来输出空格printf("\n");scanf("%d",&n);for(int j=1; j<=n; j++){scanf("%d",&a[j].num);a[j].id=j;a[j].next=-1;if(p.empty()){p.push(a[j]);}else//如果栈不为空{while(!p.empty()){struct node b;b=p.top();//拿出栈顶的元素if(b.num<a[j].num)//与栈顶元素比较,如果比栈顶元素大,记录进入next.{a[b.id].next=a[j].num;p.pop();}elsebreak;}p.push(a[j]);}}for(int j=1; j<=n; j++){printf("%d-->%d\n",a[j].num,a[j].next);}}return 0;
}


 

 

这篇关于SDUT 数据结构实验之栈六:下一较大值(二)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/719877

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

STM32(十一):ADC数模转换器实验

AD单通道: 1.RCC开启GPIO和ADC时钟。配置ADCCLK分频器。 2.配置GPIO,把GPIO配置成模拟输入的模式。 3.配置多路开关,把左面通道接入到右面规则组列表里。 4.配置ADC转换器, 包括AD转换器和AD数据寄存器。单次转换,连续转换;扫描、非扫描;有几个通道,触发源是什么,数据对齐是左对齐还是右对齐。 5.ADC_CMD 开启ADC。 void RCC_AD

HNU-2023电路与电子学-实验3

写在前面: 一、实验目的 1.了解简易模型机的内部结构和工作原理。 2.分析模型机的功能,设计 8 重 3-1 多路复用器。 3.分析模型机的功能,设计 8 重 2-1 多路复用器。 4.分析模型机的工作原理,设计模型机控制信号产生逻辑。 二、实验内容 1.用 VERILOG 语言设计模型机的 8 重 3-1 多路复用器; 2.用 VERILOG 语言设计模型机的 8 重 2-1 多

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据,每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明: 1. 列表 (List) 列表是一种可变的有序集合,可以存放任意类型的数据。列表中的元素可以通过索

浙大数据结构:04-树7 二叉搜索树的操作集

这道题答案都在PPT上,所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现,小就进左子树,大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客,我们学习了排序算法中的插入排序和选择排序,接下来我们将继续探索交换排序与归并排序,这两个排序都是重头戏,让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换,让较大的元素逐渐向右移动,从而将最大的元素移动到最右边。 动画演示: 1.1.2 具体步