数据构造实验报告—停车场问题.docx

数据构造实验报告停车场问题（计算机软件技术基础）实验报告I数据构造实验二：停车场管理问题一、问题描绘1.实验题目：设停车场是一个可停放n辆汽车的狭长通道，且只要一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列大门在最南端，最先到达的第一辆车停放在车场的最北端。若停车场内已经停满n辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。2基本要求：以栈模拟停车场，以队列模拟车场外的便道，根据从终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项：汽车的“到达A表示或“离去D表示信息、汽车标识牌照号以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用便道上停留的时间不收费。栈以顺序构造实现，队列以链表构造实现。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。每一组输入数据包括三个数据项：汽车“到达或“离去信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D表示离去，E表示输入结束。其中：A，1，5表示1号牌照车在5这个时刻到达，而D，1，15表示1号牌照车在15这个时刻离去。二、需求分析1.程序所能到达的基本可能：本程序用来模拟一个可停放n辆车的停车场的停车管理问题。用栈和队列模拟停车场及场外通道，输入车辆状态到达或者离开，车牌号和时间，就可显示停车位置或者该车在停车场停留时间及应缴费用。2.输入的形式及输入值范围：程序接受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，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.栈抽象数据类型定义：ADTSqStack数据对象：D=ai,bi,ci,di|aiint,biint,ciint,dichar),i=1,2.,n,n0:数据关系：R=(ai,bi,di,)|ai,bi,diD,ai,bi,distructcar;基本操作：Car_enter(carnum,cartime).,n,n0;数据关系：R=?基本操作：Car_enter(carnum,cartime)主程序流程及其模块调用关系:1主程序流程：主函数提示用户输入指令：到达A,车牌号,时间)；离去(D,车牌号,时间)；停车场P显示停车场的车数；候车场W显示候车场的车数；退出E退出程序。调用intResult(charcarmove,intcarnum,intcartime)根据输入信息完成车辆的离开或者到达。若输入A则调用Car_enter(intcarnum,intcartime)，创立顺序栈CarS和链式队列CarQ，根据栈能否满决定输入的信息入栈还是入队列。若栈未满，输入的车辆信息入栈，若已满，入队列。若输入D则调用Car_Leave(intcarnum,intcartime)：创立一个临时栈存放退出让路的车，若在车库中找到对应的车，车库中该车后面的车辆信息进入临时栈CarS2，该车出栈，显示车牌号，此时时间，停留时间，应缴费用。临时栈中的车的信息再回到CarS中。此时若队列CarQ不为空则将队列中车辆信息放入栈CarS中。若在车库中找不到对应的车的车牌号信息，则在表示候车场的队列中找该车信息，假如它在队列的最后，直接出列并输出车牌号，此时时间，停留时间，应缴费用。假如它不在队尾，先把对应信息保存在一个指向队列的指针中，输出车牌号，此时时间，停留时间，应缴费用。删除队列中此结点表示此车离开候车场。若输入P，则输出车库车辆数PCar；若输入W，则输出候车场车辆数WCar；若输入E，则退出程序。2调用关系四、具体设计1.元素类型、结点类型和结点指针类型：typedefstructNode1arnum=carnum;ime=cartime;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，5，30，D，2，35，D，4，40，E，0，0。初始界面为：输入到达车辆：当前位置：文档视界数据构造实验报告停车场问题数据构造实验报告停车场问题当前位置：文档视界数据构造实验报告停车场问题数据构造实验报告停车场问题当前位置：文档视界数据构造实验报告停车场问题数据构造实验报告停车场问题八、碰到的问题和解决方法1.开场，程序编写完成后固然没有报错，却不能运行，如图经检查程序，将Stack*CarS;Queue*CarQ;这两个指针型变量改成StackCarS;arnum=>carnum;ime=cartime;算费用时发现错误，在候车厅时间也被计入停车费。经检查程序，将 .time=>time;改成.time=cartime;使其计费时间从进入车库开场而不是从到达候车场开场。再次运行发现结果正确。九、实验收货和感想这是第一次运用栈和队列的相关知识编写程序，开场看到这个题目感觉挑战很大，从未尝试过这么复杂的一个系统。停车场问题相较与约瑟夫斯问题要复杂得多，分了多个模块。起初编写时漏洞很多，好在当框架出来后各个漏洞都能够被弥补。比方程序刚运行成功时，发现不能显示位置，车库车辆数和候车场车辆数不正确，计费不正确等很多漏洞，但这些细节的小问题都比拟容易排查修改，最终终于做出了符合要求的停车场管理系统。当完成后，我对栈和队列的相关算法的理解也愈加明晰深入了。这个程序中还有一些灵敏可变的地方，用宏定义定义了车库容量和费用单价，使详细数字能够较为灵敏的改变，增加了这个程序的使用价值。计算机实践课程给了我动手操作的时机，使我将理论和实际操作结合起来，更好地理解算法，更快地学会编程。每次编程都感觉收获非常多。练习的越多，对算法语句越是熟练，越能有深入的理解，不仅帮助我更好的学习（软件技术基础）也为以后我们专业课的道路打好基石，对我们的逻辑能力也是很大的提升。十、源程序#include#include#include#defineMaxSize2arnum=carnum;ime=cartime;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;/将此时的时刻记录入栈CarS，确保计算费用是从车辆从候车场进入车库后才开场算+;PCar+;/车库车辆数+1WCar-;/候车场车辆数-1p=;=>next;free(p);else/假如车库中找不到此车，再在候车场找p=;if(p!=&&p->carnum!=carnum)/候车场队列不为空