实验五 栈、队列的高级应用—停车场管理.doc

实验五 栈、队列的高级应用——停 车 场 管 理 【问题描述】 设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆次序。编制一程序模拟该停车场的管理。【需求分析】 停车场采用栈式结构，停车场外的便道采用队列结构（即便道就是等候队列）。停车场的管理流程如下：当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进栈（车辆进入停车场）；如果停车场已满，则车辆进入等候队列（车辆进入便道等候）。当车辆要求出栈时，该车到栈顶的那些车辆先弹出栈（在它之后进入的车辆必须先退出车场为它让路），再让该车出栈，其他车辆再按原次序进栈（进入车场）。当车辆出栈完毕后，检查等候队列（便道）中是否有车，有车则从队列头取出一辆车压入栈中。 提示：可把停车场内的车辆管理看做是堆栈，采用先进后出的运算规则；而在停车场外排队的车辆管理，可以看做是队列，采用先进先出的运算规则。 基本思想：根据题目要求，停车场只有一个大门，因此可用一个栈来模拟。而当栈满后，继续来到的车辆只能停在便道上，根据便道停车的特点，可知这可以用一个队列来模拟，先排队的车辆先离开便道，进入停车场。由于排在停车场中间的车辆可以提出离开停车场，并且要求在离开车辆到停车场大门之间的车辆都必须离开停车场，让此车辆离去，然后再让这些车辆依原来的次序进入停车场，因此在一个栈和一个队列的基础上，还需要有一个地方保存为了让路离开停车场的车辆，很显然这也应该用一个栈来模拟，因此，本题中要用到两个栈和一个队列。 【实验】 【】#include stdio.h #include stdlib.h #include string.h /*------------------------------------------------------------------------------*/ #define MAX 2 /*车库容量*/ #define price 0.05 /*每车每分钟费用*/ typedef struct time{ int hour; int min; }Time; /*时间结点*/ typedef struct node{ char num[10]; Time reach; Time leave; }CarNode; /*车辆信息结点*/ typedef struct NODE{ CarNode *stack[MAX+1]; int top; }SeqStackCar; /*模拟车站*/ typedef struct car{ CarNode *data; struct car *next; }QueueNode; typedef struct Node{ QueueNode *head; QueueNode *rear; }LinkQueueCar; /*模拟通道*/ /*------------------------------------------------------------------------------*/ void InitStack(SeqStackCar *); /*初始化栈*/ int InitQueue(LinkQueueCar *); /*初始化便道*/ int Arrival(SeqStackCar *,LinkQueueCar *); /*车辆到达*/ void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *); /*车辆离开*/ void List(SeqStackCar,LinkQueueCar); /*显示存车信息*/ /*------------------------------------------------------------------------------*/ void main() { SeqStackCar Enter,Temp; LinkQueueCar Wait; int ch; InitStack(Enter); /*初始化车站*/