队列的应用火车车厢重排问题

一、试验课题队列的应用实验目的：（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。二、试验内容(1)问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。车厢的重排工作可以通过国转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重排问题。(2)基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能三、试验分析实验说明：转轨站示意图如下：出轨入轨581742963987654321H1H3H2出轨入轨581H1H3H2963742出轨入轨58H1H3H29674321出轨入轨5H1H3H2968754321出轨入轨H1H3H2987654321(a)将369、247依次入缓冲轨(b)将1移至出轨，234移至出轨(c)将8入缓冲轨，5移至出轨(d)将6789移至出轨火车车厢重排过程如下：火车车厢重排算法伪代码如下：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不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束；四、源程序代码#includeiostreamusingnamespacestd;constMS=100;templateclassTstructQNode{Tdata;QNodeT*next;};templateclassTclassLiQueue{public:LiQueue();//构造函数，初始化一个空的链队列~LiQueue();//析构函数，释放链队列中各结点的存储空间voidEnQueue(Tx);//将元素x入队TDeQueue();//将队头元素出队TGetFront();//取链队列的队头元素TGetRear();boolEmpty();//判断链队列是否为空QNodeT*front,*rear;//队头和队尾指针，分别指向头结点和终端结点};templateclassTLiQueueT::LiQueue(){QNodeT*s;s=newQNodeT;s-next=NULL;front=rear=s;}templateclassTLiQueueT::~LiQueue(){QNodeT*p;while(front){p=front;front=front-next;deletep;}}templateclassTvoidLiQueueT::EnQueue(Tx){QNodeT*s;s=newQNodeT;s-data=x;//申请一个数据域为x的结点ss-next=NULL;rear-next=s;//将结点s插入到队尾rear=s;}templateclassTTLiQueueT::DeQueue(){QNodeT*p;intx;if(rear==front)throw下溢;p=front-next;x=p-data;//暂存队头元素front-next=p-next;//将队头元素所在结点摘链if(p-next==NULL)rear=front;//判断出队前队列长度是否为1deletep;returnx;}templateclassTTLiQueueT::GetFront(){if(rear!=front)returnfront-next-data;}templateclassTTLiQueueT::GetRear(){if(rear!=front)returnrear-data;}templateclassTboolLiQueueT::Empty(){if(front==rear)return0;elsereturn1;}classTrain{private:intn,k,th;public:Train();voidChongPai();};Train::Train(){cout请输入火车(货运列车）的车厢个数为：endl;cinn;cout请输入转轨站的缓冲轨个数为：endl;cink;}voidTrain::ChongPai(){inta[MS];LiQueueint*b;b=newLiQueueint[k+2];cout请输入车厢入轨编号次序：endl;for(inti=0;in;i++)cina[i];for(i=n-1;i=0;i--)b[k].EnQueue(a[i]);cout则进行车厢重排过程如下:endl;th=1;while(b[k].Empty()){intxx=b[k].DeQueue();if(xx==th){coutth号车厢直接移至出轨endl;b[k+1].EnQueue(th);th++;intj=0;while(b[j].Empty()){intx=b[j].GetFront();if(x==th){coutx号车厢从j+1号缓冲轨出轨endl;b[j].DeQueue();b[k+1].EnQueue(x);j=0;th++;}elsej++;}continue;}else{intj=0,u=5;while(b[j].Empty()&&jk){if(xxb[j].GetRear())j++;else{coutxx号车厢移至j+1号缓冲轨endl;b[j].EnQueue(xx);u=1;break;}}if(u==5&&jk){coutxx号车厢移至j+1号缓冲轨endl;b[j].EnQueue(xx);}if(j==k-1){cout\n缓冲轨不够，重排车厢失败\n;return;}}}cout车厢依次出轨的编号为：;while(b[k+1].Empty())coutb[k+1].DeQueue();coutendl;}voidmain(){Traina;a.ChongPai();}五、测试用例1.当有9个火车车厢，3个缓冲轨道时，运行结果如下：2.当有12个火车车厢，3个缓冲轨道时，运行结果如下：3.当有12个火车车厢，5个缓冲轨道，运行结果如下：4.当有12个火车车厢，7个缓冲轨道时，运行结果如下：几次测试都表明试验设计的正确性。六、试验总结本次试验中，在解决火车车厢重排问题中，结合了最近刚学的队列的知识，并且运用到之前C++语言，很好的解决了这一类问题。其中，每一个轨道缓冲区就形如一个队列一样，车厢先进缓冲轨道的要先出来，所以把它看成一个队列，运用队列的相关算法，实现高效快速的解决火车车厢重排问题。通过本次试验，学会了队列的应用，加深了对队列的理解，知道了队列是一种先进队列的后出队列的储存结构。本次试验让我更好的把书本上的知识运用到具体的例子中来，学会了通过vc6.0来建立队列，以及初始化队列、进队列、出队列等等。同时也了解到了火车车厢重排问题可以通过队列的相关知识来解决，也体会其中算法的奥妙。