火车车厢重排实验报告

1、本文格式为Word版，下载可任意编辑 火车车厢重排实验报告 东华理工大学长江学院 数据结构课程设计报告 学号： 姓名： 刘 曹 杰 指导老师：刘自强 2022年1月3日 队列的应用举例火车车厢重排 一、试验分析 一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1 n，即货运列车依照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站（目的地）的编号一致，使各车厢从前至后按编号1到n的次序排列，这样，在每个车站只需卸掉结果一节车厢即可。所以，给定任意次序的车厢，务必重新排列他们。可以通过转轨站完成车厢的重排工作，在转轨站中有一个入轨、

2、一个出轨和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、车厢之前，因此，把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

4、(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

5、.2nowOut+； 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.2nowOut+； 3.3假如入轨和缓冲轨的对头元素没有编号为nowOut的车厢，则 3.3.1求小雨入轨中第一个车厢编号的最大队尾元素所在队列编号j； 3.3.2假如j存在，则把入轨中的第一个车厢移至缓冲轨j； 3.3.2 假如j不存在，但有多余一个空缓冲轨，则把入轨第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法终止； 二、程序分析 1. 存储结构 本程序采用单链表结构，具体

6、为链队列结构，使用队列结构的先进先出原则可以较好地处理车厢重排问题。链队列结构示意图如下： . front a1 a2 . . . an rear 2. 关键算法分析 一、本程序的关键算法主要为处理车厢重排问题的函数TrainPermute()，其伪代码如下： ? void TrainPermute(): 1.?初始化条件:计数器i=0,与非门aa=1 2.?判断是否能入轨while(用in判断是否n节车厢都入缓冲轨)(用aa=1判断是否有适合的缓冲轨可入) 2.1将aa置空； 2.2用for循环，依次取入入轨中的每一个车厢的编号进入适合的缓冲轨； ? 2.2.1假如缓冲轨中尾指针比进入缓冲轨

7、元素小，则 进入该缓冲轨； 计数器i+1; 有适合缓冲轨，将aa变为真; 跳出for循环并进入while循环； 2.2.2假如缓冲轨中第一个元素为空，则 ? 进入缓冲轨成为第一个元素； 计数器i+1; 有适合缓冲轨，将aa变为真; ? 跳出for循环并进入while循环； 2.3 用aa判断是否有进入适合的缓冲轨 ? aa=0即没有适合的缓冲轨，则 输出无法排列； aa=1即有适合的缓冲轨，则 遍历缓冲轨， 输出每个缓冲轨按顺序存储的车厢； 按从小到大的顺序出轨 for(引入输出轨计数器newOut=1;newOutn; newOut+1;) ?newOut与每个队列的头元素对比若相等，则 ?

8、 元素出队； ?输出显示； ?具体代码如下： void TrainPermute(int arr,LinkQueueint a,int n,int k) int i=0; bool aa=1; while(in)(aa) /当入轨中有车厢时 aa=0; /亮点：与非门思想！ for(int m=0;mk;m+) if(am.GetRear()arri) am.EnQueue(arri); i+; aa=1; break; if(am.front-next=NULL) am.EnQueue(arri); aa=1; i+; break; if(aa=0) /当无法将入轨中队头车厢移至适合缓冲轨中

9、时，程序终止 cout车厢无法重排,算法终止endl; else /当入轨中已经没有车厢时 for(int m=0;mk;m+) cout第(m+1)个缓冲轨的列车编号; am.Trans(); coutendl; cout火车车厢出轨顺序为:endl; for(int newOut=1;newOut=n;newOut+) for(int j=0;jk;j+) /扫描缓冲轨，将其队头元素依次由小到大输出 if(aj.GetFront()=newOut) coutaj.DeQueue() ; 二、主函数伪代码如下： 1. 输入n与k值，若输入值错误，则程序终止； 2. 通过循环结构为数组arra

10、y赋值，具体分析见代码； 3. 输出入轨中火车车厢号码排列； 4. 调用TrainPermute()函数； 三、为array随机赋值的根本思想为：设置计数器count=0，设置数组ifmark来标记array赋值状况，依次将1至n等n个数随机赋给array，其中，若arrayt未被赋值，即ifmarkt=0，则将值赋给arrayt，计数器加一；若arrayt已被赋值，即ifmarkt=1，则重新开始循环。 srand(unsigned)time(NULL); int count=0; int *array; array=new intn; int *ifmark; ifmark=new int

11、n; while(count!=n) t=rand()%n; if(ifmarkt!=1) arrayt=count+1; ifmarkt=1; count+; 三、试验过程 程序代码及运行结果 #includeiostream #includectime using namespace std; const int QueueSize=1000; templateclass T struct Node ?T data; ?NodeT *next; ; templateclass T class LinkQueue? /链队列模板类? public: ?LinkQueue(); /构造函数 ?

12、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,LinkQueueT a,in

13、t n,int k); private: ?NodeT *front,*rear; ; templateclass T LinkQueueT:LinkQueue() ?NodeT *s=new NodeT; ?s-next=NULL; ?front=rear=s; templateclass T LinkQueueT:LinkQueue() ?NodeT *p=front; ?while(p!=NULL) ? NodeT *q=p; p=p-next; delete q; ? templateclass T void LinkQueueT:EnQueue(T x) ?NodeT *s=new

14、NodeT; ?s-data=x; ?s-next=NULL; ?rear-next=s; ?rear=s; templateclass T T LinkQueueT:DeQueue() ?if(rear=front) throw下溢; ?NodeT *p=front-next; ?int x=p-data; ?front-next=p-next; ?if(p-next=NULL) rear=front; ?delete p; ?return x; templateclass T void LinkQueueT:Trans() NodeT *p=front-next; while(p) ?co

15、utp-data ; ?p=p-next; ; void main() ?try ? int n,k,t; cout请输入火车车厢数n（n请小于1000）: nn=; cinn; ? cout请输入缓冲轨数k：nk=; cink; cout系统将对n个数字随机排列入轨，并重新出轨。n; if(n1000) throw输入错误!车厢数务必小于1000!; if(n=0) throw输入错误!车厢数务必大于0!; if(k=0) throw输入错误!缓冲轨数务必大于0!; srand(unsigned)time(NULL); int count=0; int *array; array=new i

16、ntn; int *ifmark; ifmark=new intn; while(count!=n) t=rand()%n; if(ifmarkt!=1) ?arrayt=count+1; ?ifmarkt=1; ?count+; cout火车车厢入轨顺序为:endl; for(int i=0;in;i+) coutarrayi ; coutendl; LinkQueueint *buffer; buffer=new LinkQueueintk; TrainPermute(array,buffer,n,k); coutendl; ? ?catch(char*s) ? coutsendl; ?

17、void TrainPermute(int arr,LinkQueueint a,int n,int k) ?int i=0; ? ?bool aa=1; ? ?while(in)(aa) /当入轨中有车厢时 ? aa=0;? /亮点：与非门思想！ for(int m=0;mk;m+) if(am.GetRear()arri) ?am.EnQueue(arri); ?i+; ?aa=1; ?break; if(am.front-next=NULL) ?am.EnQueue(arri); ?aa=1; ?i+; ?break; ? ?if(aa=0)/当无法将入轨中队头车厢移至适合缓冲轨中时，程

18、序终止 ? cout车厢无法重排,算法终止endl; ? ?else ?/当入轨中已经没有车厢时 ? for(int m=0;mk;m+) cout第(m+1)个缓冲轨的列车编号; am.Trans(); coutendl; cout火车车厢出轨顺序为:endl; for(int newOut=1;newOut=n;newOut+) for(int j=0;jk;j+)/扫描缓冲轨，将其队头元素依次由小到大输出 ?if(aj.GetFront()=newOut) ? coutaj.DeQueue() ; ? ? ? 四、总结 本次数据结构试验主要是练习使用队列的思想，我做的是火车重排问题的试验，此试验在课本上有一些讲解，