數(shù)據(jù)結(jié)構(gòu)實驗之棧與隊列六：下一較大值（二）

Time Limit:?150MS?Memory Limit:?8000KB Submit?Statistic?Discuss

Problem Description

對于包含n（1<=n<=100000）個整數(shù)的序列，對于序列中的每一元素，在序列中查找其位置之后第一個大于它的值，如果找到，輸出所找到的值，否則，輸出-1。

Input

?輸入有多組，第一行輸入t（1<=t<=10），表示輸入的組數(shù)；

以后是 t 組輸入：每組先輸入n，表示本組序列的元素個數(shù)，之后依次輸入本組的n個元素。

Output

?輸出有多組，每組之間輸出一個空行（最后一組之后沒有）；

每組輸出按照本序列元素的順序，依次逐行輸出當前元素及其查找結(jié)果，兩者之間以-->間隔。

Example Input

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

Example Output

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

Hint

?本題數(shù)據(jù)量大、限時要求高，須借助棧來完成。

解題策略和上一道題一樣，在這兒那位小哥哥只是借用建立鏈形隊列時用到的數(shù)據(jù)結(jié)構(gòu)。

http://blog.csdn.net/horizonhui/article/details/78113255

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXSIZE 100000 typedef int status; typedef struct node {int data;int next;int pos; }elemtype; typedef struct {elemtype *base;elemtype *top; } Sqstack; struct node p[100005]; status isEmpty(Sqstack &S) {if(S.top == S.base)return true;elsereturn false; } void initStack(Sqstack &S) {S.base = new elemtype[MAXSIZE];S.top = S.base; } elemtype getTop(Sqstack &S) {return *(S.top-1); } void Push(Sqstack &S, elemtype e) {*S.top++ = e; } elemtype Pop(Sqstack &S, elemtype &e) {return e = * --S.top; } void clear(Sqstack &S) {S.base = S.top; } int main() {int t, n;scanf("%d", &t);while(t--){Sqstack S;initStack(S);scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", &p[i].data);p[i].pos = i;p[i].next = -1;if(isEmpty(S))Push(S, p[i]);else{while(!isEmpty(S)){struct node a = getTop(S);if(a.data < p[i].data){p[a.pos].next = p[i].data;Pop(S, a);}elsebreak;}}Push(S, p[i]);}for(int i=0;i<n;i++){printf("%d-->%d\n", p[i].data, p[i].next);}if(t>=0)printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的sdut 3333 数据结构实验之栈与队列六：下一较大值（二）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。