火车车厢重排问题解决c队列方法.docx

火车车厢重排问题解决c队列方法.docx

《火车车厢重排问题解决c队列方法.docx》由会员分享，可在线阅读，更多相关《火车车厢重排问题解决c队列方法.docx（9页珍藏版）》请在冰点文库上搜索。

火车车厢重排问题解决c队列方法

火车车厢重排问题c++解决方法（队列实现）

//Queue.h

#ifndefQUEUE_H

#defineQUEUE_H

#include

usingnamespacestd;

template

classQueue

{

public:

virtualvoidMakeEmpty（）=0;

virtualvoidEnqueue（Tx）=0;

virtualTDequeue（）=0;

virtualboolIsEmpty（）const=0;

virtualboolIsFull（）const=0;

virtualTGetFirstItem（）=0;

};

classEmptyQueue

{

};

classFullQueue

{

};

#endif

//LinkQueue.h//链表队列

#ifndefLINKQUEUE_H

#defineLINKQUEUE_H

#include

#include"Queue.h"

usingnamespacestd;

template

structNode

{

Tdate;

Node*next;

};

template

classLinkQueue:

publicQueue

{

template

friendostream&operator<<（ostream&s,constLinkQueue&lq）;

public:

LinkQueue（）;

~LinkQueue（）;

voidMakeEmpty（）;

voidEnqueue（Tx）;

TDequeue（）;

boolIsEmpty（）const;

boolIsFull（）const;

TGetFirstItem（）;

TGetlastItem（）;

private:

Node*front;

Node*rear;

};

template

LinkQueue:

:

LinkQueue（）

{

front=newNode;

front->next=NULL;

rear=front;

}

template

LinkQueue:

:

~LinkQueue（）

{

MakeEmpty（）;

deletefront;

}

template

voidLinkQueue:

:

Enqueue（Tx）{

Node*newnode;

newnode=newNode;

newnode->date=x;

newnode->next=NULL;

rear->next=newnode;

rear=newnode;

}

template

TLinkQueue:

:

Dequeue（）

{

if（IsEmpty（））

throwEmptyQueue（）;

Node*p;

p=front->next;

Tx=p->date;

front->next=p->next;

if（p->next==NULL）

rear=front;

deletep;

returnx;

}

template

boolLinkQueue:

:

IsFull（）const{

returnfalse;

}

template

boolLinkQueue:

:

IsEmpty（）const{

returnfront==rear;

}

template

TLinkQueue:

:

GetFirstItem（）{

if（IsEmpty（））

throwEmptyQueue（）;

Node*p;

p=front->next;

returnp->date;

}

template

TLinkQueue:

:

GetlastItem（）{

if（IsEmpty（））

throwEmptyQueue（）;

returnrear->date;

}

template

voidLinkQueue:

:

MakeEmpty（）{

Node*p;

while（front->next!

=NULL）

{

p=front->next;

front->next=p->next;

deletep;

}

}

template

ostream&operator<<（ostream&s,constLinkQueue&lq）

{

Node*p;

p=lq.front->next;

while（p!

=NULL）

{

s<date<<"";

p=p->next;

}

returns;

}

#endif

//TrainResort.h//火车车厢重排代码核心部分

#ifndefTRAINRESORT

#defineTRAINRESORT

#include

#include"LinkQueue.h"

usingnamespacestd;

classTrainResort

{

friendostream&operator<<（ostream&s,TrainResort&tr）;public:

TrainResort（LinkQueue*or,intm=3）;

~TrainResort（）;

private:

intbuf;

LinkQueueorbit;

LinkQueue*buffer;

};

TrainResort:

:

TrainResort（LinkQueue*or,intm）

{

buf=m;

while（!

or->IsEmpty（））

orbit.Enqueue（or->Dequeue（））;

buffer=newLinkQueue[buf];

}

TrainResort:

:

~TrainResort（）

{

delete[]buffer;

}

ostream&operator<<（ostream&s,TrainResort&tr）

{

intnowOut=1;

inttemp;

intx,y;

intz;

while（!

tr.orbit.IsEmpty（））

{

x=0,y=0;z=0;

temp=tr.orbit.Dequeue（）;

if（temp==nowOut）

{

tr.buffer[0].Enqueue（nowOut）;

nowOut++;

for（intj=1;j

{

intk=0;

while（!

tr.buffer[j].IsEmpty（）&&tr.buffer[j].GetFirstItem（）==nowOut）

{

tr.buffer[0].Enqueue（nowOut）;

nowOut++;

tr.buffer[j].Dequeue（）;

k++;

}

if（k!

=0）

{

if（temp==nowOut）

{

tr.buffer[0].Enqueue（nowOut）;

nowOut++;

}

j=0;

}

}

}

else

{

for（intj=1;j

{

if（!

tr.buffer[j].IsEmpty（））

{

if（temp-tr.buffer[j].GetlastItem（）>0）

{

y=（x>temp-tr.buffer[j].GetlastItem（）?

y:

j）;

x=（y==j?

temp-tr.buffer[j].GetlastItem（）:

x）;

}

}

else

{

z=j;

}

}

if（y!

=0）

{

tr.buffer[y].Enqueue（temp）;

}

elseif（z!

=0）

{

tr.buffer[z].Enqueue（temp）;

}

else

{

s<<"Don'tresort!

";

break;

}

}

}

s<

returns;

}

#endif