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

计算机软件技术基础实验报告I数据结构实验二停车场管理问题一、问题描述1实验题目设停车场是一个可停放N辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满N辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。2基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项汽车的“到达”（A表示）或“离去”（D表示）信息、汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。3测试数据设N2,输入数据为（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测试数据要求设N2,输入数据为（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数据对象DAI,BI,CI,DI|AIINT,BIINT,CIINT,DICHAR,I1,2,N,N0数据关系RAI,BI,DI,|AI,BI,DID,AI,BI,DISTRUCTCAR基本操作CAR_ENTERCARNUM,CARTIME/将到达车辆A的信息入栈S或者入队QCAR_LEAVECARNUM,CARTIME；/将待离开车辆D出栈S，并将Q中相应车辆入栈并进行相关的操作RESULTCHARCARMOVE,INTCARNUM,INTCARTIME/根据输入信息完成车辆的离开或者到达ADTSQSTACKADT的C语言形式说明TYPEDEFSTRUCT/构造一个顺序栈STRUCTNODE1HOMEMAXSIZEINTSTACKTOP/栈顶的指针STACK2队列抽象数据类型定义ADTLINKQUEUE数据对象DAI,BI,CI|AIQNODE,BIQNODE,CIINT,I1,2,N,N0数据关系R基本操作CAR_ENTERCARNUM,CARTIME/将到达车辆A的信息入栈S或者入队QCAR_LEAVECARNUM,CARTIME；/将待离开车辆D出栈S，并将Q中相应车辆入栈并进行相关的操作RESULTCHARCARMOVE,INTCARNUM,INTCARTIME/根据输入信息完成车辆的离开或者到达ADTLINKQUEUEADT的C语言形式说明TYPEDEFSTRUCT/构建一个链式队列QNODEFRONT,REARQUEUEVOIDCAR_ENTERINTCARNUM,INTCARTIME/到达车辆的信息入栈或者入队VOIDCAR_LEAVEINTCARNUM,INTCARTIME/车离开INTRESULTCHARCARMOVE,INTCARNUM,INTCARTIME/根据输入信息完成车辆的离开或者达到3主程序流程及其模块调用关系1）主程序流程主函数提示用户输入指令到达（A,车牌号,时间；离去D,车牌号,时间；停车场P显示停车场的车数；候车场W显示候车场的车数；退出E退出程序。调用INTRESULTCHARCARMOVE,INTCARNUM,INTCARTIME根据输入信息完成车辆的离开或者达到。若输入A则调用CAR_ENTERINTCARNUM,INTCARTIME，创建顺序栈CARS和链式队列CARQ，根据栈是否满决定输入的信息入栈还是入队列。若栈未满，输入的车辆信息入栈，若已满，入队列。若输入D则调用CAR_LEAVEINTCARNUM,INTCARTIME创建一个临时栈存放退出让路的车，若在车库中找到对应的车，车库中该车后面的车辆信息进入临时栈CARS2，该车出栈，显示车牌号，此时时间，停留时间，应缴费用。临时栈中的车的信息再回到CARS中。此时若队列CARQ不为空则将队列中车辆信息放入栈CARS中。若在车库中找不到对应的车的车牌号信息，则在表示候车场的队列中找该车信息，如果它在队列的最后，直接出列并输出车牌号，此时时间，停留时间，应缴费用。如果它不在队尾，先把对应信息保存在一个指向队列的指针中，输出车牌号，此时时间，停留时间，应缴费用。删除队列中此结点表示此车离开候车场。若输入P，则输出车库车辆数PCAR；若输入W，则输出候车场车辆数WCAR；若输入E，则退出程序。2）调用关系四、详细设计1元素类型、结点类型和结点指针类型TYPEDEFSTRUCTNODE1/构建一个结构体INTCARNUMINTTIMENODE1TYPEDEFSTRUCTNODE2INTCARNUMINTTIMESTRUCTNODE2NEXTNODE22、创建顺序栈TYPEDEFSTRUCT/构造一个顺序栈STRUCTNODE1HOMEMAXSIZEINTSTACKTOP/栈顶的指针STACK3、创建链式队列TYPEDEFSTRUCT/构建一个链式队列NODE2FRONT,REARQUEUE4车辆到达VOIDCAR_ENTERINTCARNUM,INTCARTIME/到达车辆的信息入栈或者入队IFCARSSTACKTOPCARNUMCARNUMCARQFRONTTIMECARTIME/到达车辆信息加入到队列中WCAR/候车场车辆数1PRINTF“D号车进入候车场到达时刻D位置DN“,CARQFRONTCARNUMCARNUM,CARQFRONTTIMECARTIME,WCARCARQFRONTNEXTNODE2MALLOCSIZEOFNODE2/分配空间CARQFRONTCARQFRONTNEXT/更改队列指针5车辆离开VOIDCAR_LEAVEINTCARNUM,INTCARTIME/车离开STACKCARS2/构造一个栈临时存放为了让位退出来的车INTIINTFINDCAR1NODE2P,FCARS2STACKTOP0/设临时栈CARS2为空FORI0IFINDCARCARS2STACKTOP/将车库里面在I车外面的车移动到临时栈CARS2中CARS2HOMECARS2STACKTOPCARNUMCARSHOMECARSSTACKTOPCARNUMCARS2HOMECARS2STACKTOPTIMECARSHOMECARSSTACKTOPTIMEPRINTF“D号车离开停车场离开时刻D,停留时长DN“,CARSHOMECARSSTACKTOPCARNUM,CARTIME,CARTIMECARSHOMECARSSTACKTOPTIMEPCAR/车库内车辆1PRINTF“应付停车费DN“,CARTIMECARSHOMECARSSTACKTOPTIME5FORICARS2STACKTOP1I0I/把临时栈里面的车移回去CARSHOMECARSSTACKTOPCARNUMCARS2HOMEICARNUMCARSHOMECARSSTACKTOPTIMECARS2HOMEITIMECARSSTACKTOPCARS2STACKTOPIFCARQFRONTCARQREAR/如果候车场有车，将它移进车库CARSHOMECARSSTACKTOPCARNUMCARQREARCARNUM/将队列中的车牌号信息放入栈CARSHOMECARSSTACKTOPTIMECARTIME/将此时的时刻记录入栈CARS，确保计算费用是从车辆从候车场进入车库后才开始算CARSSTACKTOPPCAR/车库车辆数1WCAR/候车场车辆数1PCARQREARCARQREARCARQREARNEXTFREEPELSE/如果车库中找不到此车，再在候车场找PCARQREARIFPCARQFRONTWHILEFCARQFRONTFFNEXTIFFCARNUMCARNUM/如果寻找的车在便道上，出队列FINDCAR1PNEXTFNEXTPRINTF“D号车离开候车场离开时间D,停留时长DN“,FCARNUM,CARTIME,CARTIMEFTIMEWCARPRINTF“应付停车费DN“,CARTIMEFTIME0FREEFIFPCARNUMCARNUM/要离开的车在队尾，直接出队FINDCAR1CARQREARCARQREARNEXTPRINTF“D号车离开候车场离开时间D,停留时长DN“,PCARNUM,CARTIME,CARTIMEPTIMEWCARPRINTF“应付停车费DN“,CARTIMEPTIME0FREEPIFFINDCAR1PRINTF“D号车不在停车场中N“,CARNUM6主函数MAINPRINTF“试验名称停车场管理问题N“PRINTF“学号N“PRINTF“姓名XXN“PRINTF“N“TIME_TRAWTIME1STRUCTTMTIMEINFO1TIMETIMEINFO1LOCALTIME/时间函数；PRINTF“程序运行开始,当前日期和时间S“,ASCTIMETIMEINFO1INTGO1,CARNUM,CARTIME,MMCHARCARMOVECARSSTACKTOP0CARQREARCARQFRONTNODE2MALLOCSIZEOFNODE2WHILEGOPRINTF“N车辆到达请输入AN车辆离开请输入DN显示停车场内车数请输入PN显示候车场车数请输入WN退出程序请输入EN“PRINTF“N请输入信息“CARMOVEGETCHARPRINTF“N“SWITCHCARMOVECASEAPRINTF“CN车牌号T“,CARMOVESCANF“D“,PRINTF“时间T“SCANF“D“,MMRESULTCARMOVE,CARNUM,CARTIMEIFMMGO0BREAKCASEDPRINTF“CN车牌号T“,CARMOVESCANF“D“,PRINTF“现在时刻T“SCANF“D“,MMRESULTCARMOVE,CARNUM,CARTIMEIFMMGO0BREAKCASEWPRINTF“正在外通道等待的车数量是DN“,WCARBREAKCASEPPRINTF“车库内车的数量是DN“,PCARBREAKCASEEPRINTF“退出N“TIME_TRAWTIME2STRUCTTMTIMEINFO2TIMETIMEINFO2LOCALTIMEPRINTF“程序运行结束,当前日期和时间S“,ASCTIMETIMEINFO2RETURN0GETCHAR五、调试分析此程序是分模块设计，根据输入的指令调用“到达”和“离开”模块，使车的信息入栈入队，或出栈出队。每次运行后又返回主菜单。程序整体结构清晰，操作方便。六、使用说明用户根据提示输入指令到达输入A,离开输入D，显示车库车辆数输入P，显示候车场车辆数输入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），（D，4，40），（E，0，0）。初始界面为输入到达车辆到达车辆超过车库容量时输入车辆离开信息输入P输入W输入E八、遇到的问题和解决方法1开始，程序编写完成后虽然没有报错，却不能运行，如图经检查程序，将STACKCARSQUEUECARQ这两个指针型变量改成STACKCARS/用来表示车库的栈QUEUECARQ/用来表示候车场的队列，再次运行发现可以成功运行。2当输入上述数据后输入P和W后显示的车辆数不对，当车库内车辆离开时，外通道的车进入车库，但PCAR和WCAR没有正确跟随变化，如图经检查程序，在IFCARQFRONTCARQREAR/如果候车场有车，将它移进车库CARSHOMECARSSTACKTOPCARNUMCARQREARCARNUM/将队列中的车牌号信息放入栈CARSHOMECARSSTACKTOPTIMECARTIME/将此时的时刻记录入栈CARS，确保计算费用是从车辆从候车场进入车库后才开始算CARSSTACKTOPPCARQREARCARQREARCARQREARNEXTFREEP这段程序中少了PCARWCAR，加上后再次运行，程序正确。3计算费用时发现错误，在候车厅时间也被计入停车费。经检查程序，将CARSHOMECARSSTACKTOPTIMECARQREARTIME改成CARSHOMECARSSTACKTOPTIMECARTIME使其计费时间从进入车库开始而不是从达到候车场开始。再次运行发现结果正确。九、实验收货和感想这是第一次运用栈和队列的相关知识编写程序，开始看到这个题目感觉挑战很大，从未尝试过这么复杂的一个系统。停车场问题相较与约瑟夫斯问题要复杂得多，分了多个模块。起初编写时漏洞很多，好在当框架出来后各个漏洞都可以被弥补。比如程序刚运行成功时，发现不能显示位置，车库车辆数和候车场车辆数不正确，计费不正确等很多漏洞，但这些细节的小问题都比较容易排查修改，最终终于做出了符合要求的停车场管理系统。当完成后，我对栈和队列的相关算法的理解也更加清晰深刻了。这个程序中还有一些灵活可变的地方，用宏定义定义了车库容量和费用单价，使具体数字可以较为灵活的改变，增加了这个程序的使用价值。计算机实践课程给了我动手操作的机会，使我将理论和实际操作结合起来，更好地理解算法，更快地学会编程。每次编程都感觉收获非常多。练习的越多，对算法语句越是熟练，越能有深刻的理解，不仅帮助我更好的学习软件技术基础也为以后我们专业课的道路打好基石，对我们的逻辑能力也是很大的提升。十、源程序INCLUDEINCLUDEINCLUDEDEFINEMAXSIZE2/车库最大容量DEFINEFEE10/在车库中停车的单价TYPEDEFSTRUCTNODE1/构建一个结构体INTCARNUMINTTIMENODE1TYPEDEFSTRUCT/构造一个顺序栈STRUCTNODE1HOMEMAXSIZEINTSTACKTOP/栈顶的指针STACKTYPEDEFSTRUCTNODE2INTCARNUMINTTIMESTRUCTNODE2NEXTNODE2TYPEDEFSTRUCT/构建一个链式队列NODE2FRONT,REARQUEUESTACKCARS/用来表示车库的栈QUEUECARQ/用来表示候车场的队列INTPCAR0/车库里车的数量INTWCAR0/候车场的车的数量VOIDCAR_ENTERINTCARNUM,INTCARTIME/到达车辆的信息入栈或者入队IFCARSSTACKTOPCARNUMCARNUMCARQFRONTTIMECARTIME/到达车辆信息加入到队列中WCAR/候车场车辆数1PRINTF“D号车进入候车场到达时刻D位置DN“,CARQFRONTCARNUMCARNUM,CARQFRONTTIMECARTIME,WCARCARQFRONTNEXTNODE2MALLOCSIZEOFNODE2/分配空间CARQFRONTCARQFRONTNEXT/更改队列指针VOIDCAR_LEAVEINTCARNUM,INTCARTIME/车离开STACKCARS2/构造一个栈临时存放为了让位退出来的车INTIINTFINDCAR1NODE2P,FCARS2STACKTOP0/设临时栈CARS2为空FORI0IFINDCARCARS2STACKTOP/将车库里面在I车外面的车移动到临时栈CARS2中CARS2HOMECARS2STACKTOPCARNUMCARSHOMECARSSTACKTOPCARNUMCARS2HOMECARS2STACKTOPTIMECARSHOMECARSSTACKTOPTIMEPRINTF“D号车离开停车场离开时刻D,停留时长DN“,CARSHOMECARSSTACKTOPCARNUM,CARTIME,CARTIMECARSHOMECARSSTACKTOPTIMEPCAR/车库内车辆1PRINTF“应付停车费DN“,CARTIMECARSHOMECARSSTACKTOPTIME5FORICARS2STACKTOP1I0I/把临时栈里面的车移回去CARSHOMECARSSTACKTOPCARNUMCARS2HOMEICARNUMCARSHOMECARSSTACKTOPTIMECARS2HOMEITIMECARSSTACKTOPCARS2STACKTOPIFCARQFRONTCARQREAR/如果候车场有车，将它移进车库CARSHOMECARSSTACKTOPCARNUMCARQREARCARNUM/将队列中的车牌号信息放入栈CARSHOMECARSSTACKTOPTIMECARTIME/将此时的时刻记录入栈CARS，确保计算费用是从车辆从候车场进入车库后才开始算CARSSTACKTOPPCAR/车库车辆数1WCAR/候车场车辆数1PCARQREARCARQREARCARQREARNEXTFREEPELSE/如果车库中找不到此车，再在候车场找PCARQREARIFPCARQFRONTWHILEFCARQFRONTFFNEXTIFFCARNUMCARNUM/如果寻找的车在便道上，出队列FINDCAR1PNEXTFNEXTPRINTF“D号车离开候车场离开时间D,停留时长DN“,FCARNUM,CARTIME,CARTIMEFTIMEWCARPRINTF“应付停车费DN“,CARTIMEFTIME0FREEFIFPCARNUMCARNUM/要离开的车在队尾，直接出队FINDCAR1CARQREARCARQREARNEXTPRINTF“D号车离开候车场离开时间D,停留时长DN“,PCARNUM,CARTIME,CARTIMEPTIMEWCARPRINTF“应付停车费DN“,CARTIMEPTIME0FREEPIFFINDCAR1PRINTF“D号车不在停车场