数据结构停车场问题试验报告讲解

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

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

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

4、tStack(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:Arrive(Park,Q,car);break;case D:case d:Leave(Park,TempPark,Q,car);break;default: printf( 您的第一个数据输入有误 !n);break;printf( 程序结束，谢谢使用 !n);re

5、turn 0;2) 分别构造空栈和空队列栈： Status InitStack(SqStack &S)/构造一个空栈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)ex

6、it(OVERFLOW);printf( 存储空间分配失败 );Q.front-next=NULL;Q.queuesize=0;return OK;3) 车辆到达处理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.basenum) / 车辆处在栈顶Pop(S, a);leatime=e.time;leanum=e.num;entertime=a.time

7、;printf( 车辆进入车库时间 :%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 停留时 间:%dtn,

8、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.timenext-data.num!=e.num);DeQueue(Q,

9、e);/前面的车进入队尾printf( 您的车牌号为 %d 的车辆未进入车库从便道直接离开，费用为 0!n,e.num);return true;2主要设计程序如下#include#include#include#define MAX 2 / 停车场容量#define price 2 / 单价#define OK 1#define FALSE 0#define TRUE 1#define ERROR -1#define OVERFLOW -2typedef int Status;/=typedef struct CarNodechar event;int num;int time;CarNod

10、e; / 车辆信息结点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)/构造一个空栈S.Stacksize=0;S.

11、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( 存储空间分配失败 );Q.front-next=NULL;Q.queuesize=0;return OK;/

12、= 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,CarNode e)/插入元素为新的栈顶元素 (在栈不满的前提下 )if(S.top-S.base=MAX)return FALSE;*S.top+=e;return

13、 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.queuesize-;return OK;/=Status EnQueue(LinkQueue &Q,CarNode e)/插入新的队尾元素QueueNode *p=(QueueNode*)malloc(sizeof(QueueNod

14、e);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=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)/车

15、辆到达时便道上是否有同名车QueueNode *Temp=Q.front;while(Temp!=Q.rear) & (Temp-data.num!=e.num)Temp=Temp-next;if(Temp=Q.rear) & (Temp-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)/ 是否已存

16、在if(S.top-S.basenum) / 车辆处在栈顶Pop(S, a);leatime=e.time;leanum=e.num;entertime=a.time;printf( 车辆进入车库时间 :%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

17、.time;leanum=e.num;entertime=a.time;printf( 车进入停车场时间 :%dt 现在(离开)时间 :%dt 停留时 间:%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.f

18、ront!=Q.rear) / 队列不空的话从便道进停车场DeQueue(Q,a);if(a.timenext-data.num!=e.num);DeQueue(Q,e);/前面的车进入队尾printf( 您的车牌号为 %d 的车辆未进入车库从便道直接离开，费用为 0!n,e.num);return true;/=void Initialization() / 初始化程序printf( 姓名：杨智伟 学号： 2012040651n);printf(=n);printf(* 停车场管理模拟程序 *n);printf(=n);printf( 请依次输入车辆到达 (A/a)/离去(D/d)/ 结束(E/e)信息、车牌号以及当前时间： n