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

数据结构课程设计停车场管理问题 姓名： 学号：1、 问题描述设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。2、 实现要求要求程序输出每辆车到达后的停车位置(停车场或便道上)，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。3、 实现提示汽车的模拟输入信息格式可以是：(到达离去，汽车牌照号码，到达离去的时刻)。例如，(A，1，5)表示1号牌照车在5这个时刻到达，而(D，5，20)表示5号牌照车在20这个时刻离去。整个程序可以在输入信息为(E，0，0)时结束。本题可用栈和队列来实现。4、 需求分析 停车场采用栈式结构，停车场外的便道采用队列结构（即便道就是等候队列）。停车场的管理流程如下 当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进栈（车辆进入停车场）；如果停车场已满，则车辆进入等候队列（车辆进入便道等候）。 当车辆要求出栈时，该车到栈顶的那些车辆先弹出栈（在它之后进入的车辆必须先退出车场为它让路），再让该车出栈，其他车辆再按原次序进栈（进入车场）。当车辆出栈完毕后，检查等候队列（便道）中是否有车，有车则从队列头取出一辆车压入栈中。5、 流程图6、 详细设计 1.本程序主要包含四个模块 1) 主程序模块 int main() Initialization(); CarNode 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:Arrive(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(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; 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; printf(车辆进入车库时间:%dt现在（离开）时间:%dt停留时间:%dtn,entertime,leatime,leatime-entertime); else /车辆处在栈中间 do Pop(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-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,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 CarNode char event; int num; int time;CarNode; /车辆信息结点typedef struct SqStack CarNode *base; CarNode *top; int Stacksize;SqStack; /栈（停车场）typedef struct QNode CarNode data; struct QNode *next;QueueNode; /便道结点typedef struct LinkQueue QueueNode *front; QueueNode *rear; int queuesize;LinkQueue; /队列（便道）/=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) exit(OVERFLOW); printf(存储空间分配失败); 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,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.queuesize-; 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=S.base; while(Temp!=(S.top)&(Temp-num!=e.num) Temp+; if(Temp=S.top) return FALSE; else return 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) & (Temp-data.num!=e.num) return FALSE; else return 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.basenum) /车辆处在栈顶 Pop(S, a); leatime=e.time; leanum=e.num; entertime=a.time; printf(车辆进入车库时间:%dt现在（离开）时间:%dt停留时间:%dtn,entertime,leatime,leatime-entertime); else /车辆处在栈中间 do Pop(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-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,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)信息、车牌号以及当前时间：nn);/=int mai