车厢重排问题实验报告.docx

文档介绍：实验报告

    利用队列结构实现车厢重排问题。车厢重排问题如下:
一列货车共有n节车厢,每个车厢都有自己的编号,编号范围从1~n。给定任意次序的车厢,的车厢编号。
提示:
一列火车的每个车厢按顺序从入轨进入不同缓冲轨,缓冲轨重排后的进入出轨,重新编排成一列货车。比如:编号为3的车厢进入缓冲轨1,则下一个编号小于3的车厢则必须进入下一个缓冲轨2,而编号大于3的车厢则进入缓冲轨1,排在3号车厢的后面,这样,出轨的时候才可以按照从小到大的顺序重新编排。
 
2. 程序分析
存储结构
本程序采用单链表结构,具体为链队列结构,使用队列结构的先进先出原则可以较好地处理车厢重排问题。链队列结构示意图如下:

  关键算法分析
一、本程序的关键算法主要为处理车厢重排问题的函数TrainPermute(),其伪代码如下:
 
void TrainPermute():
1.       初始化条件:计数器i=0,与非门aa=1
2.       判断是否能入轨while(用i<n判断是否n节车厢都入缓冲轨)&&(用aa=1判断是否有合适的缓冲轨可入)
;
,依次取入入轨中的每一个车厢的编号进入合适的缓冲轨;
  ,则
   进入该缓冲轨;
   计数器i+1;
   有合适缓冲轨,将aa变为真;
   跳出for循环并进入while循环;
  ,则
  进入缓冲轨成为第一个元素;
   计数器i+1;
   有合适缓冲轨,将aa变为真;
              跳出for循环并进入while循环;
   用aa判断是否有进入合适的缓冲轨
        aa=0即没有合适的缓冲轨,则
          输出无法排列;
        aa=1即有合适的缓冲轨,则
          ,
                输出每个缓冲轨按顺序存储的车厢;
          按从小到大的顺序出轨
                for(引入输出轨计数器newOut=1;newOut<n; newOut+1;)
                    newOut与每个队列的头元素比较若相等,则
                    元素出队;
                    输出显示;
 
 
具体代码如下:
void TrainPermute(int arr[],LinkQueue<int> a[],int n,int k)
{
       int i=0;
      
       bool aa=1;
      
       while((i<n)&&(aa))          //当入轨中有车厢时
       {
              for(int m=0;m<k;m++)
              {  
                     if(a[m].GetRear()<arr[i])