main.cpp

使用堆栈完成火车车厢重排的算法

/*===============================================================
********************实现火车车厢重排*****************************
===============================================================*/

#include<iostream>
#include"stack.h"
using namespace std;

//函数声明
void Output(int& minH,int& minS,stack<int> H[],int k,int n); 
bool Hold(int c,int& minH,int &minS,stack<int> H[],int k,int n);


//--------------------------------------------------------------
bool Railroad(int p[],int n,int k)
{		// k 个缓冲铁轨，车厢初始排序为p[1:n]
		// 如果重排成功，返回true，否则返回false
		// 如果内存不足，则引发异常NoMem 。
		//创建与缓冲铁轨对应的堆栈
	stack<int> *H;
	H=new stack<int> [k+1];
	int NowOut=1; //下一次要输出的车厢
	int minH=n+1; //缓冲铁轨中编号最小的车厢
	int minS;	 //minH号车厢对应的缓冲铁轨
				//车厢重排
	for(int i=1;i<=n;i++)
	if(p[i]== NowOut)
	{// 直接输出t
		cout<<"Move car "<<p[i]<<" from input to output"<<endl;
		NowOut++;
		//从缓冲铁轨中输出
		while(minH==NowOut)
		{
			Output(minH, minS, H, k, n);
			NowOut++;
		}
	}
	else 
	{
		// 将p[i] 送入某个缓冲铁轨
		if (!Hold(p[i], minH, minS, H, k, n))
			return false;
	}
	return true;
}

//----------------------------------------------------------------------
void Output(int& minH,int& minS,stack<int> H[],int k,int n)
{ 
			//把车厢从缓冲铁轨送至出轨处，同时修改minS和minH
	int c; // 车厢索引
			// 从堆栈minS中删除编号最小的车厢minH
	//H[minS].Delete(c);
	c=H[minS].pop();
	cout<< "Move car "<<minH<<" from holding track "<<minS<<" to output"<<endl;
		// 通过检查所有的栈顶，搜索新的m i n H和m i n S
	minH=n+2;
	for(int i=1;i<=k;i++)
		if(!H[i].empty()&&(c=H[i].top())<minH)
	{
		minH=c;
		minS = i;  
	}
}

//--------------------------------------------------------------------
bool Hold(int c,int& minH,int &minS,stack<int> H[],int k,int n)
{		// 在一个缓冲铁轨中放入车厢c
		// 如果没有可用的缓冲铁轨，则返回false
		// 如果空间不足，则引发异常NoMem
		// 否则返回true
		// 为车厢c寻找最优的缓冲铁轨
		// 初始化
	int BestTrack=0; // 目前最优的铁轨
	int BestTop=n+1; // 最优铁轨上的头辆车厢
	int x;// 车厢索引
		//扫描缓冲铁轨
	for(int i=1;i<=k;i++)
	if(!H[i].empty())   
	{		// 铁轨i 不空
		x=H[i].top();
		if (c<x&&x<BestTop) 
		{
			//铁轨i 顶部的车厢编号最小
			BestTop=x;
			BestTrack=i;
		}
	}
	else // 铁轨i 为空
		if(!BestTrack) 
			BestTrack=i;
	if (!BestTrack)
		return false; //没有可用的铁轨
			//把车厢c 送入缓冲铁轨
	H[BestTrack].push(c);
	cout<<"Move car "<<c<<" from input " "to holding track "<<BestTrack<<endl;
			//必要时修改minH 和minS
	if(c<minH) 
	{
		minH=c;
		minS=BestTrack;
	}
	return true;
}
//------------------------------------------------------------------
//主函数开始
void main()
{
	int nTemp;
	int p[10]={0,5,8,1,7,4,2,9,6,3};
	cout<<"please input the number of the Temps:"<<endl;
	cin>>nTemp;
	if(!Railroad(p,9,nTemp))
		cout<<"false!"<<endl;
}