本文实例为大家分享了C语言实现出栈序列的具体代码,供大家参考,具体内容如下
题目描述:
现在有一个1-n的排列,入栈序列已知,请给出字典序最大的出栈序列。
输入格式
第一行一个整数n。(1<=n<=100)
第二行n个整数,数据确保为1-n的排列。
输出格式
输出n个整数,既字典序最大的出栈序列。
输入样例
5
1 2 4 5 3
输出样例
5 4 3 2 1
解题思路:
1、获取当前数组的最大值,并且需要知道它的下标。所以定义了两个方法,getMax来获取数组的最大值maxNum,getMaxIndex获取最大值的下标max_index。
2、将最大值以及它前面的数字都压入到栈中去
3、这时候将最大值从栈中跳出来。(可要可不要,不要的话可以减少代码的冗余)
4、调用方法getMax,getMaxIndex来获取maxNum后面子数组的最大值r_max,以及下标。
5、将后面数组的最大值r_max和当前栈顶元素进行比较,如果栈顶元素大于等于r_max,那么将栈顶元素tmp从栈中跳出,同时将这个栈顶元素tmp输出。否则,如果r_max大于当前的栈顶元素,那么就将r_max之前的数字压入到栈中,同时需要获取r_max后面数组中的最大值以及下标。
注意这一步,必须是要将后面子数组的最大值r_max和栈顶元素进行比较。而不是拿后面子数组的最大值r_max和maxNum前面数字的最大值进行比较,这样的话,得到的就不是正确的出栈序列了。
6、重复上面的操作,直到将输入的数组已经遍历完了,程序结束。
对应的代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
#include<stdio.h>
#define ERROR 0
#define OK 1
#define MAX_SIZE 100
#define N 100
typedef struct NODE{
int arr[MAX_SIZE];
int top;
}Node;
void init(Node &s){
s.top = 0;
}
//压栈
int pushElem(Node &s, int c){
if (s.top == MAX_SIZE){
return ERROR; //如果栈满了,那么返回ERROR
}
s.arr[s.top++] = c;
return OK;
}
//跳出栈顶元素
int popElem(Node &s, int &c){
if (s.top == 0){
/*
如果栈为空,那么返回ERROR
这里之所以是s.top == 0就为空,是因为下面进行删除操作
的时候s.top是先减减的,所以在s.top = 1的时候,先进行减1操作,所以
这时候s.top已经为0,表明我们已经删除了最后一个元素,再来进行这个操作的时候
s.top为0,所以才用它来判断栈是否为空
*/
return ERROR;
}
c = s.arr[--s.top]; //将删除的元素赋值给c
return OK;
}
//获取栈顶元素
int getTop(Node &s, int &c){
if (s.top == 0){
/*
如果栈为空,那么返回ERROR
这里之所以是s.top == 0就为空,是因为下面进行删除操作
的时候s.top是先减减的,所以在s.top = 1的时候,先进行减1操作,所以
这时候s.top已经为0,表明我们已经删除了最后一个元素,再来进行这个操作的时候
s.top为0,所以才用它来判断栈是否为空
*/
return ERROR;
}
c = s.arr[s.top - 1]; //将栈顶元素赋值给c
return OK;
}
int isEmpty(Node &s){
return s.top == 0;
}
/*
将maxNum及其之前的数字压入栈中,同时返回maxNum的下标
*/
int getMax_index( int *arr,Node &s, int left, int right, int maxNum){
int i;
for (i = left; i < right; i++){
pushElem(s,arr[i]); //将当前的数字压入栈中
if (arr[i] == maxNum){
//如果栈顶元素是最大值,那么就将退出循环遍历
break ;
}
}
return i;
}
/*
获取left - right区间的最大值
*/
int arrayMax( int *arr, int left, int right){
int i,maxNum = 0;
for (i = left; i < right; i++){
if (maxNum == 0 || arr[i] > maxNum)
maxNum = arr[i];
}
return maxNum;
}
//获取最大的出栈序列
void getMax( int *arr,Node &s, int left, int right, int maxNum){
if (left >= right){
//如果区间的范围不正确的时候,那么结束递归
return ;
}
//tmp表示栈顶元素,r_max表示maxNum后面子数组的最大值,i表示maxNum的下标
int i,tmp,r_max;
/*
将maxNum及它前面的数字压入栈中,同时将maxNum的下标返回
*/
i = getMax_index(arr,s,left,right,maxNum);
r_max = arrayMax(arr,i + 1,right); //获取maxNum后面子数组的最大值
/*
这段代码也可以不写,因为下面会拿栈顶元素和r_max进行比较,所以
maxNum是最大值,必然会先输出manNum的
popElem(s,tmp);//将最大值maxNum赋值给tmp,并从栈中跳出
printf("%d ",tmp);
*/
while (!isEmpty(s)){
getTop(s,tmp); //获取栈顶元素
if (r_max > tmp){
//判断r_max是否大于栈顶元素,如果是,将它及其之前的数字压入栈中,同时获取r_max的下标
i = getMax_index(arr,s,i + 1,right,r_max);
r_max = arrayMax(arr,i + 1,right); //获取 i + 1 到right区间的最大值
// printf("\n右边最大值下标为:%d\n",i);
} else {
//如果r_max小于等于栈顶元素,那么就将栈顶元素从栈中跳出,并将其输出
popElem(s,tmp);
printf ( "%d " ,tmp);
}
}
getMax(arr,s,i + 1,right,r_max);
}
int main(){
int arr[N];
int n,i,maxNum;
Node s;
init(s); //初始栈
printf ( "请输入栈的元素个数:" );
scanf ( "%d" ,&n); //输入栈元素个数
for (i = 0; i < n; i++)
scanf ( "%d" ,&arr[i]);
maxNum = arrayMax(arr,0,n); //获取left-right区间的最大值
getMax(arr,s,0,n,maxNum);
return 0;
}
|
运行结果:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/weixin_46544385/article/details/115439128