《数据结构实验报告—停车场问题》由会员分享，可在线阅读，更多相关《数据结构实验报告—停车场问题（32页珍藏版）》请在金锄头文库上搜索。
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), (
3、A, 5, 30), (D, 2, 35), (D, 4, 40), (E, 0, 0)。每一组输入 数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻 其中，A表示到达；D表示离去，它表示输入结束。其中：(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, 25)，(A, 5，30), (D, 2, 35), (D, 4, 40)
5、, (E, 0, 0)。每一组输入 数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻 其中，(A表示到达；(D表示离去，(E表示输入结束。其中：A, 1, 5)表示1号牌 照车在5这个时刻到达，而(D, 1,15)表示1号牌照车在15这个时刻离去。三、概要设计为了实现上述功能,该程序以栈模拟停车场以及临时停放为给要离去的汽车让路而从 停车场退出来的汽车的场地,以队列模拟车场外的便道,因此需要栈和队列这两个抽象数据 类型。1. 栈抽象数据类型定义：ADT SqStack数据对象：D=ai,bi,ci,di|ai Gint, biGint,ciWint,diWchar
6、),i =1,2.,n,n$0:数据关系：R二(ai,bi,di,)|ai,bi,diGD,ai,bi,diGstruct car;基本操作：Car_enter(carnum,cartime)/将到达车辆a的信息入栈s或者入队qCar_Leave(carnum,car time) ； /将待离开车辆d出栈s,并将q中相应 车辆入栈并进行相关的操作Result(char carmove,int carnum,int cartime)/根据输入信息完成车 辆的离开或者到达ADT SqStackADT的C语言形式说明：typedef struct /构造一个顺序栈struct Node1 homeM
7、axSize;int stacktop; /栈顶的指针Stack;2. 队列抽象数据类型定义ADT LinkQueue数据对象：D二ai,bi,ci|aiWQnode*, bi GQnode*,ciGint), i =1,2.,n,n$0;数据关系：R=基本操作：Car_en ter(carnum,car ti me)/将到达车辆a的信息入栈s或者入队qCar_Leave(carnum,car time) ； /将待离开车辆d出栈s,并将q中相应 车辆入栈并进行相关的操作Resul t(char carmove,int carnum,int car time)/根 据输入信息完成车辆的离开或者
8、到达ADT LinkQueueADT的C语言形式说明：typedef struct /构建一个链式队列QNode *front,*rear;Queue;void Car_enter(int carnum,int cartime) /到达车辆的信息入栈或者入队void Car_Leave(i nt carnum,i nt car ti me)/车离开int Resul t(char carmove,int carnum,in t car ti me)/根 据输入信息完成车辆的离开或者 达到3. 主程序流程及其模块调用关系:1)主程序流程：主函数提示用户输入指令：到达A，车牌号，时间)；离去(D，
9、车牌号，时间)；停 车场P 显示停车场的车数；候车场W显示候车场的车数；退出E退出程序。调用int Resul t(char carmove,in t carnum,in t car time根据输入信息完成车辆的离 开或者达到。若输入A则调用Car_en ter(in t carnum,in t car time)，创建顺序栈CarS和链式队列 CarQ，根据栈是否满决定输入的信息入栈还是入队列。若栈未满，输入的车辆信息入栈，若 已满，入队列。若输入D则调用Car_Leave(in t carnum,in t car time):创建一个临时栈存放退出让 路的车，若在车库中找到对应的车，车库
10、中该车后面的车辆信息进入临时栈CarS2，该车出 栈，显示车牌号，此时时间，停留时间，应缴费用。临时栈中的车的信息再回到CarS中。 此时若队列CarQ不为空则将队列中车辆信息放入栈CarS中。若在车库中找不到对应的车的 车牌号信息，则在表示候车场的队列中找该车信息，如果它在队列的最后，直接出列并输出 车牌号，此时时间，停留时间，应缴费用。如果它不在队尾，先把对应信息保存在一个指向 队列的指针中，输出车牌号，此时时间，停留时间，应缴费用。删除队列中此结点表示此车四、详细设计1元素类型、结点类型和结点指针类型:/构建一个结构体typedef struet Nodelint carnum;int
11、time;Node1;typedef struct Node2int 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.s tack topcarnum=
12、carnum;CarQ.fron t-t ime二car time;/至I达车辆信息加入到队列中WCar+; /候车场车辆数+1printf(%d 号 车 进 入 候 车 场 ! 到 达 时 刻 ：%d置：dn,CarQ.fro nt-carnum二carnum,CarQ.fro nt-ti me=car ti me,WCar);CarQ.fron t-nex t=(Node2 *)malloc(sizeof(Node2);/分配空间CarQ.fron t二 CarQ.fron t-nex t;/更改队列指针5. 车辆离开void Car_Leave(i nt carnum,i nt car
13、ti me)/车离开St ack CarS2;/构造一个栈临时存放为了让位退出来的车int i;int findcar=-1;Node2 *p,*f;CarS2.stacktop=0;/设临时栈 CarS2 为空for(i=0;ifindcar;CarS2.s tack top+)/将车库里面在 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,ca
