火车车厢重排问题

实验二：火车车厢重排问题班级：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.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不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束；五.源程序代码：#includestdio.h#includestdlib.h#defineMax20typedefstruct{intdata[Max];intfront,rear;}squeue;voidinitqueue(squeue*&q){q=(squeue*)malloc(sizeof(squeue));q-front=q-rear=0;}voidenqueue(squeue*&q,inte){q-rear=(q-rear+1)%Max;q-data[q-rear]=e;}voiddequeue(squeue*&q){q-front=(q-front+1)%Max;}intgettop(squeue*&q){returnq-data[q-front+1];}intgetrear(squeue*&q){{returnq-data[q-rear];}}voidreset(squeue*&q,squeue*&w1,squeue*&w2,intk){intnowout=1;intn1=0,n2=0;for(inti=0;i50;i++){if(q-data[q-front+1]==nowout){printf(%d号车厢出轨！\t,q-data[q-front+1]);nowout++;dequeue(q);}elseif(gettop(w1)==nowout){printf(%d号车厢出轨！\t,gettop(w1));nowout++;dequeue(w1);}elseif(gettop(w2)==nowout){printf(%d号车厢出轨！\t,gettop(w2));nowout++;dequeue(w2);}else{intc=gettop(q);n1=getrear(w1);n2=getrear(w2);if(n1n2){if(cn1){enqueue(w1,c);dequeue(q);}else{enqueue(w2,c);dequeue(q);}}else{if(cn2){enqueue(w2,c);dequeue(q);}else{enqueue(w1,c);dequeue(q);}}}}}intexamenter(inta[],intk){for(inti=1;i=k;i++){if(a[i]!=i){return0;break;}}}voidmain(){squeue*q,*w1,*w2;initqueue(q);initqueue(w1);initqueue(w2);inta[10],k;label:printf(要输入几个车厢？\n);scanf(%d,&k);if(k=0){printf(请输入正确的车厢号!\n);printf(****************************************************);printf(\n);gotolabel;}label2:printf(输入重排前的序列\n);for(inti=1;i=k;i++){scanf(%d,&a[i]);enqueue(q,a[i]);}intr=examenter(a,k);if(r==0){printf(您的输入车厢号有误!请输入连续自然数:\n);gotolabel2;}elseif(r!=0){printf(重排前的序列为\n);for(i=1;i=k;i++){printf(%d\t,a[i]);}printf(\n);printf(排列后的车厢号为：\n);reset(q,w1,w2,k);}else{printf(我也不知道错哪了？');}}六.测试结果1.输入正确的序列后得到结果如图：2.如果输入的车厢数有误的时候（为负数或零）六、总结本次数据结构实验主要是练习使用队列的思想，我做的是火车重排问题的实验，此实验在课本上有一些讲解，也给出来主要函数TrainPermute()的主要编写思路，减轻了自己的工作量，不过由于此程序的代码比较复杂，在编译调试过程中也很耗费时间，通过设置断点，分步调试，才使得程序没有了bug。例如，由于程序用了较多的循环，包括多重循环，在刚刚写出代码的时候常常陷入死循环，而因为代码冗长，仅仅通过看代码很难找出逻辑上的错误。功夫不负有心人，最后终于用与非门的思想解决了这个死循环问题，并简单优化程序。总的来说，本程序由于使用了模板类结构，扩展性还算比较好。但是代码部分有些冗长，可读性不算太好。如果要做下一步工作的话，应该是尽量精简代码，使得程序更加具有实用性和可读性