数据结构与算法课程设计

《数据结构与算法课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构与算法课程设计》实验报告学号：班级序号：姓名：授课老师：【实习一】停车场管理一．问题描述设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北边），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入：当停车场内某车辆要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停

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

3、，4,25），（‘A’，5,30），（‘D’，2,35），（‘D’，4,40），（‘E’，0,0）。其中：‘A’表示到达（Arrival）；‘D’表示离去（Departure）；‘E’表示输入结束（END）。【实现提示】需另设一个栈，临时停放为给要离去的汽车让路二从停车场推出的汽车，也用顺序存储结构实现。输入数据到达或离去的时刻有序。栈中每个元素表示一辆汽车，包括两个数据项：汽车的牌照号码和进入停车场的时刻。二．需求分析1.程序所能达到的基本可能：程序用栈来模拟停车场，用队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。栈以顺序结构实现，队列以链表结构实现

4、。同时另设一个栈，临时停放为要离去的汽车让路而退出停车场的汽车。输入数据按到达或离去的时刻有序。当输入数据包括数据项为汽车的“到达”（‘A’表示）信息，汽车牌照号以及到达时刻时，提示车辆停车成功；当输入数据包括数据项为汽车的“离去”（‘D’表示）信息，显示汽车牌照号以及离去时刻时，应输出显示汽车离开停车场并显示缴纳的费用；当输入数据项为（‘E’,0,0），退出程序；2.输入输出形式及输入值范围：程序运行后进入循环，显示提示信息：“请输入停车场容量”，提示用户输入车辆信息，若车辆信息为“到达”，车辆信息开始进栈（模拟停车场），当栈满，会显示栈满信息：“停车场已满，车牌

5、号为X的车进入变道等待”，车辆进队列（模拟停车场旁便道），并显示该进入便道车辆的车牌编号；若车辆信息为“离开”，会显示该车进入停车场的时间以及相应的停车费用，若该车较部分车早进停车场，这部分车需先退出停车场，暂时进入一个新栈为其让道，会显示进入新栈的车辆的车牌编号及其入停车场的时间，当待离开车离开停车场后，这部分车会重新进入停车场，同时便道上的第一辆车进入停车场；若输入（‘E’，0，0），程序会跳出循环，同时程序结束；3.测试数据要求：用户输入车辆信息时，输入第一个参数必须是Ａ、Ｄ、Ｅ三个参数中的其中一个，第二个参数为车辆的车牌号，第三个参数中操作数为Ｄ的参数一定要

6、比对应的操作数为Ａ的参数大，因为停车时间＝离开的时间－进入的时间；三．概要设计为了实现上述功能，该程序以栈模拟停车场以及临时停放为给要离去的汽车让路而从停车场退出来的汽车的场地，以队列模拟车场外的便道，因此需要栈和队列这两个抽象数据类型。1.主要算法流程图：1.车辆进入停车场算法流程图：停车场未满停车进入变道ＴＦ开始结束2．车辆离开的算法流程图：4.本程序保护模块：主函数模块栈单元模块：实现栈的抽象数据类型队列单元模块：实现队列的抽象数据类型调用关系：四．详细设计1.相关头文件库的调用说明：#include"stdafx.h"#include"stack.h"#in

7、clude"queue.h"#include"xcept.h"#include1.栈类型和队列类型：//栈templateclassStack{//LIFOobjectspublic:Stack(intMaxStackSize=10);~Stack(){delete[]stack;}boolIsEmpty()const{returntop==-1;}boolIsFull()const{returntop==MaxTop;}TTop()const;Stack&Add(constT&x);Stack&Delete(T&