完整可編譯運行代碼見：Github::Data-Structures-Algorithms-and-Applications/_10Train_carriages_rearrangement/

列車車廂重排問題

一列貨運列車有 n 節(jié)車廂，每節(jié)車廂要?？吭诓煌能囌尽＜僭O n個車站從 1 到n 編號，而且貨運列車按照從n到1的順序經(jīng)過車站。車廂的編號與它們要?？康能囌揪幪栂嗤榱吮阌趶牧熊嚿闲兜粝鄳能噹?，必須按照從前至后、從1到 n 的順序把車廂重新排列。這樣排列之后，在每個車站只需卸掉最后一節(jié)車廂即可。車廂重排工作在一個轉(zhuǎn)軌站（shunting yard）上進行，轉(zhuǎn)軌站上有一個入軌道（input track）、一個出軌道（output track）和k個緩沖軌道（holding track）。緩沖軌道位于入軌道和出軌道之間。圖 8-6a 顯示了一個轉(zhuǎn)軌站，其中有 3 個緩沖軌道 H1、H2 和 H3，即 k=3。開始時，掛有 n 節(jié)車廂的貨車開始在入軌道，而最后在出軌道上的順序是從右到左，從1 至n。在圖 8-6a 中，n=9，車廂從后至前的初始順序為5，8，1，7，4，2，9，6，3。圖8-6b是按要求的順序重新排列的結果。

使用棧解決

思路

為了重排車廂，我們從前至后檢查入軌道上的車廂。如果正在檢查的車廂是滿足排列要求的下一節(jié)車廂，就直接把它移到出軌道上。如果不是，就把它移到一個緩沖軌道上，直到它滿足排列要求時才將它移到出軌道上。緩沖軌道是按照 LIFO的方式管理的，車廂的進出都在緩沖軌道的頂部進行。在重排車廂過程中，僅允許以下移動：

• 車廂可以從入軌道的前端（即右端）移動到一個緩沖軌道的頂部或出軌道的后端（即左端）。
• 車廂可以從一個緩沖軌道的頂部移到出軌道的后端。
• 使用單調(diào)棧，棧頂?shù)綏５椎脑貜男〉酱蟆?/li>

代碼

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
/*列車車廂重排全局變量*/
stack<int>* trackStack;//緩沖軌道數(shù)組
vector<int> outputTrackStack;//輸出數(shù)組
int numberOfCarsStack;//需要重排的列車數(shù)目
int numberOfTracksStack;//緩沖軌道數(shù)目
int smallestCarStack;//在緩沖軌道中編號最小的車廂
int itsTrackStack;//?？恐钚【幪栜噹木彌_軌道

/*列車車廂重排問題*/
/*將編號最小的車廂從緩沖軌道移到出軌道*/
void outputFromHoldingTrackStack()
{
    //從棧itsTrack中刪除編號最小的車廂
    outputTrackStack.push_back(trackStack[itsTrackStack].top());
    trackStack[itsTrackStack].pop();
    cout << "Move car " << smallestCarStack << " from holding track " << itsTrackStack << " to output track" << endl;
    //檢查所有的棧頂，尋找編號最小的車廂和它所屬的棧itsTrack
    smallestCarStack = numberOfCarsStack + 2;
    for (int i = 1; i <= numberOfTracksStack; i++)
    {
        if (!trackStack[i].empty() && (trackStack[i].top() < smallestCarStack))
        {
            smallestCarStack = trackStack[i].top();
            itsTrackStack = i;
        }
    }
}
/*將車廂c移到一個緩沖軌道。返回false,當且僅當沒有可用的緩沖軌道*/
bool putInHoldingTrackStack(int c)
{
    //為車廂c尋找最適合的緩沖軌道
    //初始化
    int bestTrack = 0;//目前沒有適合的緩沖軌道
    int bestTop = numberOfCarsStack + 1;//取bestTrack中最頂部的車廂，便于比較
    //掃描緩沖軌道
    for (int i = 1; i <= numberOfTracksStack; i++)
    {
        //緩沖軌道i不為空
        // 是一個單調(diào)棧，棧底到棧頂?shù)臄?shù)據(jù)是從小到大
        if (!trackStack[i].empty())
        {
            if (c < trackStack[i].top() && trackStack[i].top() < bestTop)
            {//緩沖軌道i的棧頂具有編號更小的車廂
                bestTop = trackStack[i].top();
                bestTrack = i;
            }
        }
        else if (bestTrack == 0) bestTrack = i;
    }
    if (bestTrack == 0) return false;//沒有可用的緩沖軌道
    //把車廂c移動到軌道bestTrack
    trackStack[bestTrack].push(c);
    cout << "Move car " << c << " from input track to holding track " << bestTrack << endl;
    //如果需要，更新smallestCar和itsTrack
    if (c < smallestCarStack)
    {
        smallestCarStack = c;
        itsTrackStack = bestTrack;
    }
    return true;
}
/*從初始順序開始重排車廂；如果重排成功，返回true,否則返回false*/
bool railRoadStack(int inputOrder[], int theNumberOfCars, int theNumberOfTracks)
{
    numberOfCarsStack = theNumberOfCars;
    numberOfTracksStack = theNumberOfTracks;
    /*創(chuàng)建用于緩沖軌道的棧*/
    trackStack = new stack<int>[numberOfTracksStack + 1];
    smallestCarStack = numberOfCarsStack + 1;//緩沖軌道中無車廂

    int nextCarToOutput = 1;//當前需要被輸出軌道的車廂編號
    //重排車廂
    for (int i = 0; i < numberOfCarsStack; i++)
    {
        if (inputOrder[i] == nextCarToOutput)
        {
            /*將車廂inputOrder[i]直接移到出軌道*/
            cout << "Move car " << inputOrder[i] << " from input track to output track" << endl;
            outputTrackStack.push_back(inputOrder[i]);
            nextCarToOutput++;
            /*從緩沖軌道移到出軌道*/
            while (smallestCarStack == nextCarToOutput)
            {
                outputFromHoldingTrackStack();
                nextCarToOutput++;
            }
        }
        else
        {
            if(!putInHoldingTrackStack(inputOrder[i]))
                return false;
        }
    }
    return true;
}

int main()
{
    // 列車車廂重排問題
    cout << "railRoadStack()*****************" << endl;
    int inputOrder[9] = { 5, 8, 1, 7, 4, 2, 9, 6, 3 };
    railRoadStack(inputOrder, 9, 3);
    for(int& data : outputTrackStack)
        cout << data << " ";
    cout << endl;
    return 0;
}

運行結果

C:\Users\15495\Documents\Jasmine\Work\coding\cmake-build-debug\coding.exe
railRoadStack()*****************
Move car 5 from input track to holding track 1
Move car 8 from input track to holding track 2
Move car 1 from input track to output track
Move car 7 from input track to holding track 2
Move car 4 from input track to holding track 1
Move car 2 from input track to output track
Move car 9 from input track to holding track 3
Move car 6 from input track to holding track 2
Move car 3 from input track to output track
Move car 4 from holding track 1 to output track
Move car 5 from holding track 1 to output track
Move car 6 from holding track 2 to output track
Move car 7 from holding track 2 to output track
Move car 8 from holding track 2 to output track
Move car 9 from holding track 3 to output track
1 2 3 4 5 6 7 8 9

Process finished with exit code 0

使用隊列解決

思路

為了重排車廂，我們從前至后檢查入軌道上的車廂。如果正在檢查的車廂是滿足排列要求的下一節(jié)車廂，就直接把它移到出軌道上。如果不是，就把它移到一個緩沖軌道上，直到它滿足排列要求時才將它移到出軌道上。緩沖軌道是按照 LILO的方式管理的，車廂的進出都在緩沖軌道的隊頭進行。在重排車廂過程中，僅允許以下移動：

• 車廂可以從入軌道的前端（即右端）移動到一個緩沖軌道的隊尾或出軌道的后端（即左端）。
• 車廂可以從一個緩沖軌道的隊頭移到出軌道的后端。
• 使用單調(diào)隊列，隊頭到隊尾的元素從小到大。

代碼

#include <iostream>
#include <queue>
using namespace std;
/*列車車廂重排全局變量*/
queue<int>* trackQueue;//緩沖軌道數(shù)組
queue<int> outputTrackQueue;//輸出數(shù)組
int numberOfCarsQueue;//需要重排的列車數(shù)目
int numberOfTracksQueue;//緩沖軌道數(shù)目
int smallestCarQueue;//在緩沖軌道中編號最小的車廂
int itsTrackQueue;//?？恐钚【幪栜噹木彌_軌道

/*列車車廂重排問題*/
/*將編號最小的車廂從緩沖軌道移到出軌道*/
void outputFromHoldingTrackQueue()
{
    //從隊列itsTrack中刪除編號最小的車廂
    outputTrackQueue.push(smallestCarQueue);
    trackQueue[itsTrackQueue].pop();
    cout << "Move car " << smallestCarQueue << " from holding track " << itsTrackQueue << " to output track" << endl;
    //檢查所有的隊頭，尋找編號最小的車廂和它所屬的隊itsTrackQueue
    smallestCarQueue = numberOfCarsQueue + 2;
    for (int i = 1; i <= numberOfTracksQueue; i++)
    {
        if (!trackQueue[i].empty() && (trackQueue[i].front() < smallestCarQueue))
        {
            smallestCarQueue = trackQueue[i].front();
            itsTrackQueue = i;
        }
    }
}
/*將車廂c移到一個緩沖軌道。返回false,當且僅當沒有可用的緩沖軌道*/
/*此處使用了單調(diào)隊列：從隊頭元素到隊尾元素是從小到大的順序*/
bool putInHoldingTrackQueue(int c)
{
    //為車廂c尋找最適合的緩沖軌道
    //初始化
    int bestTrack = 0;//目前沒有適合的緩沖軌道
    int bestTop = 0;//取bestTrack為0，便于比較
    //掃描緩沖軌道
    for (int i = 1; i <= numberOfTracksQueue; i++)
    {
        //緩沖軌道i不為空
        if (!trackQueue[i].empty())
        {
            if (c > trackQueue[i].back() && trackQueue[i].back() > bestTop)
            {//緩沖軌道i的隊尾具有編號更大的車廂
                bestTop = trackQueue[i].back();
                bestTrack = i;
            }
        }
        else//緩沖軌道i為空
            if (bestTrack == 0) bestTrack = i;
    }
    if (bestTrack == 0) return false;//沒有可用的緩沖軌道
    //把車廂c移動到軌道bestTrack
    trackQueue[bestTrack].push(c);
    cout << "Move car " << c << " from input track to holding track " << bestTrack << endl;
    //如果需要，更新smallestCar和itsTrack
    if (c < smallestCarQueue)
    {
        smallestCarQueue = c;
        itsTrackQueue = bestTrack;
    }
    return true;
}
/*從初始順序開始重排車廂；如果重排成功，返回true,否則返回false*/
bool railRoadQueue(int inputOrder[], int theNumberOfCars, int theNumberOfTracks)
{
    numberOfCarsQueue = theNumberOfCars;
    numberOfTracksQueue = theNumberOfTracks;
    /*創(chuàng)建用于緩沖軌道的隊列*/
    trackQueue = new queue<int>[numberOfTracksQueue + 1];
    smallestCarQueue = numberOfCarsQueue + 1;//緩沖軌道中無車廂

    int nextCarToOutput = 1;//當前需要被輸出軌道的車廂編號
    //重排車廂
    for (int i = 0; i < numberOfCarsQueue; i++)
    {
        if (inputOrder[i] == nextCarToOutput)
        {
            /*將車廂inputOrder[i]直接移到出軌道*/
            cout << "Move car " << inputOrder[i] << " from input track to output track" << endl;
            outputTrackQueue.push(inputOrder[i]);
            nextCarToOutput++;
            /*從緩沖軌道移到出軌道*/
            while (smallestCarQueue == nextCarToOutput)
            {
                outputFromHoldingTrackQueue();
                nextCarToOutput++;
            }
        }
        else
        {
            if (!putInHoldingTrackQueue(inputOrder[i]))
                return false;
        }
    }
    return true;
}


int main()
{
    //列車車廂重排問題
    cout << "railRoadQueue()*****************" << endl;
    int inputOrder[9] = { 5, 8, 1, 7, 4, 2, 9, 6, 3 };
    if(railRoadQueue(inputOrder, 9, 3)){
        for(int i = 0; i < outputTrackQueue.size(); i++){
            cout << outputTrackQueue.front() << " ";
            outputTrackQueue.pop();
        }
        cout << endl;
    }

    return 0;
}

運行結果

C:\Users\15495\Documents\Jasmine\Work\coding\cmake-build-debug\coding.exe
railRoadQueue()*****************
Move car 5 from input track to holding track 1
Move car 8 from input track to holding track 1
Move car 1 from input track to output track
Move car 7 from input track to holding track 2
Move car 4 from input track to holding track 3
Move car 2 from input track to output track
Move car 9 from input track to holding track 1
Move car 6 from input track to holding track 3
Move car 3 from input track to output track
Move car 4 from holding track 3 to output track
Move car 5 from holding track 1 to output track
Move car 6 from holding track 3 to output track
Move car 7 from holding track 2 to output track
Move car 8 from holding track 1 to output track
Move car 9 from holding track 1 to output track
1 2 3 4 5

Process finished with exit code 0

既不使用棧也不使用隊列解決

思路

使用數(shù)組模擬單調(diào)?；騿握{(diào)隊列。文章來源地址http://www.zghlxwxcb.cn/news/detail-846858.html

代碼

#include <iostream>
using namespace std;
/*不使用隊列的列車車廂重排全局變量*/
/*存儲車廂所在的軌道和軌道隊尾的值*/
int* whichTrack;  // track that has the car,存儲了某車子在哪個軌道
int* lastCar;     // last car in track
int numberOfCars;
int numberOfTracks;

/*不使用隊列的列車車廂重排問題*/
void outputFromHoldingTrackNoQueues(int c)
{// Move car c from its holding track to the output track.
    cout << "Move car " << c << " from holding track "
         << whichTrack[c] << " to output track" << endl;

    // if c was the last car in its track, the track is now empty
    if (c == lastCar[whichTrack[c]])
        lastCar[whichTrack[c]] = 0;
}
bool putInHoldingTrackNoQueues(int c)
{// Put car c into a holding track.
    // Return false iff there is no feasible holding track for this car.

    // find best holding track for car c
    // initialize
    int bestTrack = 0,  // best track so far
    bestLast = 0;  // last car in bestTrack

    // scan tracks
    for (int i = 1; i <= numberOfTracks; i++)
        if (lastCar[i] != 0)
        {// track i not empty
            if (c > lastCar[i] && lastCar[i] > bestLast)
            {
                // track i has bigger car at its rear
                bestLast = lastCar[i];
                bestTrack = i;
            }
        }
        else // track i empty
            if (bestTrack == 0)
                bestTrack = i;

    if (bestTrack == 0)
        return false; // no feasible track

    // add c to bestTrack
    whichTrack[c] = bestTrack;
    lastCar[bestTrack] = c;
    cout << "Move car " << c << " from input track "
         << "to holding track " << bestTrack << endl;

    return true;
}
bool railroadNoQueues(int* inputOrder, int theNumberOfCars, int theNumberOfTracks)
{// Rearrange railroad cars beginning with the initial order.
    // inputOrder[1:theNumberOfCars]
    // Return true if successful, false if impossible.

    numberOfCars = theNumberOfCars;
    // keep last track open for output
    numberOfTracks = theNumberOfTracks - 1;

    // create the arrays lastCar and whichTrack
    lastCar = new int[numberOfTracks + 1];
    fill(lastCar + 1, lastCar + numberOfTracks + 1, 0);
    whichTrack = new int[numberOfCars + 1];
    fill(whichTrack + 1, whichTrack + numberOfCars + 1, 0);

    int nextCarToOutput = 1;

    // rearrange cars
    for (int i = 1; i <= numberOfCars; i++)
        if (inputOrder[i] == nextCarToOutput)
        {// send car inputOrder[i] straight out
            cout << "Move car " << inputOrder[i] << " from input "
                 << "track to output track" << endl;
            nextCarToOutput++;

            // output from holding tracks
            while (nextCarToOutput <= numberOfCars &&
                   whichTrack[nextCarToOutput] != 0)
            {
                outputFromHoldingTrackNoQueues(nextCarToOutput);
                nextCarToOutput++;
            }
        }
        else
            // put car inputOrder[i] in a holding track
            if (!putInHoldingTrackNoQueues(inputOrder[i]))
                return false;
    return true;
}


int main()
{
    //列車車廂重排問題
    cout << "railroadNoQueues()**************" << endl;
    int p[] = {0, 3, 6, 9, 2, 4, 7, 1, 8, 5};
    cout << "Input permutation is 369247185" << endl;
    railroadNoQueues(p, 9, 3);

    return 0;
}

運行結果

C:\Users\15495\Documents\Jasmine\Work\coding\cmake-build-debug\coding.exe
railroadNoQueues()**************
Input permutation is 369247185
Move car 3 from input track to holding track 1
Move car 6 from input track to holding track 1
Move car 9 from input track to holding track 1
Move car 2 from input track to holding track 2
Move car 4 from input track to holding track 2
Move car 7 from input track to holding track 2
Move car 1 from input track to output track
Move car 2 from holding track 2 to output track
Move car 3 from holding track 1 to output track
Move car 4 from holding track 2 to output track
Move car 8 from input track to holding track 2
Move car 5 from input track to output track
Move car 6 from holding track 1 to output track
Move car 7 from holding track 2 to output track
Move car 8 from holding track 2 to output track
Move car 9 from holding track 1 to output track

Process finished with exit code 0

到了這里，關于《數(shù)據(jù)結構、算法與應用C++語言描述》-列車車廂重排問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！