数据结构停车场问题实验报告

1、.数据结构课程设计 停车场管理问题姓名：学号：.专业 .专注.一、问题描述设有一个可以停放n 辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。 如果停车场已放满 n 辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，

2、允许其离去 ，不收停车费 ，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。二、实现要求要求程序输出每辆车到达后的停车位置 (停车场或便道上 )，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间 。三、实现提示汽车的模拟输入信息格式可以是 ：(到达离去，汽车牌照号码 ，到达离去的时刻 )。例如， (A，1，5) 表示 1 号牌照车在 5 这个时刻到达 ，而 (D，5， 20) 表示 5 号牌照车在 20 这个时刻离去 。 整个程序可以在输入信息为 (E，0，0) 时结束 。 本题可用栈和队列来实现 。四、需求分析停车场采用栈式结构，停车场外的便道采用队列结构（即便

3、道就是等候队列）。停车场的管理流程如下 当车辆要进入停车场时 ，检查停车场是否已满 ，如果未满则车辆进栈 （车辆进入停车场 ）；如果停车场已满 ，则车辆进入等候队列 （车辆进入便道等候 ）。 当车辆要求出栈时，该车到栈顶的那些车辆先弹出栈（在它之后进入的车辆必须先退出车场为它让路），再让该车出栈 ，其他车辆再按原次序进栈 （进入车场 ）。当车辆出栈完毕后 ，检查等候队列 （便道）中是否有车 ，有车则从队列头取出一辆车压入栈中 。.专业 .专注.五、流程图.专业 .专注.六、详细设计1. 本程序主要包含四个模块1) 主程序模块int main()Initialization();CarNode

4、car;SqStack Park,TempPark;LinkQueue Q;InitStack(Park);InitStack(TempPark);InitQueue(Q);while(scanf("%c%d%d",&car.event,&car.num,&car.time)&&(car.event!='e'&&car.event!='E')getchar();/ 除去输入结束时的回车switch(car.event)case 'A':case 'a':A

5、rrive(Park,Q,car);break;case 'D':case 'd':Leave(Park,TempPark,Q,car);break;default: printf("您的第一个数据输入有误!n");break;printf(" 程序结束 ，谢谢使用 !n");return 0;2）分别构造空栈和空队列栈： Status InitStack(SqStack &S)/ 构造一个空栈.专业 .专注.S.Stacksize=0;S.base=(CarNode*)malloc(MAX)*sizeof(Car

6、Node);if(!S.base)exit(OVERFLOW);printf(" 存储空间分配失败");S.top=S.base;return OK;队列：Status InitQueue(LinkQueue &Q)/ 构造一个空队列（带头结点 ）Q.front=Q.rear=(QueueNode*)malloc(sizeof(QueueNode);if(!Q.front)exit(OVERFLOW);printf(" 存储空间分配失败");Q.front->next=NULL;Q.queuesize=0;return OK;3）车辆到达处

7、理Status Arrive(SqStack &S,LinkQueue &Q,CarNode &e)/ 车辆到达处理if(S.top-1)->time<=e.time)/ 时间处理if(!Check_Stack(S,e)&&!Check_Queue(Q,e)/ 是否已存在if(S.top-S.base<MAX)Push(S,e);printf(" 成功进入停车场,在 %d 号车库 !n",S.top-S.base);return OK;elseEnQueue(Q,e);.专业 .专注.printf(" 停车

8、场已满 ，车辆进入便道 ,在%d 号车位 !n",Q.queuesize);elseprintf(" 该牌照的车已存在，输入有误 ，请重新输入 n");return OK;elseprintf(" 时间输入有误 ，请重新输入 !n");return FALSE;4）车辆离开处理Status Leave(SqStack &S,SqStack &TempS,LinkQueue &Q,CarNode &e)/ 车辆离开处理CarNode a;int leatime,leanum;int entertime;/ 进入停车

9、场时间int cost;if(!(Check_Stack(S,e) | Check_Queue(Q,e)printf(" 数据输入错误 ，本停车场内无所查询车辆，请重新输入 ！ n");return true;elseif(Check_Stack(S,e)/ 若需要离开的车辆在停车场if(e.num=(S.top-1)->num)/ 车辆处在栈顶.专业 .专注.Pop(S, a);leatime=e.time;leanum=e.num;entertime=a.time;printf(" 车辆进入车库时间:%dt现在（离开）时间 :%dt停留时间:%dtn&q

10、uot;,entertime,leatime,leatime-entertime);else/ 车辆处在栈中间doPop(S,a);/ 从栈中依次退出Push(TempS,a);/ 依次进入临时栈while(S.top-1)->num!=e.num);/直到 top 指针下一个位置的num= 车牌号Pop(S, a);/ 该车离开leatime=e.time;leanum=e.num;entertime=a.time;printf(" 车进入停车场时间:%dt现在（离开）时间 :%dt停留时间:%dtn",entertime,leatime,leatime-enter

11、time);do / 其余车辆按原来次序返回停车场Pop(TempS,a);Push(S,a);while(TempS.top!=TempS.base);/条件与上面不同，此时是全部回去cost=(leatime-entertime)*price;if(cost>=0)printf(" 您的车牌号为%d 的车应交纳的费用是:%dn",leanum,cost);if(Q.front!=Q.rear)/ 队列不空的话从便道进停车场DeQueue(Q,a);if(a.time<leatime)/ 便道车辆进车库时间应该比车库车辆离开时间晚.专业 .专注.enterti

12、me=leatime;a.time=leatime;Push(S,a);/ 该车进入停车场printf(" 车牌号为 %d 的车辆从便道上进入 %d 号车库 !从现在开始计时 ，现在时间为 ： %dn",a.num,S.top-S.base,a.time);else if(Check_Queue(Q,e)/ 从便道直接离开doDeQueue(Q,a);EnQueue(Q,a);while(Q.front->next->data.num!=e.num);DeQueue(Q,e);/ 前面的车进入队尾printf(" 您的车牌号为%d 的车辆未进入车库从便

13、道直接离开，费用为0!n",e.num);return true;2主要设计程序如下#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define MAX 2/ 停车场容量#define price 2/ 单价#define OK 1#define FALSE 0#define TRUE 1#define ERROR -1#define OVERFLOW -2.专业 .专注.typedef int Status;/=typedef struct CarNodechar event;int n

14、um;int time;CarNode;/ 车辆信息结点typedef struct SqStackCarNode *base;CarNode *top;int Stacksize;SqStack;/ 栈（停车场 ）typedef struct QNodeCarNode data;struct QNode *next;QueueNode;/ 便道结点typedef struct LinkQueueQueueNode *front;QueueNode *rear;int queuesize;LinkQueue;/ 队列（便道）/=Status InitStack(SqStack &S)/

15、 构造一个空栈S.Stacksize=0;S.base=(CarNode*)malloc(MAX)*sizeof(CarNode);.专业 .专注.if(!S.base)exit(OVERFLOW);printf(" 存储空间分配失败");S.top=S.base;return OK;/=Status InitQueue(LinkQueue &Q)/ 构造一个空队列（带头结点 ）Q.front=Q.rear=(QueueNode*)malloc(sizeof(QueueNode);if(!Q.front)exit(OVERFLOW);printf(" 存储

16、空间分配失败");Q.front->next=NULL;Q.queuesize=0;return OK;/=Status GetTop(SqStack S,CarNode &e)/ 返回栈顶元素if(S.top=S.base)return ERROR;e=*(S.top-1);return TRUE;/=Status Pop(SqStack &S,CarNode &e)/ 删除栈顶元素if(S.top=S.base).专业 .专注.return ERROR;e=*-S.top;return OK;/=Status Push(SqStack &S,

17、CarNode e)/插入元素为新的栈顶元素(在栈不满的前提下)if(S.top-S.base>=MAX)return FALSE;*S.top+=e;return OK;/=Status DeQueue(LinkQueue &Q,CarNode &e)/ 删除队头元素 (带头结点 )if(Q.rear=Q.front)return ERROR;QueueNode *p=Q.front->next;e=p->data;Q.front->next=p->next;if(p=Q.rear)Q.rear=Q.front;free(p);Q.queuesi

18、ze-;return OK;/=Status EnQueue(LinkQueue &Q,CarNode e)/ 插入新的队尾元素QueueNode *p=(QueueNode*)malloc(sizeof(QueueNode);if(!p).专业 .专注.exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;Q.queuesize+;return OK;/=Status Check_Stack(SqStack &S,CarNode e)/车辆到达时车库内是否有同名车CarNode *Temp

19、=S.base;while(Temp!=(S.top)&&(Temp->num!=e.num)Temp+;if(Temp=S.top)return FALSE;elsereturn TRUE;/=Status Check_Queue(LinkQueue &Q,CarNode e)/车辆到达时便道上是否有同名车QueueNode*Temp=Q.front;while(Temp!=Q.rear) && (Temp->data.num!=e.num)Temp=Temp->next;if(Temp=Q.rear) && (Tem

20、p->data.num!=e.num)return FALSE;elsereturn TRUE;/=.专业 .专注.=Status Arrive(SqStack &S,LinkQueue &Q,CarNode &e)/ 车辆到达处理if(S.top-1)->time<=e.time)/ 时间处理if(!Check_Stack(S,e)&&!Check_Queue(Q,e)/ 是否已存在if(S.top-S.base<MAX)Push(S,e);printf(" 成功进入停车场,在 %d 号车库 !n",S.to

21、p-S.base);return OK;elseEnQueue(Q,e);printf(" 停车场已满 ，车辆进入便道 ,在%d 号车位 !n",Q.queuesize);elseprintf(" 该牌照的车已存在，输入有误 ，请重新输入 n");return OK;elseprintf(" 时间输入有误 ，请重新输入 !n");return FALSE;/=Status Leave(SqStack &S,SqStack &TempS,LinkQueue &Q,CarNode &e)/ 车辆离开处理Ca

22、rNode a;int leatime,leanum;int entertime;/进入停车场时间.专业 .专注.int cost;if(!(Check_Stack(S,e) | Check_Queue(Q,e)printf(" 数据输入错误 ，本停车场内无所查询车辆，请重新输入 ！ n");return true;elseif(Check_Stack(S,e)/ 若需要离开的车辆在停车场if(e.num=(S.top-1)->num)/车辆处在栈顶Pop(S, a);leatime=e.time;leanum=e.num;entertime=a.time;print

23、f(" 车辆进入车库时间:%dt现在（离开）时间 :%dt停留时间:%dtn",entertime,leatime,leatime-entertime);else/ 车辆处在栈中间doPop(S,a);/ 从栈中依次退出Push(TempS,a);/ 依次进入临时栈while(S.top-1)->num!=e.num);/直到 top 指针下一个位置的num= 车牌号Pop(S, a);/ 该车离开leatime=e.time;leanum=e.num;entertime=a.time;printf(" 车进入停车场时间:%dt现在（离开）时间 :%dt停留

24、时间:%dtn",entertime,leatime,leatime-entertime);.专业 .专注.do / 其余车辆按原来次序返回停车场Pop(TempS,a);Push(S,a);while(TempS.top!=TempS.base);/条件与上面不同，此时是全部回去cost=(leatime-entertime)*price;if(cost>=0)printf(" 您的车牌号为%d 的车应交纳的费用是:%dn",leanum,cost);if(Q.front!=Q.rear)/ 队列不空的话从便道进停车场DeQueue(Q,a);if(a.t

25、ime<leatime)/ 便道车辆进车库时间应该比车库车辆离开时间晚entertime=leatime;a.time=leatime;Push(S,a);/ 该车进入停车场printf(" 车牌号为 %d 的车辆从便道上进入 %d 号车库 !从现在开始计时 ，现在时间为 ： %dn",a.num,S.top-S.base,a.time);else if(Check_Queue(Q,e)/ 从便道直接离开doDeQueue(Q,a);EnQueue(Q,a);while(Q.front->next->data.num!=e.num);DeQueue(Q,e);/ 前面的车进入队尾printf(" 您的车牌号为%d 的车辆未进入车库从便道直接离开，费用为0!n",e.num);return true;.专业 .专注./=void Initialization()/初始化程序printf(" 姓名：杨智伟学号：2012040651n");printf("=n");printf("*停车场管理模拟程序*n");pr