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

. .
优选
"计算机软件技术根底"实验报告I—数据构造
实验二：停车场管理问题
一、问题描述
：
设停车场是一个可停放 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这个时刻离去。
二、需求分析
：
本程序用来模拟一个可停放n辆车的停车场的停车管理问题。用栈和队列模拟停车场及场外通道，输入车辆状态〔到达或者离开〕，车牌号和时间，就可显示停车位置或者该车在停车场停留时间及应缴费用。
：
程序承受5个命令，分别是：到达〔‘A’,车牌号,时间)；离去(‘D’,车牌号,时间)；停车场〔‘P’, 0, 0〕显示停车场的车数；候车场〔‘W’, 0, 0〕显示候车场的车数；退出〔‘E’, 0, 0〕退出程序。
：
对于车辆到达，要输出汽车在停车场或者便道上的停车位置；对于车辆离去，那么输出汽车在停车场停留的时间和应缴纳的费用〔便道上不收费〕。用户输入完毕后，程序自动运行输出运行结果。
：
设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这个时刻离去。
三、概要设计
为了实现上述功能，该程序以栈模拟停车场以及临时停放为给要离去的汽车让路而从停车场退出来的汽车的场地，以队列模拟车场外的便道，因此需要栈和队列这两个抽象数据类型。
栈抽象数据类型定义：
ADT SqStack{
数据对象：D={ai,bi,ci,di|ai∈int, 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)//将到达车辆a的信息入栈s或者入队q
Car_Leave(carnum,cartime)；//将待离开车辆d出栈s，并将q中相应车辆入栈并进展相关的操作
Result(char carmove,int carnum,int cartime)//根据输入信息完成车辆的离开或者到达
}ADT SqStack
ADT的C语言形式说明：
typedef struct //构造一个顺序栈
{
struct