1、第 1 页 设计设计 1 1 约瑟夫环问题约瑟夫环问题 一、需求分析一、需求分析 一、具体目标包括：一、具体目标包括： 1实现单循环链表的初始化 2理解约瑟夫环的定义，用循环找到每次报数人的序号 3. 从单循环链表中删除节点，并判断链表空与非空的临界条件。 二、单向循环链表的抽象数据类型定义为：二、单向循环链表的抽象数据类型定义为： ADT CircleList 数据对象：Dai | aiElemset,i=1,2,n,n0 数据关系：R=, | ai-1,aiD,i=2,n 基本操作： Link InitList（int n） 操作结果：构造一个含有 n 个元素的单向循环链表。 三、问题描述
2、三、问题描述 设编号为 1， 2， n(n0)个人按顺时针方向围坐一圈， 每人持有一个 正 整数密码。开始时任意给出一个报数上限值 m，从第一人开始顺时针方向自 1 起顺序报数，报到 m 时停止报数，报 m 的人出列，将他的密码作为新的 m 值，从他在顺指针方向上的下一个人起重新自 1 起顺序报数；下去，直到 所有人全部出列为止。要求设计一个程序模拟此过程。 第 2 页 四、基本要求四、基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的 编号。 二、概要设计二、概要设计 一、本程序分三个模块一、本程序分三个模块 1）主模块 Void main() 初始化； 接受命令； 处理
3、命令； 2）单向循环表单元模块，实现单向循环链表的抽象数据类型功能； 3）节点结构单元模块，定义单向循环链表的节点结构。 三、详细设计三、详细设计 1 1、构建一个单循环链表算法、构建一个单循环链表算法 typedef struct Node *Link,Lnode; Link InitList( int n) Link p1,p2,head; int i; for(i=1;inext=NULL; if(i=1) head=p2; else p1-next=p2; p1=p2; p1-next=head; return head; 流程图 1 P2 指向申请空间 inext=p2 P1=p2
4、P1-next=head 结束 第 4 页 2 2 主模块实现算法主模块实现算法 从头结点开始，根据报数上限找到下一个出列人的序号，并读出该人的密 码作为新的报数上限，从此节点的下一个节点开始进行新的查找。通过指 针依次删除出列人相应的节点，直到该链表中无节点，退出循环。 第 5 页 四、运行结果及分析四、运行结果及分析 测试用例 1： （一般数据） 输入报数上限 jnex t 输出 q 的 number mnext-number 删除 q 节点 初始化一个 单循环链表 第 6 页 测试用例 2： （边界数据） 只输入一个人： 测试用例 3（错误数据） 初始报数上限为负数 运行结果分析：运行结果分析： (1)对一般数据能否输出正确结果？能 第 7 页 (2)对边界数据能否给出合适的反应？能 (3)对错误数据能否做出合适的反应？ (4)算法的复杂度多少？正比于 2n 加所有人密码和 五、总结五、总结 本次实验主要考察了对单循环链表的应用。 附：主要源代码附：主要源代码 #include #include
