C言語はスタックシーケンスの合法性判定を実現する。

3729 ワード

本論文の例では、C言語によるスタックの合法性判定を実現するための具体的なコードを共有しています。
2つの整数系列を入力し、1番目のシーケンスはスタックの圧入順序を表します。2番目のシーケンスがスタックのポップアップ順序である可能性があるかどうかを判断してください。
スタックに押し込む数字はすべて等しくないと仮定する。例えば、シーケンス1,2,3,4,5は、あるスタックの圧入順序であり、シーケンス4,5,3,2,1は、このスタックシーケンスに対応する1つのポップアップシーケンスであるが、4,3,5,1,2は、このスタックシーケンスのポップアップシーケンスであることが不可能である（ステップS）。この2つのシーケンスの長さは同じです。
入力フォーマット
1行目の整数nは、入力シーケンスの長さを表します。1<=n<=10000)
第二行n個の整数は、スタックの圧入順序を表す。
第三行n個の整数は、スタックの出庫順序を表す。
出力フォーマット
ポップアップシーケンスなら、yesを出力します。そうでなければ、Noを出力します。
入力サンプル
5
1 2 3 8
8 6 3 2 1
出力サンプル
yes
準備：
①スタックを定義し、その基本的な操作を実現する（スタックpopStock（）/スタックpusshStock（）/スタックトップ要素get Top（）/スタックが空のisEmptyであるかどうかを判断する（など）
②2つの長さが10000の整形配列を定義するのは、押し込む順番の数字msgと、スタックの順序の数字targetをそれぞれ表します。ここでは、2つのforループを書くことを避けるために、メソッドinputを呼び出すことにより、msg/targetを入力するたびに、この方法を呼び出すだけでコード量を減らすことができます。
問題の考え方：（主に循環ネストを通して）
1、msgを遍歴して得られた数字をスタックに押し込む。
2、数字を押した後に、スタックトップ要素chを取得し、chが現在のタブダウンに対応する数字と同じかどうかを判断します。同じなら、スタックから一つの要素を飛び出し、同時にtargetの下付き後に移動します。この時、私達は依然としてスタックの一番上の要素を獲得したいです。このスタックの一番上の要素は現在のtargetの下の数字と比較します。もし等しいなら、上記の操作を続けます。
ここでなぜこのようにする必要があるのかというと、一つの要素を押し込んだ後に、一つの要素が飛び出す可能性を考慮して、私達はtargetの中で同じ数字を見つけてから、targetを後に移動するだけでなく、スタックから元のスタックの一番上の要素を飛び出す必要があります。そして、新しいスタックの一番上の要素とtargetの現在の標的の値を比較します。新しいスタックトップ要素とtarget現在の下付き値が等しくないまで。
3、もし等しくないなら、この時msgを後に移動します。1、2のステップを繰り返します。msgまでもういっぱいです。
4、この時、もしtargetがすでに遍歴済みであれば、targetはmsgの一種の出庫可能性であると説明しました。そうでなければ、targetが遍歴していないなら、targtはmsgの一種の出庫可能性ではないと説明しました。
図解:

完全コード(C言語):


#include<stdio.h>
#define ERROR 0
#define OK 1
#define MAX_SIZE 10000
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;
   s.arr[s.top++] = c;
   return OK;
}
int popElem(Node &s,int &e){
   if(s.top == 0)
     return ERROR;
   e = s.arr[--s.top];
   return OK;
}
int getTop(Node &s,int &e){
   if(s.top == 0)
     return ERROR;
   e = s.arr[s.top - 1];
   return OK;
}
int isEmpty(Node &s){
   return s.top == 0;
}
int testIsTrue(int *msg,int *target){
  Node s;
  int ch;
  init(s);
  while(*msg != '\0'){
     pushElem(s,*msg);//              
     //      
     getTop(s,ch);
     while(ch == *target){
        //                ，        
        popElem(s,ch);
        target++;//       
        /*
        //      ,              ，       ch    target
           target     ，          
        */
        getTop(s,ch);
     }
     msg++;// ch              ，      
  }
  if(*target != '\0')
    return 0;
  return 1;
}
void input(int *arr,int n){
  int i;
  for(i = 0; i < n; i++)
    scanf("%d",&arr[i]);
}
int main(){
  int msg[10000],target[10000];
  int n,flag;
  printf("         :");
  scanf("%d",&n);
  input(msg,n);//  input  ，    n   
  input(target,n);
  flag = testIsTrue(msg,target);//                    
  if(flag)
    printf("yes");
  else
    printf("no");
  return 0;
}

実行結果:

以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。

C言語でハフマンの木を実現する方法

C言語のカスタムデータタイプの構造体、列挙と連携の詳細