火车车厢重排实验报告

东华理工大学长江学院

数据结构课程设计报告

学号： 09321110

姓名： 刘 曹 杰

指导老师：刘自强

2011年1月3日

队列的应用举例——火车车厢重排

一、实验分析

一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1 ~ n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站（目的地）的编号相同，使各车厢从前至后按编号1到n的次序排列，这样，在每个车站只需卸掉最后一节车厢即可。所以，给定任意次序的车厢，必须重新排列他们。可以通过转轨站完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。开始时，n节车厢从入轨进入转轨站，转轨结束时各车厢按照编号1至n的次序离开转轨站进入出轨。假定缓冲轨按先进先出的方式运作，因此可将它们视为队列，并且禁止将车厢从缓冲轨移至入轨，也禁止从出轨移至缓冲轨。图中给出了一个转轨站，其中有3个缓冲轨H1，H2和H3。

为了重排车厢，若有k个缓冲轨，缓冲轨Hk为可直接将车厢从入轨移动到出轨的通道，则可用来暂存车厢的缓冲轨的数目为k-1。假定重排9节车厢，其初始次序为5, 8, 1, 7, 4, 2, 9, 6, 3，同时令k=3，如图3-23所示。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号车厢之后。如图3-24(a)所示。至此，1号车厢可通过H3直接移至出轨，然后从H2移动2号车厢至出轨，从H1移动3号车厢至出轨，从H2移动4号

车厢至出轨，如图3-24(b)所示。由于5号车厢此时仍在入轨中，所以把8号车厢移动至H2，这样就可以把5号车厢直接从入轨移至出轨。如图3-24(c)所示。此后，可依次从缓冲轨中移出6号、7号、8号和9号车厢。如图所示。

在把车厢c移至缓冲轨时，车厢c应移动到这样的缓冲轨中：该缓冲轨中队尾车厢的编号小于c；如果有多个缓冲轨满足这一条件，则选择队尾车厢编号最大的缓冲轨；否则选择一个空的缓冲轨。

假定重排n个车厢，可使用k个缓冲轨，将每个缓冲轨看成是一个队列，用nowOut表示下一个输出至出轨的车厢编号。火车车厢重排的算法用伪代码描述如下：

1. 分别对k个队列初始化；

2. 初始化下一个有爱输出的车厢编号nowOut=1； 3. 依次取入轨中的每一个车厢编号； 3.1如果入轨中的车厢编号等于nowOut，则 3.1.1输出该车厢； 3.1.2nowOut++；

3.2否则，考虑每一个缓冲轨队列 for(j=1;j

3.2.1取队列j的对头元素c； 3.2.2如果c=nowOut，则

3.2.2.1将队列j的对头元素出队并输出； 3.2.2.2nowOut++；

3.3如果入轨和缓冲轨的对头元素没有编号为nowOut的车厢，则

3.3.1求小雨入轨中第一个车厢编号的最大队尾元素所在队列编号j； 3.3.2如果j存在，则把入轨中的第一个车厢移至缓冲轨j；

3.3.2 如果j不存在，但有多余一个空缓冲轨，则把入轨第一个车厢移至一

个空缓冲轨；否则车厢无法重排，算法结束；

二、程序分析

1. 存储结构

本程序采用单链表结构，具体为链队列结构，使用队列结构的先进先出原则可以较好地处理车厢重排问题。链队列结构示意图如下： ……..

front

a1 a2

. . .

an

rear

2. 关键算法分析

一、本程序的关键算法主要为处理车厢重排问题的函数TrainPermute()，其伪代码如下：

void TrainPermute():

1. 初始化条件:计数器i=0,与非门aa=1

2. 判断是否能入轨while(用i

2.2用for循环，依次取入入轨中的每一个车厢的编号进入合适的缓冲轨 ； 2.2.1如果缓冲轨中尾指针比进入缓冲轨元素小，则 进入该缓冲轨； 计数器i+1;

有合适缓冲轨，将aa变为真; 跳出for循环并进入while循环； 2.2.2如果缓冲轨中第一个元素为空，则 进入缓冲轨成为第一个元素； 计数器i+1;

有合适缓冲轨，将aa变为真;

跳出for循环并进入while循环； 2.3 用aa判断是否有进入合适的缓冲轨 ① aa=0即没有合适的缓冲轨，则 输出无法排列；

② aa=1即有合适的缓冲轨，则 遍历缓冲轨，

输出每个缓冲轨按顺序存储的车厢； 按从小到大的顺序出轨

for(引入输出轨计数器newOut=1;newOut

void TrainPermute(int arr[],LinkQueue a[],int n,int k) {

int i=0; bool aa=1;

while((i

aa=0; //亮点：与非门思想！ for(int m=0;m

if(a[m].GetRear()

a[m].EnQueue(arr[i]); i++; aa=1; break; }

if(a[m].front->next==NULL) {

a[m].EnQueue(arr[i]); aa=1; i++; break; } } }

if(aa==0) //当无法将入轨中队头车厢移至合适缓冲轨中时，程序结束 {

cout

else //当入轨中已经没有车厢时 {

for(int m=0;m

cout

cout

for(int j=0;j

{

if(a[j].GetFront()==newOut) {

cout二、主函数伪代码如下：

1. 输入n与k值，若输入值错误，则程序结束； 2. 通过循环结构为数组array[]赋值，具体分析见代码； 3. 输出入轨中火车车厢号码排列；

4. 调用TrainPermute()函数；

三、为array[]随机赋值的基本思想为：设置计数器count=0，设置数组ifmark[]来标记array[]赋值情况，依次将1至n等n个数随机赋给array[]，其中，若array[t]未被赋值，即ifmark[t]=0，则将值赋给array[t]，计数器加一；若array[t]已被赋值，即ifmark[t]=1，则重新开始循环。

srand((unsigned)time(NULL)); int count=0; int *array;

array=new int[n]; int *ifmark;

ifmark=new int[n]; while(count!=n) {

t=rand()%n;

if(ifmark[t]!=1) {

array[t]=count+1; ifmark[t]=1; count++; } }

三、实验过程

程序代码及运行结果

#include #include using namespace std;

const int QueueSize=1000; template struct Node {

T data;

Node *next; };

template

class LinkQueue //链队列模板类 {

public:

LinkQueue(); //构造函数 ~LinkQueue(); //析构函数 void Trans(); //遍历缓冲轨 void EnQueue(T x);//入队 T DeQueue(); //出队

T GetFront() //查找队头元素

{if(front!=rear) return front->next->data;} T GetRear() //查找队尾元素 {if(front!=rear) return rear->data;}

bool Empty() {front==NULL?return 1:return 0;} //判断队空 friend void TrainPermute(int arr[],LinkQueue a[],int n,int k); private:

Node *front,*rear; };

template

LinkQueue::LinkQueue() {

Node *s=new Node; s->next=NULL;

front=rear=s; }

template

LinkQueue::~LinkQueue() {

Node *p=front; while(p!=NULL) {

Node *q=p; p=p->next; delete q; } }

template

void LinkQueue::EnQueue(T x) {

Node *s=new Node; s->data=x;

s->next=NULL; rear->next=s; rear=s; }

template

T LinkQueue::DeQueue() {

if(rear==front) throw"下溢"; Node *p=front->next; int x=p->data;

front->next=p->next; if(p->next==NULL) rear=front; delete p; return x; }

template

void LinkQueue::Trans() { Node *p=front->next; while(p) {

coutdatanext; }; }

void main() { try {

int n,k,t;

cout>n;

cout>k;

cout1000) throw"输入错误!车厢数必须小于1000!"; if(n

srand((unsigned)time(NULL)); int count=0; int *array;

array=new int[n]; int *ifmark;

ifmark=new int[n]; while(count!=n) {

t=rand()%n; if(ifmark[t]!=1) {

array[t]=count+1; ifmark[t]=1; count++; } }

coutLinkQueue *buffer;

buffer=new LinkQueue[k];

TrainPermute(array,buffer,n,k); cout

catch(char*s) {

cout

}

void TrainPermute(int arr[],LinkQueue a[],int n,int k) {

int i=0;

bool aa=1;

while((i

aa=0; //亮点：与非门思想！ for(int m=0;m

if(a[m].GetRear()

a[m].EnQueue(arr[i]); i++; aa=1; break; }

if(a[m].front->next==NULL) {

a[m].EnQueue(arr[i]); aa=1; i++; break; } } }

if(aa==0) //当无法将入轨中队头车厢移至合适缓冲轨中时，程序结束 {

cout

else //当入轨中已经没有车厢时 {

for(int m=0;m

cout

cout

for(int j=0;j

{

if(a[j].GetFront()==newOut)

{

cout}

}

}

}

}

四、总结

本次数据结构实验主要是练习使用队列的思想，我做的是火车重排问题的实验，此实验在课本上有一些讲解，也给出来主要函数TrainPermute()的主要编写思路，减轻了自己的工作量，不过由于此程序的代码比较复杂，在编译调试过程中也很耗费时间，通过设置断点，分步调试，才使得程序没有了bug。例如，由于程序用了较多的循环，包括多重循环，在刚刚写出代码的时候常常陷入死循环，而因为代码冗长，仅仅通过看代码很难找出逻辑上的错误。功夫不负有心人，最后终于用与非门的思想解决了这个死循环问题，并简单优化程序。

总的来说，本程序由于使用了模板类结构，扩展性还算比较好。但是代码部分有些冗长，可读性不算太好。如果要做下一步工作的话，应该是尽量精简代码，使得程序更加具有实用性和可读性。