return SCListInsertEnd(J,x); } 时间复杂度为 O（1）。 d) 构造约瑟夫环 SCListInitiate(&JR); for(i=0;i<n;i++)//构造约瑟夫环
JesephRingInsertEnd (&JR,test[i]); 时间复杂度 O（n）。 e) JesephRing(J,m)基本算法 1、根据初始报数上限 m 值，寻找第 m 个结点（应该找到第 m-1 个结点的地址才 便于删除，因此为便于删除，定义 curr 指针找第 m 个结点，pre 指针始终指向 curr 结点的直接前驱结点） 。 2、输出第 m 结点的 number 值； 3、把该结点的 cipher 值赋给 m，作为下一次循环的报数上限 m； 4、删除第 m 个结点； 如此循环 n 次或直至表为空时结束。（实际只需循环 n-1 次，最后只剩一个结点时， 直接输出即可）。
q->data=x; q->next=L->rear->next;
/*插入*/
L->rear->next=q; L->rear=q;
//尾指针处理
return 1;
} 时间复杂度为 O（1）。
e) int SCListDeleteAfter(SCListWithRear *L,SLNode *p) /*删除并释放带尾指针的循环单链表 L 中 p 结点的下一个结点*/
数据必须为正整数，请修改 JRInput.txt 中数据并保存后，重新运行 JesephRing.exe！”。 4． 输出结果表示依次出列人的序号。输出结果后程序结束，敲回车键关闭输出窗口。
六、 测试数据
1． 测试实例 1 运行 JesephRing.exe 结果如下：
结论：测试结果正确。 2． 测试实例 2
1、 问题的抽象数据类型分析
约瑟夫环的数据元素是由编号和密码值组成的二元组。约瑟夫环的逻辑结构是线性表。 求解约瑟夫环问题可以分为两个步骤：
1. 构造约瑟夫环； 2. 约瑟夫环循环报数、出列。 在第一个步骤，由于构造约瑟夫环是通过在表尾循环插入元素结点，因此约瑟夫环的逻 辑操作有： 1. 初始化约瑟夫环； 2. 在约瑟夫环表尾插入； 3. 循环报数出列。 通过以上分析，确定约瑟夫环抽象数据类型定义如下： ADT JesephRing 数据元素： ai=(ni，mi)，i=0,1,…,n-1 (n≥0)，ni，mi 代表第 i 个人的编号和持有的密码 ，其 中 ni 不能省略。 结构：线性结构，对数据元素 ai (0≤i≤n-2)存在次序关系<ai， ai+1>, a0 的直驱是 an-1 ，an-1 的 直继是 a0。 逻辑操作：设 J 为 JesephRing 型 JesephRingInitiate(J); //构造一个空的约瑟夫环 J。 JesephRingInsertEnd(J, x); //在约瑟夫环 J 尾部插入新元素 x ，成功返回 1，失败返回 0。 JesephRing(J,m); /*给定初始报数上限 m，从 1 开始循环报数、删除、输出直至 J 为空， 得到出列序列。*/
n
∑ 时间复杂度为 O（ mi ）。 i=0
4、 函数的调用关系图反映程序层次结构
main()
JesephRing类型
1、从文件JRInput.txt读入数据。 2、检查各数据的合法性。 3、构造约瑟夫环。
JesephRingInitiate(J); JesephRingInsertEnd(J, x); JesephRing(J,m);
n
∑ 时间复杂度为 O（ mi ），其中 n 为人数，m i 是第 i 个人的密码值（ 0 ≤ i ≤ n ）。 i=0
3、 主函数基本算法 1、 从文件 JRInput.txt 文件读入数据到 n，m 以及动态结构体一维数组 test 中。 2、 检查 n，m 以及 test 中各元素的合法性，如果非法则输出提示并退出。 3、 循环调用 JesephRingInsertEnd(J,x)函数构造约瑟夫环。 4、 调用 JesephRing(J,m)函数约瑟夫环循环出列和输出。
运行 JesephRing.exe 结果如下：
结论：测试结果正确。 3． 测试实例 3
运行 JesephRing.exe 结果如下：
结论：测试结果正确。
七、 心得体会
数据结构 上机实习报告
实验题目： 约瑟夫环问题求解 班级： 姓名： 学号： 完成日期：
一、 需求分析
1、 问题描述
已知 n 个人（编号分别为 1，2，...，n）按顺时针方向围坐一圈，每人持有一个正整数 密码。 开始时任选一个报数上限值 m，从编号为 1 的人按顺时针方向自 1 开始报数，报到 m 时停止报数，报 m 的那个人出列；将他的密码作为新的 m 值，从他在顺时针方向的下一 个人开始重新从 1 报数，数到 m 的那个人又出列；依此规律重复下去，直到所有人全部出 列。输入 n，m 两个正整数以及 n 个正整数为密码，设计程序来求 出列的编号序列。
{ SLNode *s;
s=p->next; p->next=p->next->next; //删除 p 结点的下一个结点
if(s->next==L->head) L->rear=p;
//尾指针处理
free(s);
return 1;
}
时间复杂度为 O（1）。 2、 约瑟夫环的实现
通过带尾指针的循环单链表数据结构实现约瑟夫环。 a) 元素类型定义
2、设计带尾指针的循环单链表 a) 结构描述
b) 逻辑操作 设带尾指针的循环单链表类型名为 SCListWithRear，L 是 SCListWithRear 型。通过
分析约瑟夫环的抽象数据类型，进一步确定带尾指针的循环单链表的逻辑操作如下所示： 1. SCListInitiate(L); //初始化 2. SCListNotEmpty(L); // 判断是否是空表。如果表为空，返回 0，否则返回 1。 3. SCListInsertEnd(L, x); //在表尾插入新结点 x。插入成功返回 1，失败返回 0。 4. SCListDeleteAfter(L,p); //删除 p 结点的下一个结点，删除成功返回 1，失败返 回 0。
五、 用户手册
1． 本程序运行在 windows 系列的操作系统下，执行文件为：JesephRing.exe。 2． 用户需严格按照第 1.2 节输入文件的格式说明建立 JRInput.txt 文件，并且把 JRInput.txt
文件放在 JesephRing.exe 所在的目录下 ，即可运行 JesephRing.exe 得到输出结果。 3． 在 JRInput.txt 文件中所有的数值均必须为正整数，否则会出现提示：“JRInput.txt 文件中
2、 存储结构设计
1、存储结构的确定 数据结构的目的是有效组织和处理数据。为了有效组织和处理数据，先要分析约瑟夫环
逻辑操作的特点和指针所占空间比例，然后确定最优的存储结构。 a) 确定采用顺序存储结构还是采用链式存储结构 1. 约瑟夫环在构造时频繁执行插入操作，在出列阶段频繁执行删除操作。 2. 如果采用链表，指针存储开销和整个结点内容所占空间相比，其比例较小 综上所述，认为不采用顺序表，而采用链表。 b) 选择哪种链式存储结构？ 1. 约瑟夫环在构造时都是在尾部插入，因此增设尾指针，尾指针始终指向链表的 尾部结点。 通过增设尾指针，在表尾插入的算法时间复杂度为 O（1）。 2. a0 的直驱是 an-1 ，an-1 的直继是 a0 ，因此采用循环单链表。 综上所述，采用带尾指针的循环单链表存储结构。
4、约瑟夫环循环出列和输出。
SCListWithRear类型
SCListInitiate(L); SCListNotEmpty(L); SCListInsertEnd(L, x); SCListDeleteAfter(L,p);
四、 调试分析
1、 在 VC 里点！按钮运行程序没问题，可以看到一个窗口显示运行结果。但是运行 Debug 文件夹里的 exe 文件却不显示运行结果。 解 决 方 法 ： 在 程 序 末 尾 加 上 getchar(); 或 者 加 上 system("pause"); （ 前 面 要 加 上 头 文 件 #include<stdlib.h>）。 2、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行判断和检查，调试的时候经 常会出错，比如 n 和 mi 的输入值为字母、0、大于 32767 的数（出现溢出）。 解决方法：在从文件读入 n 和 m 的值后，增加代码检查 n 和 mi 值的合法性。如果值非法， 则在窗口中输出提示并退出程序。 3、程序写完后发现所有基本操作的结果均不能够返回到主函数。 解决方法：通过在百度中搜索和查阅 C 教材，我知道在函数调用的时候要用传址的方式传 递参数，但是具体实现起来还是耗费了不少的时间。
从第三行开始有 n 对正整数分别代表 n 个人的编码和密码。 2、 输出数据：（屏幕输出）只有一行，含 n 个整数，表示 n 个人的出列顺序。 3、 输入输出样例：
输入文件 JRInput.txt 内容如下 7 20 13 21 37 42 54 68 74
屏幕输出：6 1 4 7 2 3 5
二、 概要设计
三、 详细设计
1、 带尾指针的循环单链表实现 通过单链表数据结构实现带尾指针的循环单链表。
a) 带尾指针的循环单链表类型定义
typedef struct { SLNode * head;//头指针 SLNode * rear;//尾指针
} SCListWithRear;
b) void SCListInitiate(SCListWithRear *L) //初始化带尾指针的循环单链表
else return 1;
} 时间复杂度为 O（1）。
d) int SCListInsertEnd(SCListWithRear *L,DataType x) /*在带尾指针的循环单链表的末尾结点后插入一个新元素 x。*/
{ SLNode *q; q=(SLNode *)malloc (sizeof(SLNode)); /*新结点*/
2Biblioteka Baidu 功能需求
用户准备好输入文件，其中包含程序中需要的输入数据。程序在计算机终端上显示运算结果。 程序执行的命令包括： 1） 构造约瑟夫环； 2）判断并分析输入数据的； 3）约瑟夫算法的实现与结果输出； 4）结束。
3、 输入及输出格式
1、 输入数据：（从文件输入） 输入文件的格式如下： 文件“JRInput.txt”第一行的正整数代表人数 n， 第二行的正整数代表密码的初始值 m，
{
ListInitiate(&(L->head)); L->head->next=L->head;//循环结构 L->rear=L->head;//尾指针处理
} 时间复杂度为 O（1）。
c) int SCListNotEmpty(SCListWithRear *L)
{ if(L->head->next==L->head) return 0;
typedef struct { int number;//编号
int cipher;//密码 }DataType; b) void JesephRingInitiate(SCListWithRear *J) {/*构造一个空的约瑟夫环 J。*/
SCListInitiate(J); } 时间复杂度为 O（1）。 c) int JesephRingInsertEnd(SCListWithRear *J, DataType x) {/*在约瑟夫环 J 尾部插入新元素 x */
