数据结构上机实验2016_blue解读.doc

数据结构上机实验题2016 报告要求 简述每一部分的对象、目的和要求； 画出算法(程序)的流程图； 说明程序的数据输入要求； 附源程序清单； 遇到的问题解决办法实验的收获方法的优缺点、对本实验的要求和建议；忌空、大话。对源程序的功能块做适当注释。其他未尽事项按写报告的一般要求进行（“如何撰写实验报告.PDF”）。 报告统一采用A4纸打印（正文采用5号字体，1.25倍行距），左侧装订（推荐双面打印）。 提交源程序。刻一张，每个同学的程序放在一个以命名的文件夹中如：“031x20xxx_张三”。031x20xxx_张三 实验一：约瑟夫斯问题求解 1） 问题描述 约瑟夫斯（Josephus）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。 2）基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 3）测试数据 n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。 4）提示 程序运行后，首先要求用户指定初始报数上限m，然后读取个人的密码。可设n≤30。注意链表中空表和非空表的界限。 5）输入输出: 输入数据：建立输入处理，输入n输入以及每个人的密码；m的初值。 输出形式：建立一个输出函数，输出正确的序列。 6）选作内容 添加采用顺序存储结构实现问题求解的模块。 实验二：停车场管理问题 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这个时刻离去。 4）提示 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 5）输入输出: 输入数据：程序接受5个命令，分别是：到达（‘A’,车牌号,时间)；离去(‘D’,车牌号,时间)；停车场（‘P’, 0, 0）显示停车场的车数；候车场（‘W’, 0, 0）显示候车场的车数；退出（‘E’, 0, 0）退出程序。 输出数据：对于车辆到达，要输出汽车在停车场内或者便道上的停车位置；对于车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不收费）。 实验三：管道铺设施工的最佳方案问题 1） 问题描述 需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。 2）基本要求 在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接