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

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

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