渡船问题.cpp

一个用队列实现的渡船算法

//渡船管理问题--用队列实现

#include<iostream.h>
#include<stdlib.h>
typedef struct QNode     //节点
{
	int data;
	QNode*next;
}*QueuePtr;             //指向结点的指针
struct LinkQueue         //头、尾指针
{
	QueuePtr front,rear;
};
LinkQueue car1,car2,boat;     //定义客车，货车，船队列
int InitQueue(LinkQueue&Q)    //空队列
{
	Q.front=(QueuePtr)malloc(sizeof(QNode));
	Q.rear=Q.front;
	if(!Q.front)exit(1);
	Q.front->next=NULL;
	return 1;
}
int ClearQueue(LinkQueue&Q)    //清空队列
{
	QueuePtr p,q;
	Q.rear=Q.front;
	p=Q.front->next;
	Q.front->next=NULL;
	while(p)
	{
		q=p;
		p=p->next;
		free(q);      //释放空间
	}
	return 1;
}
int QueueEmpty(LinkQueue Q)    //判断是否空
{
	if(Q.front==Q.rear)
		return 1;
	else return 0;
}

int GetHead(LinkQueue Q,int&e)    //获取队列头，并且不改变队列头
{
	if(Q.front==Q.rear)
		return 0;
	QueuePtr p;
	p=Q.front->next;
	e=p->data;
	return 1;
}
int QueueLength(LinkQueue&Q)  //计算队列长度
{
	int i=0;
	QueuePtr p=Q.front;
	while(p!=Q.rear)
	{
		i++;
		p=p->next;
	}
	return i;

}
int EnQueue(LinkQueue&Q,int e)     //进队列
{
	QueuePtr p;
	p=(QueuePtr)malloc(sizeof(QNode));
	if(!p)exit(1);
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return 1;
}
int DeQueue(LinkQueue&Q,int&e)      //出队列
{
	QueuePtr p;
	if(Q.front==Q.rear)
		return 0;
	p=Q.front->next ;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)
		Q.rear=Q.front;
	free(p);
	return 1;
}
void print(LinkQueue&Q)      //输入队列
{
	QueuePtr p;
	p=Q.front->next;
	while(p)
	{
		cout<<p->data<<" ";
		p=p->next;
	}
}
void Enboat()              //船队列
	{
		int hh=0;    //标记已上船车辆数目
	 for(hh=1;hh<=10;)
	 {
	  for(int k=1;k<=4;k++ )  //先上4 辆客车
	  {if(QueueEmpty(car1)) break;   //如果客车队列已空，则跳出
	   int e1=0;
	   DeQueue(car1,e1);              //从客车中出队
	   EnQueue(boat,e1);              //上船
	   hh++;
	  }
	 int e2=0;
     if(!QueueEmpty(car2))          //上一辆货车
	 {
	 DeQueue(car2,e2);
	 EnQueue(boat,e2);
	 
	 }
	 hh++;
	 }
	 print(boat);       //打印船队列
	}
	
void main()
{
	InitQueue(car1);
	InitQueue(car2);
    InitQueue(boat);
    cout<<endl<<"请输入将要渡船的客车辆数:";
	int n; 
	cin>>n;
    cout<<"请输入客车车牌号码（4位数字）:"<<endl;
	for(int i=1;i<=n;i++)     //客车队列
	{
		cout<<"输入第"<<i<<"辆客车的车牌号:";
		int a;
		cin>>a;
        EnQueue(car1,a);
	}
	cout<<"客车队列: ";
    print(car1);
	cout<<endl;
	cout<<"请输入将要渡船的货车辆数:";
	int m;cin>>m;
    cout<<"请输入货车车牌号码（4位数字）:"<<endl;
	for(int k=1;k<=m;k++)          //货车队列
	{
		cout<<"输入第"<<k<<"辆货车的车牌号:";
		int b;
		cin>>b;
        EnQueue(car2,b);
	}
	cout<<"货车队列: ";
    print(car2);
	cout<<endl;
	cout<<"现在上船"<<endl; 
    int w=0;
   for(w=1;w<=(m+n)/10+1  ;w++)
	{
	   cout<<"第 "<<w<<" 批渡江："<<endl;
		Enboat();
		cout<<endl<<"第 "<<w<<" 批渡过江的车辆车牌号码分别为："<<endl;
	 for(int u=1;u<=10;u++)    //下船--出队列，并且打印
	 {if(QueueEmpty(boat)) break;
		 int bo;
	 DeQueue(boat,bo);
	 cout<<bo<<",  ";
	 }
	 cout<<endl;
	}
}