数据结构实验报告(实验三停车场管理).docVIP

韶 关 学 院 学 生 实 验 报 告 册 实验课程名称：数据结构与算法 实验项目名称：实验三 栈和队列及其应用 停车场管理 实验类型（打√ ）：（基础 、综合 、设计√ ） 院 系：信息工程学院计算机系 专 业：***** 姓 名：*** 学 号：***** 指导老师：陈正铭 韶关学院教务处编制 一、实验预习报告内容 预习日期：2007年 4 月 16 日 实验预习报告内容原则上应包括实验目的、实验所用的主要仪器药品、实验原理与公式、 实验预习疑问等项目。 【实验目的】深入了解栈和队列的特性，以便在实际问题背景下灵活运用它们，同时巩固对这两种结构的构造方法的掌握，接触较复杂问题的递归算法设计。 【需要分析】设停车场是一个可停放n辆汽车的通道，且只有一个大门可供汽车进出，汽车在停车场内按车辆到达时间的先后顺序，一次由北向南排列，若车场内已停满n辆车，这后来的汽车只能在门外的便道上等候，一旦有车开车，则排在便道的第一辆车即可进入；当停车场内某辆车要离开时，在它之后的必须先退出车场为它让路，待该车开出大门外，其他车辆再按原次序进入车场，每辆停放在停车场的车在它离开停车场时必须按他停留的时间长短交纳费用。试为停车场编制按上要求进行管理的模拟程序。 【软件平台】 Windows 2000，Visual C＋＋ 6.0或WINTC 【概要设计】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包含三个数据项：汽车“到达”或“离去”信息，汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用。栈以顺序结构实现，队列以链表结构实现。 抽象数据类型栈定义如下： ADT Stack { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ ai-1, ai | ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： InitStack(S) 操作结果：构造一个空栈 S。 DestroyStack(S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。 StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。 StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度。 GetTop(S, e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素。 ClearStack(S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。 Push(S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。 Pop(S, e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。 抽象数据类型队列定义如下： ADT Queue { 数据对象： D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系： R1＝{ a i-1,ai | ai-1, ai ∈D, i=2,...,n}约定其中a1 端为队列头， an 端为队列尾 基本操作： InitQueue(Q) 操作结果：构造一个空队列Q。 DestroyQueue(Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁，不再存在。 QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。 QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素