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

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

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和 …… 此处隐藏：2044字，全部文档内容请下载后查看。喜欢就下载吧 ……