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

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，

3、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. 程序所能达到的基本可能：本程序用来模拟一个可停放 n 辆车的停车场的停车管理问题。 用栈和队列模拟停车场及场外通道，输入车辆状态（到达或者离开） ，车牌号和时间，就可显示停车位置或者该车在停车场停留时间及应缴费用。2. 输入的形式及输

4、入值范围：程序接受 5 个命令，分别是：到达（ A , 车牌号 , 时间 ) ；离去 ( 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，2

5、5），（ 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.栈抽象数据类型定义：ADT SqStack数据对象：D=a

6、i,bi,ci,di|aiint, bi int,ci int,di char),i =1,2.,n,n 0:数据关系：R=(ai,bi,di,)|ai,bi,di D,ai,bi,di struct car;基本操作：Car_enter(carnum,cartime).,n,n 0 ;数据关系： R= ?基本操作：Car_enter(carnum,cartime)主程序流程及其模块调用关系:1）主程序流程：主函数提示用户输入指令：到达（A, 车牌号 , 时间 ) ；离去 ( D, 车牌号 , 时间 ) ；停车场 P 显示停车场的车数；候车场W显示候车场的车数；退出E退出程序。调用 int R

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

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

9、artime;PCar+;arnum,.time,PCar);+;arnum)findcar=i;arnum=.carnum;.time=.time;printf(%d 号 车 离 开 停 车 场 ! 离 开 时 刻 : %d, 停 留 时 长 (%d)n,.carnum,cartime,.time);PCar-;ime)*5);for(i=;i=0;i-)arnum=i.carnum;.time=i.time;+;if!=arnum=carnum;ime=cartime;入一组数据进行测试：（ A，1，5），（ A，2，10），（D，1，15），（A，3， 20 ），（A，4，25），（A，

10、5，30），（D，2，35），（D，4，40），（E，0，0）。初始界面为：输入到达车辆：到达车辆超过车库容量时：输入车辆离开信息：输入 P输入 W：输入 E：八 、遇到的问题和解决方法1. 开始，程序编写完成后虽然没有报错，却不能运行，如图经检查程序，将Stack *CarS; Queue *CarQ;这两个指针型变量改成Stack CarS;arnum=carnum;ime=cartime;算费用时发现错误，在候车厅时间也被计入停车费。经检查程序，将.time=time;改成 .time=cartime;使其计费时间从进入车库开始而不是从达到候车场开始。再次运行发现结果正确。九、实验收货和

11、感想这是第一次运用栈和队列的相关知识编写程序，开始看到这个题目感觉挑战很大，从未尝试过这么复杂的一个系统。 停车场问题相较与约瑟夫斯问题要复杂得多，分了多个模块。 起初编写时漏洞很多， 好在当框架出来后各个漏洞都可以被弥补。比如程序刚运行成功时，发现不能显示位置， 车库车辆数和候车场车辆数不正确，计费不正确等很多漏洞， 但这些细节的小问题都比较容易排查修改，最终终于做出了符合要求的停车场管理系统。当完成后， 我对栈和队列的相关算法的理解也更加清晰深刻了。这个程序中还有一些灵活可变的地方，用宏定义定义了车库容量和费用单价，使具体数字可以较为灵活的改变，增加了这个程序的使用价值。 计算机实践课程给

12、了我动手操作的机会，使我将理论和实际操作结合起来，更好地理解算法， 更快地学会编程。每次编程都感觉收获非常多。练习的越多，对算法语句越是熟练，越能有深刻的理解， 不仅帮助我更好的学习软件技术基础也为以后我们专业课的道路打好基石，对我们的逻辑能力也是很大的提升。十、源程序#include#include#include #define MaxSize 2arnum=carnum;ime=cartime;PCar+;arnum,.time,PCar);+;arnum)findcar=i;arnum=.carnum;.time=.time;printf(%d 号 车 离 开 停 车 场 ! 离 开

13、时 刻 : %d, 停 留 时 长 (%d)n,.carnum,cartime,.time);PCar-;ime)*5);for(i=;i=0;i-)arnum=i.carnum;.time=i.time;+;if!=arnum=carnum;ime=cartime;/将此时的时刻记录入栈CarS，确保计算费用是从车辆从候车场进入车库后才开始算+;PCar+;/车库车辆数 +1WCar-;/候车场车辆数-1p=;=next;free(p);else/如果车库中找不到此车，再在候车场找p=;if(p!=&p-carnum!=carnum) /候车场队列不为空f=p-next;while(f!=&

14、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-f-time)*0);free(f);if(p-carnum=carnum)/要离开的车在队尾，直接出队findcar=1;=next;printf(%d号 车离开候车 场!离 开时间:%d

15、, 停留时长(%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;d

16、efault :printf(输入错误 !n);break;return 1;main()printf(试验名称：停车场管理问题n);printf(学号： n);printf(姓名： xxn);printf(=n);time_t rawtime1;struct tm * timeinfo1;time (&rawtime1);timeinfo1 = localtime (&rawtime1);/时间函数；printf (程序运行开始, 当前日期和时间: %s, asctime(timeinfo1);int go=1,carnum,cartime,MM;char carmove;=0;=(Node

17、2 *)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)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);printf(现在时刻 :t);scanf(%d,&cartime);MM=Result(carmove,carnum,cartime);if(!M