数据结构上机实验2012_blue

《数据结构上机实验2012_blue》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《计算机软件技术基础》2012实验报告I—数据结构_031020xxx_张三数据结构上机实验题2012报告要求l简述每一部分的对象、目的和要求；l画出算法(程序)的流程图；l说明程序的数据输入要求；l附源程序清单；l实验的收获：遇到的问题以及解决的办法、方法的优缺点、对本实验的要求和建议；忌空、大话简述每一部分。ll对源程序的功能块做适当注释。其他未尽事项按写报告的一般要求进行（“如何撰写实验报告.PDF”）。l报告统一采用A4纸打印（正文采用5号字体，1.25倍行距）或手写，左侧装订（推荐双面打印）。l以班级为单位提交光盘形式的电子稿，包括j实验报告打印稿的WOR

2、D2003版本，k源程序（包括可以直接运行演示的可执行文件）。每班刻一张光盘，每个同学的程序放在一个以“DS2012_学号_姓名”方式命名的文件夹中，如：“DS2012_031020xxx_张三”。（此部分可与后续“软件工程实验报告”电子稿一起刻录）l实验题求解的构思、程序实现可以适当参考文献资料，但应避免直接照搬。每人独立完成实验，如发现实验程序或报告的内容有雷同，雷同双方（或多方）报告视为无效。l实验报告格式如附件提供的模板，提交的文档格式应严格按规定的模板格式（文字水印格式为“DS2012_学号_姓名”，如“DS2012_031020xxx_张三”），打印稿件

3、和电子稿件内容要一致。第7页共7页《计算机软件技术基础》2012实验报告I—数据结构_031020xxx_张三实验一：约瑟夫斯问题求解1）问题描述约瑟夫斯（Josephus）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。2）基本要求利用单向循环链表存储结构模拟此过程，按

4、照出列的顺序印出各人的编号。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辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时

5、间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若停车场内已经停满n辆车，那么后来的车只能在门外的便道上等候。一旦有车开走，则排在便道上的第一辆车即可开入。第7页共7页《计算机软件技术基础》2012实验报告I—数据结构_031020xxx_张三当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。2）基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读

6、入数据的序列进行模拟管理。每一组输入数据包括三个数据项：汽车的“到达”（‘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，

7、40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。其中：（‘A’，1，5）表示1号牌照车在5这个时刻到达，而（‘D’，1，15）表示1号牌照车在15这个时刻离去。4）提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。5）输入输出:输入数据：程序接受5个命令，分别是：到达（‘A’,车牌号,时间)；离去(‘D’,车牌