<acronym id="cp1ch"><cite id="cp1ch"></cite></acronym>

C++火車入軌算法的實現(xiàn)代碼

來源：本站原創(chuàng)|時間：2020-01-10|欄目：C語言|點擊：次

【問題描述】

某城市有一個火車站，鐵軌鋪設(shè)如圖所示。有n節(jié)車廂從A方向駛?cè)胲囌?，按進站順序編號為1~n。你的任務(wù)是讓它們按照某種特定的順序進入B方向的鐵軌并駛出車站。為了重組車廂，你可以借助中轉(zhuǎn)站C。這是一個可以停放任意多節(jié)車廂的車站，但由于末端封頂，駛?cè)隒的車廂必須按照相反的順序駛出。對于每個車廂，一旦從A移入C，就不能再回到A了；一旦從C移入B，就不能回到C了。換句話說，在任意時刻，只有兩種選擇：A→C和C→B。

這個問題和之前數(shù)據(jù)結(jié)構(gòu)實驗的火車入軌類似，而且較之簡化。自己嘗試寫了下，和書上參考答案的代碼量仍有較大差距。代碼如下：

復(fù)制代碼代碼如下:

#include<iostream>
using namespace std;
const int MAXSIZE=100;
void main()
{
    int n;
    cin>>n;
    int a[MAXSIZE],b[MAXSIZE];
    int stack[MAXSIZE];
    for(int i=0;i<n;i++)
    {
        a[i]=i+1;
        cin>>b[i];                   　　 //出棧順序
    }
    int top=-1;
    int count=0;
    int i=0;
    for(;;)
    {
        if(i<n)
        {
            ++top;
            stack[top]=a[i++];            //入棧
            cout<<"PUSH"<<endl;
        }

        if(stack[top]==b[count])
        {
            top--;count++;
            cout<<"POP"<<endl;
        }
        else if(i==n)
        {
            cout<<"NO"<<endl;
            break;
        }
        if(count==n)
        {
            cout<<"YES"<<endl;
            break;
        }
        if(top<-1)
        {
            cout<<"NO"<<endl;
            break;
        }
    }

}

書中參考代碼如下：

復(fù)制代碼代碼如下:

 #include<iostream>
using namespace std;
const int MAXN=1000+10;
int n,target[MAXN];
void main()
{
    while(cin>>n)
    {
        int stack[MAXN],top=0;
        int A=1,B=1;                                          　　  //A用來記錄入棧次數(shù)，B用來記錄出軌的火車序號
        for(int i=1;i<=n;i++)
            cin>>target[i];                                        //記錄出軌順序
        int ok=1;
        while(B<=n)
        {
            if(A==target[B]){A++;B++;}
            else if(top && stack[top]==target[B]){top--;B++;}    　　//出棧
            else if((A<=n)) stack[++top]=A++;                   　　 //入棧
            else {ok=0;break;}
        }
        if(ok)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
 

同樣，可以用STL來實現(xiàn)，只需對書中參考答案作微小改動，代碼如下：

復(fù)制代碼代碼如下:

 /*STL棧來實現(xiàn)*/
#include<iostream>
#include<stack>
using namespace std;
const int MAXN=1000+10;
int n,target[MAXN];
int main()
{
    while(cin>>n)
    {
        stack<int> s;
        int A=1,B=1;
        for(int i=1;i<=n;i++)
            cin>>target[i];
        int ok=1;
        while(B<=n)
        {
            if(A==target[B]){A++;B++;}
            else if(!s.empty() && s.top()==target[B]){s.pop();B++;}
            else if(A<=n) s.push(A++);
            else {ok=0;break;}
        }
        if(ok)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
}
 

【總結(jié)】

自己寫的代碼仍有優(yōu)化的空間。學(xué)習(xí)參考答案的清晰邏輯的表達。學(xué)習(xí)STL棧的使用。

聯(lián)系數(shù)據(jù)結(jié)構(gòu)實驗中關(guān)于火車入軌的提升，對緩沖軌的限制，應(yīng)該增加一個判斷即可。

不知坑有多深的C++初學(xué)者目前停留在“水題”階段走一步看一步，摸著石頭過河向大牛看齊

上一篇：c++ vector(向量)使用方法詳解(順序訪問vector的多種方式）

欄目：C語言

下一篇：深入理解C語言內(nèi)存對齊

本文標(biāo)題：C++火車入軌算法的實現(xiàn)代碼

本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/3874.html

更多C語言

欧美大屁股bbbbxxxx,狼人大香伊蕉国产www亚洲,男ji大巴进入女人的视频小说,男人把ji大巴放进女人免费视频,免费情侣作爱视频

C語言

C++火車入軌算法的實現(xiàn)代碼

您可能感興趣的文章

閱讀排行

本欄相關(guān)

隨機閱讀