沈阳工程学院数据结构课设报告

沈沈 阳阳 工工 程程 学学 院院课 程 设 计设计题目：设计题目：约瑟夫环、安排教学计划约瑟夫环、安排教学计划系系 别别 信息学院信息学院 班级班级 学生姓学生姓 学号学号 指导教师指导教师 姜柳姜柳 、吕海华、吕海华 职称职称 副教授、讲师副教授、讲师 起止日期：起止日期： 年年 月月 日起日起至至 年年 月月 日止日止沈 阳 工 程 学 院课程设计任务书课程设计题目：课程设计题目：约瑟夫环约瑟夫环系系 别别 信息学院信息学院 班级班级 学生姓名学生姓名 学号学号 指导教师指导教师 姜柳姜柳 、吕海华、吕海华 职称职称 副教授、讲师副教授、讲师 课程设计进行地点：课程设计进行地点： 实训实训 F F 座座 任任 务务 下下 达达 时时 间：间： 年年 月月 日日起止日期：起止日期： 年年 月月 日起日起至至 年年 月月 日止日止教教研研室室主主任任 张欣张欣 年年 月月 日日批批准准 一、课程设计的原始资料及依据约瑟夫（Joeph）问题的一种描述是：编号为 1、2、n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序及最后一个出列的人。二、课程设计主要内容及要求1约瑟夫环. 认真阅读资料，掌握程序设计模块化的思想。. 要求在设计的过程中，建立清晰的层次结构。. 画出主要的功能结构图和主要模块的流程图。. 建立一个具有 n 个结点，无头结点的循环链表。. 确定参与人数及初始报数上限值 m。. 不断地从链表中删除链结点，直到链表为空。三、对课程设计说明书撰写内容、格式、字数的要求1课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于 3000 字。2在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组组长给出评语。4课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用 A4 纸，页边距均为 20mm，正文采用宋体小四号字，行间距 18磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求 1完成“任务书”中指定的操作功能，运行稳定。2课程设计说明书。五、时间进度安排顺序阶段日期计 划 完 成 内 容备注1第 1 天阅读资料2第 23 天系统分析设计3第 48 天程序编制、调试及运行4第 9 天成绩评定#5第 10 天撰写课程设计说明书六、主要参考资料（文献）1郭翠英.C 语言课程设计案例精编.北京：中国水利水电出版社.2004.3 2谭浩强.C 语言程序设计.北京:清华大学出版社.1999.123张翔.C 语言函数大全.北京:清华大学出版社.2002.44浦滨.C 游戏编程从入门到精通.北京: 北京希望电子出版社.2002.55陈天洲.C 语言高级程序设计. 北京:人民邮电出版社.2002 6杨旭.C 语言程序设计案例教程.北京: 人民邮电出版社.20057 王为青C 语言高级编程及实例剖析北京:人民邮电出版社2008028徐慧.C 语言实例解析精粹.北京:人民邮电出版社.2006.04 9 姚大鹏 栾好利 张翼英 等编著.C 语言程序设计教程习题与上机实训指导.中国水利水电出版社.200510 王为青C 语言实例解析北京:人民邮电出版社200802 沈 阳 工 程 学 院课程设计任务书课程设计题目：课程设计题目：安排教学计划安排教学计划系系 别别 信息学院信息学院 班级班级 学生姓名学生姓名 学号学号 指导教师指导教师 姜柳姜柳 、吕海华、吕海华 职称职称 副教授、讲师副教授、讲师 课程设计进行地点：课程设计进行地点： 实训实训 F F 座座 任任 务务 下下 达达 时时 间：间： 年年 月月 日日起止日期：起止日期： 年年 月月 日起日起至至 年年 月月 日止日止教教研研室室主主任任 张欣张欣 年年 月月 日日批批准准 一、课程设计的原始资料及依据学校每个学期开设的课程是又先后顺序的，如计算机专业：开设数据结构课程之前，必须先开设C 语言程序设计和离散数学课程，这种课程开设的先后顺序关系称为先行，后继课程关系。现在需要根据给定的课程信息及课程之间的先行、后继关系，合理安排出开设各门课程的先后顺序。查阅有关程序设计的案例资料，进一步理解程序设计模块化的思想，并利用此思想，根据对程序设计学习编写一个安排教学计划系统。通过本设计可以加深理解利用程序设计思想开发一个系统的整个流程，提高分析问题、解决问题和实际动手的能力。二、课程设计主要内容及要求1 对输入的课程先行、后继关系如果存在回路关系时应提示现错误；2 根据读入的课程信息及其先行、后继关系，计算出安排教学计划的序列。3 输出教学计划的安排顺序或给出错误提示信息。三、对课程设计说明书撰写内容、格式、字数的要求1课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于 3000 字。2在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组组长给出评语。4课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用 A4 纸，页边距均为 20mm，正文采用宋体小四号字，行间距 18磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求1完成“任务书”中指定的操作功能，运行稳定。2课程设计说明书。 五、时间进度安排顺序阶段日期计 划 完 成 内 容备注1第 1 天阅读资料2第 23 天系统分析设计3第 48 天程序编制、调试及运行4第 9 天成绩评定5第 10 天撰写课程设计说明书六、主要参考资料（文献）1严蔚敏 吴伟民.数据结构（C 语言版）. 北京:清华大学出版社.20072谭浩强.C 程序设计.北京:清华大学出版社.1999.123滕国文.数据结构课程设计.北京:清华大学出版社.2010.094苏仕华 等编著. 数据结构课程设计. 北京:机械工业出版社.2005.055李春葆.数据结构（C 语言版）习题与解析.北京:清华大学出版社.2002.04 沈沈 阳阳 工工 程程 学学 院院数据结构数据结构课程设计成绩评定表课程设计成绩评定表系（部）：系（部）： 信息信息学院学院 班级：班级： 学生姓名：学生姓名： 指指 导导 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15 54 43 32 2工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25 54 43 32 2工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55 54 43 32 2指导教师评审成绩（加权分合计乘以指导教师评审成绩（加权分合计乘以 8 8） 分分加权分合计加权分合计指指 导导 教教 师师 签签 名：名： 年年 月月 日日评评 阅阅 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25 54 43 32 2工作量工作量饱满，难度适中。0.55 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35 54 43 32 2评阅教师评审成绩评阅教师评审成绩（加权分合计乘以（加权分合计乘以 4 4）分分加权分合计加权分合计评评 阅阅 教教 师师 签签 名：名： 年年 月月 日日答答 辩辩 小小 组组 评评 审审 意意 见见评价容具 体 要 求权重评 分加权分学生报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.53 32 2答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.5答辩小组评审成绩（加权分合计乘 8）分加权分合计答辩小组教师签名： 年 月 日课 程 设 计 总 评 成 绩分 沈沈 阳阳 工工 程程 学学 院院数据结构数据结构课程设计成绩评定表课程设计成绩评定表系（部）：系（部）： 信息信息学院学院 班级：班级： 学生姓名：学生姓名： 指指 导导 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15 54 43 32 2工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25 54 43 32 2工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55 54 43 32 2指导教师评审成绩（加权分合计乘以指导教师评审成绩（加权分合计乘以 8 8） 分分加权分合计加权分合计指指 导导 教教 师师 签签 名：名： 年年 月月 日日评评 阅阅 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25 54 43 32 2工作量工作量饱满，难度适中。0.55 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35 54 43 32 2评阅教师评审成绩（加权分合计乘以评阅教师评审成绩（加权分合计乘以 4 4）分分加权分合计加权分合计评评 阅阅 教教 师师 签签 名：名： 年年 月月 日日答答 辩辩 小小 组组 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.5答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.5答辩小组评审成绩答辩小组评审成绩（加权分合计乘以（加权分合计乘以 8 8）分分加权分合计加权分合计答辩小组教师签名：答辩小组教师签名： 年年 月月 日日课课 程程 设设 计计 总总 评评 成成 绩绩分分 沈沈 阳阳 工工 程程 学学 院院数据结构数据结构课程设计成绩评定表课程设计成绩评定表系（部）：系（部）： 信息信息学院学院 班级：班级： 学生姓名：学生姓名： 指指 导导 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15 54 43 32 2工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25 54 43 32 2工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55 54 43 32 2指导教师评审成绩（加权分合计乘以指导教师评审成绩（加权分合计乘以 8 8） 分分加权分合计加权分合计指指 导导 教教 师师 签签 名：名： 年年 月月 日日评评 阅阅 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分查阅文献查阅文献有一定广泛性；有综合归纳资料的能力0.25 54 43 32 2工作量工作量饱满，难度适中。0.55 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35 54 43 32 2评阅教师评审成绩（加权分合计乘以评阅教师评审成绩（加权分合计乘以 4 4）分分加权分合计加权分合计评评 阅阅 教教 师师 签签 名：名： 年年 月月 日日答答 辩辩 小小 组组 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.5答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.5答辩小组评审成绩答辩小组评审成绩（加权分合计乘以（加权分合计乘以 8 8）分分加权分合计加权分合计答辩小组教师签名：答辩小组教师签名： 年年 月月 日日课课 程程 设设 计计 总总 评评 成成 绩绩分分沈阳工程学院课程设计 摘 要 摘 要随着科学技术的发展，计算机技术在世界的每个角落得以运用与推广，其强大的功能已为人们深刻认识，利用计算机进行日常工作的管理也成为国家机关信息化的标志。同时，人们对计算机技术需求的增加，也促进了计算机新技术的发展。时代在进步，科技在发展，这改变了整个世界和人类的生活方式。同时，这也要求我们新世纪的大学生掌握现代科学技术知识，调整自己的知识结构和能力结构，以适应社会发展的要求，跟上时代的脚步。新世纪需要具有丰富的现代科学知识，能够独立解决面临的任务，充满活力，又有创新意识的新型人才。随着各个领域的突飞猛进，计算机也有它卓越的进步。数据结构不仅为计算机专业工作者所使用，而且为广大计算机应用人员所喜爱和使用。数据结构是国际上广泛流行的计算机高级语言。它适合作为系统描述语言，既可以用来编写系统软件，也可以用来编写应用软件。许多高等学校，不仅在计算机专业开设数据结构课程，而且在非计算机专业也开设了数据结构课程。学习数据结构已经成为广大计算机应用人员和广大青年学生的迫切要求。约瑟夫生死游戏是典型的线性表的应用实例，其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等特点。现如今，无论是小学、中学还是大学每学期都要面临教学计划安排的问题。然而学校的课程繁多，每所学校的课程也大不相同。给学生们安排课程成了老师的一项繁重而又难免的工作。虽然有软件可以实现课程的安排，但是大都需要购买，而且过程繁琐不好掌握。其实这项工作并没有想象中的那么难做，我们完全可以运用我们所学的有关图的知识利用邻接表和拓扑排序让计算机来帮我们完成这项工作，体验计算机技术给我带来的高效、和快速。课程安排普遍的要求是：根据课程之间的依赖关系，在满足各学期课程数大致相同的条件下制定出课程安排计划。在为期两周的数据结构课程设计学习中，先要学习数据结构课程的目的掌握数据结构存储的方法，学习会用计算机语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法结构存储是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重点放在语法规则上，语法是重要的，不掌握语法规则就无法编写出正确的程序。一定要把重点放在解题的思路上和运用何种存储的方法，通过思考和大量的阅读，来构造一个完整的程序。数据结构存储的设计直接关系到程序的好坏。最后，感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲。关键词关键词 线性表，图，邻接表，拓扑排序， 依赖关系， 算法结构存储沈阳工程学院课程设计 目 录I目目 录录摘摘 要要 .I第一章第一章 问题分析问题分析.11.1 引言.11.2 背景 .11.2.1 约瑟夫生死游戏背景.11.2.2 安排教学计划背景.11.3 分析 .21.3.1 约瑟夫生死游戏分析.21.3.2 安排教学计划分析.2第二章第二章 原理与运行环境原理与运行环境.42.1 数据结构理论 .42.1.1 线性表.42.1.2 邻接表和图.42.2 运行环境 .5第三章第三章 系统分析与设计系统分析与设计.73.1 约瑟夫生死游戏 .73.1.1 系统的功能.73.1.2 模块分析及流程图.83.2 安排教学计划 .103.2.1 系统的功能.103.2.2 模块分析及流程图.10第四章第四章 系统功能实现系统功能实现.164.1 约瑟夫生死游戏 .164.1.1 头文件、宏、数据结构体定义.164.1.2 主函数和菜单函数.164.1.3 创建约瑟夫环函数.184.1.4 输出出队顺序函数.194.2 安排教学计划 .214.2.1 头文件、宏、数据结构体定义.214.2.2 初始化栈、压栈、弹栈、判断栈空函数.214.2.3 邻接表建立函数.244.2.4 求图的入度函数.254.2.5 拓扑排序函数.254.2.6 主函数和菜单函数.28总总 结结.29致致 谢谢.30参考文献参考文献.31沈阳工程学院课程设计 第一章 问题分析0第一章 问题分析1.1 引言数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。 在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。 选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为（K，R）（或（D，S），其中，K 是数据元素的有限集，R 是 K 上的关系的有限集。 数据元素相互之间的关系称为结构。有四类基本结构：集合、线性结构、树形结构、图状结构（网状结构）。树形结构和图形结构全称为非线性结构。集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。在图形结构中每个结点的前驱结点数和后续结点数可以任意多个。数据结构它既是理论性较强的基础课，又是实践性很强的专业课，在计算机科学领域的主干课程中具有承上启下的作用。它的先行课程有计算机基础、程序设计语言、离散数学和数学等；后继课程有操作系统、数据库原理、编译原理和软件开发技术等。综上所述我们应该，在实践中理解它学好它。数据结构学习的技巧：学习数据结构的概念后对于抽象数据类型的设计参考 C+ STL 标准库中容器的设计。这样对于无论是数据结构的学习还有程序设计接口能力上都会有很大的提高。对于数据结构课程中很多时候都不太重视的顺序（数组）做存储的数据结构，希望大家还是要多留意这快的知识对于有些场合需要考虑时间换空间的情况下需要考虑顺序存储结构。数据结构学习一定要自己独立完成代码实现，虽然有时候你理解内容了，但是实现上面还是会愈要很多困难的，解决这些困难会帮助你提高程序设计的能力的。沈阳工程学院课程设计 第一章 问题分析11.2 背景1.2.1 约瑟夫生死游戏背景Josephus（约瑟夫斯）: 约 37-100 ,犹太历史学家和军人原名约瑟夫本马赛厄斯生于耶路撒冷西元 66 年在反对罗马的犹太起义中他指挥一支加利利军队在向罗马人投降时他施展手段获取优待，得以前往罗马，在那里写出几部关于犹太历史和宗教的著作，包括犹太战争史(History of the Jewish War,西元 75-79 年问世)和犹太古事记(Antiquities of the Jews,西元 93 年问世)卒于罗马。 据说著名犹太历史学家 Josephus 有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，每报数到第 3 人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而 Josephus 和他的朋友并不想遵从。首先从一个人开始，越过 k-2 个人（因为第一个人已经被越过），并杀掉第 k 个人。接着，再越过 k-1 个人，并杀掉第 k 个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus 要他的朋友先假装遵从，他将朋友与自己安排在第 16 个与第 31 个位置，于是逃过了这场死亡游戏。17 世纪的法国数学家加斯帕在数目的游戏问题中讲了这样一个故事：15 个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30 个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余 15 个人为止。问怎样排法，才能使每次投入大海的都是非教徒。题目中 30 个人围成一圈 ，因而启发我们用一个循环的链来表示，可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为 1 表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到 9 时，将结构中的标记改为 0，表示该人已被扔下海了。这样循环计数直到有 15个人被扔下海为止。约瑟夫环问题的具体描述是：设有编号为 1，2，n 的 n(n0)个人围成一个圈，从第 1 个人开始报数，报到 m 时停止报数，报 m 的人出圈，再从他的下一个人起重新报数，报到 m 时停止报数，报 m 的出圈，如此下去，直到所有人全部出圈为止。当任意给定n 和 m 后，设计算法求 n 个人出圈的次序。根据此问题用单链表构成的约瑟夫生死游戏系统。约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。1.2.2 安排教学计划背景随着科学技术的发展，计算机技术在世界的每个角落得以运用与推广，其强大的功能已沈阳工程学院课程设计 第一章 问题分析2为人们深刻认识，利用计算机进行日常工作的管理也成为国家机关信息化的标志。同时，人们对计算机技术需求的增加，也促进了计算机新技术的发展。近代以来，特别是在实行学科课程的条件下，教学计划主要是学科的计划，或只是学科表。随着社会经济和科学技术的新发展，教育结构不断发生变革，现代教育和教学理论主张对教学计划的结构实行改革。除了教学以外，生产劳动、科技活动、发展体力和增进健康的活动、艺术活动和社会活动等也应列入教学计划。在工具课和一般科学知识课、自然学科和社会学科、普通教育课和职业教育课之间应相互渗透。在新知识不断涌现的形势下，只有必修课而无选修课的单一结构不能适应学生个性才能的发展和知识多样性的要求，适当增设选修课,已成为发展的趋势。一些选修课在一定条件下,可能成为必修课。根据一定的教育目的和培养目标制定的教学和教育工作的指导文件。教学计划决定着教学内容总的方向和总的结构，并对有关学校的教学、教育活动，生产劳动和课外活动校外活动等各方面作出全面安排，具体规定一定学校的学科设置、各门学科的教学顺序、教学时数以及各种活动等。教学计划、教学大纲和教科书互相联系，共同反映教学内容。 然而学校的课程繁多，每所学校的课程也大不相同。给学生们安排课程成了老师的一项繁重而又难免的工作。虽然有软件可以实现课程的安排，但是大都需要购买，而且过程繁琐不好掌握。其实这项工作并没有想象中的那么难做，我们完全可以运用我们所学的知识让计算机来帮我们完成这项工作，体验计算机技术给我带来的高效、和快速。课程安排普遍的要求是：根据课程之间的依赖关系，在满足各学期课程数大致相同的条件下制定出课程安排计划。针对各大院校课程繁多课程安排难的问题，并且避免以往程序的繁琐和不易上手，我们从实际出发，充分运用我们所学的知识，根据不同学校的情况设计出教学计划安排检验程序。安排教学计划系统可以根据用户输入的课程数、课程编号、课程间的先后关系数目以及课程间两两间的先后关系，给出学生每学期应学的课程。该教学计划安排程序具有操作简单，功能完善，实用性强等特点，能很好的完成教学计划的拓扑排序即课程安排的先后顺序。课程安排的先后顺序，与拓扑结构相同。可利用拓扑排序来实现。从而让计算机代替人工安排课程。1.3 分析1.3.1 约瑟夫生死游戏分析为了解决约瑟夫问题，并为了解决由此而衍生的类似的游戏原理理解问题。在制作的过程中要解决问题分析，编码，制作等相关问题，本课程设计的目标是运用循环链表来解决Josephus 环问题，其中运用了许多链表中的基本操作使该程序能够解决多个 Josephus 的简沈阳工程学院课程设计 第一章 问题分析3单链表，Josephus 函数则是用 C+程序编写的程序，实现队列的建立、插入和删除等基本功能，在程序设计成功的基础上，进一步深化理解队列的作用和实现原理。主要分析：1.输入的形式和输入值的范围：本程序中，输入人数上限，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。2.输出的形式：从屏幕显示出列顺序。3.程序功能：提供用户从键盘输入，Joseph 约瑟夫环的必要数据，并显示出列顺序。1.3.1 安排教学计划分析总体思想是利用拓扑排序的思想和堆栈思想编写相应函数。首先根据课程的先后关系画出 AOV 网，网中的结点代表课程，有向边表示各学科之间的次序关系。可以采用邻接表作AOV 网的存储结构，且在头结点中增加一个存放顶点入度的数组。为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。然后根据拓扑排序依次输出应学的课程。编写的程序根据用户输入的课程数，课程编号，课程间的先后关系数目以及课程间两两间的先后关系，实现输出课程安排的先后顺序的功能。拓扑排序时有向图的一种重要运算。在课表排序中，每门课都有多种关系：（一）先后关系，即必须在一门课学完后，才能开始学习另一门课；（二）在一类课之间没有次序要求，即两门课可以同时学习，互不影响。将 AOV 网络中的各个顶点排列成一个线性有序序列，使得所有的要求的前趋、后趋关系都能得到满足。在 AOV 网络进行拓扑排序的方法： 1选择一个没有前趋的顶点，并把它输出； 2从网络中删去该顶点和从该顶点出发的所有有向边； 3重复执行上述两步，直到网中所有的顶点都被输出。 沈阳工程学院课程设计 第二章 运行原理和环境0第二章 运行原理和环境2.1 数据结构理论2.1.1 线性表线性表：是由类型相同的数据元素组成的有限序列，不同线性表的数据元素类型可以不同，可以是最简单的数值和字符，也可以是比较复杂的信息。线性表的存储结构共分为两种：顺序存储结构和链式存储结构。约瑟夫生死游戏采用的数据结构是线性表的链式存储结构中的单向循环链表。顺序存储结构：逻辑上相邻的数据元素在物理位置上也是相邻的，采用数组实现。文本文件单词的检索和计数采用的数据结构是线性表的链式存储结构。链式存储结构：不要求逻辑上相邻的数据元素在物理位置上也是相邻的，插入删除操作时不需要移动元素。链式存储结构中单链表是一种最简单的线性表的链式存储结构，单链表也称为线性链表，用它来存储线性表时，每个数据元素用一个结点（node）来存储，一个结点由两个成分域组成，一个是存放数据元素的 data，称为数据域，另一个是存储指向此链表下一个结点的指针 next，称为指针域。循环链表：是一种线性表链式存储结构，它的结点结构与单链表相同，与单链表不同的是在循环链表中表尾结点的 next 指针域不空（NULL），而是指向头结点，如图 2.1 所示。图 2.1 循环链表2.1.2 邻接表和图邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器（n 个顶点建立 n 个容器），第 i 个容器中的结点包含顶点 Vi 的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。在有向图中，描述每个点向别的节点连的边（点 a-点 b 这种情况）。在无向图中，描述每个点所有的边(点 a-点 b 这种情况)与邻接表相对应的存图方式叫做边集表，这种方法用一个容器存储所有的边。注意：n 个顶点 e 条边的无向图的邻接表表示中有 n 个顶点表结点和 2e 个边表结点。(换句话说，每条边（i,j）在邻接表 中出现两次：一次在关于 i 的邻接表中，另一次在关于 j 的邻接表中)有向图：对于有向图，vi 的邻接表中每个表结点都对应于以 vi 为始点射出的一条边。因此，将有向图的邻接表称为出边表。沈阳工程学院课程设计 第二章 运行原理和环境1【例】有向图 G6 如下图所示，其中顶点 v1 的邻接表上两个表结点中的顶点序号分别为0 和 4，它们分别表示从 v1 射出的两条边(简称为 v1 的出边)：和。图存储的方法举例如图 2.2：图 2.2 图存储的方法举例注意：n 个顶点 e 条边的有向图，它的邻接表表示中有 n 个顶点表结点和 e 个边表结点。（因为有向图是单向的）逆邻接表在有向图中，为图中每个顶点 vi 建立一个入边表的方法称逆邻接表表示法。入边表中的每个表结点均对应一条以 vi 为终点(即射入 vi)的边。【例】G6 的逆邻表如上面(b)图所示，其中 v0 的入边表上两个表结点 1 和 3 分别表示射人 v0 的两条边(简称为 v0 的入边)：和。注意：n 个顶点 e 条边的有向图，它的逆邻接表表示中有 n 个顶点表结点和 e 个边表结点。3邻接表的形式说明。邻接表是一个二维容器，第一维描述某个点，第二维描述这个点所对应的边集们。实现邻接表的方法绝对有 100 种以上。即使是前向星这种东西也是邻接表，因为它还是描述某个点和这个点所对应的边集们.我们说说常用的邻接表存图法（静态的 array 就不说了.）必须有开 O1 以及以上编译的条件，不然没有测试的效率无任何意义。沈阳工程学院课程设计 第二章 运行原理和环境22.2 运行环境 Microsoft Visual Studio（简称 VS）是美国微软公司的开发工具包系列产品。VS 是一个基本完整的开发工具集，它包括了整个软件生命周期中所需要的大部分工具，如 UML 工具、代码管控工具、集成开发环境(IDE)等等。所写的目标代码适用于微软支持的所有平台，包括 Microsoft Windows、Windows Mobile、Windows CE、.NET Framework、.NET Compact Framework 和 Microsoft Silverlight 及 Windows Phone。Visual Studio 是目前最流行的 Windows 平台应用程序的集成开发环境。最新版本为 Visual Studio 2013 版本，基于.NET Framework 4.5.1 。此次课程设计需要使用 Microsoft Visual Studio 2010 集成开发环境。Visual Studio是微软公司推出的开发环境。是目前较流行的 Windows 平台应用程序开发环境。Visual Studio 2010 版本于 2010 年 4 月 12 日上市，其集成开发环境（IDE）的界面被重新设计和组织，变得更加简单明了。Visual Studio 2010 同时带来了 NET Framework 4.0、Microsoft Visual Studio 2010 CTP( Community Technology Preview-CTP)，并且支持开发面向 Windows 7 的应用程序。除了 Microsoft SQL Server，它还支持 IBM DB2 和Oracle 数据库。Visual C+ 全称是 MicroSoft Visual C+, 即微软的 C+ 和 C 的编译器。 用Visual C+写程序，即用微软的 C+语言写程序，可以调用微软的 C+ 的 MFC 等程序库，应用微软的 C+ 的头文件。 MicroSoft Visual C+ 是 C+ 语言或编译器的一种，只能用于普通的 PC 机视窗环境，不能用于 unix 等其它计算机。Visual C+ 也可以看成是名称或商业标记，以便于与别的公司出的编译器区分。 Visual 是强调它的 C+支持“可视”，支持作图。 C+ 是 统称。有各式各样的 C+，有用于 PC 的别的 C+，有用于其它平台的 C+。 就如 unix 是 统称，具体的 unix 有 Sun 的，HP 的，SGI 的,DEC 的,linux 等。 不讲Visual 的 C 或 C+,不等于它不支持“可视”，不支持作图。 Visual C+ 调用的 OpenGL 来源于硅图公司的 GL，硅图在 SiliconGraphics IRIS （unix 系统）机上就叫 C, “可视”搞得最好。在 Windows 环境下，先通过浏览找到 VS2010 打开如图 2.3 所示，新建一个文件即可进行编程，其运行界面如图 2.4 所示。图 2.3 VS2010 运行环境沈阳工程学院课程设计 第二章 运行原理和环境3 图 2.4 运行界面沈阳工程学院课程设计 第三章 系统分析与设计0第三章 系统分析与设计3.1 约瑟夫生死游戏3.1.1 系统的功能约瑟夫环问题描述的是：设编号为 1，2，n 的 n（n0）个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限 m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 时停止报数，报 m 的人出圈，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人起重新从 1 报数。如此下去，直到所有人都出圈为止。所需要的数据结构为线性表的链式储存结构，根据思想可以确定约瑟夫生死游戏的功能主要包括，初始化约瑟夫生死环、设定生死规则、输出出队顺序和游戏界面设置。系统功能模块图如图3.1 所示。图 3.1 系统功能模块图如图 3.1 所示，本系统分为 4 个功能模块分别为：初始化约瑟夫生死环、设定生死规则、输出生者和死者和游戏界面设置。1.初始化约瑟夫生死环：使整个游戏在链表中运行，使得结点在删除时不需要移动大量的结点；2.设定生死规则：输入要删除的位置序号，进而使链表具化体，从而可以构建一个具体的链表；3.输出出队顺序：输出被投入海中人的位置序号、每个人的密码及最后一个出队的人和其密码值； 4.游戏界面设置：游戏开始时提示“按任意键继续”，运行最后显示菜单界面，可以继续进行游戏或者直接退出。3.1.2 模块分析及流程图约瑟夫生死游戏分为 4 个模块分别为：初始化约瑟夫生死环、设定生死规则、输出生者沈阳工程学院课程设计 第三章 系统分析与设计1和死者和游戏界面设置。主要模块的设计如下：1.初始化约瑟夫生死环初始化约瑟夫生死环主要实现使整个游戏在链表中运行，使得结点在删除时不需要移动大量的结点，用 p，q 两个指针的移动构建一个单循环链表用 next 作为存放下一个接点的地址空间并将头结点放入最后一个地址空间使之能形成以循环单链表结构，使整个游戏在链表中运行，使得结点在删除时不需要移动大量的结点。初始化约瑟夫生死环模块的流程图如图3.2 所示。图 3.2 初始化约瑟夫生死环流程图2.设定生死规则输入要删除的位置序号，进而使链具化体，从而可以构建一个具体的链表；接收头指针L 对其进行循环遍历找到输入的第 n 个对其剔除结点后的链表进行重新连接又有构成了一个新的链表，使得循环继续进行。设定生死规则的流程图如图 3.3 所示。沈阳工程学院课程设计 第三章 系统分析与设计2图 3.3 设定生死规则流程图3.输出出队顺序输出第一个被投入海中人的位置序号和其密码值；接收指针 L 并将其赋值给头指针输出数据域 data 然后指向下一个地址循环遍历链表输出所有被投入海中人的位置序号和密码值及最后一个出队的人和其密码值。设计流程图如图 3.4 所示。图 3.4 输出出队顺序流程图沈阳工程学院课程设计 第三章 系统分析与设计33.2 安排教学计划3.2.1 系统的功能总体思想是利用拓扑排序的思想和堆栈思想编写相应函数。首先根据课程的先后关系画出 AOV 网，网中的结点代表课程，有向边表示各学科之间的次序关系。可以采用邻接表作 AOV 网的存储结构，且在头结点中增加一个存放顶点入度的数组。为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。然后根据拓扑排序依次输出应学的课程。编写的程序根据用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，实现输出每学期应学的课程的功能。安排教学计划菜 单 及 默 认 课 程 名 求 图 的 入 度 拓 扑 排 序 输 出 排 序 栈 的 一 系 列 操 作 建 临 接 表 其功能模块图如图 3.5 所示。如图 3.5 所示，本系统分为 6 个功能模块分别为：菜单及默认课程、栈的一系列操作、建立邻接表、求图的入度、拓扑排序、输出排序。1. 菜单及默认课程：使整个系统在运行前，让用户了解系统默认的值及初始条件；2. 栈的一系列操作：用于求图的入度、拓扑排序、输出排序等模块运行使用；3. 建立邻接表：用于存储图即课程编号，课程的先后顺序； 4. 求图的入度：用于拓扑排序和输出排序。5. 拓扑排序：将输入的课程编号和课程的先后顺序进行拓扑排序。6. 输出排序：输出运行结果。3.2.2 系统分析模块分析及流程图总体思想是利用拓扑排序的思想和堆栈思想编写相应函数。沈阳工程学院课程设计 第三章 系统分析与设计4首先根据课程的先后关系画出 AOV 网，网中的结点代表课程，有向边表示各学科之间的次序关系。可以采用邻接表作 AOV 网的存储结构，且在头结点中增加一个存放顶点入度的数组。为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。然后根据拓扑排序依次输出应学的课程。编写的程序根据用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，实现输出每学期应学的课程的功能。 1.系统总流程图，如图 3.6 所示。 2.拓扑排序算法思想和流程图 系统总流程图，图 3.6 流程图如图 3-5 所示。沈阳工程学院课程设计 第四章 系统功能实现0第四章 系统功能实现4.1 约瑟夫生死游戏4.1.1 头文件、宏、数据结构体定义一般而言，每个 C+/C 程序通常由头文件(header files)和定义文件(definition files)组成。头文件作为一种包含功能函数、数据接口声明的载体文件，用于保存程序的声明(declaration)，而定义文件用于保存程序的实现 (implementation)。约瑟夫生死游戏中包含的头文件有：#include 定义输入/输出函数、#include 定义杂项函数及内存分配函数和#include 定义数学函数，通过宏定义把空指针、错误返回值和正确返回值进行定义数值，结构体定义相关类型的链表空间有整型数据空间，循环单链表存储下一个指针空间。/头文件定义#include /输入输出函数头文件#include /字符串转短整形函数的头文件/宏定义#define NULL 0#define ERROR 0#define OK 1/数据结构类型定义typedef struct LNode/定义单循环链表中节点的结构 int num;/编号 int pwd;/passwordstruct LNode *next;/指向下一结点的指针LNode; 4.1.2 主函数和菜单函数 本功能模块主要是通过源程序的编写实现的主函数菜单界面。对使用者在使用该软件时进行提示如何进行操作。在本软件中是利用人机交互的方式达到实现软件中各个功能的目的的。但由于编写人员能力有限及编写需求的双重条件，在本人机交互界面中只有输入命令提示符这一种命令交互方式并没有如：快捷键、点击的交互方式。主要程序代码如下：/*主函数模块*/void main() int n,m,x; LNode *ppHead=NULL; menu(); for(;)沈阳工程学院课程设计 第四章 系统功能实现1 printf(n 请选择要执行的操作：); scanf(%d,&x); system(cls); switch(x)case 1:printf(*n); printf(约瑟夫环:n); printf( 编号为 1,2,3,4,n 的 n 个人按顺时针方向围坐一圈,每人持有一个密n); printf(码(正整数).一开始任选一个正整数作为报数的上限值 m,从第一个人开始n); printf(按顺时针方向自 1 开始顺序报数,报到 m 时停止.报 m 的人出列，将他的密码n); printf(m 作为新的 m 值,从他在顺时针方向上的下一人开始重新从 1 报数,如此下去,n); printf(直到所有人全部出列为止.编程打印出列顺序.n); printf(*n); main(); break; case 2: printf(n 请输入总人数 n：); scanf(%d,&n); printf(请输入开始上限数 m：); scanf(%d,&m); createList(&ppHead,n); printf(n); printf(出队顺序：n); jose(ppHead,m); printf(n 约瑟夫环游戏结束!n); main(); break;case 0: exit(0); default: system(cls); printf(n 您选择的操作有误，请重新选择.nnn); main(); 沈阳工程学院课程设计 第四章 系统功能实现2 /*菜单函数模块*/void menu()printf(*约瑟夫环*n);printf( n);printf( 1约瑟夫环问题的阐述 n);printf( 2按要求求解约瑟夫环 n);printf( 0退出 n);printf(*欢迎使用*n);运行上述程序，系统的主函数界面如图 4.1 所示。 图 4.1 主函数和菜单函数开始 4.1.3 创建约瑟夫环函数 创建单向循环链表 ppHead，人数个数为 n，并输入每个人的密码值，若建立失败则生成头结点，让 cur 指向他，若建立成功则插入结点 P，cur 指向的数据元素为 p，后续为空的节点，再把 P 插入循环链表 ppHead 中。主要程序代码如下：/*构造结点*/LNode *createNode(int m_num,int m_pwd)LNode *p;p=(LNode *)malloc(sizeof(LNode);/生成一个结点 p-num=m_num;/把实参赋给相应的数据域p-pwd=m_pwd;p-next=NULL;/指针域为空return p; 沈阳工程学院课程设计 第四章 系统功能实现3/*创建循环链表*/void createList(LNode *ppHead,int n)int i,m_pwd;LNode *p,*cur;/cur:浮标指针for(i=1;inext=*ppHead;/cur 的指针域指向自身 else/如果不为空，则插入结点 p-next = cur-next;cur-next = p;cur= p;/cur 指向新插入结点 printf(完成创建！n); /提示链表创建完成 功能实现图如图 4.2 所示。图 4.2 初始化约瑟夫生死环4.1.4 输出出队顺序函数 定义指针 p 指向要删除节点的前一个节点，ppHead 指向要删除的节点，使p=ppHead，ppHead 再指向要删除节点的下一个节点，使 p 和 ppHead 链接，输出 p 指向节点的编号和密码值，释放 ppHead，如此循环，直至把所有节点都打印和删除为止！主要代码如下：沈阳工程学院课程设计 第四章 系统功能实现4/出队函数void jose(LNode *ppHead,int m_pwd)int i,j;LNode *p,*p_del;/定义指针变量for(i=1;p!=ppHead;i+)for(j=1;jnext;/ppHead 指向下一个元素p-next = ppHead-next;/p 结点与头结点链接i=ppHead-pwd;/i 赋值为 ppHead-pwd j=ppHead-num;/j 赋值为 ppHead-num，j 为要删除的密码值printf(第%d 个人出列，密码：%dn,j,i); m_pwd=ppHead-pwd;/m_pwd 赋值为 ppHead-pwdfree(ppHead);/释放头结点ppHead=p-next;/ppHead 重新赋值给 p-next,即释放前的 ppHead-pwd 指针i=ppHead-pwd;/i 赋值为 ppHead-pwdj=ppHead-num;/j 赋值为 ppHead-numprintf(最后一个出列是%d 号，密码是:%dn,j,i); free(ppHead);/释放头结点运行结果界面如图 4.3 所示。图 4.3 运行结果4.2 安排教学计划4.2.1 头文件、宏、数据结构体定义沈阳工程学院课程设计 第四章 系统功能实现5一般而言，每个 C+/C 程序通常由头文件(header files)和定义文件(definition files)组成。头文件作为一种包含功能函数、数据接口声明的载体文件，用于保存程序的声明(declaration)，而定义文件用于保存程序的实现 (implementation)。文本文件单词的检索和计数中包含的头文件有：#include 定义输入/输出函数、#include 定义杂项函数及内存分配函数#include 和#include定义字符串函数，通过宏定义把空指针、错误返回值和正确返回值进行定义数值，结构体定义相关类型的链表空间有整型数据空间，单链表存储下一个指针空间。/头文件定义#include /输入输出函数头文件#include /字符串转短整形函数的头文件#include/内存分配函数头文件#include /字符串函数头文件/宏定义