数据结构实验报告 班级： 计科0 9 0 1 班 学号： 0 9 0 8 0 3 0 1 0 6 姓名： 王玲 西安科技大学 计算机科学与技术学院 题 目： 约瑟夫环问题 一、设计内容 约瑟夫环问题的一种描述是：编号为1，2，3，…，n 的n 个人按顺时针方向围坐一圈，每人手持一个密码（正整数）。一开始任选一个整数作为报数上限值，从第一人开始顺时针自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将它的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去直到所有人全部出列为止。试设计程序实现之。 二、设计目的 1. 达到熟练掌握 C++语言的基本知识和技能； 2. 能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题。 三、系统分析与设计（确定程序功能模块） JesephRing()函数是实现问题要求的主要函数，其算法思想是：从 1 至m 对带头结点的单循环链表计数，到 m 时，输出该结点的编号值，将该结点的密码作为新的m 值，并删除该结点，然后从该结点的下一个结点起重新从 1 开始循环计数；如此下去，直到单循环链表为空时，循环过程结束。 模块划分： （1）头文件 SCLinLish.h。头文件 SCLinLish.h 中包括结点结构体定义.初始化操作.插入一个结点操作.删除一个结点操作.取一个数据元素操作及判单循环链表是否为空操作等！ （2）Main.c 文件。Main.c 文件包括以下 3 个函数。 v oid SCLLDeleteAfter(SCLNode *p)函数：其功能是删除带头结点的单循环链表中指针 p 所指结点的下一个结点。这是根据本问题中需要设计的一个函数。 Void JesephRing(SCLNode *head,int m)函数：其功能是对带头结点的单循环链表 head，以 m 为初始报数上限值，完成约瑟夫环问题程序模拟过程。 Void main(v oid )函数：主函数，其功能是给出测试数据值，建立测试数据值的带头结点单循环链表，调用 JesephRing()函数实现问题要求。 数据结构： （1）数据类型DataType 定义如下： Typedef struct { Int number; Int cipher; }DataType; (2) 带头结点单循环链表结点的结构体定义如下： typedef struct node { DataType data; struct node *next; }SCLNode; 四、源程序代码 #include #include #include #include #include"SCLinList.h" // 包含头文件 SCLinList typedef struct nod...
VIP
