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

《计算机软件技术基础》 实验报告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. 栈抽象数据类型定义 ： 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 Node1 home[MaxSize]; int stacktop; //栈顶的指针}Stack;2. 队列抽象数据类型定义 ADT LinkQueue{ 数据对象：D={ai,bi,ci|ai∈Qnode*, bi∈Qnode*,ci∈int), i =1,2...,n,n≥0}; 数据关系：R= ∅ 基本操作：Car_enter(carnum,cartime)//将到达车辆a的信息入栈s或者入队q Car_Leave(carnum,cartime)；//将待离开车辆d出栈s，并将q中相应车辆入栈并进行相关的操作 Result(char carmove,int carnum,int cartime)//根据输入信息完成车辆的离开或者到达 }ADT LinkQueueADT的C语言形式说明：typedef struct //构建一个链式队列{ QNode *front,*rear;}Queue; void Car_enter(int carnum,int cartime) //到达车辆的信息入栈或者入队void Car_Leave(int carnum,int cartime)//车离开int Result(char carmove,int carnum,int cartime)//根据输入信息完成车辆的离开或者达到 3. 主程序流程及其模块调用关系:1） 主程序流程： 主函数提示用户输入指令：到达（‘A’,车牌号,时间)；离去(‘D’,车牌号,时间)；停车场‘P’ 显示停车场的车数；候车场‘W’显示候车场的车数；退出‘E’退出程序。

调用int Result(char carmove,int carnum,int cartime)根据输入信息完成车辆的离开或者达到 若输入A则调用Car_enter(int carnum,int cartime) ，创建顺序栈CarS和链式队列CarQ，根据栈是否满决定输入的信息入栈还是入队列若栈未满，输入的车辆信息入栈，若已满，入队列 若输入D则调用Car_Leave(int carnum,int cartime)：创建一个临时栈存放退出让路的车，若在车库中找到对应的车，车库中该车后面的车辆信息进入临时栈CarS2，该车出栈，显示车牌号，此时时间，停留时间，应缴费用临时栈中的车的信息再回到CarS中此时若队列CarQ不为空则将队列中车辆信息放入栈CarS中若在车库中找不到对应的车的车牌号信息，则在表示候车场的队列中找该车信息，如果它在队列的最后，直接出列并输出车牌号，此时时间，停留时间，应缴费用如果它不在队尾，先把对应信息保存在一个指向队列的指针中，输出车牌号，此时时间，停留时间，应缴费用删除队列中此结点表示此车离开候车场 若输入P，则输出车库车辆数PCar； 若输入W，则输出候车场车辆数WCar； 若输入E，则退出程序。

2） 调用关系 四、详细设计 1. 元素类型、结点类型和结点指针类型：typedef struct Node1 //构建一个结构体{ int carnum; int time;}Node1;typedef struct Node2 { int carnum; int time; struct Node2 *next;}Node2; 2、 创建顺序栈 typedef struct //构造一个顺序栈{ struct Node1 home[MaxSize]; int stacktop; //栈顶的指针}Stack;3、 创建链式队列 typedef struct //构建一个链式队列{ Node2 *front,*rear;}Queue; 4. 车辆到达：void Car_enter(int carnum,int cartime) //到达车辆的信息入栈或者入队 { if(CarS.stacktopcarnum=carnum; CarQ.front->time=cartime;//到达车辆信息加入到队列中 WCar++; //候车场车辆数+1 printf("%d号车进入候车场! 到达时刻:%d 位置:%d\n",CarQ.front->carnum=carnum,CarQ.front->time=cartime,WCar); CarQ.front->next=(Node2 *)malloc(sizeof(Node2));//分配空间 CarQ.front=CarQ.front->next;//更改队列指针 }}5. 车辆离开void Car_Leave(int carnum,int cartime)//车离开{ Stack CarS2;//构造一个栈临时存放为了让位退出来的车 int i; int findcar=-1; Node2 *p,*f; CarS2.stacktop=0;//设临时栈CarS2为空 for(i=0;i