火车车厢重排问题

【www.nmgzasp.com--2010高考】

实验二：火车车厢重排问题

班级：2010级数学班 学号:201008101127 姓名：裴志威

一.问题描述：

一列货运列车共有n节车厢，每节车厢将停放在不同的车站，

火车车厢重排问题

的顺序经过这些车站。车厢编号与他们的目的地一样。为了便于从列车上卸掉相应的车厢，必须重排车厢顺序，使得各车厢

从前往后按编号1到n的次序排列。当所有车厢按照这种次序排列时，在每个车站只需卸掉最后一个车厢即可。我们在一个

转轨站里完成重拍的工作，在转轨站有一个入轨，一个出轨和k个缓冲轨（位于入轨和出轨之间）。

二.基本要求：

（1）：设计存储结构表示n个车厢，k个缓冲轨以及入轨和出轨，

（2）设计并实现车厢重排算法，

（3）分析算法的时间性能。

三.算法描述：

为了重排车厢，需从前往后依次检查入轨上的所有车厢。如果正在检查的车厢就是下一个满足要求的车厢，可以直接把它放

到出轨上。否则，则把它移动到缓冲轨上，直到按输出顺序要求轮到它的时候才可以将他放到出轨上。缓冲轨是按照FILO

的方式使用的，因为车厢的进出都是在缓冲轨的顶端进行的。

在重排车厢过程中，仅允许以下活动：

1、车厢可以从入轨的前部移动到一个缓冲轨的顶部或者是出轨的左端

2、车厢可以从一个缓冲轨的顶部移动到出轨的左端

在将车厢放入缓冲轨的过程中，应该注意：有空的可以优先放，没空的缓冲轨时，要将新的车厢放在满足以下条件的缓冲轨

中：在缓冲轨的顶部车厢编号比新车厢的编号大的所有缓冲轨中选择顶部车厢编号最小的那个。

四.伪代码：

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

2. 初始化下一个要输出的车厢编号nowOut = 1;

3. 依次取入轨中的每一个车厢的编号；

3.1 如果入轨中的车厢编号等于nowOut，则

3.1.1 输出该车厢；

3.1.2 nowOut++；

3.2 否则，考察每一个缓冲轨队列

for (j=1; j<=k; j++)

3.2.1 取队列 j 的队头元素c；

3.2.2 如果c=nowOut，则

3.2.2.1 将队列 j 的队头元素出队并输出；

3.2.2.2 nowOut++；

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

3.3.1 求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j;

3.3.2 如果 j 存在，则把入轨中的第一个车厢移至缓冲轨 j；

3.3.2 如果 j 不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束；

五.源程序代码：

#include

#include

#define Max 20

typedef struct

int data[Max]; int front,rear;

}squeue;

void initqueue(squeue *&q)

{

}

void enqueue(squeue *&q,int e)

{

}

void dequeue(squeue *&q)

{

}

int gettop(squeue *&q)

{

}

int getrear(squeue *&q)

{

}

void reset(squeue *&q,squeue *&w1,squeue *&w2,int k)

{

int nowout=1; int n1=0,n2=0; for(int i=0;i<50;i++) { if(q->data[q->front+1]==nowout) { { } return q->data[q->rear]; return q->data[q->front+1]; q->front=(q->front+1)%Max; q->rear=(q->rear+1)%Max; q->data[q->rear]=e; q=(squeue *)malloc(sizeof(sq第一文库网ueue)); q->front=q->rear=0;

} nowout++; dequeue(q); else if(gettop(w1)==nowout) { printf("%d号车厢出轨！\t",gettop(w1)); nowout++; dequeue(w1); } else if(gettop(w2)==nowout) { } else { int c=gettop(q); n1=getrear(w1); n2=getrear(w2); if(n1>n2) { if(c>n1) { } else { enqueue(w2,c); dequeue(q); enqueue(w1,c); dequeue(q); printf("%d号车厢出轨！\t",gettop(w2)); nowout++; dequeue(w2); } else { } if(c>n2) { enqueue(w2,c); dequeue(q);

}

else { enqueue(w1,c); dequeue(q); } } } }

int examenter(int a[],int k)

{

}

void main()

{

squeue *q,*w1,*w2; initqueue(q); initqueue(w1); initqueue(w2); int a[10],k; label: printf("要输入几个车厢？\n"); for(int i=1;i<=k;i++) { } if(a[i]!=i) { } return 0; break; scanf("%d",&k); if(k<=0) { } printf("请输入正确的车厢号!\n"); printf("****************************************************"); printf("\n"); goto label;

} for(int i=1;i<=k;i++) { } int r=examenter(a,k); if(r==0) { } else if(r!=0) { } else { } printf("我也不知道错哪了？""); printf("重排前的序列为\n"); for(i=1;i<=k;i++) { } printf("\n"); printf("排列后的车厢号为：\n"); reset(q,w1,w2,k); printf("%d\t",a[i]); printf("您的输入车厢号有误! 请输入连续自然数:\n"); goto label2; scanf("%d",&a[i]); enqueue(q,a[i]);

六.测试结果

1.输入正确的序列后得到结果如图：

2.如果输入的车厢数有误的时候（为负数或零）

六、总结

本次数据结构实验主要是练习使用队列的思想，我做的是火车重排问题的实验，此实验在课本上有一些讲解，也给出来主要函数TrainPermute()的主要编写思路，减轻了自己的工作量，不过由于此程序的代码比较复杂，在编译调试过程中也很耗费时间，通过设置断点，分步调试，才使得程序没有了bug，

资料大全

总的来说，本程序由于使用了模板类结构，扩展性还算比较好。但是代码部分有些冗长，可读性不算太好。如果要做下

一步工作的话，应该是尽量精简代码，使得程序更加具有实用性和可读性

本文来源：http://www.nmgzasp.com/gk/43832/