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