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右邊最大值下標為:%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; }
運行結果:
以上就是本文的全部內容,希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。