c/c++开发分享C语言实现出栈序列实例为大家分享了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、重复上面的操作,直到将输入的数组已经遍历完了,程序结束。
对应的代码:
#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右边最大值下标为:%dn",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; }
运行结果:
以上就是c/c++开发分享C语言实现出栈序列的全部内容,希望对大家的学习有所帮助,也希望大家多多支持<计算机技术网(www.ctvol.com)!!>。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/595588.html