数据结构课程设计说明书.docxVIP

课程设计说明书 设计题目： 数据结构课程设计 专 业： 软件工程 班级： 2013 级 2 班 设 计 人： 李烁 山 东 科 技 大 学 2015 年 1 月 6 日 山 东 科 技 大 学 课 程 设 计 任 务 书 软件工程 专业 2013 级 2 班 李烁 一、课程设计题目： 数据结构课程设计 二、设计原始资料：《数据结构（C 语言版）》 《数据结构题集（C 语言版）》 《算法竞赛 入门经典（第 2 版）》 《算法竞赛 入门经典（训练指南）》 三、设计应解决下列各主要问题： 1、约瑟夫环 2、车厢调度 3、最小生成树问题 4、哈希表设计 四、设计说明书应附有下列图纸： 五、命题发出日期： 2014 年 9 月 4 日 设计应完成日期： 2015 年 1 月 9 日 设计指导教师（签章）： 系主任（签章）： 指导教师对课程的评语 指导教师（签章）： 年 月 日 目录 一、需求分析……………………………………………………………1 二、概要设计……………………………………………………………2 三、详细设计……………………………………………………………6 四、调试分析……………………………………………………………10 五、用户手册……………………………………………………………11 六、测试结果……………………………………………………………13 七、附录…………………………………………………………………13 车厢调度………………………………………………………………14 一、需求分析……………………………………………………………14 二、概要设计……………………………………………………………15 三、详细设计……………………………………………………………17 四、调试分析……………………………………………………………21 五、用户手册……………………………………………………………21 六、测试结果……………………………………………………………22 七、附录…………………………………………………………………23 最小生成树问题………………………………………………………24 一、需求分析……………………………………………………………24 二、概要设计……………………………………………………………24 三、详细设计……………………………………………………………27 四、调试分析……………………………………………………………31 五、用户手册……………………………………………………………32 六、测试结果……………………………………………………………33 七、附录…………………………………………………………………33 哈希表设计……………………………………………………………34 一、需求分析……………………………………………………………34 二、概要设计……………………………………………………………35 三、详细设计……………………………………………………………37 四、调试分析……………………………………………………………44 五、用户手册……………………………………………………………44 六、测试结果……………………………………………………………46 七、附录…………………………………………………………………46 【实习一】约瑟夫环 一、需求分析 1.摘要：Josephus 问题的一种描述是编号为 1，2，…，n 的 n 个人按顺时针方向围坐一圈, 每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直到所有人全部出列为止。在这个问题中，每个人持有的密码需顺序存储， n 个人围成一圈，需要将首尾连接。每次循环到报数上限值 m 都有人出列，分别记录下他们的编号，即可求出出列顺序。所以约瑟夫环问题可以采用单向循环链表存储结构模拟这个过程。单向循环链表的数据结构，就是将一个链表的最后一个节点指针指向第一个结点。出列时，根据密码找到对应的人，将其密码重新赋值给 m 后，释放该节点，形成新的约瑟夫环，所有人出列后结束程序。 2.本演示程序中，人数 n 应为任意的，这里设 n≤30，首先要 求用户指定初始报数上限值，故需输入一个值赋给初始报数 上限 m。然后读取 n 个人的密码，按顺序与编号对应存储到循 环表中。这里的初始报数上限值 m 和每个人的密码应为正整 数的，程序应能自动滤去非法数字。程序应能自动存储出列 人的序号，并将出列的人所持的密码赋给 m，作为新的报数上 限，重复如上操作，直至所有人都出列为止，打印出列顺序。 1 输出的运算结果所有的值都