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

1、精选优质文档-倾情为你奉上计算机软件技术基础 实验报告I数据结构实验二：停车场管理问题一、问题描述1.实验题目： 设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满 n辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场

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

3、0），（D，2，35），（D，4，40），（E，0，0）。每一组输入数据包括三个数据项：汽车 “到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去，E表示输入结束。其中：（A，1，5）表示1号牌照车在5这个时刻到达，而（D，1，15）表示1号牌照车在15这个时刻离去。二、需求分析 1.程序所能达到的基本可能： 本程序用来模拟一个可停放n辆车的停车场的停车管理问题。用栈和队列模拟停车场及场外通道，输入车辆状态（到达或者离开），车牌号和时间，就可显示停车位置或者该车在停车场停留时间及应缴费用。2.输入的形式及输入值范围： 程序接受5个命令，分别是：到达（A,车牌号,

4、时间)；离去(D,车牌号,时间)；停车场（P, 0, 0）显示停车场的车数；候车场（W, 0, 0）显示候车场的车数；退出（E, 0, 0）退出程序。3.输出的形式： 对于车辆到达，要输出汽车在停车场内或者便道上的停车位置；对于车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不收费）。用户输入完毕后，程序自动运行输出运行结果。4.测试数据要求： 设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）。每一组输入数据包括三个数据项：汽车 “到达”或“离去”信息

5、、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去，E表示输入结束。其中：（A，1，5）表示1号牌照车在5这个时刻到达，而（D，1，15）表示1号牌照车在15这个时刻离去。三、概要设计 为了实现上述功能，该程序以栈模拟停车场以及临时停放为给要离去的汽车让路而从停车场退出来的汽车的场地，以队列模拟车场外的便道，因此需要栈和队列这两个抽象数据类型。 1. 栈抽象数据类型定义 ： ADT SqStack 数据对象：D=ai,bi,ci,di|aiint, biint,ciint,dichar),i =1,2.,n,n0: 数据关系：R=(ai,bi,di,)|ai,bi,diD,ai,b

6、i,distruct car; 基本操作： Car_enter(carnum,cartime)/将到达车辆a的信息入栈s或者入队q Car_Leave(carnum,cartime)；/将待离开车辆d出栈s，并将q中相应车辆入栈并进行相关的操作 Result(char carmove,int carnum,int cartime)/根据输入信息完成车辆的离开或者到达 ADT SqStack ADT的C语言形式说明： typedef struct /构造一个顺序栈struct Node1 homeMaxSize; int stacktop; /栈顶的指针Stack;2. 队列抽象数据类型定义 A

7、DT LinkQueue 数据对象：D=ai,bi,ci|aiQnode*, biQnode*,ciint), i =1,2.,n,n0; 数据关系：R= 基本操作：Car_enter(carnum,cartime)/将到达车辆a的信息入栈s或者入队q Car_Leave(carnum,cartime)；/将待离开车辆d出栈s，并将q中相应车辆入栈并进行相关的操作 Result(char carmove,int carnum,int cartime)/根据输入信息完成车辆的离开或者到达 ADT LinkQueueADT的C语言形式说明：typedef struct /构建一个链式队列QNode

8、 *front,*rear;Queue; void Car_enter(int carnum,int cartime) /到达车辆的信息入栈或者入队void Car_Leave(int carnum,int cartime)/车离开int Result(char carmove,int carnum,int cartime)/根据输入信息完成车辆的离开或者达到 3. 主程序流程及其模块调用关系:1） 主程序流程： 主函数提示用户输入指令：到达（A,车牌号,时间)；离去(D,车牌号,时间)；停车场P 显示停车场的车数；候车场W显示候车场的车数；退出E退出程序。 调用int Result(char

9、 carmove,int carnum,int cartime)根据输入信息完成车辆的离开或者达到。 若输入A则调用Car_enter(int carnum,int cartime) ，创建顺序栈CarS和链式队列CarQ，根据栈是否满决定输入的信息入栈还是入队列。若栈未满，输入的车辆信息入栈，若已满，入队列。 若输入D则调用Car_Leave(int carnum,int cartime)：创建一个临时栈存放退出让路的车，若在车库中找到对应的车，车库中该车后面的车辆信息进入临时栈CarS2，该车出栈，显示车牌号，此时时间，停留时间，应缴费用。临时栈中的车的信息再回到CarS中。此时若队列Ca

10、rQ不为空则将队列中车辆信息放入栈CarS中。若在车库中找不到对应的车的车牌号信息，则在表示候车场的队列中找该车信息，如果它在队列的最后，直接出列并输出车牌号，此时时间，停留时间，应缴费用。如果它不在队尾，先把对应信息保存在一个指向队列的指针中，输出车牌号，此时时间，停留时间，应缴费用。删除队列中此结点表示此车离开候车场。 若输入P，则输出车库车辆数PCar； 若输入W，则输出候车场车辆数WCar； 若输入E，则退出程序。2） 调用关系 四、详细设计 1. 元素类型、结点类型和结点指针类型：typedef struct Node1 /构建一个结构体 int carnum; int time;N

11、ode1;typedef struct Node2 int carnum; int time; struct Node2 *next;Node2; 2、 创建顺序栈 typedef struct /构造一个顺序栈struct Node1 homeMaxSize; int stacktop; /栈顶的指针Stack;3、 创建链式队列 typedef struct /构建一个链式队列Node2 *front,*rear;Queue; 4. 车辆到达：void Car_enter(int carnum,int cartime) /到达车辆的信息入栈或者入队 if(CarS.stacktop<

12、MaxSize)/如果栈没有满的时候CarS.homeCarS.stacktop.carnum=carnum;/到达车辆信息放入顺序栈 CarS.homeCarS.stacktop.time=cartime; PCar+;/车库里的车数量+1 printf("%d号车进入停车场! 进入时刻:%d 位置:%dn",CarS.homeCarS.stacktop.carnum,CarS.homeCarS.stacktop.time,PCar);CarS.stacktop+;/栈顶指针加一else /若栈满CarQ.front->carnum=carnum; CarQ.fro

13、nt->time=cartime;/到达车辆信息加入到队列中 WCar+; /候车场车辆数+1 printf("%d号车进入候车场! 到达时刻:%d 位置:%dn",CarQ.front->carnum=carnum,CarQ.front->time=cartime,WCar); CarQ.front->next=(Node2 *)malloc(sizeof(Node2);/分配空间 CarQ.front=CarQ.front->next;/更改队列指针5. 车辆离开void Car_Leave(int carnum,int cartime)/

14、车离开Stack CarS2;/构造一个栈临时存放为了让位退出来的车 int i;int findcar=-1; Node2 *p,*f; CarS2.stacktop=0;/设临时栈CarS2为空 for(i=0;i<CarS.stacktop;i+) /通过循环对比查找要离开的车if(carnum=CarS.homei.carnum) findcar=i;/如果要寻找的车在车库里则让findcar等于车的号码 break; if(findcar!= -1) /如果在车库里找到这辆车 for(;-CarS.stacktop>findcar;CarS2.stacktop+)/将车库

15、里面在i车外面的车移动到临时栈CarS2中 CarS2.homeCarS2.stacktop.carnum=CarS.homeCarS.stacktop.carnum; CarS2.homeCarS2.stacktop.time=CarS.homeCarS.stacktop.time; printf("%d号车离开停车场! 离开时刻: %d,停留时长(%d)n",CarS.homeCarS.stacktop.carnum,cartime,cartime-CarS.homeCarS.stacktop.time); PCar-;/车库内车辆-1 printf("应付停

16、车费 %dn",(cartime-CarS.homeCarS.stacktop.time)*5); for(i=CarS2.stacktop-1;i>=0;i-)/把临时栈里面的车移回去 CarS.homeCarS.stacktop.carnum=CarS2.homei.carnum; CarS.homeCarS.stacktop.time=CarS2.homei.time; CarS.stacktop+; CarS2.stacktop-; if(CarQ.front!=CarQ.rear)/如果候车场有车，将它移进车库 CarS.homeCarS.stacktop.carnu

17、m=CarQ.rear->carnum;/将队列中的车牌号信息放入栈 CarS.homeCarS.stacktop.time=cartime;/将此时的时刻记录入栈CarS，确保计算费用是从车辆从候车场进入车库后才开始算 CarS.stacktop+; PCar+;/车库车辆数+1 WCar-;/候车场车辆数-1 p=CarQ.rear; CarQ.rear=CarQ.rear->next; free(p); else/如果车库中找不到此车，再在候车场找 p=CarQ.rear; if(p!=CarQ.front&&p->carnum!=carnum) /候车

18、场队列不为空 f=p->next; while(f!=CarQ.front&&f->carnum!=carnum) p=f; f=f->next; if(f->carnum=carnum)/如果寻找的车在便道上，出队列 findcar=1; p->next=f->next; printf("%d号车离开候车场! 离开时间: %d,停留时长(%d)n",f->carnum,cartime,cartime-f->time); WCar-; printf("应付停车费: %dn",(cartime

19、-f->time)*0); free(f); if(p->carnum=carnum)/要离开的车在队尾，直接出队 findcar=1; CarQ.rear=CarQ.rear->next; printf("%d号车离开候车场!离开时间: %d,停留时长(%d)!n",p->carnum,cartime,cartime-p->time); WCar-; printf("应付停车费: %dn",(cartime-p->time)*0); free(p); if(findcar=-1) printf("%d号车不

20、在停车场中!n",carnum);6. 主函数 main()printf("试验名称：停车场管理问题n"); printf("学号：n"); printf("姓名：xxn"); printf("=n"); time_t rawtime1; struct tm * timeinfo1; time (&rawtime1); timeinfo1 = localtime (&rawtime1); /时间函数；printf ("程序运行开始,当前日期和时间: %s", ascti

21、me(timeinfo1);int go=1,carnum,cartime,MM; char carmove; CarS.stacktop=0; CarQ.rear=CarQ.front=(Node2 *)malloc(sizeof(Node2); while(go) printf("n车辆到达请输入A;n车辆离开请输入D;n显示停车场内车数请输入P;n显示候车场车数请输入W;n退出程序请输入E:n"); printf("n请输入信息:");carmove=getchar(); printf("n"); switch(carmove)

22、 case 'A': printf("%cn车牌号:t",carmove); scanf("%d",&carnum); printf("时间:t"); scanf("%d",&cartime); MM=Result(carmove,carnum,cartime); if(!MM)go=0; break; case 'D': printf("%cn车牌号:t",carmove); scanf("%d",&carnum);

23、printf("现在时刻:t"); scanf("%d",&cartime); MM=Result(carmove,carnum,cartime); if(!MM)go=0; break; case 'W': printf("正在外通道等待的车数量是: %dn",WCar); break; case 'P': printf("车库内车的数量是: %dn",PCar); break; case 'E':printf("退出!n"); time

24、_t rawtime2; struct tm * timeinfo2; time (&rawtime2); timeinfo2 = localtime (&rawtime2); printf ("程序运行结束,当前日期和时间: %s", asctime(timeinfo2); return 0; getchar();五、调试分析 此程序是分模块设计，根据输入的指令调用“到达”和“离开”模块，使车的信息入栈入队，或出栈出队。每次运行后又返回主菜单。程序整体结构清晰，操作方便。六、使用说明用户根据提示输入指令：到达输入A,离开输入D，显示车库车辆数输入P，显示候

25、车场车辆数输入W，退出程序输入E。输入A后，根据提示输入车牌号i和此时时间，将显示“第i号车进入车库！时间： 位置：”或“第i号车进入候车场！时间： 位置：”；输入D后，根据提示输入车牌号i和此时时间，将显示“第i号车离开车库！时间： 停留时间： 应缴费用：”。或“第i号车离开候车场！时间： 停留时间： 应缴费用：”；输入W后显示“正在外通道等待的车数量是：”；输入P后显示“车库内车的数量是”；输入E后退出程序。七、调试结果 设车库最大容量为2.输入一组数据进行测试：（A，1，5），（A，2，10），（D，1，15），（A，3， 20），（A，4，25），（A，5，30），（D，2，35），（

26、D，4，40），（E，0，0）。初始界面为：输入到达车辆：到达车辆超过车库容量时：输入车辆离开信息：输入P输入W：输入E：八 、遇到的问题和解决方法1. 开始，程序编写完成后虽然没有报错，却不能运行，如图经检查程序，将Stack *CarS; Queue *CarQ; 这两个指针型变量改成Stack CarS; /用来表示车库的栈Queue CarQ; /用来表示候车场的队列，再次运行发现可以成功运行。2. 当输入上述数据后输入P和W后显示的车辆数不对，当车库内车辆离开时，外通道的车进入车库，但PCar和WCar没有正确跟随变化，如图经检查程序，在if(CarQ.front!=CarQ.rea

27、r)/如果候车场有车，将它移进车库 CarS.homeCarS.stacktop.carnum=CarQ.rear->carnum;/将队列中的车牌号信息放入栈 CarS.homeCarS.stacktop.time=cartime;/将此时的时刻记录入栈CarS，确保计算费用是从车辆从候车场进入车库后才开始算 CarS.stacktop+; p=CarQ.rear; CarQ.rear=CarQ.rear->next; free(p);这段程序中少了 PCar+; WCar-;，加上后再次运行，程序正确。3.计算费用时发现错误，在候车厅时间也被计入停车费。经检查程序，将CarS.

28、homeCarS.stacktop.time=CarQ.rear->time;改成CarS.homeCarS.stacktop.time=cartime;使其计费时间从进入车库开始而不是从达到候车场开始。再次运行发现结果正确。九、实验收货和感想 这是第一次运用栈和队列的相关知识编写程序，开始看到这个题目感觉挑战很大，从未尝试过这么复杂的一个系统。停车场问题相较与约瑟夫斯问题要复杂得多，分了多个模块。起初编写时漏洞很多，好在当框架出来后各个漏洞都可以被弥补。比如程序刚运行成功时，发现不能显示位置，车库车辆数和候车场车辆数不正确，计费不正确等很多漏洞，但这些细节的小问题都比较容易排查修改，最

29、终终于做出了符合要求的停车场管理系统。当完成后，我对栈和队列的相关算法的理解也更加清晰深刻了。这个程序中还有一些灵活可变的地方，用宏定义定义了车库容量和费用单价，使具体数字可以较为灵活的改变，增加了这个程序的使用价值。计算机实践课程给了我动手操作的机会，使我将理论和实际操作结合起来，更好地理解算法，更快地学会编程。每次编程都感觉收获非常多。练习的越多，对算法语句越是熟练，越能有深刻的理解，不仅帮助我更好的学习软件技术基础也为以后我们专业课的道路打好基石，对我们的逻辑能力也是很大的提升。十、源程序#include<stdio.h>#include<stdlib.h>#in

30、clude <time.h>#define MaxSize 2/车库最大容量#define fee 10/在车库中停车的单价typedef struct Node1 /构建一个结构体 int carnum; int time;Node1;typedef struct /构造一个顺序栈struct Node1 homeMaxSize; int stacktop; /栈顶的指针Stack;typedef struct Node2 int carnum; int time; struct Node2 *next;Node2; typedef struct /构建一个链式队列Node2 *

31、front,*rear;Queue; Stack CarS; /用来表示车库的栈Queue CarQ; /用来表示候车场的队列int PCar=0;/车库里车的数量int WCar=0;/候车场的车的数量void Car_enter(int carnum,int cartime) /到达车辆的信息入栈或者入队 if(CarS.stacktop<MaxSize)/如果栈没有满的时候CarS.homeCarS.stacktop.carnum=carnum;/到达车辆信息放入顺序栈 CarS.homeCarS.stacktop.time=cartime; PCar+;/车库里的车数量+1 pr

32、intf("%d号车进入停车场! 进入时刻:%d 位置:%dn",CarS.homeCarS.stacktop.carnum,CarS.homeCarS.stacktop.time,PCar);CarS.stacktop+;/栈顶指针加一else /若栈满CarQ.front->carnum=carnum; CarQ.front->time=cartime;/到达车辆信息加入到队列中 WCar+; /候车场车辆数+1 printf("%d号车进入候车场! 到达时刻:%d 位置:%dn",CarQ.front->carnum=carnum

33、,CarQ.front->time=cartime,WCar); CarQ.front->next=(Node2 *)malloc(sizeof(Node2);/分配空间 CarQ.front=CarQ.front->next;/更改队列指针void Car_Leave(int carnum,int cartime)/车离开Stack CarS2;/构造一个栈临时存放为了让位退出来的车 int i;int findcar=-1; Node2 *p,*f; CarS2.stacktop=0;/设临时栈CarS2为空 for(i=0;i<CarS.stacktop;i+)

34、/通过循环对比查找要离开的车if(carnum=CarS.homei.carnum) findcar=i;/如果要寻找的车在车库里则让findcar等于车的号码 break; if(findcar!= -1) /如果在车库里找到这辆车 for(;-CarS.stacktop>findcar;CarS2.stacktop+)/将车库里面在i车外面的车移动到临时栈CarS2中 CarS2.homeCarS2.stacktop.carnum=CarS.homeCarS.stacktop.carnum; CarS2.homeCarS2.stacktop.time=CarS.homeCarS.st

35、acktop.time; printf("%d号车离开停车场! 离开时刻: %d,停留时长(%d)n",CarS.homeCarS.stacktop.carnum,cartime,cartime-CarS.homeCarS.stacktop.time); PCar-;/车库内车辆-1 printf("应付停车费 %dn",(cartime-CarS.homeCarS.stacktop.time)*5); for(i=CarS2.stacktop-1;i>=0;i-)/把临时栈里面的车移回去 CarS.homeCarS.stacktop.carnum

36、=CarS2.homei.carnum; CarS.homeCarS.stacktop.time=CarS2.homei.time; CarS.stacktop+; CarS2.stacktop-; if(CarQ.front!=CarQ.rear)/如果候车场有车，将它移进车库 CarS.homeCarS.stacktop.carnum=CarQ.rear->carnum;/将队列中的车牌号信息放入栈 CarS.homeCarS.stacktop.time=cartime;/将此时的时刻记录入栈CarS，确保计算费用是从车辆从候车场进入车库后才开始算 CarS.stacktop+; P

37、Car+;/车库车辆数+1 WCar-;/候车场车辆数-1 p=CarQ.rear; CarQ.rear=CarQ.rear->next; free(p); else/如果车库中找不到此车，再在候车场找 p=CarQ.rear; if(p!=CarQ.front&&p->carnum!=carnum) /候车场队列不为空 f=p->next; while(f!=CarQ.front&&f->carnum!=carnum) p=f; f=f->next; if(f->carnum=carnum)/如果寻找的车在便道上，出队列 f

38、indcar=1; p->next=f->next; printf("%d号车离开候车场! 离开时间: %d,停留时长(%d)n",f->carnum,cartime,cartime-f->time); WCar-; printf("应付停车费: %dn",(cartime-f->time)*0); free(f); if(p->carnum=carnum)/要离开的车在队尾，直接出队 findcar=1; CarQ.rear=CarQ.rear->next; printf("%d号车离开候车场!离开时

39、间: %d,停留时长(%d)!n",p->carnum,cartime,cartime-p->time); WCar-; printf("应付停车费: %dn",(cartime-p->time)*0); free(p); if(findcar=-1) printf("%d号车不在停车场中!n",carnum);int Result(char carmove,int carnum,int cartime)/根据输入信息完成车辆的离开或者达到switch(carmove) case 'A':Car_enter(carnum,cartime);break; case 'D':Car_Leave(carnum,cartime);break; default :printf("输入错误!n");break; return 1;main()printf("试验名称：停车场管理问题n"