《队列的应用火车车厢重排问题》由会员分享，可在线阅读，更多相关《队列的应用火车车厢重排问题（13页珍藏版）》请在金锄头文库上搜索。
1、一、试验课题队列的应用实验目的：(1) 掌握队列的特点及其存储方法；(2) 掌握队列的常见算法和程序实现。二、试验容(1) 问题描述：一列货运列车共有 n节车厢，每节车厢将停放在不同的车 站。假定n个车站的编号分别为1n，即货运列车按照第n站至第1站的次序经 过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相 同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必 须重新排列它们。车厢的重排工作可以通过国转轨站完成。 在转轨站中有一个入 轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先 出飞方式运作，设计算法解决火车车厢重排问题。(2)
2、 基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨; 设计并实现车厢重排算法；分析算法的时间性能、试验分析实验说明：转轨站示意图如下：Hi581742963H3:987654321LH2581-963H1F1 J入轨H3丨岀轨 IH2(d)将6789移至出轨入轨H3岀轨742jH2(a)将369、247依次入缓冲轨196iH15! 54321入轨H3i岀轨871H2(c)将8入缓冲轨，5移至岀轨11961 H1 5811 4321入轨H3:岀轨171H2出)轨将1移至出轨，234移至:H1；1 987654321火车车厢重排算法伪代码如下:1. 分别对k个队列初始化；2. 初始化下
3、一个要输出的车厢编号nowOut = 1;3. 依次取入轨中的每一个车厢的编号；3.1如果入轨中的车厢编号等于 nowOut，贝U3.1.1输岀该车厢；3.1.2 nowOut+;3.2否则，考察每一个缓冲轨队列for (j=1; jv=k; j+ )3.2.1取队列j的队头元素c；3.2.2 如果 c=nowOut，贝U3.2.2.1将队列j的队头元素出队并输出；3.2.2.2 nowOut+ ；3.3如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢，贝U3.3.1求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j;3.3.2如果j存在，则把入轨中的第一个车厢移至缓冲轨j ；3.3
4、.2如果j不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个 空缓冲轨；否则车厢无法重排，算法结束；四、源程序代码#in cludeusing n amespace std;const MS=100;template struct QNodeT data;QNode *n ext;template class LiQueuepublic:LiQueue( ); /构造函数，初始化一个空的链队列LiQueue(); /析构函数，释放链队列中各结点的存储空间void EnQueue(T x); / 将元素 x 入队T DeQueue( ); / 将队头元素出队T GetFro nt( )
5、; /取链队列的队头元素T GetRear();bool Empty( ); /判断链队列是否为空QNode *fron t, *rear; /队头和队尾指针，分别指向头结点和终端结点;template LiQueue:LiQueue()QNode *s;s=new QNode;s-n ext=NULL;fr on t=rear=s;template LiQueue:LiQueue()QNode *p;while(fro nt)p=fron t;fr ont=front-n ext;delete p;template void LiQueue:E nQueue(T x)QNode *s;s=n
6、ew QNode;s-data=x; /申请一个数据域为x的结点ss-n ext=NULL;rear-next=s; /将结点 s 插入至U队尾 rear=s;template T LiQueue:DeQueue()QNode *p; int x;if (rear=fro nt) throw 下溢;p=front-n ext;x=p-data; /暂存队头元素fron t- next=p- next; /将队头元素所在结点摘链if (p- next=NULL) rear=fro nt; /判断出队前队列长度是否为 1delete p;return x;template T LiQueue:Ge
7、tFro nt()if (rear!=fro nt)retur n fron t- n ext-data;template T LiQueue:GetRear()if(rear!=fr on t)retur n rear-data;template bool LiQueue:Empty()if(fron t=rear) return 0;else return 1;class Trainprivate :int n ,k,th;public :Train(); void Chon gPai();Trai n:Trai n()coutvv请输入火车(货运列车)的车厢个数为：endl;cinn;c
8、outvv请输入转轨站的缓冲轨个数为： k;void Trai n:Ch on gPai()int aMS;LiQueue*b;b=new LiQueuev in tk+2;coutvv请输入车厢入轨编号次序：vvendl;for(int i=0;ivn;i+)cin ai;for(i=n-1;i=0;i-)bk.E nQueue(ai);coutvv则进行车厢重排过程如下:vvendl;th=1;while(bk.Empty()int xx=bk.DeQueue();if(xx=th)coutvvthvv号车厢直接移至出轨vvendl;bk+1.E nQueue(th);th+;int j=
9、0;while(bj.Empty()int x=bj.GetFro nt();if(x=th)coutvvxvv号车厢从vvj+1vv号缓冲轨出轨vvendl;bj.DeQueue();bk+1.E nQueue(x);j=O;th+;elsej+;con ti nue;elseint j=0,u=5;while(bj.Empty ()&jvk)if(xxb|j.GetRear()j+；elsecoutvvxxvv号车厢移至j+1号缓冲轨endl; bj.E nQueue(xx);u=1;break;if(u=5&jk)coutvvxxvv号车厢移至j+1号缓冲轨endl; bj.E nQue
10、ue(xx);if(j=k-1)coutn缓冲轨不够，重排车厢失败n;return;coutvv车厢依次出轨的编号为：;while(bk+1.Empty()coutvbk+1.DeQueue()vv;coutvve ndl;void mai n()Train a;a.Ch on gPai();-Jnl v序下次如机岀岀歳丸出出出出酋DI1 编 ft coY X1t:_l_l1- 2- 2- .al-m-Dn-nr-D- 劭2福至至至至至至iF 7 Er HP rn npn ru.T -nH-r -MHr Fnr. mH.rrp.nTr HT. -DH -DZL -mT w 亍JrJTJTff/
11、r阳/F用井幷用庫库印花 小 544IS$r 薛 R;IJlLllral?al?alpo.pqp4po 苕瓦占吾 ITOX-言 SJ臨Kt至zhg 畑 Mhhl出 y 次an 厢“五、测试用例1当有9个火车车厢，3个缓冲轨道时，运行结果如下:亡 *C : kPr QgTrui Filicx-osoEt Vi su-kl S-tudio j ecl.s54ndsA；ad.Debug：G4&ds asd. cz e2.当有12个火车车厢，3个缓冲轨道时，运行结果如下:3.当有12个火车车厢，5个缓冲轨道，运行结果如下:11ill址中轨旦请输人火车（贺运列车）的车頤个数为I誇输人转轨站的緩冲軌个数为
12、1z .匚：IPlFi 1 Hcir-ozof t Vi u-aJ. Stn.di. oHyPro j ae iLs54nd! =-a.cd.f De&-4a.ds as. ex c请输人车用入轨編号次序*57134 10 92 11 8 12则进押至朋重肖1淨车瞬至卜缓冲轨不够，董排车厢失败Picss anky to cant ious4.当有12个火车车厢，7个缓冲轨道时，运行结果如下:*C:XFrogr输入火车货运列弃）的弃厢个数为u F i_es Viicrosoft i suslI S tudi olyFrojecf.s54&dsas:dfDebufV5.,.612口言！F厢1 2tr- n- ilihhh ;ti -勢肌出出出轨衣出出出岀ntAini为on 的-hce专出出出花梓 店374厨厢两厢厢厢甫厢厢厢厢厢厢ffl厢厢厢厢厢原昴康汐2 7丿/ 牛再Fm4JJLJF1T4L4LUJFF4IJ-4-JJ-41J4UHJF-输输？“号2-S号苕卫y直10重至f2全也创百至舀laml韦号已詡恫多耳多吕wa多互丑吉4 5 4 ra总3 4 2 3.曹车討车车鑫车车车车车车车车车车车咅总卡号
