实验4线性结构综合实验

1、实验4 线性结构综合实验一、实验目的1. 熟练掌握顺序表、链表及栈和队列的概念、特点及实现2. 掌握各种线性结构的基本运算3. 加深线性结构理解，逐步培养解决复杂实际问题的编程能力。二、实验内容1. 删除单链表中的重复结点 一带头结点的单链表，结点值为整型，其中元素按结点值从小到大排列，要求删除此链表中结点值重复的结点，只保留一个结点。如：单链表中的结点元素依次为(1,3,3,3,5,5,7)，则完成此操作后单链表的结点为(1,3,5,7)。2. 约瑟夫环 约瑟夫（Joeph）问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报

2、数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。测试数据 m的初值为20=6；n=7，他们的密码为3，1，7=0，2，4，8=2，4；则正确的结果应为6，1，4，7，2，3，5。实现提示 程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n30。算法分析 本题需循环计数，为此，可以使用一个一维数组存储每个人的状态，初为零，表示此人还未出列。 然后循环报数，这需要一个变量来存储当前用户报的数，当报的数达到密码m时

3、，停止计数，并将当前用户出列。然后计数器置0，继续报数，至所有用户均出列为止。3. 停车场管理 设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理

4、的模拟程序。算法思路 根据要求由此很容易联想到栈，因此可首先设计一个堆栈，以堆栈来模拟停车场，可用顺序存储结构来存储停车场内的车辆信息，并给车辆按进栈顺序编号，当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入停车场。这是个一退一进的过程，而且让道的汽车必须保持原有的先后顺序，因此可再设计一个堆栈，以之来暂时存放为出站汽车暂时让道的汽车。当停车场满后，继续进来的汽车需要停放在停车场旁边的便道上等候，若停车场有汽车开走，则按排队的先后顺序依次进站，最先进入便道的汽车将会最先进入停车场，这完全是一个先进先出模型，因此可设计一个队列来模拟便

5、道，队列中的数据元素设计成汽车的车牌号。另外，停车场根据汽车在停车场内停放的总时长来收费的，在便道上的时间不计费，因此必须记录车辆进入停车场时的时间和车辆离开停车场时的时间，然后计算、显示费用情况。核心算法停车场使用栈存储，便道使用队列存储到达：车a到达时如果栈未满，则入栈否则，将其加入到便道车队中记录停车时间并显示之。离开：当车a离开时首先在停车场（栈）中查找车a，如果找到，则a以前的车均出栈并进入临时栈（先临时退出停车场）。然后a出栈，并记录其离开时间，计算费用。并显示之。临时栈中所有车出栈并进入停车场栈；从便道队列中取一辆车进入停车场。主函数：初始化栈和队列从键盘输入指令（停车或离开）调用到达、停车函数实现功能。三、实验报告要求1. 根据程序要求对运行结果进行分析。如果程序未能调试通过，分析其原因。2. 根据实验步骤，说明未能编译通过的原因，并正确进行