队列的应用火车车厢重排问题

一、试验课题

队列的应用

实验目的：

（1）掌握队列的特点及其存储方法； （2）掌握队列的常见算法和程序实现。

二、试验内容

(1)问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。车厢的重排工作可以通过国转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重排问题。

(2)基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能

三、试验分析

实验说明：

转轨站示意图如下：

火车车厢重排过程如下：

2

(a) 将369、247依次入缓冲轨

2 将8入缓冲轨，5移至出轨 (c)

2(b) 将1移至出轨，234移至

出轨

2(d) 将6789移至出轨

火车车厢重排算法伪代码如下：

四、源程序代码

#include using namespace std; const MS=100;

template struct QNode {

T data;

QNode *next; };

template class LiQueue {

public:

LiQueue( ); //构造函数，初始化一个空的链队列

~LiQueue( ); //析构函数，释放链队列中各结点的存储空间 void EnQueue(T x); //将元素x入队 T DeQueue( ); //将队头元素出队

T GetFront( ); //取链队列的队头元素 T GetRear();

bool Empty( ); //判断链队列是否为空

QNode *front, *rear; //队头和队尾指针，分别指向头结点和终端结点 };

template LiQueue::LiQueue( ) {

QNode *s;s=new QNode;s->next=NULL;front=rear=s; }

template

LiQueue::~LiQueue( ) {

QNode *p; while(front) {

p=front;front=front->next;delete p; } }

template

void LiQueue::EnQueue(T x) {

QNode *s;s=new QNode;

s->data=x; //申请一个数据域为x的结点s s->next=NULL;

rear->next=s; //将结点s插入到队尾 rear=s; }

template

T LiQueue::DeQueue() {

QNode *p; int x;

if (rear==front) throw "下溢"; p=front->next;

x=p->data; //暂存队头元素

front->next=p->next; //将队头元素所在结点摘链

if (p->next==NULL) rear=front; //判断出队前队列长度是否为1 delete p; return x; }

template

T LiQueue::GetFront() {

if (rear!=front)

return front->next->data; }

template T LiQueue::GetRear() {

if(rear!=front)return rear->data; }

template

bool LiQueue::Empty( ) {

if(front==rear) return 0;else return 1; }

class Train {

private : int n,k,th; public :

Train();void ChongPai(); };

Train::Train() {

cout>n;

cout>k; }

void Train::ChongPai() {

int a[MS];LiQueue*b; b=new LiQueue[k+2];

cout>a[i];

for(i=n-1;i>=0;i--) b[k].EnQueue(a[i]);

cout

while(b[k].Empty()) {

int xx=b[k].DeQueue(); if(xx==th) {

cout

while(b[j].Empty()) {

int x=b[j].GetFront(); if(x==th) {

cout

continue; }

else {

int j=0,u=5;

while(b[j].Empty()&&j

if(xx

cout

if(u==5&&j

cout

if(j==k-1) {

cout

cout

cout

void main() {

Train a;a.ChongPai(); }

五、测试用例

1.当有9个火车车厢，3个缓冲轨道时，运行结果如下：

2. 当有12个火车车厢，3个缓冲轨道时，运行结果如下：

3. 当有12个火车车厢，5个缓冲轨道，运行结果如下：

4. 当有12个火车车厢，7个缓冲轨道时，运行结果如下：

几次测试都表明试验设计的正确性。

六、试验总结

本次试验中，在解决火车车厢重排问题中，结合了最近刚学的队列的知识，并且运用到之前C++语言，很好的解决了这一类问题。其中，每一个轨道缓冲区就形如一个队列一样，车厢先进缓冲轨道的要先出来，所以把它看成一个队列，运用队列的相关算法，实现高效快速的解决火车车厢重排问题。

通过本次试验，学会了队列的应用，加深了对队列的理解，知道了队列是一种先进队列的后出队列的储存结构。本次试验让我更好的把书本上的知识运用到具体的例子中来，学会了通过vc6.0来建立队列，以及初始化队列、进队列、出队列等等。同时也了解到了火车车厢重排问题可以通过队列的相关知识来解决，也体会其中算法的奥妙。