①问题描述
一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1～n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。
车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出的方式运作，设计算法解决火车车厢重排问题。
②基本要求
-
设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨；
-
设计并实现车厢重排算法；
-
分析算法的时间性能。
③设计思想
假设有3个缓冲轨，入轨中有9节车厢，次序为5,8,1,7,4,2,9,6,3，重排后，9节车厢出轨次序为9,8,7,6,5,4,3,2,1。重排过程如下：
3号车厢不能直接移至出轨（因为1号车厢和2号车厢必须排在3号车厢之前），因此，把3号车厢移至H1。6号车厢可放在H1中3号车厢之后（因为6号车厢将在3号车厢之后出轨）。9号车厢可以继续放在H1中6号车厢之后，而接下来的2号车厢不能放在9号车厢之后（因为2号车厢必须在9号车厢之前出轨）。因此，应把2号车厢移至H2，4号车厢可以放在H2中2号车厢之后，7号车厢可以继续放在4号车厢之后，如图4所示。至此，1号车厢可通过H3直接移至出轨，如图5所示。由于5号车厢此时仍在入轨中，所以把8号车厢移动至H2，这样就可以把5号车厢直接从入轨移至出轨，如图6所示。此后，可依次从缓冲轨中移出6号、7号、8号和9号车厢，如图7所示。
图4 将369、247依次入缓冲轨
图5 将1移至出轨，234移至出轨
图6 将8入缓冲轨，5移至出轨
图7 将6789移至出轨
由上述重排过程可知：在把车厢c移至缓冲轨时，车厢c应移动到这样的缓冲轨中：该缓冲轨中队尾车厢的编号小于c；如果有多个缓冲轨满足这一条件，则选择队尾车厢编号最大的缓冲轨；否则选择一个空的缓冲轨。
⑤思考
-
如果缓冲轨按后进先出的方式工作，即用栈表示缓冲轨，应如何解决火车车厢重排问题？
#include<iostream>
using namespace std;
class Queue
{
public:
struct Node
{
int data;
Node * next;
Node():next(NULL) {}
Node(int a):data(a),next(NULL) {}
};
Node * Front;
Node * rear;
int length;
Queue()
{
Node * p = new Node();
Front = p;
rear = p;
length = 0;
}
int inQueue(int a)
{
Node * p = new Node(a);
rear -> next = p;
rear = rear -> next;
length ++;
}
int showrear()
{
return rear->data;
}
int showfront()
{
return Front->next->data;
}
void outQueue()
{
Node * p = Front -> next;
Front -> next = p -> next;
delete p;
length--;
}
void printf()
{
Node * p = Front -> next;
for(int i = 0 ; i < length ; i++)
{
cout<<p->data<<" ";
p = p -> next;
}
}
bool isEmpty()
{
return length == 0;
}
};
int main()
{
int n , k ;//n代表车厢数，k代表轨道
int nowOut = 1;//要输出的车厢编号
cout<<"input n:"<<endl;
cout<<"input k:"<<endl;
cout<<"input train"<<endl;
cin>>n>>k;
Queue dusk[k+2];//0到k-1代表缓冲轨道，k代表入轨，k+1代表出轨
for(int i = 0 ; i < n ; i++)//输入入队车厢号
{
int a ;
cin>>a;
dusk[k].inQueue(a);
}
while(!dusk[k].isEmpty())//出轨不为空的时候循环
{
int flag = 0;//判断进入新的缓冲轨还是进入非空缓冲轨道。
//0进入新的缓冲轨道，非0进入非空缓冲轨道
int z = 0;//判断是否能直接出轨。0为不能直接出轨，非0为可出轨。
int flag_end = 0;//退出循环判定
if(dusk[k].showfront()==nowOut)//如果出轨队头车厢号等于现在要出轨的车厢号
{
for(int i = 0 ; i < k ; i++)//遍历所有循环轨，找出一个空的
{
if(dusk[i].isEmpty())//找到空的循环轨，输出
{
cout<<dusk[k].showfront()<<" train by trace "<<i+1<<" out."<<endl;
dusk[k+1].inQueue(dusk[k].showfront());
nowOut++;
dusk[k].outQueue();
z++;
flag++;
break;
}
}
}
if(z==0)//如果不能直接出轨，找到比当前要出轨的车厢小的非空轨道，并入轨
{
for(int i = 0 ; i < k ; i++)
{
if(!dusk[i].isEmpty()&&(dusk[i].showrear()<dusk[k].showfront()))
{
cout<<dusk[k].showfront()<<" train in "<<i+1<<" trace."<<endl;
dusk[i].inQueue(dusk[k].showfront());
dusk[k].outQueue();
flag ++;
break;
}
}
}
//如果找不到比当前要出轨的车厢小的非空轨道，就找空的缓冲轨，并入轨
if(flag == 0)
{
for(int i = 0 ; i < k ; i++)
{
if(dusk[i].isEmpty())
{
cout<<dusk[k].showfront()<<" train in "<<i+1<<" trace."<<endl;
dusk[i].inQueue(dusk[k].showfront());
dusk[k].outQueue();
break;
}
if(i==k-1)//如果找不到新的缓冲轨，那么输出ERROR，结束循环
{
cout<<"ERROR!"<<endl;
flag_end = 1;//结束循环的标志
break;
}
}
}
if(flag_end == 1)//退出while循环
{
break;
}
//遍历所有非空轨道队头车厢号，如果等于要出队的车厢号，就出轨并且重新循环
for(int i = 0 ; i < k ; i++)
{
if(!dusk[i].isEmpty()&&dusk[i].showfront()==nowOut)
{
cout<<dusk[i].showfront()<<" train by trace "<<i+1<<" out."<<endl;
dusk[k+1].inQueue(dusk[i].showfront());
dusk[i].outQueue();
nowOut++;
i = -1;
}
}
}
dusk[k+1].printf();//打印出轨车厢顺序
}