火车车厢重问题.docVIP

实验二：火车车厢重排问题 班级：2010级数学班 学号:201008101127 姓名：裴志威 一.问题描述： 一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n,货运列车按照第n站至第1站的顺序经过这些车站。车厢编号与他们的目的地一样。为了便于从列车上卸掉相应的车厢，必须重排车厢顺序，使得各车厢从前往后按编号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 不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束； 五.源程序代码： #includestdio.h #includestdlib.h #define Max 20 typedef struct { int data[Max]; int front,rear; }squeue; void initqueue(squeue *q) { q=(squeue *)malloc(sizeof(squeue)); q-front=q-rear=0; } void enqueue(squeue *q,int e) { q-rear=(q-rear+1)%Max; q-data[q-rear]=e; } void dequeue(squeue *q) { q-front=(q-front+1)%Max; } int gettop(squeue *q) { return q-data[q-front+1]; } int getrear(squeue *q) { { return q-data[q-rear]; } } void reset(squeue *q,squeue *w1,squeue *w2,int k) { int nowout=1; int n1=0,n2=0; for(int i=0;i50;i++) { if(q-data[q-front+1]==nowout) { printf(%d号车厢出轨！\t,q-data[q-front+1]); nowout++; dequeue(q); } else if(gettop(w1)==nowout) { printf(%d号车厢出轨！\t,gettop(w1)); nowout++; dequeue(w1); } else if(gettop(w2)==nowout) { printf(%d号车厢出轨！\t,gettop(w2)); nowout++;