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。

推薦閱讀: