队列的应用火车车厢重排问题
一、试验课题
队列的应用
实验目的:
(1)掌握队列的特点及其存储方法; (2)掌握队列的常见算法和程序实现。
二、试验内容
(1)问题描述:一列货运列车共有n节车厢,每节车厢将停放在不同的车站。假定n个车站的编号分别为1~n,即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢,车厢的编号应与车站的编号相同,这样,在每个车站只要卸掉最后一节车厢。所以,给定任意次序的车厢,必须重新排列它们。车厢的重排工作可以通过国转轨站完成。在转轨站中有一个入轨、一个出轨和k个缓冲轨,缓冲轨位于入轨和出轨之间。假定缓冲轨按先进先出飞方式运作,设计算法解决火车车厢重排问题。
(2)基本要求:设计存储结构表示n个车厢、k个缓冲轨以及入轨和出轨;设计并实现车厢重排算法;分析算法的时间性能
三、试验分析
实验说明:
转轨站示意图如下:
火车车厢重排过程如下:
2
(a) 将369、247依次入缓冲轨
2 将8入缓冲轨,5移至出轨 (c)
2(b) 将1移至出轨,234移至
出轨
2(d) 将6789移至出轨
火车车厢重排算法伪代码如下:
四、源程序代码
#include using namespace std; const MS=100;
template struct QNode {
T data;
QNode *next; };
template class LiQueue {
public:
LiQueue( ); //构造函数,初始化一个空的链队列
~LiQueue( ); //析构函数,释放链队列中各结点的存储空间 void EnQueue(T x); //将元素x入队 T DeQueue( ); //将队头元素出队
T GetFront( ); //取链队列的队头元素 T GetRear();
bool Empty( ); //判断链队列是否为空
QNode *front, *rear; //队头和队尾指针,分别指向头结点和终端结点 };
template LiQueue::LiQueue( ) {
QNode *s;s=new QNode;s->next=NULL;front=rear=s; }
template
LiQueue::~LiQueue( ) {
QNode *p; while(front) {
p=front;front=front->next;delete p; } }
template
void LiQueue::EnQueue(T x) {
QNode *s;s=new QNode;
s->data=x; //申请一个数据域为x的结点s s->next=NULL;
rear->next=s; //将结点s插入到队尾 rear=s; }
template
T LiQueue::DeQueue() {
QNode *p; int x;
if (rear==front) throw "下溢"; p=front->next;
x=p->data; //暂存队头元素
front->next=p->next; //将队头元素所在结点摘链
if (p->next==NULL) rear=front; //判断出队前队列长度是否为1 delete p; return x; }
template
T LiQueue::GetFront() {
if (rear!=front)
return front->next->data; }
template T LiQueue::GetRear() {
if(rear!=front)return rear->data; }
template
bool LiQueue::Empty( ) {
if(front==rear) return 0;else return 1; }
class Train {
private : int n,k,th; public :
Train();void ChongPai(); };
Train::Train() {
cout>n;
cout>k; }
void Train::ChongPai() {
int a[MS];LiQueue*b; b=new LiQueue[k+2];
cout>a[i];
for(i=n-1;i>=0;i--) b[k].EnQueue(a[i]);
cout
while(b[k].Empty()) {
int xx=b[k].DeQueue(); if(xx==th) {
cout
while(b[j].Empty()) {
int x=b[j].GetFront(); if(x==th) {
cout
continue; }
else {
int j=0,u=5;
while(b[j].Empty()&&j
if(xx
cout
if(u==5&&j
cout
if(j==k-1) {
cout
cout
cout
void main() {
Train a;a.ChongPai(); }
五、测试用例
1.当有9个火车车厢,3个缓冲轨道时,运行结果如下:
2. 当有12个火车车厢,3个缓冲轨道时,运行结果如下:
3. 当有12个火车车厢,5个缓冲轨道,运行结果如下:
4. 当有12个火车车厢,7个缓冲轨道时,运行结果如下:
几次测试都表明试验设计的正确性。
六、试验总结
本次试验中,在解决火车车厢重排问题中,结合了最近刚学的队列的知识,并且运用到之前C++语言,很好的解决了这一类问题。其中,每一个轨道缓冲区就形如一个队列一样,车厢先进缓冲轨道的要先出来,所以把它看成一个队列,运用队列的相关算法,实现高效快速的解决火车车厢重排问题。
通过本次试验,学会了队列的应用,加深了对队列的理解,知道了队列是一种先进队列的后出队列的储存结构。本次试验让我更好的把书本上的知识运用到具体的例子中来,学会了通过vc6.0来建立队列,以及初始化队列、进队列、出队列等等。同时也了解到了火车车厢重排问题可以通过队列的相关知识来解决,也体会其中算法的奥妙。