数据结构与算法——综合实验(1.2)

《数据结构与算法——综合实验(1.2)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、综合应用实验一：停车场管理实验目的：学习使用栈与队列解决实际问题。实验内容：停车场问题模拟问题描述：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的

2、次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制程序模拟该停车场的管理。实验提示：本题可用栈和队列来模拟实现。设计要点：1．存储结构设计：模拟汽车到达或离去的输入数据格式可定义为：车牌号码：字符串时间：数值动作：区分是“到达”还是“离去”约定：“A”表示到达，用“L”表示离开，“E”表示结束输入。根据题目要求，停车场只有一个大门，因此可用一个栈来模拟，我们称之为主栈；当停车

3、场满后，到来的车辆只能停在便道上，根据便道停车的特点，可用一个队列来模拟（先排队的车辆先离开便道，进入停车场）而每当停车场中间的车辆离开时，要求大门到欲离开车辆之间的车辆必须先离开停车场，让此车辆离去，然后再依序进入停车场，为保存这些车辆的位置也需栈，称为辅助栈。因此本问题需要用到两个栈和一个队列。2．基本操作分析与定义停车场的操作有车辆进入和离开。根据不同情况对应以下的基本操作：车辆进入：当主栈不满时，由主栈的入栈操作实现；若主栈已满，对应队列的入队操作；车辆离开：当位于门口的车辆（用主栈的栈顶表示

4、）离开时，对应主栈的出栈操作。当中间车辆离开时的操作比较复杂，需要辅助栈和队列，步骤如下：（1）首先在主栈中查找车辆信息，若在主栈中，则循环进行“车辆由主栈出栈，进入辅助栈”的操作，直到该车辆对应的元素位于栈顶（2）车辆出栈。（3）将辅助栈元素依次入主栈。（4）队列的对头元素出队（5）对头元素进入主栈由此可见，停车场的基本操作可用队列和栈的基本操作实现。注意点：当停车场已没有车辆时，若输入数据仍要求车辆开出，则应显示错误信息；停车场的停车数量可规定为n，即为主栈的大小，未做说明时，认为便道可以停放任意

5、多的车辆。因此，栈结构可采用顺序存储结构，而队列宜采用链式队列。综合应用实验二：病人看病模拟程序病人排队看病主要重复两件事：(1)病人到达诊室，将病历本交给护士，排队等待队列中候诊；(2)护士从等待队列中取出下一位病人的病历，该病人就诊；要求编程模拟这一过程。程序采用菜单选择方式，其选项功能说明如下：(1)排队--输入排队病人的病历号，加入到病人排队队列中；(2)就诊--最前面的病人就诊，并从队列中删除；(3)查看队列--从队首到队尾列出所有排队病人病历号；(4)不在排队，余下依次就诊--从队首到队尾

6、列出所有派队病人病历号，退出运行；(5)下班--退出运行；要求：1、以组为单位一起完成实验，相互帮助。2、本次综合实验要求写实验报告3、以抽查组员的形式检查作业，检查的内容包括程序结构，调试运行，结果分析，实验报告等，如果该组员都回答不了问题的，该组的成绩将扣分。