停车场管理问题

1、停车场管理问题实验二：停车场管理问题一问题描述1. 实验题目：设停车场是一个可停放n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满n 辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。 每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。2. 基本要求：以

2、栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项：汽车的“到达"（'A'表示）或“离去" （'D表示）信息、汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。3. 测试数据：设n=2, 输入数据为：（ A ，1，5） ，（ A ，2， 10） ，（ D ， 1， 15） ，（ A ， 3，2

3、0 ） ， （ A ，4，25） ， （ A ，5，30）， （ D ，2，35） ， （ D ， 4，40） ， （ E ， 0，0） 。每一组输入数据包括三个数据项：汽车 “到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，'A'表示到达；D表示离去，'E'表示输入结束。其中：（'A', 1, 5）表示1号牌照车 在 5 这个时刻到达，而（ D ， 1， 15）表示1 号牌照车在15 这个时刻离去。二需求分析1. 程序所能达到的基本可能：程序以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。栈以顺序结构实

4、现，队列以链表结构实现。同时另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车。输入数据按到达或离去的时刻有序。当输入数据包括数据项为汽车的“到达" （'A'表示）信息，汽车标识（牌照号）以及到达时刻时，应输出汽车在停车场内或者便道上的停车位置；当输入数据包括数据项为汽车的“离去"（'D'表示）信息，汽车标识（牌照号）以及离去时刻时，应输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）；当输入数据项为（ P ， 0， 0）时，应输出停车场的车数；当输入数据项为（ W , 0, 0 ）时，应输出候车场车数；当输入数据

5、项为（ E , 0, 0 ） ，退出程序；2. 输入输出形式及输入值范围：程序运行后进入循环，显示提示信息： “请输入停车场最大容量 n=: ”，提示用户输入停车场最大容量，输入后显示提示信息：请输入车辆信息，提示用户输入车辆信息（ “到达”或者“离开” ， 车牌编号，到达或者离开的时间）。 若车辆信息为 “到达A”， 车辆信息开始进栈（ 模拟停车场），当栈满，车辆会进队列（模拟停车场旁便道），若车辆信息为“离开D”，会显示该车进入停车场的时间以及相应的停车费用，若该车较部分车早进停车场，这部分车需先退出停车场，暂时进入一个新栈为其让道，当待离开车离开停车场后，这部分车会重新进入停车场，同时便

6、道上的第一辆车进入停车场；若输入（ P ， 0， 0） ，会显示停车场的车数；若输入（ W ， 0， 0） ，会显示便道上的车数；若输入（ E ， 0， 0） ，程序会跳出循环，同时程序结束。用户每输入一组数据，程序就会根据相应输入给出输出。输入值第一个必须为字母，后两个为数字，中间用逗号隔开3. 测试数据要求：设n=2, 输入数据为：（ A ，1，5） ，（ A ，2，10） ， （ D ， 1， 15） ， （ A ，3，20 ） ， （ A ，4，25） ， （ A ，5， 30）， （ D ，2，35） ， （ D， 4， 40） ， （ E ， 0， 0） 。三概要设计1. 所用到得

7、数据结构及其ADT为了实现上述功能，该程序以顺序栈模拟停车场以及临时停放为给要离去的汽车让路而从停车场退出来的汽车的场地，以链表队列模拟车场外的便道，因此需要栈和队列这两个抽象数据类型。顺序栈数据类型定义typedef struct Stackstruct Node dataMaxSize;int top;int num;SqStack;基本操作：SqStack *Init_SeqStack（）/ 置空栈int ISEmpty_SeqStack（SqStack *s）/ 判断栈是否为空，栈为空返回1int ISFULL_SeqStack（SqStack *s,int n）/ 判断栈是否已满，若

8、栈满返回1void Push_SeqStack（SqStack *p,struct Node s） /入栈int POP_SeqStack（SqStack *s,struct Node car）/出栈2. 链表队列数据类型定义QNODE / 队列节点 struct Node data;3 / 19停车场管理问题QNODE *next;；typedef struct linkqueue /队列结构体定义QNODE *front,*rear;int num;LinkQueue;基本操作:LinkQueue *Init_LQueue() /创建空队列int ISEmpty_LQueue(LinkQu

9、eue *q)/判断队列是否为空，队列为空返回void IN_Lqueue( LinkQueue *q,struct Node s) /入队struct Node Out_LQueue(LinkQueue *q) /出队2.主程序流程及其模块调用关系1）主程序模块开始初始界面显示输入停车场最大容量n输入车辆信息N* car.AL='A'car.AL='D'car.AL='P； car.NO=0 car.time=0N car.AL='W；car.NO=Qcar.time=0N- car.AL!='E'栈满Y出栈，输出车辆停留时间J

10、'显示停车场的车数显示候车场的车数车辆在停车场的位置进入队列输出车辆在便道的位置输入车辆信息进栈，车辆从便道进入停车场*输入结束结束2）出栈9 / 19开始13）判断栈是否为空开始s->top =-1栈空返回 1栈不为空返回0结束4）判断栈是否已满s->top =n-1栈不满返回05)判断队列是否为空队列空返回1队列不为空返回6)出队函数调用:main()函数中调用:ISFULL_SeqStack(parkstack,n) ,IN_Lqueue(parkqueue,car);Push_SeqStack(parkstack,car);t=POP_SeqStack(parkst

11、ack,car);ISEmpty_LQueue(parkqueue)=0 ;Push_SeqStack(parkstack,Out_LQueue(parkqueue);POP_SeqStack(SqStack *s,struct Node car)出栈函数中调用:Init_SeqStack();Push_SeqStack(p,s->datas->top);ISEmpty_SeqStack(p)=0函数调用关系图详细设计四、1.实现每个操作的伪码，重点语句加注释1）主程序模块 int main()SqStack *parkstack;/parkstack 为表示停车场的栈LinkQu

12、eue *parkqueue; /parkqueue为表示便道的队歹Ustruct Node car;停车场管理问题为停车场栈的最大容量int n,a=0,t;/ntime_t rawtime;struct tm * timeinfo;time (&rawtime);timeinfo = localtime (&rawtime);parkstack=Init_SeqStack();parkqueue=Init_LQueue();15 / 19printf("/*/n"); /初始界面printf("学号： 031350102n");pri

13、ntf("姓名：王亚文n");printf("停车场管理问题n");printf("/*/n");printf(" 请输入停车场最大容量n=n");scanf("%d",&n);printf(" 请输入车辆信息n");scanf("%c,%d,%d",&car.AL,&car.NO,&car.time);while(car.AL!='E')if(car.AL='A' )/ 汽车到达的情况if(

14、ISFULL_SeqStack(parkstack,n)=1)/ 栈满的情况IN_Lqueue(parkqueue,car);/ 进入队列等待printf("这辆车在门外便道上第外位置n",parkqueue->num);printf("n");printf(" 请输入车辆信息n");else Push_SeqStack(parkstack,car);/ 入栈printf("这辆车在停车场内第 d个位置n",parkstack->num);printf("n");printf(&qu

15、ot; 请输入车辆信息n");if(car.AL='D' )/ 汽车离开的情况t=POP_SeqStack(parkstack,car);/出栈printf(" 这辆车停留时间为%dn",t);printf("n");printf(" 请输入车辆信息n");if(ISEmpty_LQueue(parkqueue)=0) /队列不为空需要进栈Push_SeqStack(parkstack,Out_LQueue(parkqueue) ); if(car.AL='P'&&car.NO

16、=0&&car.time=0 )/显示停车场的车数printf("停车场的车数为%dn",parkstack->num);printf("n");printf("请输入车辆信息n");if(car.AL='W'&&car.NO=0&&car.time=0 )/显示候车场的车数printf(" 候车场的车数为%dn",parkqueue->num);printf("n");printf(" 请输入车辆信息n&qu

17、ot;);scanf("%c,%d,%d",&car.AL,&car.NO,&car.time);printf(" 输入结束n");return 1;2)置空栈模块SqStack *Init_SeqStack()/ 置空栈SqStack *s;s=(SqStack*)malloc(sizeof(SqStack);s->top=-1;s->num=0;return s;3)创建空队列模块LinkQueue *Init_LQueue() /创建空队列LinkQueue *q;QNODE *p;q=(LinkQueue*)m

18、alloc(sizeof(LinkQueue);p=(QNODE*)malloc(sizeof(QNODE);p->next=NULL;q->front=q->rear=p;q->num=0;return q;4)判断栈是否为空模块int ISEmpty_SeqStack(SqStack *s)if(s->top =-1)return 1;elsereturn 0;5)判断栈是否已满模块int ISFULL_SeqStack(SqStack *s,int n)if(s->top=n-1)return 1;elsereturn 0;6)判断队列是否为空模块in

19、t ISEmpty_LQueue(LinkQueue *q)/ 判断栈是否为空，栈为空返回1/ 判断栈是否已满，若栈满返回1/ 判断队列是否为空，队列为空返回1if(q->front=q->rear)return 1;elsereturn 0;7)入队模块void IN_Lqueue( LinkQueue *q,struct Node s) /入队QNODE *p;p=(QNODE*)malloc(sizeof(QNODE);p->data=s;q->num+;p->next=NULL;q->rear->next =p;q->rear =p;8)

20、入栈模块void Push_SeqStack(SqStack *p,struct Node s) /入栈p->top +;p->datap->top=s;p->num+;9)出栈模块int POP_SeqStack(SqStack *s,struct Node car)/出栈SqStack *p;int t;p=Init_SeqStack();while(s->datas->top.NO !=car.NO)找到车牌号为 P.NO 的车,Push_SeqStack(p,s->datas->top);s->top-;s->num-;t=c

21、ar.time-s->datas->top.time;s->top-;s->num-;while(ISEmpty_SeqStack(p)=0) Push_SeqStack(s,p->datap->top);p->top-;p->num-; return t;10)出队模块struct Node Out_LQueue(LinkQueue *q) / 出队QNODE *p;p=q->front->next;q->front->next=p->next;q->num -;if( q->front->nex

22、t=NULL) q->rear=q->front;return p->data;free(p);五、 调试分析1 . 设计与调试过程中遇到的问题分析、体会1)编写代码时，由于对栈和队列不熟悉，经常会一些问题，该程序定义了车辆信息，停车场的顺序栈，便道上的链表队列，所以在函数代值时会出现代值的问题，例如在出栈的程序POP_SeqStack(SqStack *s,struct Node car) 中一开始在s->datas->top.NO !=car.NO这句话中我编的代码是s->data.NO !=car.NO' 程序报错.NO' : left

23、 operand points to'struct', use '->' ， 这就是因为定义的太多了，忘记了当初定义的停车场栈是：struct NodedataMaxSize; 就是像程序中s->datas->top.time 这样的定义因为太长了经常会搞混，再次像IN_Lqueue(parkqueue,car); ， Push_SeqStack(parkstack,car); 这 种 涉 及 函数调用的尤其要注意代的应该是什么。2)这个程序设计时还有一个问题就是有关结构体的输入问题，一开始我的程序是printf("停车场管理问题请输

24、入车辆状 态信息n");scanf("%c",&car.AL);printf("请输入车辆车牌号n");scanf( "%d",&car.NO,);printf(" 请输入车辆时间 n"); scanf("%d",&car.time );程 序 没 有 报 错， 但 在 输 入 时 就 有 问 题 了，Y7"rtln''i CuF'rent ILocail tine 或nd daite 卓车场最大容量L需验名祢：实验二停车场管理

25、问题求解 学号工0313501呢后来将程序改为 printf(" 请输入车辆信息 n");scanf("%c,%d,%d",&car.AL,&car.NO,&car.time);之后程序可以正常运行了3)再次本程序由于多次涉及到程序调用。一开始我比较喜欢把所有的语句全写在主程序中，在简单的程序这种方法是可行的，但是这个程序由于有些函数像 Push_SeqStack(p,s->datas->top);ISEmpty_SeqStack(p)=0会多次用到，所以考虑写子程序，这样减少了程序的复杂性，主函数也更加简单明了。2

26、.主要算法的时间复杂度分析主函数中 对每次输入的车辆信息只选择其中一个执行，时间复杂度 O (1);空间复杂度 O (1);入栈入队列函数根据判断条件将数据入栈或入队列，时间复杂度O (1);空间复杂度O (1);出栈数据不在最顶端需将n个数据先出该栈，再入新栈，再回旧栈，时间复杂度O(n);空间复杂度O (1);六、使用说明程序运行后进入循环，显示提示信息：“请输入停车场最大容量 n=:"，提示用户输入停车场最大容量，输入后显示提示信息：请输入车辆信息，提示用户输入车辆信息(“到达”或者“离开”，车牌编号，到达或者离开的时间)。若车辆信息为“到达A”，车辆信息开始进栈(模 拟停车场

27、)，当栈满，车辆会进队列(模拟停车场旁便道)，若车辆信息为“离开D”，会显示该车进入停车场的时间以及相应的停车费用，若该车较部分车早进停车场，这部分车需先退出停车场，暂时进入一个新栈为其让道，当待离开车离开停车场后，这部分车会重新进入停车场，同时便道上的第一辆车进入停车场；若输入('P', 0, 0),会显示停车场的车数；若输入(W, 0, 0),会显示便道上的车数；若输入('E', 0, 0),程序会跳出循环，同时 程序结束。用户每输入一组数据，程序就会根据相应输入给出输出。输入值第一个必须为字母，后两个为数字，中间用逗号隔开 七、测试结果*C:UiEk&am

28、p;ADMlNl£TFLATORDE5K7OPVCipebugCl.eJte-等验名掰 实验二 停车场管理问题求解学号：031350102姓名；王业文 程序运行开始，Current Locdtl t ine and date ：Tue Nuv S3 IS：03 ：47 2815请输入盗车场最大容量n=工输入车辆信息尚翻冬在停车场内第1个位置请输入车辆信息这辆车在停车场内第2个位置请输入车辆信息苣东皇停留时间为岂请输入车辆信息ft,3,20这辆车在停车场内第2个位置请输入车辆信息ft,4.25这辆车在门外便道上第1个位置请输入车辆信息ft,5.30这辆车在门外便道上第2个位置请输入车辆

29、信息H2.35这辆车停留时间为如请输入车辆信息D.4M0这辆车停留时间为1E清输入车辆信息E, 0, 0输入结束Gwrrent loc<il tine and datc；Tue Nov 阴 3 16 ； 03 = 4? 2015八、附录#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <time.h> typedef int ElemType;#define MaxSize 10017 / 19停车场管理问题#define QNODE struct QNodet

30、ypedef struct Node/ 车辆信息char AL;int NO;int time;Node;typedef struct Stack/ 栈定义struct Node dataMaxSize;int top;int num;SqStack;QNODE / 队列节点 struct Node data;QNODE *next;typedef struct linkqueue /队列结构体定义QNODE *front,*rear;int num;LinkQueue;SqStack *Init_SeqStack()/ 置空栈SqStack *s;s=(SqStack*)malloc(siz

31、eof(SqStack);s->top=-1;s->num=0;return s;LinkQueue *Init_LQueue() /创建空队列24 / 19LinkQueue *q;QNODE *p;q=(LinkQueue*)malloc(sizeof(LinkQueue);p=(QNODE*)malloc(sizeof(QNODE);p->next=NULL;q->front=q->rear=p;q->num=0;return q;int ISEmpty_SeqStack(SqStack *s)if(s->top =-1)return 1;els

32、ereturn 0;int ISFULL_SeqStack(SqStack *s,int n)if(s->top=n-1)return 1;elsereturn 0;int ISEmpty_LQueue(LinkQueue *q)if(q->front=q->rear)return 1;elsereturn 0;void IN_Lqueue( LinkQueue *q,struct Node s) / 判断栈是否为空，栈为空返回1/ 判断栈是否已满，若栈满返回1/ 判断队列是否为空，队列为空返回1入队QNODE *p;p=(QNODE*)malloc(sizeof(QNODE

33、);p->data=s;q->num+;p->next=NULL;q->rear->next =p;q->rear =p;void Push_SeqStack(SqStack *p,struct Node s) /入栈p->top +;p->datap->top=s;p->num+;int POP_SeqStack(SqStack *s,struct Node car)/出栈SqStack *p;int t;p=Init_SeqStack();while(s->datas->top.NO !=car.NO)找到车牌号为 P

34、.NO 的车,Push_SeqStack(p,s->datas->top);s->top-;s->num-;t=car.time-s->datas->top.time;s->top-;s->num-;while(ISEmpty_SeqStack(p)=0)Push_SeqStack(s,p->datap->top);p->top-;p->num-;return t;struct Node Out_LQueue(LinkQueue *q) / 出队QNODE *p; p=q->front->next;q->

35、front->next=p->next;q->num -;if( q->front->next=NULL) q->rear=q->front;return p->data; free(p);int main()SqStack *parkstack;/parkstack 为表示停车场的栈LinkQueue *parkqueue; /parkqueue为表示便道的队列struct Node car;int n,a=0,t;/n为停车场栈的最大容量time_t rawtime;struct tm * timeinfo;time (&rawtim

36、e);timeinfo = localtime (&rawtime); parkstack=Init_SeqStack();parkqueue=Init_LQueue(); / 初始界面printf(" 实验名称：实验二停车场管理问题求解n");printf(" 学号： 031350102n");printf(" 姓名：王亚文n");printf("=n");printf(" 程序运行开始，");printf("Current local time and date:%s&qu

37、ot;,asctime(timeinfo);printf(" 请输入停车场最大容量n=n");scanf("%d",&n);printf(" 请输入车辆信息n");scanf("%c,%d,%d",&car.AL,&car.NO,&car.time); while(car.AL!='E') if(car.AL='A' )/ 汽车到达的情况if(ISFULL_SeqStack(parkstack,n)=1)/ 栈满的情况IN_Lqueue(parkque

38、ue,car);/ 进入队列等待printf("这辆车在门外便道上第外位置n",parkqueue->num);printf("n");printf(" 请输入车辆信息n"); elsePush_SeqStack(parkstack,car);/ 入栈printf("这辆车在停车场内第 d个位置n",parkstack->num);printf("n");printf(" 请输入车辆信息n");if(car.AL='D' )/ 汽车离开的情况t=POP_SeqSta