文档文库
手机版
投诉建议
热门搜索： 心得体会 演讲稿 思想汇报
首页 > 队列的应用火车车厢重排问题

队列的应用火车车厢重排问题

发布时间：   来源：文档文库   
小 中 大
字号：
手机查看

一、试验课题
队列的应用
实验目的：
（1）掌握队列的特点及其存储方法；（2）掌握队列的常见算法和程序实现。


二、试验内容
(1问题描述：一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n，即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只要卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列它们。车厢的重排工作可以通过国转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨，缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出飞方式运作，设计算法解决火车车厢重排问题。
(2基本要求：设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法；分析算法的时间性能



三、试验分析

实验说明：
转轨站示意图如下：

H1
581742963
入轨
H3H2

987654321
出轨


火车车厢重排过程如下：


963
H1
581

H3
出轨入轨
742

H2

(a将369、247依次入缓冲轨
96
H1554321
H3
出轨入轨
87
H2
将8入缓冲轨，5移至出轨(c

96H1
58
入轨
H37H2
4321
出轨
(b将1移至出轨，234移至
出轨
H1

入轨
H3H2
(d将6789移至出轨
987654321
出轨
火车车厢重排算法伪代码如下：

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不存在，但有多于一个空缓冲轨，则把入轨中的第一个车厢移至一个
空缓冲轨；否则车厢无法重排，算法结束；



四、源程序代码
#includeusingnamespacestd;constMS=100;
templatestructQNode{
Tdata;
QNode*next;};
templateclassLiQueue{
public:
LiQueue(;//构造函数，初始化一个空的链队列
~LiQueue(;//析构函数，释放链队列中各结点的存储空间voidEnQueue(Tx;//将元素x入队TDeQueue(;//将队头元素出队
TGetFront(;//取链队列的队头元素TGetRear(;
boolEmpty(;//判断链队列是否为空
QNode*front,*rear;//队头和队尾指针，分别指向头结点和终端结点};
templateLiQueue::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的结点ss->next=NULL;
rear->next=s;//将结点s插入到队尾rear=s;}
template
TLiQueue::DeQueue({
QNode*p;intx;
if(rear==frontthrow"下溢";p=front->next;
x=p->data;//暂存队头元素
front->next=p->next;//将队头元素所在结点摘链
if(p->next==NULLrear=front;//判断出队前队列长度是否为1deletep;returnx;}
template
TLiQueue::GetFront({
if(rear!=front
returnfront->next->data;}
templateTLiQueue::GetRear({
if(rear!=frontreturnrear->data;}
template
boolLiQueue::Empty({
if(front==rearreturn0;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++;}elsej++;}
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来建立队列，以及初始化队列、进队列、出队列等等。同时也了解到了火车车厢重排问题可以通过队列的相关知识来解决，也体会其中算法的奥妙。


本文来源：https://www.2haoxitong.net/k/doc/da2c9631b1717fd5360cba1aa8114431b80d8e32.html

《队列的应用火车车厢重排问题.doc》
将本文的Word文档下载到电脑，方便收藏和打印
推荐度：
点击下载文档

文档为doc格式
相
关
案
例

相关推荐

推荐内容

四字成语不解什么 四字成语迷什么解什么意思是什么 汉语拼音有两种拼读方法 小学语文《千人糕》第二课时听课记录 重阳节的慰问信 关于学校创建无烟单位工作总结范文 小学作风建设工作总结 什么什么不解四字成语 (完整版)小升初数学必考应用题大全 徐志摩的编辑身份-徐志摩与陆小曼的爱情
网站内容来自网络，如有侵权请联系我们，立即删除！ Copyright © 范文写作网京ICP备16605803号