队列的应用火车车厢重排问题Word下载.docx

1、火车车厢重排过程如下：火车车厢重排算法伪代码如下：1. 分别对k个队列初始化；2. 初始化下一个要输出的车厢编号nowOut = 1;3. 依次取入轨中的每一个车厢的编号；3.1 如果入轨中的车厢编号等于nowOut，则 3.1.1 输出该车厢； 3.1.2 nowOut+；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.2 nowOut+；3.3 如果入轨和缓冲轨的队头元素没有编号为nowOut的车厢，则 3.3.1 求小于入

2、轨中第一个车厢编号的最大队尾元素所在队列编号j;3.3.2 如果 j 存在，则把入轨中的第一个车厢移至缓冲轨 j；3.3.2 如果 j 不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；否则车厢无法重排，算法结束；四、 源程序代码#includeusing namespace std;const MS=100;template struct QNode T data; QNode *next;class LiQueue public: LiQueue（ ）; /构造函数，初始化一个空的链队列 LiQueue（ ）; /析构函数，释放链队列中各结点的存储空间 void EnQ

3、ueue（T x）; /将元素x入队 T DeQueue（ ）; /将队头元素出队 T GetFront（ ）; /取链队列的队头元素 T GetRear（）; bool Empty（ ）; /判断链队列是否为空 *front, *rear; /队头和队尾指针，分别指向头结点和终端结点LiQueue:LiQueue（ ） QNode *s;s=new QNodenext=NULL;front=rear=s;LiQueue（ ） QNode next;delete p; void LiQueuedata=x; /申请一个数据域为x的结点s rear-next=s; /将结点s插入到队尾 rear

4、=s;T LiQueue x=p-data; /暂存队头元素 front-next=p- /将队头元素所在结点摘链 if （p-next=NULL） rear=front; /判断出队前队列长度是否为1 delete p; return x;GetFront（） if （rear!=front） return front-next-GetRear（） if（rear!=front）return rear-bool LiQueueEmpty（ ） if（front=rear） return 0;else return 1;class Train private : int n,k,th; pub

5、lic : Train（）;void ChongPai（）;Train:Train（） coutn;请输入转轨站的缓冲轨个数为：k;void Train:ChongPai（） int aMS;int*b; b=new LiQueuek+2;请输入车厢入轨编号次序： for（int i=0;iai; for（i=n-1;i=0;i-） bk.EnQueue（ai）;则进行车厢重排过程如下: th=1; while（bk.Empty（） int xx=bk.DeQueue（）; if（xx=th） coutth号车厢直接移至出轨 bk+1.EnQueue（th）; th+; int j=0; wh

6、ile（bj.Empty（） int x=bj.GetFront（）; if（x=th） coutx号车厢从j+1号缓冲轨出轨 bj.DeQueue（）;bk+1.EnQueue（x）; j=0;th+; else j+; continue; else int j=0,u=5; while（bj.Empty（）&jk） if（xxbj.GetRear（） j+; else coutxx号车厢移至号缓冲轨 bj.EnQueue（xx）; u=1;break; if（u=5& cout bj.EnQueue（xx）; if（j=k-1）n缓冲轨不够，重排车厢失败nreturn;车厢依次出轨的编号为

7、： while（bk+1.Empty（）bk+1.DeQueue（） void main（） Train a;a.ChongPai（）;五、 测试用例1.当有9个火车车厢，3个缓冲轨道时，运行结果如下：2. 当有12个火车车厢，3个缓冲轨道时，运行结果如下：3. 当有12个火车车厢，5个缓冲轨道，运行结果如下：4. 当有12个火车车厢，7个缓冲轨道时，运行结果如下：几次测试都表明试验设计的正确性。六、 试验总结本次试验中，在解决火车车厢重排问题中，结合了最近刚学的队列的知识，并且运用到之前C+语言，很好的解决了这一类问题。其中，每一个轨道缓冲区就形如一个队列一样，车厢先进缓冲轨道的要先出来，所以把它看成一个队列，运用队列的相关算法，实现高效快速的解决火车车厢重排问题。通过本次试验，学会了队列的应用，加深了对队列的理解，知道了队列是一种先进队列的后出队列的储存结构。本次试验让我更好的把书本上的知识运用到具体的例子中来，学会了通过vc6.0来建立队列，以及初始化队列、进队列、出队列等等。同时也了解到了火车车厢重排问题可以通过队列的相关知识来解决，也体会其中算法的奥妙。