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

沈 阳 工 程 学 院

课 程 设 计

设计题目：约瑟夫环、安排教学计划

系 别 信息学院 班级 学生姓 学号

指导教师 姜柳 、吕海华 职称 副教授、讲师 起止日期： 年 月 日起——至 年 月 日止

沈 阳 工 程 学 院

课程设计任务书

课程设计题目：约瑟夫环

系 别 信息学院 班级 学生姓名 学号

指导教师 姜柳 、吕海华 职称 副教授、讲师 课程设计进行地点： 实训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 2 3 4 5 第1天 第2—3天 第4—8天 第9天 第10天 阶段日期 计 划 完 成 内 容 阅读资料 系统分析设计 程序编制、调试及运行 成绩评定# 撰写课程设计说明书 备注 六、主要参考资料（文献）

[1]郭翠英.C语言课程设计案例精编.北京：中国水利水电出版社.2004.3 [2]谭浩强.C语言程序设计.北京:清华大学出版社.1999.12

[3]张翔.C语言函数大全.北京:清华大学出版社.2002.4

[4]浦滨.C游戏编程从入门到精通.北京: 北京希望电子出版社.2002.5 [5]陈天洲.C语言高级程序设计. 北京:人民邮电出版社.2002

[6]杨旭.C语言程序设计案例教程.北京: 人民邮电出版社.2005

[7] 王为青．C语言高级编程及实例剖析．北京:人民邮电出版社．2008．02 [8]徐慧.《C语言实例解析精粹》.北京:人民邮电出版社.2006.04

[9] 姚大鹏 栾好利 张翼英 等编著.C语言程序设计教程习题与上机实训指导.中国水利水电出版社.2005

[10] 王为青．C语言实例解析．北京:人民邮电出版社．2008．02

沈 阳 工 程 学 院

课程设计任务书

课程设计题目：安排教学计划

系 别 信息学院 班级 学生姓名 学号 指导教师 姜柳 、吕海华 职称 副教授、讲师 课程设计进行地点： 实训F座 任 务 下 达 时 间： 年 月 日 起止日期： 年 月 日起——至 年 月 日止 教研室主任 张欣 年 月 日批准

一、课程设计的原始资料及依据

学校每个学期开设的课程是又先后顺序的，如计算机专业：开设《数据结构》课程之前，必须先开设《C语言程序设计》和《离散数学》课程，这种课程开设的先后顺序关系称为先行，后继课程关系。现在需要根据给定的课程信息及课程之间的先行、后继关系，合理安排出开设各门课程的先后顺序。

查阅有关程序设计的案例资料，进一步理解程序设计模块化的思想，并利用此思想，根据对程序设计学习编写一个安排教学计划系统。通过本设计可以加深理解利用程序设计思想开发一个系统的整个流程，提高分析问题、解决问题和实际动手的能力。

二、课程设计主要内容及要求

1对输入的课程先行、后继关系如果存在回路关系时应提示现错误；

2根据读入的课程信息及其先行、后继关系，计算出安排教学计划的序列。 3输出教学计划的安排顺序或给出错误提示信息。

三、对课程设计说明书撰写内容、格式、字数的要求

1．课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于3000字。

2．在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。

3．设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组组长给出评语。

4．课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用A4纸，页边距均为20mm，正文采用宋体小四号字，行间距18磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。

5．课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。

四、设计完成后应提交成果的种类、数量、质量等方面的要求

1．完成“任务书”中指定的操作功能，运行稳定。 2．课程设计说明书。

五、时间进度安排

顺序 1 2 3 4 5 第1天 第2—3天 第4—8天 第9天 第10天 阶段日期 计 划 完 成 内 容 阅读资料 系统分析设计 程序编制、调试及运行 成绩评定 撰写课程设计说明书 备注 六、主要参考资料（文献）

[1]严蔚敏 吴伟民.数据结构（C语言版）. 北京:清华大学出版社.2007 [2]谭浩强.C程序设计.北京:清华大学出版社.1999.12

[3]滕国文.数据结构课程设计.北京:清华大学出版社.2010.09

[4]苏仕华 等编著. 数据结构课程设计. 北京:机械工业出版社.2005.05

[5]李春葆.数据结构（C语言版）习题与解析.北京:清华大学出版社.2002..04

沈 阳 工 程 学 院 数据结构课程设计成绩评定表

系（部）： 信息学院 班级： 学生姓名：

指 导 教 师 评 审 意 见 评价内容 调研论证 工作能力态度 工作量 说明书的质量 具 体 要 求 能独立查阅文献,收集资料；能制定课程设计方案和日程安排。 权重 0.1 5 5 5 评 分 4 4 4 3 3 3 加权分 2 2 2 工作态度认真，遵守纪律，出勤情况是否良好，0.2 能够独立完成设计工作， 按期圆满完成规定的设计任务，工作量饱满，难度适宜。 0.2 说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，0.5 图表完备，书写工整规范。 分 5 4 3 2 指导教师评审成绩（加权分合计乘以8） 指 导 教 师 签 名： 加权分合计 年 月 日 评 阅 教 师 评 审 意 见 评价内容 查阅文献 工作量 说明书的质量 具 体 要 求 工作量饱满，难度适中。 权重 5 5 5 0.5 评 分 4 4 4 3 3 3 加权分 2 2 2 查阅文献有一定广泛性；有综合归纳资料的能力 0.2 说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，0.3 图表完备，书写工整规范。 评阅教师评审成绩 （加权分合计乘以4） 评 阅 教 师 签 名： 答 辩 小 组 评 审 意 见 评价容 学生报 具 体 要 求 汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。 权重 0.5 评 分 3 加权分 2 分 加权分合计 年 月 日 答 辩 思路清晰；回答问题有理论依据，基本概念清楚；0.5 主要问题回答准确，深入，有说服力。 分 答辩小组评审成绩（加权分合计乘8） 答辩小组教师签名： 课 程 设 计 总 评 成 绩 加权分合计 年 月 日 分

沈 阳 工 程 学 院 数据结构课程设计成绩评定表

系（部）： 信息学院 班级： 学生姓名：

指 导 教 师 评 审 意 见 评价内容 调研论证 工作能力态度 工作量 说明书的质量 具 体 要 求 能独立查阅文献,收集资料；能制定课程设计方案和日程安排。 权重 0.1 评 分 5 5 5 4 4 4 3 3 3 加权分 2 2 2 工作态度认真，遵守纪律，出勤情况是否良好，0.2 能够独立完成设计工作， 按期圆满完成规定的设计任务，工作量饱满，难度适宜。 说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。 分 0.2 0.5 5 4 3 2 指导教师评审成绩（加权分合计乘以8） 指 导 教 师 签 名： 加权分合计 年 月 日 评 阅 教 师 评 审 意 见 评价内容 查阅文献 工作量 说明书的质量 具 体 要 求 查阅文献有一定广泛性；有综合归纳资料的能力 工作量饱满，难度适中。 说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。 分 权重 0.2 0.5 0.3 5 5 5 评 分 4 4 4 3 3 3 加权分 2 2 2 评阅教师评审成绩（加权分合计乘以4） 评 阅 教 师 签 名： 加权分合计 年 月 日 答 辩 小 组 评 审 意 见 评价内容 学生汇报 具 体 要 求 权重 评 分 加权分 2汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上0.5 反映了所完成任务的全部内容；时间符合要求。 思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。 答辩小组评审成绩 （加权分合计乘以8） 答辩小组教师签名： 课 程 设 计 总 评 成 绩 分 0.5 答 辩 2 加权分合计 年 月 日 分

沈 阳 工 程 学 院 数据结构课程设计成绩评定表

系（部）： 信息学院 班级： 学生姓名：

指 导 教 师 评 审 意 见 评价内容 调研论证 工作能力态度 工作量 说明书的质量 具 体 要 求 能独立查阅文献,收集资料；能制定课程设计方案和日程安排。 权重 0.1 5 5 5 评 分 4 4 4 3 3 3 加权分 2 2 2 工作态度认真，遵守纪律，出勤情况是否良好，0.2 能够独立完成设计工作， 按期圆满完成规定的设计任务，工作量饱满，难度适宜。 说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。 分 0.2 0.5 5 4 3 2 指导教师评审成绩（加权分合计乘以8） 指 导 教 师 签 名： 加权分合计 年 月 日 评 阅 教 师 评 审 意 见 评价内容 查阅文献 工作量 说明书的质量 具 体 要 求 查阅文献有一定广泛性；有综合归纳资料的能力 工作量饱满，难度适中。 说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。 分 权重 0.2 0.5 0.3 5 5 5 评 分 4 4 4 3 3 3 加权分 2 2 2 评阅教师评审成绩（加权分合计乘以4） 评 阅 教 师 签 名： 加权分合计 年 月 日 答 辩 小 组 评 审 意 见 评价内容 学生汇报 具 体 要 求 权重 评 分 加权分 2汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上0.5 反映了所完成任务的全部内容；时间符合要求。 思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。 答辩小组评审成绩 （加权分合计乘以8） 答辩小组教师签名： 课 程 设 计 总 评 成 绩 分 0.5 答 辩 2 加权分合计 年 月 日 分

沈阳工程学院课程设计 摘 要

摘 要

随着科学技术的发展，计算机技术在世界的每个角落得以运用与推广，其强大的功能已为人们深刻认识，利用计算机进行日常工作的管理也成为国家机关信息化的标志。同时，人们对计算机技术需求的增加，也促进了计算机新技术的发展。时代在进步，科技在发展，这改变了整个世界和人类的生活方式。同时，这也要求我们新世纪的大学生掌握现代科学技术知识，调整自己的知识结构和能力结构，以适应社会发展的要求，跟上时代的脚步。新世纪需要具有丰富的现代科学知识，能够独立解决面临的任务，充满活力，又有创新意识的新型人才。随着各个领域的突飞猛进，计算机也有它卓越的进步。数据结构不仅为计算机专业工作者所使用，而且为广大计算机应用人员所喜爱和使用。数据结构是国际上广泛流行的计算机高级语言。它适合作为系统描述语言，既可以用来编写系统软件，也可以用来编写应用软件。许多高等学校，不仅在计算机专业开设数据结构课程，而且在非计算机专业也开设了数据结构课程。学习数据结构已经成为广大计算机应用人员和广大青年学生的迫切要求。

约瑟夫生死游戏是典型的线性表的应用实例，其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等特点。

现如今，无论是小学、中学还是大学每学期都要面临教学计划安排的问题。然而学校的课程繁多，每所学校的课程也大不相同。给学生们安排课程成了老师的一项繁重而又难免的工作。虽然有软件可以实现课程的安排，但是大都需要购买，而且过程繁琐不好掌握。其实这项工作并没有想象中的那么难做，我们完全可以运用我们所学的有关图的知识利用邻接表和拓扑排序让计算机来帮我们完成这项工作，体验计算机技术给我带来的高效、和快速。课程安排普遍的要求是：根据课程之间的依赖关系，在满足各学期课程数大致相同的条件下制定出课程安排计划。

在为期两周的数据结构课程设计学习中，先要学习数据结构课程的目的掌握数据结构存储的方法，学习会用计算机语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法结构存储是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重点放在语法规则上，语法是重要的，不掌握语法规则就无法编写出正确的程序。一定要把重点放在解题的思路上和运用何种存储的方法，通过思考和大量的阅读，来构造一个完整的程序。数据结构存储的设计直接关系到程序的好坏。

最后，感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲。

关键词 线性表，图，邻接表，拓扑排序， 依赖关系， 算法结构存储

I

沈阳工程学院课程设计 目 录

目 录

摘 要 .................................................................................................................................................... I 第一章 问题分析................................................................................................................................ 1 1.1 引言............................................................................................................................................ 1 1.2背景 .......................................................................................................... 错误！未定义书签。 1.2.1约瑟夫生死游戏背景 ........................................................................ 错误！未定义书签。 1.2.2安排教学计划背景 ............................................................................ 错误！未定义书签。 1.3分析 .......................................................................................................... 错误！未定义书签。 1.3.1约瑟夫生死游戏分析 .......................................................................................................... 4 1.3.2安排教学计划分析 ............................................................................ 错误！未定义书签。 第二章 原理与运行环境 ................................................................................. 错误！未定义书签。 2.1数据结构理论 ............................................................................................................................ 5 2.1.1线性表 .................................................................................................................................. 5 2.1.2邻接表和图 .......................................................................................................................... 5 2.2运行环境 .................................................................................................................................... 7 第三章 系统分析与设计 ................................................................................................................... 9 3.1约瑟夫生死游戏 ........................................................................................................................ 9 3.1.1系统的功能 .......................................................................................................................... 9 3.1.2模块分析及流程图 ............................................................................................................ 10 3.2安排教学计划 .......................................................................................................................... 12 3.2.1系统的功能 ........................................................................................................................ 12 3.2.2模块分析及流程图 ............................................................................ 错误！未定义书签。 第四章 系统功能实现 ..................................................................................... 错误！未定义书签。 4.1约瑟夫生死游戏 ...................................................................................... 错误！未定义书签。 4.1.1头文件、宏、数据结构体定义 ........................................................ 错误！未定义书签。 4.1.2主函数和菜单函数 ............................................................................ 错误！未定义书签。 4.1.3创建约瑟夫环函数 ............................................................................ 错误！未定义书签。 4.1.4输出出队顺序函数 ............................................................................ 错误！未定义书签。 4.2安排教学计划 .......................................................................................... 错误！未定义书签。 4.2.1头文件、宏、数据结构体定义 ........................................................................................ 19 4.2.2初始化栈、压栈、弹栈、判断栈空函数 ........................................ 错误！未定义书签。 4.2.3邻接表建立函数 ................................................................................ 错误！未定义书签。 4.2.4求图的入度函数 ................................................................................ 错误！未定义书签。 4.2.5拓扑排序函数 .................................................................................... 错误！未定义书签。 4.2.6主函数和菜单函数 ............................................................................ 错误！未定义书签。

总 结 .................................................................................................................. 错误！未定义书签。 致 谢 ................................................................................................................ 错误！未定义书签。 参考文献 ............................................................................................................ 错误！未定义书签。

II

沈阳工程学院课程设计 第一章 问题分析

第一章 问题分析

1.1 引言

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。 在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。 选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。

数据结构是指同一数据元素类中各数据元素之间存在的关系。数据结构分别为逻辑结构、存储结构（物理结构）和数据的运算。数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。 数据元素相互之间的关系称为结构。有四类基本结构：集合、线性结构、树形结构、图状结构（网状结构）。树形结构和图形结构全称为非线性结构。集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。在图形结构中每个结点的前驱结点数和后续结点数可以任意多个。数据结构它既是理论性较强的基础课，又是实践性很强的专业课，在计算机科学领域的主干课程中具有承上启下的作用。它的先行课程有计算机基础、程序设计语言、离散数学和数学等；后继课程有操作系统、数据库原理、编译原理和软件开发技术等。 综上所述我们应该，在实践中理解它学好它。数据结构学习的技巧：学习数据结构的概念后对于抽象数据类型的设计参考C++ STL标准库中容器的设计。这样对于无论是数据结构的学习还有程序设计接口能力上都会有很大的提高。对于数据结构课程中很多时候都不太重视的顺序（数组）做存储的数据结构，希望大家还是要多留意这快的知识．对于有些场合需要考虑时间换空间的情况下需要考虑顺序存储结构。数据结构学习一定要自己独立完成代码实现，虽然有时候你理解内容了，但是实现上面还是会愈要很多困难的，解决这些困难会帮助你提高程序设计的能力的。

1

沈阳工程学院课程设计 第一章 问题分析

1.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(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，??，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。根据此问题用单链表构成的约瑟夫生死游戏系统。

约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。

2

沈阳工程学院课程设计 第一章 问题分析

1.2.2安排教学计划背景

随着科学技术的发展，计算机技术在世界的每个角落得以运用与推广，其强大的功能已为人们深刻认识，利用计算机进行日常工作的管理也成为国家机关信息化的标志。同时，人们对计算机技术需求的增加，也促进了计算机新技术的发展。

近代以来，特别是在实行学科课程的条件下，教学计划主要是学科的计划，或只是学科表。随着社会经济和科学技术的新发展，教育结构不断发生变革，现代教育和教学理论主张对教学计划的结构实行改革。除了教学以外，生产劳动、科技活动、发展体力和增进健康的活动、艺术活动和社会活动等也应列入教学计划。在工具课和一般科学知识课、自然学科和社会学科、普通教育课和职业教育课之间应相互渗透。在新知识不断涌现的形势下，只有必修课而无选修课的单一结构不能适应学生个性才能的发展和知识多样性的要求，适当增设选修课,已成为发展的趋势。一些选修课在一定条件下,可能成为必修课。

根据一定的教育目的和培养目标制定的教学和教育工作的指导文件。教学计划决定着教学内容总的方向和总的结构，并对有关学校的教学、教育活动，生产劳动和课外活动校外活动等各方面作出全面安排，具体规定一定学校的学科设置、各门学科的教学顺序、教学时数以及各种活动等。教学计划、教学大纲和教科书互相联系，共同反映教学内容。

然而学校的课程繁多，每所学校的课程也大不相同。给学生们安排课程成了老师的一项繁重而又难免的工作。虽然有软件可以实现课程的安排，但是大都需要购买，而且过程繁琐不好掌握。其实这项工作并没有想象中的那么难做，我们完全可以运用我们所学的知识让计算机来帮我们完成这项工作，体验计算机技术给我带来的高效、和快速。课程安排普遍的要求是：根据课程之间的依赖关系，在满足各学期课程数大致相同的条件下制定出课程安排计划。

针对各大院校课程繁多课程安排难的问题，并且避免以往程序的繁琐和不易上手，我们从实际出发，充分运用我们所学的知识，根据不同学校的情况设计出《教学计划安排检验程序》。安排教学计划系统可以根据用户输入的课程数、课程编号、课程间的先后关系数目以及课程间两两间的先后关系，给出学生每学期应学的课程。该教学计划安排程序具有操作简单，功能完善，实用性强等特点，能很好的完成教学计划的拓扑排序即课程安排的先后顺序。

课程安排的先后顺序，与拓扑结构相同。可利用拓扑排序来实现。从而让计算机代替人工安排课程。

3

沈阳工程学院课程设计 第一章 问题分析

1.3分析

1.3.1约瑟夫生死游戏分析

为了解决约瑟夫问题，并为了解决由此而衍生的类似的游戏原理理解问题。在制作的过程中要解决问题分析，编码，制作等相关问题，本课程设计的目标是运用循环链表来解决Josephus环问题，其中运用了许多链表中的基本操作使该程序能够解决多个Josephus的简单链表，Josephus函数则是用C++程序编写的程序，实现队列的建立、插入和删除等基本功能，在程序设计成功的基础上，进一步深化理解队列的作用和实现原理。

主要分析：

1.输入的形式和输入值的范围：本程序中，输入人数上限，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。

2.输出的形式：从屏幕显示出列顺序。

3.程序功能：提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。

1.3.1安排教学计划分析

总体思想是利用拓扑排序的思想和堆栈思想编写相应函数。首先根据课程的先后关系画出AOV网，网中的结点代表课程，有向边表示各学科之间的次序关系。可以采用邻接表作AOV网的存储结构，且在头结点中增加一个存放顶点入度的数组。

为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。然后根据拓扑排序依次输出应学的课程。编写的程序根据用户输入的课程数，课程编号，课程间的先后关系数目以及课程间两两间的先后关系，实现输出课程安排的先后顺序的功能。

拓扑排序时有向图的一种重要运算。在课表排序中，每门课都有多种关系： （一）先后关系，即必须在一门课学完后，才能开始学习另一门课；

（二）在一类课之间没有次序要求，即两门课可以同时学习，互不影响。将AOV 网络中的各个顶点排列成一个线性有序序列，使得所有的要求的前趋、后趋关系都能得到满足。在AOV网络进行拓扑排序的方法：

1．选择一个没有前趋的顶点，并把它输出；

2．从网络中删去该顶点和从该顶点出发的所有有向边； 3．重复执行上述两步，直到网中所有的顶点都被输出。

4

沈阳工程学院课程设计 第二章 运行原理和环境

第二章 运行原理和环境

2.1数据结构理论

2.1.1线性表

线性表：是由类型相同的数据元素组成的有限序列，不同线性表的数据元素类型可以不同，可以是最简单的数值和字符，也可以是比较复杂的信息。线性表的存储结构共分为两种：顺序存储结构和链式存储结构。

约瑟夫生死游戏采用的数据结构是线性表的链式存储结构中的单向循环链表。 顺序存储结构：逻辑上相邻的数据元素在物理位置上也是相邻的，采用数组实现。 文本文件单词的检索和计数采用的数据结构是线性表的链式存储结构。

链式存储结构：不要求逻辑上相邻的数据元素在物理位置上也是相邻的，插入删除操作时不需要移动元素。

链式存储结构中单链表是一种最简单的线性表的链式存储结构，单链表也称为线性链表，用它来存储线性表时，每个数据元素用一个结点（node）来存储，一个结点由两个成分域组成，一个是存放数据元素的data，称为数据域，另一个是存储指向此链表下一个结点的指针next，称为指针域。

循环链表：是一种线性表链式存储结构，它的结点结构与单链表相同，与单链表不同的是在循环链表中表尾结点的next指针域不空（NULL），而是指向头结点，如图2.1所示。

图2.1 循环链表

2.1.2邻接表和图

邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。

在有向图中，描述每个点向别的节点连的边（点a->点b这种情况）。

5

沈阳工程学院课程设计 第二章 运行原理和环境

在无向图中，描述每个点所有的边(点a-点b这种情况)

与邻接表相对应的存图方式叫做边集表，这种方法用一个容器存储所有的边。 注意：n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。(换句话说，每条边（i,j）在邻接表 中出现两次：一次在关于i的邻接表中，另一次在关于j的邻接表中)

有向图：

对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。

【例】有向图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以及以上编译的条件，不然没有测试的效率无任何意义。

6

沈阳工程学院课程设计 第二章 运行原理和环境

2.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所示。

7

沈阳工程学院课程设计 第二章 运行原理和环境

图2.3 VS2010运行环境

图2.4运行界面

8

沈阳工程学院课程设计 第二章 运行原理和环境

9

沈阳工程学院课程设计 第三章 系统分析与设计

第三章 系统分析与设计

3.1约瑟夫生死游戏

3.1.1系统的功能

约瑟夫环问题描述的是：设编号为1，2，?，n的n（n>0）个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。所需要的数据结构为线性表的链式储存结构，根据思想可以确定约瑟夫生死游戏的功能主要包括，初始化约瑟夫生死环、设定生死规则、输出出队顺序和游戏界面设置。系统功能模块图如图3.1所示。

图3.1 系统功能模块图

如图3.1所示，本系统分为4个功能模块分别为：初始化约瑟夫生死环、设定生死规则、输出生者和死者和游戏界面设置。

1.初始化约瑟夫生死环：使整个游戏在链表中运行，使得结点在删除时不需要移动大量的结点；

2.设定生死规则：输入要删除的位置序号，进而使链表具化体，从而可以构建一个具体的链表；

3.输出出队顺序：输出被投入海中人的位置序号、每个人的密码及最后一个出队的人

9

沈阳工程学院课程设计 第三章 系统分析与设计

和其密码值；

4.游戏界面设置：游戏开始时提示“按任意键继续??”，运行最后显示菜单界面，可以继续进行游戏或者直接退出。

3.1.2模块分析及流程图

约瑟夫生死游戏分为4个模块分别为：初始化约瑟夫生死环、设定生死规则、输出生者和死者和游戏界面设置。主要模块的设计如下：

1.初始化约瑟夫生死环

初始化约瑟夫生死环主要实现使整个游戏在链表中运行，使得结点在删除时不需要移动大量的结点，用p，q两个指针的移动构建一个单循环链表用next作为存放下一个接点的地址空间并将头结点放入最后一个地址空间使之能形成以循环单链表结构，使整个游戏在链表中运行，使得结点在删除时不需要移动大量的结点。初始化约瑟夫生死环模块的流程图如图3.2所示。

图3.2 初始化约瑟夫生死环流程图

2.设定生死规则

输入要删除的位置序号，进而使链具化体，从而可以构建一个具体的链表；接收头指针L对其进行循环遍历找到输入的第n个对其剔除结点后的链表进行重新连接又有构成了一个新的链表，使得循环继续进行。设定生死规则的流程图如图3.3所示。

10

沈阳工程学院课程设计 第三章 系统分析与设计

图3.3 设定生死规则流程图

3.输出出队顺序

输出第一个被投入海中人的位置序号和其密码值；接收指针L并将其赋值给头指针输出数据域data然后指向下一个地址循环遍历链表输出所有被投入海中人的位置序号和密码值及最后一个出队的人和其密码值。设计流程图如图3.4所示。

图3.4 输出出队顺序流程图

11

沈阳工程学院课程设计 第三章 系统分析与设计

3.2安排教学计划

3.2.1系统的功能

总体思想是利用拓扑排序的思想和堆栈思想编写相应函数。

首先根据课程的先后关系画出AOV网，网中的结点代表课程，有向边表示各学科之间的次序关系。可以采用邻接表作AOV网的存储结构，且在头结点中增加一个存放顶点入度的数组。

为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。然后根据拓扑排序依次输出应学的课程。

编写的程序根据用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，实现输出每学期应学的课程的功能。

安排教学计划 菜 单 及 默 认 课 程 名 栈 的 一 系 列 操 作 建 临 接 表 求 图 的 入 度 拓 扑 排 序 输 出 排 序

其功能模块图如图3.5所示。

如图3.5所示，本系统分为6个功能模块分别为：菜单及默认课程、栈的一系列操作、建立邻接表、求图的入度、拓扑排序、输出排序。

1. 菜单及默认课程：使整个系统在运行前，让用户了解系统默认的值及初始条件； 2. 栈的一系列操作：用于求图的入度、拓扑排序、输出排序等模块运行使用； 3. 建立邻接表：用于存储图即课程编号，课程的先后顺序?； 4. 求图的入度：用于拓扑排序和输出排序。

5. 拓扑排序：将输入的课程编号和课程的先后顺序进行拓扑排序。 6. 输出排序：输出运行结果。

12

沈阳工程学院课程设计 第三章 系统分析与设计

3.2.2 系统分析模块分析及流程图

总体思想是利用拓扑排序的思想和堆栈思想编写相应函数。

首先根据课程的先后关系画出AOV网，网中的结点代表课程，有向边表示各学科之间的次序关系。可以采用邻接表作AOV网的存储结构，且在头结点中增加一个存放顶点入度的数组。

为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。然后根据拓扑排序依次输出应学的课程。

编写的程序根据用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，实现输出每学期应学的课程的功能。

1.系统总流程图，如图3.6所示。

2.拓扑排序算法思想和流程图

系统总流程图，图3.6 流程图如图3-5所示。

13

沈阳工程学院课程设计 第四章 系统功能实现

第四章 系统功能实现

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;//password

struct LNode *next;//指向下一结点的指针 }LNode;

4.1.2主函数和菜单函数

本功能模块主要是通过源程序的编写实现的主函数菜单界面。对使用者在使用该软件时进行提示如何进行操作。在本软件中是利用人机交互的方式达到实现软件中各个功能的

14

沈阳工程学院课程设计 第四章 系统功能实现

目的的。但由于编写人员能力有限及编写需求的双重条件，在本人机交互界面中只有输入命令提示符这一种命令交互方式并没有如：快捷键、点击??的交互方式。主要程序代码如下：

/*主函数模块*/ void main(){

{

int n,m,x;

LNode *ppHead=NULL; menu(); for(;;)

printf(\请选择要执行的操作：\

scanf(\ system(\ switch(x){ case 1:

printf(\\

printf(\约瑟夫环:\\n\

printf(\编号为1,2,3,4?,n的n个人按顺时针方向围坐一圈,每人持有一个密\\n\

printf(\码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\\n\

printf(\按顺时针方向自1开始顺序报数,报到m时停止.报m的人出列，将他的密码\\n\

printf(\作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,\\n\

printf(\直到所有人全部出列为止.编程打印出列顺序.\\n\

printf(\\

main(); break;

case 2:

printf(\请输入总人数n：\

scanf(\

printf(\请输入开始上限数m：\ scanf(\

createList(&ppHead,n); printf(\

printf(\出队顺序：\\n\ jose(ppHead,m);

15

沈阳工程学院课程设计 第四章 系统功能实现

printf(\约瑟夫环游戏结束!\\n\ main(); break; case 0:

exit(0);

default:

system(\

printf(\您选择的操作有误，请重新选择...\\n\\n\\n\ main(); } }

}

/*菜单函数模块*/ void menu() {

printf(\约瑟夫环*****************************\\n\ printf(\ printf(\ [1]约瑟夫环问题的阐述 \\n\

printf(\ [2]按要求求解约瑟夫环 \\n\

printf(\ [0]退出 \\n\

printf(\欢迎使用****************************\\n\}

运行上述程序，系统的主函数界面如图4.1所示。

图4.1 主函数和菜单函数开始

16

沈阳工程学院课程设计 第四章 系统功能实现

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; }

/**创建循环链表**/

void createList(LNode **ppHead,int n) {

int i,m_pwd;

LNode *p,*cur;//cur:浮标指针 }

for(i=1;i<=n;i++) {

printf(\输入第%d个人的密码：\ scanf(\输入持有密码

p=createNode(i,m_pwd);//调用构造结点函数 if(*ppHead==NULL)//如果头结点为空 {

*ppHead=cur=p;//生成头结点，让cur指向他 cur->next=*ppHead;//cur的指针域指向自身 }

else//如果不为空，则插入结点 {

p->next = cur->next; cur->next = p;

cur= p;//cur指向新插入结点 } }

printf(\完成创建！\\n\提示链表创建完成

17

沈阳工程学院课程设计 第四章 系统功能实现

功能实现图如图4.2所示。

图4.2 初始化约瑟夫生死环

4.1.4输出出队顺序函数

定义指针p指向要删除节点的前一个节点，ppHead指向要删除的节点，使p=ppHead，ppHead再指向要删除节点的下一个节点，使p和ppHead链接，输出p指向节点的编号和密码值，释放ppHead，如此循环，直至把所有节点都打印和删除为止！主要代码如下：

//出队函数

void jose(LNode *ppHead,int m_pwd) {

int i,j;

LNode *p,*p_del;//定义指针变量 for(i=1;p!=ppHead;i++){ for(j=1;j

p=ppHead;//p赋值为ppHead，p指向要删除结点的前一个结点 ppHead=ppHead->next;//ppHead指向下一个元素 }

p->next = ppHead->next;//p结点与头结点链接 i=ppHead->pwd;//i赋值为ppHead->pwd

j=ppHead->num;//j赋值为ppHead->num，j为要删除的密码值 printf(\第%d个人出列，密码：%d\\n\

m_pwd=ppHead->pwd;//m_pwd赋值为ppHead->pwd free(ppHead);//释放头结点

ppHead=p->next;//ppHead重新赋值给p->next,即释放前的ppHead->pwd指针 }

i=ppHead->pwd;//i赋值为ppHead->pwd j=ppHead->num;//j赋值为ppHead->num

printf(\最后一个出列是%d号，密码是:%d\\n\free(ppHead);//释放头结点

18

沈阳工程学院课程设计 第四章 系统功能实现

}

运行结果界面如图4.3所示。

图4.3 运行结果

4.2 安排教学计划

4.2.1头文件、宏、数据结构体定义

一般而言，每个C++/C程序通常由头文件(header files)和定义文件(definition files)组成。头文件作为一种包含功能函数、数据接口声明的载体文件，用于保存程序的声明(declaration)，而定义文件用于保存程序的实现 (implementation)。文本文件单词的检索和计数中包含的头文件有：#include 定义输入/输出函数、#include 定义杂项函数及内存分配函数#include 和#include定义字符串函数，通过宏定义把空指针、错误返回值和正确返回值进行定义数值，结构体定义相关类型的链表空间有整型数据空间，单链表存储下一个指针空间。

//头文件定义

#include //输入输出函数头文件

#include //字符串转短整形函数的头文件

#include//内存分配函数头文件 #include //字符串函数头文件 //宏定义

#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0

#define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量

19

沈阳工程学院课程设计 第四章 系统功能实现

#define MAX_VERTEX_NUM 20 //数据结构类型定义 int NUM,C,N;//定义全局变量

typedef int Status;

typedef int SElemType; /定义类型名 typedef struct //栈的结构体

{

SElemType *base; //在栈构造之前和销毁之后,base的值为NULL SElemType *top; //栈顶指针

int stacksize; //当前已分配的存储空间,以元素为单位 }SqStack;

typedef struct ArcNode//弧的结构体

{

int adjvex;//该弧所指向的顶点的位置

struct ArcNode *nextarc;//指向第一条依附该顶点的弧的指针 }ArcNode;

typedef struct VNode//课程的结构体 {

char data[10];//课程名编号存储 char string[20];//课程名存储 ArcNode *firstarc;

}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct//图的结构体 {

AdjList vertices;

int vexnum,arcnum;//图的当前顶点数和弧数 }ALGraph;

int indegree[20]={0};//存储图的入度的全局变量数组

4.2.2初始化栈、压栈、弹栈、判断栈空函数

本功能模块主要是通过源程序的编写实现的。对使用者在使用该软件时进行提示如下。本程序构造一个空栈S并予S存储空间函数，此函数可循环利用。具体代码如下：

//构造一个空栈S

Status InitStack(SqStack &S) {

S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));

20

沈阳工程学院课程设计 第四章 系统功能实现

if(!S.base) =

return ERROR;//内存分配失败 S.top=S.base;

S.stacksize=STACK_INIT_SIZE; return OK;

}//InitStack

本功能模块主要是通过源程序的编写实现的。对使用者在使用该软件时进行提示如下。本程序对栈S插入元素e为新的栈顶元素的压栈函数，此函数可循环利用。具体代码如下：

//插入元素e为新的栈顶元素

Status Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) //栈满,追加存储空间 {

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!S.base)

return ERROR;//存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }//Push

本功能模块主要是通过源程序的编写实现的。对使用者在使用该软件时进行提示如下。本程序中若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR 。仍然是很简单的循环语句实现。具体代码如下：

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR Status Pop(SqStack &S,SElemType &e) {

if(S.top==S.base) return ERROR; e=*--S.top; return OK; }//Pop

本功能模块主要是通过源程序的编写实现的。对使用者在使用该软件时进行提示如下。本程序判断栈是否为空,为空返回TRUE否则返回，FALSE。仍然是很简单的循环语句实现。具体代码如下：

//判断栈是否为空,为空返回TRUE否则返回，FALSE Status StackEmpty(SqStack S)

21

沈阳工程学院课程设计 第四章 系统功能实现

{

if(S.top==S.base) return TRUE;

else return FALSE; }

4.2.3邻接表建立函数

本功能模块主要是通过源程序的编写实现的。对使用者在使用该软件时进行提示如下。本程序为创建邻接表，首先输入课程数目及课程间的先后关系数即为顶点数和弧数（教学计划应为有向图）其后输入课程编号，输入课程间两两间的先后关系即为有向边，以此创建邻接表。具体代码如下：

//建立邻接表

Status CreateDG(ALGraph &G) {

int i,v,w,vex;

printf(\请输入课程数目(课程数（顶点）必须小于等于12)：\ scanf(\ if(vex>=13)

{

printf(\请重新输入课程数目(课程数（顶点)必须小于等于12)：\ scanf(\ }

G.vexnum=vex;

printf(\请输入课程间的先后关系数（弧数）：\ scanf(\

printf(\课程名的长度小于等于10个字符且必须为Cn(n=1，2，...,12(最佳取得值）)\\n\

printf(\请输入课程的代表值:\\n\

for(i=0;i

scanf(\ G.vertices[i].firstarc = NULL; }//输入顶点信息

printf(\请输入课程间两两间的先后关系(数字编号)：\ for(i=0;i

scanf(\形式2

22

沈阳工程学院课程设计 第四章 系统功能实现

ArcNode *p= new ArcNode;//建立结点 if(!p) return ERROR;

p->adjvex=w-1;

p->nextarc=G.vertices[v-1].firstarc;//顶点v的链表 G.vertices[v-1].firstarc=p;//添加到最左边

}

return OK; }

当输入课程数目大于12时，系统显示错误并要求重新输入课程数目；输入课程间的先后关系数即弧的数目；如图4.4所示。

图4.4输入课程数目和输入课程间的先后关系数目

输入课程的代表值即课程编号如图4.5所示。

图4.5输入课程的代表值

输入课程的代表值即课程间两两的先后关系即输入弧，如图4.6所示。

图4.6输入课程的代表值即课程间两两的先后关系

4.2.4求图的入度函数

本功能模块主要是通过源程序的编写实现的。对使用者在使用该软件时进行提示如下。本程序为求图的入度函数，初始化图后需要求出图中各个地点的入度数，并将结果保存到整型数组indegree中，为拓扑排序做准备。具体代码如下：

23

沈阳工程学院课程设计 第四章 系统功能实现

//求图的入度

void FindInDegree(ALGraph G)

{

ArcNode* p;

for(int i=0;i

{

p=G.vertices[i].firstarc;//取出第i个顶点，将由该顶点所出发的弧所对应的弧尾结点的入度加1

while(p) {

for(int j=0;j

if(p->adjvex==j) indegree[j]++; p=p->nextarc; } } }

4.2.5拓扑排序函数

本功能模块主要是通过源程序的编写实现的。对使用者在使用该软件时进行提示如下。本程序为拓扑排序过程，首先将入度为i（初始i=0）的顶点入栈S1并对输出顶点计数，然后在栈不为空的情况下输出入度为i的顶点对应的编号及课程名，再把顶点压入栈S2 ；计数；对i号顶点的每个邻接点的入度减1，若入度减为0,则压入栈S1...重复循环；判断若有向图有回路则返回ERROR，反知无回路则返回OK。具体代码如下：

//拓扑排序

Status TopologicalSort(ALGraph G) {

//有向图G采用邻接表存储结构

SqStack S1,S2; ArcNode* p; int i,count,k; FindInDegree(G); InitStack(S1); InitStack(S2);

for(i=0;i

Push(S1,i); //把入度为i的压入栈S1

24

沈阳工程学院课程设计 第四章 系统功能实现

count=0; //对输出顶点计数 while(!StackEmpty(S1)) {

while(!StackEmpty(S1)) {

Pop(S1,i);

printf(\

printf(\输出i号顶点 Push(S2,i); //把i号顶点压入栈S2 }

count++; //计数

while(!StackEmpty(S2)) {

Pop(S2,i);

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex; //对i号顶点的每个邻接点的入度减1 if(!(--indegree[k])) //若入度减为0,则入栈 Push(S1,k); } }

}

if(count

4.2.6主函数和菜单函数

主函数是程序的入口，采用模块化设计。本功能模块主要是通过源程序的编写实现的主函数菜单界面。先对string（字符串赋值）赋予课程名。然后调用CreateDG函数开始以建立邻接表建立。再调用TopologicalSort函数，经拓扑排序来实现教学计划安排的算法。对使用者在使用该软件时进行提示如何进行操作。对使用者在使用该软件时进行提示如何进行操作。主要程序代码如下：

//主函数 int main() {

ALGraph G;

25

沈阳工程学院课程设计 第四章 系统功能实现

printf(\┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\\n\ printf(\┃ ★ ☆欢迎使用教学计划安排系统☆★ ┃\\n\ printf(\┣━━━━━━┳━━━━━━━━━┳━━━━━━━━━━┫\\n\ printf(\┃【课程编号】┃ 【课程名】 ┃ 【先决条件】 ┃\\n\ printf(\┣━━━━━━╋━━━━━━━━━╋━━━━━━━━━━┫\\n\ printf(\┃ C1 ┃ 程序设计基础 ┃ 无 ┃\\n\ printf(\┃ C2 ┃ 离散数学 ┃ C1 ┃\\n\ printf(\┃ C3 ┃ 数据结构 ┃ C1, C2 ┃\\n\ printf(\┃ C4 ┃ 汇编语言 ┃ C1 ┃\\n\ printf(\┃ C5 ┃ 语言的设计和分析 ┃ C3, C4 ┃\\n\ printf(\┃ C6 ┃ 计算机原理 ┃ C11 ┃\\n\ printf(\┃ C7 ┃ 编译原理 ┃ C5, C3 ┃\\n\ printf(\┃ C8 ┃ 操作系统 ┃ C3, C6 ┃\\n\ printf(\┃ C9 ┃ 高等数学 ┃ 无 ┃\\n\ printf(\┃ C10 ┃ 线性代数 ┃ C9 ┃\\n\ printf(\┃ C11 ┃ 普通物理 ┃ C9 ┃\\n\ printf(\┃ C12 ┃ 数值分析 ┃ C9, C10, C11 ┃\\n\ printf(\┗━━━━━━┻━━━━━━━━━┻━━━━━━━━━━┛\\n\ printf(\望使用上述课程编号及课程名！\\n\ strcpy(G.vertices[0].string, \程序设计基础\ strcpy(G.vertices[1].string, \离散数学\

strcpy(G.vertices[2].string, \数据结构\ strcpy(G.vertices[3].string, \汇编语言\

strcpy(G.vertices[4].string, \语言的设计和分析\ strcpy(G.vertices[5].string, \计算机原理\ strcpy(G.vertices[6].string, \编译原理\ strcpy(G.vertices[7].string, \操作系统\ strcpy(G.vertices[8].string, \高等数学\ strcpy(G.vertices[9].string, \线性代数\ strcpy(G.vertices[10].string, \普通物理\ strcpy(G.vertices[11].string, \数值分析\ printf(\初始化完成！\ CreateDG(G);

TopologicalSort(G); system(\ return 0; }

26

沈阳工程学院课程设计 第四章 系统功能实现

功能实现图及主菜单运行界面如图4.7所示。

图4.7 主菜单运行界面

按给定的课程编号，课程名，先决条件输入如图4.8所示。

图4.8输入所有条件

27

沈阳工程学院课程设计 第四章 系统功能实现

运行结果如图4.9。

图4.9运行结果

总的系统流程如图4.10所示

图4.10总的系统流程

28

沈阳工程学院课程设计 结 论

结论

经过两个星期的学习和努力我们小组终于完成了<<约瑟夫环游戏>>和<<教学计划安排检验程序>>的课程设计，在这里首先感谢老师对我们小组的帮助，其次感谢我的组员都能尽自己所能，完成自己各自任务并互相帮助。

从确定题目到算法基本完成，从程序的逐步完善再到设计报告的结束，每一步都是对我们的一种新的挑战。这次训练，让我意识到自己掌握的知识是远远不够的。在这次训练中，有成功有失败，要完全掌握编程技术以后还得多加练习。

通过查看相关的资料和书籍，通过仔细的思考，使我们的设计一步步完善起来。我们也切实认识到做设计必然会遇到许许多多新的难题，通过这次课程设计我们小组两个人都受益匪浅。我们形成了一种信念：做设计只要认认真真的用心去做，难点都会一一解决。

通过这次课程设计，我们收获的不仅仅是技术，本次程序设计使我不仅深化理解了教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，并且在总体分析、总体结构设计、算法设计、课程设计、上机操作及程序调试等基本技能方面受到了综合训练，使我在编读程序时更容易。我们将会在以后的学习中，不断提高自己技术水平，不断完善自己的知识体系，为成为优秀的编程人才努力。

这次课程设计中，我们发现书本上的知识是一个基础，但是我们基础都没掌握，更别说写出一个完整的程序了。在写程序的时候，也发现自己掌握的知识确实太少了，尤其是对于一些基础知识点的认识比较模糊，没有真正将其融会贯通，所以自己编写程序时会感到万分痛苦，每每涉及一个生僻的知识点就得去看看书，导致编写速度比较慢，而且易出错。在饭后闲暇时间我们也总结了一下，以前上课时自己虽然也认真的听课了，但是独立写程序时却写不出来，这主要归结于自己的练习太少了，而且遇到不明白的地方也总是半懂不懂的，很少去深入研究它。所以必须以严谨的态度刻苦的努力去编程。其实，看懂一个程序其实不难，难的是对于一个程序的思想的体会，我们要掌握一个算法，不仅仅限于读懂，更主要的是要理解其设计算法的思路，学习其解决问题的方法。

所以在以后的学习当中，我们要勤于实践，多多动手练习。不断的编程不断的修改才是真正的学习！当我们全身心的投入其中时，它将会是一件很有乐趣的事情。

最后，再次感谢老师认真而辛勤的指导，也感激其他同学们对我们组的建议和帮助。

29

沈阳工程学院课程设计 致 谢

致谢

在这次课程设计的过程中，我们得到了许多人的帮助。

首先，我们要感谢我们的老师在课程设计上给予我们的指导、提供给我们的支持和帮助，这是我们能顺利完成本次课程设计的主要原因。本次课程设计的选题、研究及论文的撰写均是在我们的指导教师姜柳老师和吕海华老师的悉心指导下进行的。设计中的每一个环节无不凝聚着两位老师的心血。老师在数据结构课程设计有很多的实践经验，在我面对问题时对我的悉心指导及其严谨的工作态度锐意创新的精神，使我们受益匪浅，在此特别向老师表示深深的感谢和由衷的敬意。

其次，我们要感谢帮助过我们的同学，他们也为我解决了不少我不太明白的设计商的难题。在我们课程设计完善过程中，我们也遇到了这样或那样的技术问题，但通过我们自己的不懈努力，查阅大量的资料，以及其他同学积极善意的提醒，给了我们带来了许多有益的启示，促动和帮助，使我们能够顺利的完成课题。

同时，也感谢学校给了我们这次难得的课程设计机会，课程设计的过程让我们看到了自己理论知识上的不足，已掌握的知识也在这次的课程设计中有了质的飞跃，知识能够应用了才是真正掌握了，也希望学校多给我们一些这样的机会。

最后，再次感谢我们的老师，如果没有老师的耐心指导，就不会有我们的成果。本次课程设计中，老师对我们的指导，我们将永远感激在心，我们相信这是我们人生中宝贵的财富。老师，谢谢您！祝老师在今后的日子里，工作顺利，万事如意。

30

沈阳工程学院课程设计 参考文献

参考文献

[1]严蔚敏，吴伟民，数据结构（C语言版）， 北京：清华大学出版社.2007 [2]谭浩强，C程序设计，北京：清华大学出版社，1999.12

[3]滕国文，数据结构课程设计，北京：清华大学出版社，2010.09

[4]苏仕华 等编著， 数据结构课程设计，北京：机械工业出版社，2005.05

[5]李春葆，数据结构（C语言版）习题与解析，北京：清华大学出版社，2002..04 [6]佟伟光，杨政，实用数据结构（第二版），科学出版社，2008.5 [7]严蔚敏，数据结构（C语言版），清华大学出版社，2006.3 [8]李保春，数据结构习题与解析，清华大学出版， 2001.6 [9]徐孝凯，数据结构课程实验，清华大学出版，2002.7 [10]张乃笑，数据结构与算法，电子工业出版社，2004.10

[11]王卫东，数据结构辅导课，西安电子科技大学出版社，2001.6 [12]陈文博，朱青，数据结构与算法，机械工业出版社，1996.9 [13]赵文静，数据结构辅导.西安交通大学出版社，1999.9

31

本文来源：https://www.bwwdw.com/article/btnw.html