数据结构实验报告实验题目：停车场管理学生姓名：班级：学号：问题描述设有一个停车场，它是利用一个南北向的狭窄通道建成，北端封闭，大门在最南端。

最先到达的汽车停放在最北端，后面到达的汽车从北至南依次顺序停放。

停车场只能停放n 辆汽车。

当停车场停满n辆车后，后面到达的汽车只能在门外的便道上等候。

一旦有汽车开走，便道上等候的第一辆车就可以开入停车场停放。

当停车场内某辆汽车要离开时，在它之后进入的车辆必须先退出停车场为它让路，待该车开出大门外，其他汽车再按原次序返回车场。

每辆停放在车场内的汽车在离开时必须按它停放时间的长短交纳费用。

例题分析每到达一辆汽车，先检查停车场栈是否已满，若未满则该车进入停车场停放（入栈操作），并将该车的车号和停放时刻记录在停车场栈的相应元素中，同时显示该车在停车场内的停放位置。

反之，若停车场已满，则该车排到便道上等候的汽车队列最后（入队列操作），并将该车的车号信息记录在汽车队列的相应结点内，同时显示该车在便道上的停放位置。

若要取一辆汽车，则需依次进行下述操作：将阻挡在它后面的汽车退出（停车场栈的出栈操作），并将这些汽车临时存放在另一个辅助栈中（辅助栈的入栈操作）；开走要取的汽车（停车场栈的出栈操作），并显示该车应交纳的费用；依次从辅助栈中开出汽车（辅助栈出栈操作），开回停车场中（停车场栈的入栈操作）；这时停车场已有一个空车位，便道上等候的第一辆汽车则可以开进停车场内停放（汽车队列的出队列操作和停车场栈的入栈操作）。

程序源代码#include<iostream>#include<conio.h>#include<iomanip>#include<fstream>#include<string>#include <stdlib.h>#include <windows.h>using namespace std;#define Max_Size 2//停车的最大容量#define HourFare 2 //每小时的停车费用int CountForStack=0; //栈里现有的车数int CountForQueue=0; //排队等候的车数typedef struct{char Condition;//到达或者离开的状态int Arrivetime;//到达时间，默认为-1，表示没有到达int Leavetime;//离开时间，默认为-1，表示没有离开int License;//车牌号}CarNode;//保存每辆车的信息typedef struct//栈的定义{CarNode *base;//栈底指针CarNode *top;//栈顶指针int Stacksize;//栈的最大容量}CarStack;typedef struct QNode{char Condition;//到达或者离开的状态int Arrivetime;//到达时间，默认为-1，表示没有到达int Leavetime;//离开时间，默认为-1，表示没有离开int License;//车牌号QNode *next;}QNode;typedef struct//队列的定义QNode *front;//对头指针QNode * rear;//队尾指针}Queue;bool InitStack(CarStack &S1)//初始化栈S1{S1.base=(CarNode*)malloc(Max_Size*sizeof(CarNode));if(!S1.base){cout<<"栈S1 内存分配失败"<<endl;return false;}S1.top=S1.base;S1.Stacksize=Max_Size;return true;}bool InitQueue(Queue &Q){Q.front=(QNode*)malloc(sizeof(QNode));if(!Q.front){cout<<"队列Q 内存分配失败！"<<endl;return false;}Q.rear=Q.front;Q.front->next=NULL;return true;}bool EnQueue(Queue &Q,QNode &e)//插入元素e 为Q 的新的队尾元素QNode *p=(QNode *)malloc(sizeof(QNode));if(!p){cout<<"p 内存分配失败"<<endl;return false;}p->Arrivetime=e.Arrivetime;p->Leavetime=e.Leavetime;p->Condition=e.Condition;p->License=e.License;//将e 赋给Pp->next=NULL;Q.rear->next=p;Q.rear=p;return true;}bool DeQueue(Queue &Q,QNode &t)//出队列函数{if(Q.front==Q.rear){cout<<"队列为空！"<<endl;return false;}QNode *p=Q.front->next;t.Arrivetime=p->Arrivetime;t.Condition=p->Condition;t.Leavetime=p->Leavetime;t.License=p->License;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;}free(p);return true;}void InitCarNode(CarNode &C,char condition,int arrivetime,int leavetime,int license) {C.Arrivetime=arrivetime;C.Condition=condition;C.Leavetime=leavetime;C.License=license;}bool Push(CarStack &S1,CarNode &car)//插入新的元素car 为的栈顶元素{if(S1.top-S1.base>=S1.Stacksize){cout<<"此栈已满，不能压入新的信息"<<endl;return false;}(*S1.top).Arrivetime=car.Arrivetime;(*S1.top).Condition=car.Condition;(*S1.top).Leavetime=car.Leavetime;(*S1.top).License=car.License;++S1.top;//栈顶指针上移return true;}bool Pop(CarStack &S1,CarNode &t)//出栈操作{if(S1.top==S1.base)cout<<"栈S1 为空，不能执行出栈操作"<<endl;return false;}--S1.top;//栈顶指针下移t.Arrivetime=(*S1.top).Arrivetime;t.Condition=(*S1.top).Condition;t.Leavetime=(*S1.top).Leavetime;t.License=(*S1.top).License;return true;}bool IsStackFull(CarStack &S1)//判断S1 栈是否已满{if(S1.top-S1.base>=S1.Stacksize)return true;elsereturn false;}bool IsStackEmpty(CarStack &S1)//判断S1 栈是否已空{if(S1.top==S1.base)return true;elsereturn false;}bool IsQueueEmpty(Queue &Q)//判断队列是否为空{if(Q.front==Q.rear)return true;elsereturn false;}bool SearchInStack(CarStack &S1,int a)//a 表示要查找的车牌号，如果在停车场里面，就返回true{bool tag=false;if(!IsStackEmpty(S1))//如果栈S1 非空{CarNode *p=S1.top-1;while(p!=S1.base){if((*p).License==a)tag=true;--p;}if((*p).License==a)tag=true;}return tag;}bool SearchInQueue(Queue &Q,int a)//a 表示要查找的车牌号,如果在通道里面，就返回true{bool tag=false;if(!IsQueueEmpty(Q))//如果队列非空{QNode *p=Q.front->next;while(p!=Q.rear){if((*p).License ==a)tag=true;p=p->next;}//退出此while 循环时p 指向最后一个元素if((*p).License ==a)tag=true;}return tag;}void InCar(CarStack &S1,Queue &Q,int a1,int a2)//表示进入车辆,a1 表示到达时间,a2 表示车牌号码{if(SearchInStack(S1,a2)){cout<<"车号"<<a2<<"已经存在于停车场内，输入有误"<<endl;return;}if(SearchInQueue(Q,a2)){cout<<"车号"<<a2<<"已经存在于通道内，输入有误"<<endl;return;}if(IsStackFull(S1))//如果堆栈已满，说明停车场已满，需要停车在通道里面{QNode qnode;qnode.Arrivetime=-1;//在通道里面不收费，所以不计时qnode.Condition='A';qnode.Leavetime=-1;//定义为-1，说明还没有开始离开qnode.License=a2;EnQueue(Q,qnode);//停在通道上++CountForQueue;cout<<"车号:"<<qnode.License<<"停在通道的第"<<CountForQueue<<"号位置"<<endl;}else{CarNode carnode;carnode.Arrivetime=a1;carnode.Condition='A';carnode.Leavetime=-1;carnode.License=a2;Push(S1,carnode);++CountForStack;cout<<"车号："<<carnode.License<<"，到达时间:"<<carnode.Arrivetime<<" 点，停在停车场的第"<<CountForStack<<"号位置"<<endl;}}void Sreach(CarStack &S1,Queue &Q,int a){if(SearchInStack(S1,a)){cout<<"车号："<<a<<"已存在停车场里面的第"<<CountForStack<<"号位置"<<endl;return;}if(SearchInQueue(Q,a)){cout<<"停车场已满，车号"<<a<<"存在于通道里面的第"<<CountForQueue<<"号位置，在次等候"<<endl;return;}else{cout<<"对不起!你查找的车号不在停车场里面"<<endl;return;}}void OutCar(CarStack &S1,Queue &Q,int a1,int a2)//出车函数，a1 表示离开时间，a2 表示车牌号码{if(SearchInQueue(Q,a2)){cout<<"车号"<<a2<<"存在于通道里面,还没有进入停车场，不能离开"<<endl;return;}if(!SearchInStack(S1,a2)){cout<<"车号"<<a2<<"该车不在停车场内"<<endl;return;}CarStack tempstack;InitStack(tempstack);//新建一个栈，存放让路的汽车bool tag1=false;//标志这个停车场出车以前是否已满，默认为没有满tag1=IsStackFull(S1);bool tag2=true;//标志通道是否有汽车在等待，默认为通道为空tag2=IsQueueEmpty(Q); CarNode temp;//用来保存暂时取出的汽车bool tag3=false;while(1){Pop(S1,temp);if(temp.License==a2){if(a1<temp.Arrivetime){cout<<"离开失败！"<<endl;tag3=true;Push(tempstack,temp);}else{cout<<"车号："<<a2<<"现在离开停车场，所用时间为："<<a1-temp.Arrivetime<<"小时，应收RMB 为："<<(a1-temp.Arrivetime)*HourFare<<"元"<<endl;}break;}elsePush(tempstack,temp);//进入暂存栈} 则把前面倒出的车再次放while(!IsStackEmpty(tempstack))//如果临时栈不空，入停车场{Pop(tempstack,temp);Push(S1,temp);}QNode tempqnode;//用来暂时保存从通道出来的汽车if(tag1==true&&tag2==false&&tag3==false)//如果出车前停车场已满，并且通道不为空，并且离开没有失败{DeQueue(Q,tempqnode);--CountForQueue;temp.Arrivetime=a1;temp.Condition=tempqnode.Condition;temp.Leavetime=tempqnode.Leavetime;temp.License=tempqnode.License;Push(S1,temp);}if(tag3==false)//如果停车通道是空的，停车场没有满，并且离开成功{--CountForStack;}}}void showmenu(CarStack &S1,Queue &Q){cout<<"******************************选择菜单*******************************"<<endl;cout<<" 1: 停车"<<endl;cout<<" 2: 离开停车场"<<endl;cout<<" 3: 查看车辆信息"<<endl;cout<<" 4: 退出系统"<<endl;cout<<"*****************************请按键选择******************************"<<endl;int tag;cin>>tag;while(tag!=1&&tag!=2&&tag!=3&&tag!=4)cin>>tag;int a1;unsigned int a2;switch(tag){case 1:cout<<"请输入到达的车号："<<endl;cin>>a1;cout<<"请输入到达的时间："<<endl;cin>>a2;InCar(S1,Q,a2,a1);Sreach(S1,Q,a1);break;case 2:cout<<"请输入离开的车号："<<endl; cin>>a1;cout<<"请输入离开的时间："<<endl; cin>>a2;OutCar(S1,Q,a2,a1);break;case 3:cout<<"请输入你要查看的车号："<<endl;cin>>a1;Sreach(S1,Q,a1);break;case 4:return;break;}showmenu(S1,Q);}void main(){CarStack carstack;InitStack(carstack);//建立并且初始化用于停车场的堆栈Queue carQueue;InitQueue(carQueue);//建立并且初始化用于通道的队列showmenu(carstack,carQueue);}。