《数据结构》实验报告二
题目：
学号： 日期：
班级： 姓名： 程序名：
一、上机实验的问题和要求：
约瑟夫环（《数据结构题集》P79 1.2）：约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
二、程序设计的基本思想，原理和算法描述：
此程序实现的方法是建立一个没有表头结点循环链表，然后对循环链表进行相关操作，模拟整个报数及出列过程。将每个人的信息用一个结点存储，包括三个信息，一是他的编号number,二是他持有的密码 code,三是指向下一结点的指针。其中编号是一开始按照相邻顺序编号的，密码可以设置，需要输入数值。 typedef struct LNode //定义结点
{
int number; //编号
int code; //持有密码
struct LNode *next; //指向下一结点的指针 }LNode,*LinkList;
主要过程由以下两个函数实现
void CreateList(LinkList &L,int &n); //创建循环链表 void Joseph(LinkList &L,int &n); //约瑟夫环解决方案 其中约瑟夫环解决方案比较复杂，后面具体介绍。 主函数为
void main(void) {
LinkList L; int n;
printf(\"请输入人数：\");
scanf(\"%d\设置人数 CreateList(L,n); //创建循环链表 Joseph(L,n); //约瑟夫环解决方案 }
首先要创建循环链表，在确定人数基础上编号，并输入每个人的密码，连接成一个循环链表，头指针 L 指向编号为 1 号的结点。
/**********************************************************************
1
创建循环链表
**********************************************************************/ void CreateList(LinkList &L,int &n) {
printf(\"将这%d个人编号为1-%d号。\\n请依次输入这%d个人的密码:\ LinkList q;
for(int i=1;i<=n;i++) {
LinkList p=(LinkList)malloc(sizeof(LNode)); //创建新结点用p指向它 p->number=i; //编号
scanf(\"%d\输入持有密码 p->next=NULL;
if(i==1) L=q=p; //若是第一个结点，直接用头指针指向它 else {
q->next=p; //将p指向的结点加入链表
q=q->next; //q始终保持指向最后的结点 } }
q->next=L; //q指向的最后的结点指针域指向头结点，则成为循环链表 }
约瑟夫环解决方案具体实现方案：
第一次报数 默认为 从1 号开始报数，需设置报数上限值m ,报m 的人出列，然后从出列的人后面一个人开始下一轮报数，且报数上限值m变为出列的人持有密码。 即第一次由头指针 L 开始向后数到第 m-1 个结点，删掉 第 m-1 个结点的后继结点，即第 m 个结点，（可由一个指针q 反馈回第m 个结点，以便读取被删除结点的信息），这时 第 m-1 个结点 直接指向第 m+1 个结点，同时让头指针 L 也指向第 m+1 个结点。因为下一轮报数时将从第 m+1 个结点开始，即还是 L指向的结点开始。第二轮报数首先将m值修改为刚刚被删除结点的持有密码，即m=q->code 再进行和第一轮报数相同的操作。
以后每轮报数如次反复执行，直到所有结点被删除结束。
这个过程需要一个删除函数来实现，函数功能是：删除以头指针L开始第i个结点，q返回结点指针，并改变头指针位置为下一轮报数的第一个结点。
/********************************************************************** 删除以L为头第i个结点，q返回结点指针,改变头指针位置
**********************************************************************/
void DeleteList(LinkList &L,int i,LinkList &q) {
if(i==1) DeleteList(L,i+LengthList(L),q);//i=1时需要特殊处理 else {
LinkList p=L; int j=0;
while(jnext;j++;} //p指向第i-1个结点，即被删除结点的前驱结点 q=p->next; //p指向被删除结点，返回信息 p->next=p->next->next; //删除第i个结点 L=p->next; //修改头指针 } }2
其中i=1时情况比较特殊，需要特殊处理，因为i=1时表示要删除头指针本身指向的结点，无法直接找到其前驱结点。可以改为删除第i+LengthList(L)个结点，同样也是删除头指针本身指向的结点，但需要加一个求表长的函数。
/********************************************************************** 约瑟夫环解决方案
**********************************************************************/ void Joseph(LinkList &L,int &n) {
int m;
printf(\"请输入第一个报数上限值:\");//设置第一轮报数上限值 scanf(\"%d\
printf(\"\\n出列顺序:\\n\"); LinkList q;
for(int i=1;iDeleteList(L,m,q); //删除L开始第m个结点，修改头指针位置，q返回信息 printf(\"%d.\%d号\他的密码为:%d\\n\打印相关信息 m=q->code; //修改报数上限值为被删除结点的密码值 free(q); }printf(\"%d.\%d号\他的密码为:%d\\n\ }
三、源程序及注释：
#include #includetypedef struct LNode {
int number; //编号 int code; //持有密码
struct LNode *next; //指向下一结点的指针 }LNode,*LinkList;
void CreateList(LinkList &L,int &n); //创建循环链表
void Joseph(LinkList &L,int &n); //约瑟夫环解决方案
void DeleteList(LinkList &L,int i,LinkList &q); //删除以L为头第i个结点,返回结点 //指针,改变表头位置 int LengthList(LinkList L); //求循环链表长度
/********************************************************************** 主函数
**********************************************************************/ void main(void) {
LinkList L; int n;
printf(\"请输入人数：\");
scanf(\"%d\ //设置人数
CreateList(L,n); //创建循环链表
3
Joseph(L,n); //约瑟夫环解决方案 }
/********************************************************************** 创建循环链表
**********************************************************************/ void CreateList(LinkList &L,int &n) {
printf(\"将这%d个人编号为1-%d号。\\n请依次输入这%d个人的密码:\ LinkList q; for(int i=1;i<=n;i++) {
LinkList p=(LinkList)malloc(sizeof(LNode)); //创建新结点用p指向它 p->number=i; //编号
scanf(\"%d\ //输入持有密码 p->next=NULL;
if(i==1) L=q=p; //若是第一个结点，直接用头指针指向它 else {
q->next=p; //将p指向的结点加入链表
q=q->next; //q始终保持指向最后的结点 } }
q->next=L; //q指向的最后的结点指针域指向头结点，则成为循环链表 }
/********************************************************************** 约瑟夫环解决方案
**********************************************************************/ void Joseph(LinkList &L,int &n) {
int m;
printf(\"请输入第一个报数上限值:\");//设置第一轮报数上限值 scanf(\"%d\
printf(\"\\n出列顺序:\\n\"); LinkList q;
for(int i=1;iDeleteList(L,m,q); //删除L开始第m个结点，修改头指针位置，q返回信息 printf(\"%d.\%d号\他的密码为:%d\\n\打印相关信息 m=q->code; //修改报数上限值为被删除结点的密码值 free(q); }printf(\"%d.\%d号\他的密码为:%d\\n\ }
/********************************************************************** 删除以L为头第i个结点，返回结点指针,改变表头位置
**********************************************************************/ void DeleteList(LinkList &L,int i,LinkList &q) {
if(i==1) DeleteList(L,i+LengthList(L),q);//i=1时需要特殊处理 else {
LinkList p=L; int j=0;
while(jnext;j++;} //p指向第i-1个结点，即被删除结点的前驱结点4
q=p->next; //p指向被删除结点，返回信息 p->next=p->next->next; //删除第i个结点 L=p->next; //修改头指针 } }
/********************************************************************** 求循环链表长度
**********************************************************************/ int LengthList(LinkList L) {
int i=1;
LinkList p=L->next; while(p!=L) { i++;
p=p->next; }
return i; //返回长度 }
四、运行输出结果：
五、调试和运行程序过程中产生的问题及采取的措施：
5
六、对算法的程序的讨论、分析，改进设想，其它经验教训：
1、优化到O(N)：这种思路也可以应用于n>2 的情况，无法得出常数表达式，推广后的递归算法具体的思路如下：当n个人围成一圈并以m为步长第一次报数时，第m个人出列，此时就又组成了一个新的，人数为n-1的约瑟夫环，要求n个人的约瑟夫环问题的解，就依赖于求n-1个人的约瑟夫问题的解，要求n-2个人的约瑟夫问题的解，则依赖于求n-2个人的约瑟夫换问题的解，依次类推，直至求1个人的时候，该问题的解。回到问题的原始描述中，m是一个固定的值，即步长；n为一个圈的总人数，k为这个圈第一个报数的人的编号，显然，n在每次递归过程中会减1，而k则可以由m,n来唯一确定，这样的话，当n=1的时候，我们所确定的当前的k值，就是我们所要求的解。那么，我们可列出如下的递归式：P(n, m, k)=1 (i = 1)，P(n, m, k)=(P(i - 1, m, k ) + m - 1) % n + 1; (i > 1)（此处m需先减1是为了让模n的值不为0）
2、与人数无关：如果令第一个出圈人的编号为变量k，但在循环的过程中，我们会发现它常常处在一种等差递增的状态，我来看这个式子：k = (k + m - 1) % i + 1，可以看出，当i比较大而k+m-1比较小的时候，k就处于一种等差递增的状态，这个等差递增的过程并不是必须的，可以跳过。我们设一中间变量x，列出如下等式：k + m * x – 1 = i + x，解出x，令k = k + m * x，将i + x直接赋值给 i，这样就跳过了中间共x重的循环，从而节省了等差递增的时间开销。可是其中求出来的x + i可能会超过n，这样的结果事实上已经告诉我们此时可以直接结束算法了，即：
k = k + m * (n - i) ;
i = n; 结束。另外对于m = 1的情况可以单独讨论：当k == 1时，最终结果就是n，当k != 1时，最终结果就是(k + n - 1) % n。
七、对实验方式、组织、设备、题目的意见和建议：
本次实验是更多的是在完成一个游戏，比较有趣，比起古板的编程实验有一定的趣味性，也可以激发学生编写程序的热情，对于建议就是，实验课要多安排同学做一些有趣味性的实验，这样同学也可以即达到课堂练习编写程序的能力，又可以帮助同学更好理解数据结构的作用。
6