文档介绍:实验报告
实验要求
利用队列结构实现车厢重排问题。车厢重排问题如下:
一列货车共有n节车厢,每个车厢都有自己的编号,编号范围从1~n。给定任意次序的车厢,的车厢编号。
提示:
一列火车的每个车厢按顺序从入轨进入不同缓冲轨,缓冲轨重实验报告
实验要求
利用队列结构实现车厢重排问题。车厢重排问题如下:
一列货车共有n节车厢,每个车厢都有自己的编号,编号范围从1~n。给定任意次序的车厢,的车厢编号。
提示:
一列火车的每个车厢按顺序从入轨进入不同缓冲轨,缓冲轨重排后的进入出轨,重新编排成一列货车。比如:编号为3的车厢进入缓冲轨1,则下一个编号小于3的车厢则必须进入下一个缓冲轨2,而编号大于3的车厢则进入缓冲轨1,排在3号车厢的后面,这样,出轨的时候才可以按照从小到大的顺序重新编排。
本程序采用单链表结构,具体为链队列结构,使用队列结构的先进先出原则可以较好地处理车厢重排问题。链队列结构示意图如下:
datancxt+J
,-
一、本程序的关键算法主要为处理车厢重排问题的函数TrainPermute(),其伪代码如下:
voidTrainPermute():
初始化条件:计数器i=0,与非门aa=1
判断是否能入轨while(用i<n判断是否n节车厢都入缓冲轨)&&(用aa=1判断是否有合适的缓冲轨可入)
;
,依次取入入轨中的每一个车厢的编号进入合适的缓冲轨;
,则
进入该缓冲轨;
计数器i+1;
有合适缓冲轨,将aa变为真;
跳出for循环并进入while循环;
,则
进入缓冲轨成为第一个元素;
计数器i+1;
有合适缓冲轨,将aa变为真;
跳出for循环并进入while循环;
=0即没有合适的缓冲轨,则
输出无法排列;
=1即有合适的缓冲轨,,输出每个缓冲轨按顺序存储的车厢;
for(引入输出轨计数器newOut=1;newOut<n;newOut+1;)newOut与每个队列的头元素比较若相等,则元素出队;输出显示;
具体代码如下:voidTrainPermute(intarr[],LinkQueue<int>a[],intn,intk){
inti=0;
boolaa=1;
while((i<n)&&(aa)) 〃当入轨中有车厢时
{for(intm=0;m<k;m++){if(a[m].GetRear()<arr[i]){a[m].EnQueue(arr[i]);i++;}if(a[m].front->next==NULL){a[m].EnQueue(arr[i]);aa=1;i++;break;}}}if(aa==0) 〃当无法将入轨中队头车厢移至合适缓冲轨中时,程序结束
{cout<<"车厢无法重排,算法结束"<<endl;}else 〃当入轨中已经没有车厢时
{for(intm=0;m<k;m++)
{
cout<<"第"<<(m+1)<<"个缓冲轨的列车编号