数据结构课程设计——停车场管理问题姓名:学号: 问题描述设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。
车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。
如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。
停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。
每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。
如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。
编制一程序模拟该停车场的管理。
二、实现要求要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。
三、实现提示汽车的模拟输入信息格式可以是：（到达/离去，汽车牌照号码，到达/离去的时刻）。
例如，（‘A'，，1，5）表示1号牌照车在5这个时刻到达，而（‘ D '，，5，20）表示5号牌照车在20这个时刻离去。
整个程序可以在输入信息为（‘ E '，0，0）时结束。
本题可用栈和队列来实现。
四、需求分析停车场采用栈式结构，停车场外的便道采用队列结构（即便道就是等候队列）。
停车场的管理流程如下①当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进栈（车辆进入停车场）；如果停车场已满，则车辆进入等候队列（车辆进入便道等候）。
②当车辆要求出栈时，该车到栈顶的那些车辆先弹出栈（在它之后进入的车辆必须先退出车场为它让路），再让该车出栈，其他车辆再按原次序进栈（进入车场）。
当车辆出栈完毕后，检查等候队列（便道）中是否有车，有车则从队列头取出一辆车压入栈中。
五、流程图六、详细设计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 lnitQueue(LinkQueue &Q){ //构造一个空队列(带头结点) Q.front=Q.rear=(QueueNode*)malloc(sizeof(QueueNode));if(!Q.front){exit(OVERFLOW);printf("存储空间分配失败");}Q.front->next=NULL;Q.queuesize=O;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.base<MAX){Push(S,e);printf("成功进入停车场，在%d号车库!\n",S.top-S.base);return OK;}else{EnQueue(Q,e);printf("停车场已满，车辆进入便道，在%d号车位!\n",Q.queuesize);elseprintf("该牌照的车已存在，输入有误，请重新输入\n");return OK;}else{printf("时间输入有误，请重新输入!\n");return FALSE;}}4) 车辆离开处理Status Leave(SqStack & S,SqStack & TempS,LinkQueue & Q,CarNode &e){ //车辆离开处理CarNode a;int leatime,leanum;int entertime; //进入停车场时间int cost;if(!(Check_Stack(S,e) || Check_Queue(Q,e))){printf("数据输入错误，本停车场内无所查询车辆，请重新输入！\n");return true;}else{if(Check_Stack(S,e)) 〃若需要离开的车辆在停车场{if(e.num==(S.top-1)->num) // 车辆处在栈顶{Pop(S, a);leatime=e.time;leanum=e.num;entertime=a.time;printf(”车辆进入车库时间：％d\t现在(离开)时间：％d\t停留时「可:％d\t\n",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("车进入停车场时间:%d\t现在(离开)时间:%d\t停留时「可:%d\t\n",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的车应交纳的费用是：％d\n",leanum,cost);if(Q.front!=Q.rear){ //队列不空的话从便道进停车场DeQueue(Q,a);if(a.timevleatime) //便道车辆进车库时间应该比车库车辆离开时间晚entertime=leatime;a.time=leatime;Push(S,a); //该车进入停车场printf("车牌号为%d的车辆从便道上进入%d号车库！从现在开始计时，现在时间为：%d\n",a.num,S.top-S.base,a.time);}}else if(Check_Queue(Q,e)){ 〃从便道直接离开do{DeQueue(Q,a);EnQueue(Q,a);}while(Q.front->next->data.num!=e.num);DeQueue(Q,e); 〃前面的车进入队尾printf("您的车牌号为%d的车辆未进入车库从便道直接离开，费用为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 -2typedef int Status;//typedef struct CarNode{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 lnitStack(SqStack & S){ 〃构造一个空栈S.Stacksize=O;S.base=(CarNode*)malloc((MAX)*sizeof(CarNode));if(!S.base){exit(OVERFLOW);printf("存储空间分配失败");}S.top=S.base;}//===================================================================== Status lnitQueue(LinkQueue & Q){ // 构造一个空队列(带头结点)Q.front=Q.rear=(QueueNode*)malloc(sizeof(QueueNode));if(!Q.front){exit(OVERFLOW);printf(”存储空间分配失败");}Q.front->next=NULL;Q.queuesize=O;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;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) && (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)){ // 是否已存在if(S.top-S.base<MAX){Push(S,e);printf("成功进入停车场，在%d号车库!\n",S.top-S.base);return OK;} else{EnQueue(Q,e);printf（”停车场已满，车辆进入便道，在％d号车位!\n",Q.queuesize）;}elseprintf("该牌照的车已存在，输入有误，请重新输入\n");return OK;}else{printf("时间输入有误，请重新输入!\n");return FALSE;}}//========================================================Status Leave(SqStack & S,SqStack &TempS,LinkQueue & Q,CarNode &e){ //车辆离开处理CarNode a;int leatime,leanum;int entertime; //进入停车场时间int cost;if(!(Check_Stack(S,e) || Check_Queue(Q,e))){printf("数据输入错误，本停车场内无所查询车辆，请重新输入！\n");return true;}else{if(Check_Stack(S,e)) //若需要离开的车辆在停车场{if(e.num==(S.top-1)->num) // 车辆处在栈顶{Pop(S, a);leatime=e.time;leanum=e.num;entertime=a.time;printf("车辆进入车库时间：％d\t现在(离开)时间：％d\t停留时「可:%d\t\n",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("车进入停车场时间:%d\t现在(离开)时间:%d\t停留时「可:%d\t\n",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的车应交纳的费用是：％d\n",leanum,cost);if(Q.front!=Q.rear){ //队列不空的话从便道进停车场DeQueue(Q,a);if(a.timevleatime) //便道车辆进车库时间应该比车库车辆离开时间晚entertime=leatime;a.time=leatime;Push(S,a); //该车进入停车场printf(”车牌号为%d的车辆从便道上进入%d号车库！从现在开始计时，现在时间为：％d\n",a.num,S.top-S.base,a.time);}}else if(Check_Queue(Q,e)){ 〃从便道直接离开do{DeQueue(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 lnitialization(){ // 初始化程序printf("姓名：杨智伟学号：2012040651\n");printf("==========================================================\n");printf("* 停车场管理模拟程序*\n");printf("==========================================================\n");printf("请依次输入车辆到达(A/a)/离去(D/d)/结束(E/e)信息、车牌号以及当前时间：\n\n"); } //===================================================================== 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;}七、程序运行截图1 .交互界面2 .车辆进入= =■==■= = = = =■ = = == = = = = = == = = = = = = == = = === = =* * r车场管理模拟程序请依次输人车辆到达<A/a>/离去<D/d>z结耒信息“车稈母以及当前吋厲h a1 S *成功进入停车场■在1容车库，2 10成功进入停车场•在2号车库？3. 车辆离去- 停车场管理模拟程序*LH.E=. = = = H,=. =.=：™S = =.=.= —— E. =.=.= —S=.=.=. = =S=.=.=. = B« = =.=.™S = =.=.= ——S = =. = S 请依次输入车辆到达<ftz a>z离去5”结束车牌号以及当前时间「a 1 5成功逬入停车场■在1号车眸？a 2 10成功进入停车场”在2号车库？d 1 5 出李进入僵丰场时冋汚圳在「离开）时百停留时间洱您的车楝寻为i關车应交纳的费用是洱4. 停车场已满进入便道- 停车场管理模拟程序*an23.= Z2.£：E；S3ZZ=SSE3iZS： = E12!E=.ZIZZSS.S=2Z = 2ZEi=S3Z2 = lZ=：ST3.= Er：：3.J=SE22Z£-ESS.S2E = E.E3E.S!=.= £l=S2请依次输入辛辆到达“心"高去＜w 结東CE/I信息、车牌号以及当前时间:甘 1 5成功进入停车场.在i昏车.库甲A 2 10成功进入停车场「在2号■车库甲霸鑼觀算轨交髓靈2时恥停留时间汨a 3 20咸功进入停车场•在去号车库甲衫车场已满.车辆进入侵道■在，号车位亍a 5 305. 便道车辆进入车库吓譽硼停留时恥¥入溥车库甲从现衽幵始计时，现衽时间为*6.程序结束界面八、实验总结i •学会了栈和队列的综合使用，更加灵活运用栈和队列。