实验二栈和队列的应用.docVIP

实验二 栈和队列的应用 实验目的和要求： 通过实验进一步理解栈和队列的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 主要内容： 题目1：模拟停车厂管理 问题描述： 设停车厂只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达的先后顺序依次排列，若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入;当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门后，为它让路的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走。 基本要求： 以栈模拟停车场，以队列模拟车场外的便道，按照从终端输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出车辆在停车场内或便道上的停车位置;若是车辆离去，则输出车辆在停车场内停留的时间和应缴纳的费用（在便道上停留的时间不收费）。栈以顺序结构出现，队列以链表结构实现。 测试数据： （1）连续有7辆车到来，牌照号分别为JF001、JF002、JF003、JF004、、JF005、JF006、JF007，前5辆车应该进入停车位1－5车位，第6、7辆车应停入便道的1、2位置上。 （2）（1）中的情况发生后，让牌照号为JF003的汽车从停车厂开走，应显示JF005、JF004的让路动作和JF006从便道到停车位上的动作。 （3）随时检查停车位和便道的状态，不应该出现停车位有空位而便道上还有车的情况。 （4）程序容错性的测试，当按键输入错误的时候是否有错误提示给用户指导用户正确操作，并作出相应处理保证程序健康的运行。 选作内容： （1）汽车可有不同种类，则它们的占地面积不同，消费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。 （2）汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （3）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改以满足这种要求。 题目2：算术表达式求值 问题描述： 表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。 基本要求： 以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，实现对算术四则混合运算表达式的求值。请参照教材3－2的例题，中缀表达式和后缀表达式的的求值过程中运算符栈、运算数栈、输入字符和主要操作的变化过程。 测试数据： （1）8;1＋2＋3＋4;88－1*5;1024／4*8;1024／（4*）;（20＋2）（6／2）; （2）3－3－3;8／（9－9）;2*（6＋2*（3＋6*（6＋6）））;（（（6＋6）*6＋3）*2＋6）*2; 选作内容： （1）扩充运算符集，如增加乘方、单目减、赋值等运算。 （2）运算量可以是变量。 （3）运算量可以是实数类型。 （4）计算器的功能和仿真界面。