队列的应用

出轨入轨581H1H3H2963742出轨入轨58H1H3H29674321出轨入轨5H1H3H2968754321出轨入轨H1H3H2987654321(a)将369、247依次入缓冲轨(b)将1移至出轨，234移至出轨(c)将8入缓冲轨，5移至出轨(d)将6789移至出轨《算法与数据结构》实验报告实验题目：队列的应用1、实验目的：（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。2、实验内容：火车车厢重排问题。3、实验说明：转轨站示意图如下：火车车厢重排过程如下：火车车厢重排算法伪代码如下：出轨入轨581742963987654321H1H3H2设计分析用队列解决出列问题，这里采用的是顺序队列的存储结构。采用的算法思想是：分别对k个队列初始化；初始化下一个要输出的车厢编号nowOut=1;依次取入轨中的每一个车厢的编号；如果入轨中的车厢编号等于nowOut，则输出该车厢；nowOut++；否则，考察每一个缓冲轨队列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++；如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢，则求小于入轨中第一个车厢编号的最大队尾元素所在队列编号j;如果j存在，则把入轨中的第一个车厢移至缓冲轨j；如果j不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束源程序代码#includeiostream.hconstN=10;templateclassTstructNode1.分别对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不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束；{Tdata;Node*next;};templateclassTclassLinkQueue{public:LinkQueue();~LinkQueue();voidEnQueue(Tx);TDeQueue();TGetQueue();boolEmpty();NodeT*front,*rear;};templateclassTLinkQueueT::LinkQueue(){NodeT*s;s=newNodeT;s-next=NULL;front=rear=s;}templateclassTLinkQueueT::~LinkQueue(){while(front){NodeT*p;p=front-next;deletefront;front=p;}}templateclassTvoidLinkQueueT::EnQueue(Tx){NodeT*s;s=newNodeT;s-data=x;s-next=NULL;rear-next=s;rear=s;}templateclassTTLinkQueueT::DeQueue(){NodeT*p;intx;if(rear==front)throw下溢;p=front-next;x=p-data;front-next=p-next;if(p-next==NULL)rear=front;deletep;returnx;}templateclassTTLinkQueueT::GetQueue(){if(front!=rear)returnfront-next-data;}templateclassTboolLinkQueueT::Empty(){if(front==rear)return1;elsereturn0;}voidOutput(int&minH,int&minQ,LinkQueueintH[],intk,intn){intc;H[minQ].DeQueue();coutmovecarminHfromholdingtrackminQtooutputendl;minH=n+2;for(inti=1;i=k;i++)if(!H[i].Empty()&&(c=H[i].front-next-data)minH){minH=c;minQ=i;}}boolHold(intc,int&minH,int&minQ,LinkQueueintH[],intk){intBestTrack=0,BestLast=0,x;for(inti=1;i=k;i++)if(!H[i].Empty()){x=H[i].rear-data;if(cx&&xBestLast){BestLast=x;BestTrack=i;}}elseif(!BestTrack)BestTrack=i;if(!BestTrack)returnfalse;H[BestTrack].EnQueue(c);coutmovecarcfrominputtoholdingtrackBestTrackendl;if(cminH){minH=c;minQ=BestTrack;}returntrue;}boolRailroad(intp[],intn,intk){LinkQueueint*H;H=newLinkQueueint[k+1];intNowOut=1;intminH=n+1;intminS;for(inti=0;in;i++)if(p[i]==NowOut){coutmovecarp[i]frominputtooutputendl;NowOut++;while(minH==NowOut){Output(minH,minS,H,k,n);NowOut++;}}else{if(!Hold(p[i],minH,minS,H,k))returnfalse;}returntrue;}voidmain(){intp[N],i,j;cout请输入一列火车的车厢总数i和缓冲轨数jendl;cinij;if(i=N)cout输入车厢总数i不能超过(N=10)endl;elsecout输入火车进轨的顺序endl;for(intk=0;ki;k++)cinp[k];Railroad(p,i,j);}测试用例当车厢数为7个缓冲数为3时当车厢数为8个缓冲数为3时当车厢数为8个缓冲数为4时当车厢数为9个缓冲数为3时当车厢数为9个缓冲数为4时当输入车厢总数i超过(N=10)时当缓冲轨数不足时（失败）实验总结通过本次实验我理解了栈和队列的特性以及它们之间的差异，知道在何时使用哪种数据结构。掌握了在顺序栈和链栈上实现栈和队列的进栈出栈、入队列出队等基本运算算法，以及它们的顺序存储结构和链式存储结构。这次实验我参考了书上的报数问题和迷宫问题的求解方法思想，根据火车重排问题伪代码编写，在实验过程中出现了不少问题，同学给了我很大的帮助，同时我也收获了很多。