队列的应用火车车厢重排问题Word下载.docx
《队列的应用火车车厢重排问题Word下载.docx》由会员分享，可在线阅读，更多相关《队列的应用火车车厢重排问题Word下载.docx（11页珍藏版）》请在冰点文库上搜索。
火车车厢重排过程如下：
火车车厢重排算法伪代码如下：
1.分别对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不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个空缓冲轨；
否则车厢无法重排，算法结束；
四、源程序代码
#include<
iostream>
usingnamespacestd;
constMS=100;
template<
classT>
structQNode
{
Tdata;
QNode<
T>
*next;
};
classLiQueue
public:
LiQueue（）;
//构造函数，初始化一个空的链队列
~LiQueue（）;
//析构函数，释放链队列中各结点的存储空间
voidEnQueue（Tx）;
//将元素x入队
TDeQueue（）;
//将队头元素出队
TGetFront（）;
//取链队列的队头元素
TGetRear（）;
boolEmpty（）;
//判断链队列是否为空
*front,*rear;
//队头和队尾指针，分别指向头结点和终端结点
LiQueue<
:
LiQueue（）
QNode<
*s;
s=newQNode<
;
s->
next=NULL;
front=rear=s;
}
~LiQueue（）
QNode<
*p;
while（front）
{
p=front;
front=front->
next;
deletep;
}
voidLiQueue<
EnQueue（Tx）
s->
data=x;
//申请一个数据域为x的结点s
rear->
next=s;
//将结点s插入到队尾rear=s;
TLiQueue<
DeQueue（）
{
intx;
if（rear==front）throw"
下溢"
p=front->
x=p->
data;
//暂存队头元素
front->
next=p->
//将队头元素所在结点摘链
if（p->
next==NULL）rear=front;
//判断出队前队列长度是否为1
deletep;
returnx;
GetFront（）
if（rear!
=front）
returnfront->
next->
GetRear（）
if（rear!
=front）returnrear->
boolLiQueue<
Empty（）
if（front==rear）return0;
elsereturn1;
classTrain
private:
intn,k,th;
public:
Train（）;
voidChongPai（）;
Train:
Train（）
cout<
<
"
请输入火车（货运列车）的车厢个数为：
endl;
cin>
>
n;
请输入转轨站的缓冲轨个数为：
k;
voidTrain:
ChongPai（）
inta[MS];
int>
*b;
b=newLiQueue<
[k+2];
请输入车厢入轨编号次序：
for（inti=0;
i<
i++）
cin>
a[i];
for（i=n-1;
i>
=0;
i--）
b[k].EnQueue（a[i]）;
则进行车厢重排过程如下:
th=1;
while（b[k].Empty（））
intxx=b[k].DeQueue（）;
if（xx==th）
{
cout<
th<
号车厢直接移至出轨"
b[k+1].EnQueue（th）;
th++;
intj=0;
while（b[j].Empty（））
{
intx=b[j].GetFront（）;
if（x==th）
{
cout<
x<
号车厢从"
j+1<
号缓冲轨出轨"
b[j].DeQueue（）;
b[k+1].EnQueue（x）;
j=0;
th++;
}
else
j++;
}
continue;
}
else
intj=0,u=5;
while（b[j].Empty（）&
&
j<
k）
if（xx<
b[j].GetRear（））
j++;
else
{
cout<
xx<
号车厢移至"
号缓冲轨"
b[j].EnQueue（xx）;
u=1;
break;
}
if（u==5&
cout<
b[j].EnQueue（xx）;
if（j==k-1）
\n缓冲轨不够，重排车厢失败\n"
return;
车厢依次出轨的编号为：
while（b[k+1].Empty（））
b[k+1].DeQueue（）<
"
voidmain（）
Traina;
a.ChongPai（）;
五、测试用例
1.当有9个火车车厢，3个缓冲轨道时，运行结果如下：
2.当有12个火车车厢，3个缓冲轨道时，运行结果如下：
3.当有12个火车车厢，5个缓冲轨道，运行结果如下：
4.当有12个火车车厢，7个缓冲轨道时，运行结果如下：
几次测试都表明试验设计的正确性。
六、试验总结
本次试验中，在解决火车车厢重排问题中，结合了最近刚学的队列的知识，并且运用到之前C++语言，很好的解决了这一类问题。
其中，每一个轨道缓冲区就形如一个队列一样，车厢先进缓冲轨道的要先出来，所以把它看成一个队列，运用队列的相关算法，实现高效快速的解决火车车厢重排问题。
通过本次试验，学会了队列的应用，加深了对队列的理解，知道了队列是一种先进队列的后出队列的储存结构。
本次试验让我更好的把书本上的知识运用到具体的例子中来，学会了通过vc6.0来建立队列，以及初始化队列、进队列、出队列等等。
同时也了解到了火车车厢重排问题可以通过队列的相关知识来解决，也体会其中算法的奥妙。
升级会员 