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

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

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