火车车厢重排问题源程序代码
#include<iostream.h>
#include<stdlib.h>
typedef struct QNode
{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front; // 头指针，若队列不空，指向队列头元素
QueuePtr rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
} LinkQueue;
int InitQueue (LinkQueue &Q)// 构造一个空队列Q
{
Q.front = Q.rear = (QueuePtr) malloc (sizeof (QNode));
if (!Q.front) return 0; // 存储分配失败
Q.front->next=NULL;
return 1;
}
int EnQueue (LinkQueue &Q, int e) // 插入元素e为Q的新的队尾元素{
QueuePtr p;
p=(QueuePtr) malloc (sizeof (QNode));
if(!p) return 0; //队列满
p->data=e; p->next =NULL;
Q.rear->next =p;
Q.rear =p;
return 1;
}
int DeQueue (LinkQueue &Q) // 若队列不空，则删除Q的队头元素，用e 返回其值，并返回1; 否则返回0
{
QueuePtr p;
if (Q.front == Q.rear) return 0;
else
{
p=Q.front->next;
Q.front->next=p->next;
if(p->next==NULL)
Q.front=Q.rear;
int m=p->data;
free(p);
return m;
}
}
int Getfront(LinkQueue &Q)//取队头元素
{
if(Q.front==Q.rear) return 0;
else
return Q.front->next->data;
}
int Getrear(LinkQueue &Q)//取队尾元素
{
if(Q.front==Q.rear) return 0;
else
return Q.rear->data;
}
int IsEmpty(LinkQueue &Q)//判断队列为空
{
if (Q.front == Q.rear)
return 0;
return 1;
}
void Resort(LinkQueue &Q,LinkQueue *H,int k)//火车车厢重排{
int nowOut=1,no=1;
while(nowOut<10)
{
int flag=0,flag2=0;//车厢出轨标记初始化为0
int c=DeQueue(Q);
if(c==nowOut)
{
cout<<c<<" ";nowOut++;flag=1;
}
for(int j=0;j<k;j++)//输出对头元素
{
if(IsEmpty(H[j]))
{
if(Getfront(H[j])==nowOut)
{
int m=DeQueue(H[j]);
cout<<m<<" ";nowOut++; j=0;flag=1;
}
}
}
if(flag==0)//插入新的缓冲队列
{
for(int i=0;i<k;i++)
{
if(IsEmpty(H[i]))
{
int n=Getrear(H[i]);
if(c>n)
{
EnQueue(H[i],c);flag2=1;break;
}
}
}
if(flag2==0)
{
if(no==k)
{
cout<<"缓冲队列已用完，无法输出"<<endl;break;
}
else
{
EnQueue(H[no],c);no++;
}
}
}
}
}
void main()
{
LinkQueue Q,H[9];
int k,a[9];
InitQueue(Q);
cout<<"请输入你需要的缓冲队列个数:";
cin>>k;
for(int i=0;i<k;i++)
InitQueue(H[i]);
cout<<"请输入火车入轨的编号序列:";
for(int j=0;j<9;j++)
{
cin>>a[j]; EnQueue(Q,a[j]);
}
cout<<"火车车厢重排序列为:";
Resort(Q,H,k);
cout<<endl;
}。