数据结构-------列车重排-----队列的应用

#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
typedef struct QType
{
int number;
}QType;
typedef struct Queue
{
QType *element;
int front;
int rear;
int maxsize;
}Queue;
//主体为一个以数组为存储对象的循环队列，其中Q[0]不存放数据
void CreatQueue(Queue &Q,int MaxQueueSize);//初始化队列函数声明
bool EnQueue(Queue &Q,QType &x);//元素入队
bool DeQueue(Queue &Q,QType &x);//元素出队
bool GetFront(Queue &Q,QType &x);//获取front指向的元素值
bool GetRear(Queue &Q,QType &x);//获取rear指向的元素值
bool IsEmpty(Queue &Q);//判断队列是否为空
bool IsFull(Queue &Q);//判断队列是否满
bool RearrangementTrack(int r[],int n,int k);
void Output(int &minH,int &minQ,Queue Q[],int k,int n);
bool Hold(int current ,int &minH,int &minQ,Queue Q[],int k,int n);
int main()
{
int a[9] = {9,8,7,6,2,3,5,4,1};
int k;
for(k=1;k<=8;k++)
{
if(!RearrangementTrack(a,9,k))
{
system("cls");//若缓冲轨道不够，就清屏
}
else
{
printf("缓冲轨道最少要%d个n",k-1);//因为0号轨道不用，所以为k-1
exit(0);//找到最少缓冲轨道就结束
}
}
return 0;
}
void CreatQueue(Queue &Q,int MaxQueueSize)
{
Q.maxsize = MaxQueueSize;
Q.element = new QType[Q.maxsize+1];
Q.front = Q.rear = 0;
}
bool IsFull(Queue &Q)
{
if(Q.front == (Q.rear+1)%(Q.maxsize+1))//当front=rear+1时，队列满
return true;
return false;
}
bool EnQueue(Queue &Q,QType &x)//进队时将rear往前移
{
if(IsFull(Q))
return false;
Q.rear = (Q.rear+1)%(Q.maxsize+1);
Q.element[Q.rear] = x;
return true;
}
bool DeQueue(Queue &Q,QType &x)//出队时将front往前移
{
if(IsEmpty(Q))
return false;
Q.front = (Q.front+1)%(Q.maxsize+1);
x = Q.element[Q.front];
return true;
}
bool GetFront(Queue &Q,QType &x)
{
if(IsEmpty(Q))
return false;
x = Q.element[(Q.front+1)%(Q.maxsize+1)];
return true;
}
bool GetRear(Queue &Q,QType &x)
{
if(IsEmpty(Q))
return false;
x = Q.element[Q.rear];
return true;
}
bool IsEmpty(Queue &Q)
{
if(Q.front == Q.rear)
return true;
return false;
}
bool RearrangementTrack(int r[],int n,int k)
{
Queue *Q = new Queue[k];//创建k个轨道，其中0号缓冲轨道不使用
int MaxQueueSize = 10;
for(int i=0;i<k;i++)
{
CreatQueue(Q[i],MaxQueueSize);//初始化各个队列
}
int NowOut = 1;//一开始，NowOut为1
int minH = n+1;//这里minH为10
int minQ;
for(i = 0;i<n;i++)
{
if(r[i] == NowOut)//当前到站的车厢编号刚刚是应该输出的车厢编号，就直接输入出轨
{
printf("从入轨输出%d号车厢到出轨n",r[i]);
if(NowOut!=n)//判断是否出轨完
NowOut++;
while(minH == NowOut)//从缓冲区输出minH
{
Output(minH,minQ,Q,k,n);
if(NowOut!=n)
NowOut++;
}
}
else
{
if(!Hold(r[i],minH,minQ,Q,k,n))
{
delete []Q;
return false;
}
}
}
delete []Q;//free掉各个队列
return true;
}
void Output(int &minH,int &minQ,Queue Q[],int k,int n)
{
int current;
QType x;
x.number = minH;
DeQueue(Q[minQ],x);
printf("从%d号缓冲铁轨输出%d号车厢到出轨n",minQ,minH);
minH = n+1;
for(int i=1;i<k;i++)
{//通过检查所有的队列的首部，寻找新的minH和minQ
GetFront(Q[i],x);
current = x.number;
if(!IsEmpty(Q[i])&&current<minH)//找到输出minH后缓冲轨道中最小编号的车箱，并给minH、minQ赋值
{
minH = current;
minQ = i;
}
}
}
bool Hold(int current ,int &minH,int &minQ,Queue Q[],int k,int n)
{
int BestCushion = 0;//表示最优缓冲轨道，0表示没找到最优的
int BestLast = 0;//BestCushion中最后一节车厢的编号
QType x;
for(int i=1;i<k;i++)//扫描缓冲区
{
if(!IsEmpty(Q[i]))
{
GetRear(Q[i],x);
if(current > x.number&&x.number > BestLast)//比较current与各个缓冲轨道的最后一个编号
{
//若比每一个小且没有空轨道，就返回false(有空轨道，就进入空轨道)
BestLast = x.number;//若有几个缓冲轨道的最后一个编号都比current小，那么就找与
BestCushion = i;//current差最小的缓冲轨道作为最优缓冲轨道入队
}
}
else
{
if(!BestCushion)//有空轨道就如空轨道(前提是current小于所有缓冲轨道的最后一个编号)
BestCushion = i;
}
}
if(!BestCushion)//最优缓冲轨道没找到，返回false
{
return false;
}
x.number = current;
EnQueue(Q[BestCushion],x);//把current进入最优缓冲轨道
printf("从入轨将%d号车厢移到%d号缓冲铁轨n",current,BestCushion);
if(current < minH)//检查current可否成为新的minH和minQ，如果是，就修改
{
minH = current;
minQ = BestCushion;
}
return true;
}