huoche.cpp

通过输入火车车次可以得到火车的运行情况等

#include<iostream>   
#include<iomanip>   
#include<stack>   
#include<vector>   
    
using namespace std;   
    
static allnumber = 0; //记录总的排列数  
#define PUSH 1   
#define POP 0 
  
void Display( stack<int> &trainStack, int trainFlagSize, int *flag, const int flagSize) //显示所有的火车排列情况   
{   
	if( trainFlagSize == 0 )   
	{   
		vector<int> newTrain; //出栈的火车排列容器   
		int trainNumber = flagSize / 2;   
		const constTrainSize = flagSize / 2;   
		int pushTimes = 0;   
		int i;   
		while( !trainStack.empty() ) //清空栈   
			trainStack.pop();   
		for( i = 0; i < flagSize; ++i )   
		{   
			if( flag[i] == PUSH )   
			{
				++pushTimes;   
				trainStack.push( trainNumber-- );   
				if( pushTimes > constTrainSize ) //如果进栈的次数多于了火车的总数目，出错退出  
					return;   
			}   
			else if( !trainStack.empty() )   
			{ 
				newTrain.push_back(   trainStack.top()   );   
				trainStack.pop();   
			}   
			else  
				return;   
		}   
		for( i = 0; i < newTrain.size(); ++i )   //输出火车排列
		{   
			cout   <<   setw(4)   <<   newTrain[i];   
		}   
		cout << endl;     
		allnumber++;   
   	}   
    else   
	{      
		trainFlagSize--;         
		flag[trainFlagSize] = PUSH;   
		Display( trainStack, trainFlagSize, flag, flagSize);  //通过递归，得出所有进出栈次序排列                       
		flag[trainFlagSize] = POP;   
		Display( trainStack, trainFlagSize, flag, flagSize);   
	}   
}    
int main()   
{   
	stack<int> trainStack; //火车栈  
	int trainSize = 0; // 火车数目
	int *flag = NULL;  // 每个火车标识位
	int flagSize = 0;   
    
	cout << "Input   size   of   train:   ";   
    cin   >> trainSize;   
    if( trainSize < 0   )   
		return -1;      
    flagSize = 2 * trainSize; //n次进栈，n次出栈，共2n次  
    flag = new int[flagSize];   
    
    if( flag == NULL )   
	{   
		cerr << "memory   get   error!" << endl;   
		return   -1;   
	}   
    Display( trainStack, 2*trainSize, flag, flagSize );             
    delete []flag;   
    flag = NULL;        
    cout << allnumber << endl;   
    return 0;   
}