数据库约瑟夫环问题

攀枝花学院

学生课程设计（论文）

题目：约瑟夫环问题

学生姓名：学号：

所在院(系)：计算机学院

专业：计算机科学与技术

班级：

指导教师：职称：讲师

2011年6月17日

攀枝花学院本科学生课程设计任务书

注：任务书由指导教师填写。

课程设计（论文）指导教师成绩评定表

摘要

约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫问题的描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈, 每人有一个密码Ki（整数），留作其出圈后应报到Ki后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head解决问题的核心步骤：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。

关键词：约瑟夫环，双向循环链表，数据结构，删除

目录

摘要................................................................................................................................. I 目录................................................................................................................................ II 1 需求分析.. (1)

1.1功能分析 (1)

1.2设计平台 (1)

2 算法设计 (2)

2.1分析问题 (2)

2.2基本要求 (2)

2.3实现提示 (2)

2.4建立结点Node (3)

3 程序流程图 (4)

3.1主程序流程图 (4)

3.2子程序流程图 (5)

4 程序源代码 (7)

4.1约瑟夫环的操作模块 (7)

4.2单循环链表的建立 (8)

4.3主程序 (9)

4.4出列顺序和密码顺序的输出 (9)

5 程序调试与运行 (11)

2.1程序调试 (11)

5.2程序运行 (11)

6 总结 (14)

7 参考文献 (15)

8 附录 (16)

1 需求分析

1.1功能分析

本次选做的课程设计是改进约瑟夫(Joseph)环问题。约瑟夫环问题是一个古老的数学问题，本次课题要求用程序语言的方式解决数学问题。此问题仅使用单循环链表就可以解决此问题。而改进的约瑟夫问题通过运用双向循环链表，同样也能方便地解决。

在建立双向循环链表时，因为约瑟夫环的大小由输入决定。为方便操作，我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。进行操作时，用一个指针current指向当前的结点，指针front始终指向头结点。然后建立双向循环链表，因为每个人的密码是通过rand()函数随机生成的，所以指定第一个人的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后一个结点，通过一系列的循环就可以解决改进约瑟夫环问题。

1.2设计平台

Windows2000以上操作系统；debug 软件

2 算法设计

2.1分析问题

为了解决这一问题，可以先定义一个长度为n（人数）的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每次报m的人，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。这样做不仅算法较复杂，而且效率低，还要移动大量的元素。

用单循环链表来解决这一问题，实现的方法相对要简单得的多。首先定义链表结点，单循环链表的结点结构与一般单链表的结点结构完全相同，只是数据域用一个整数来表示位置；然后将它们组成一个具有n个结点的单循环链表。接下来从位置为1的结点开始数，数到第m个结点，就将此结点从循环链表中删去，然后再从删去结点的下一个结点开始数起，数到第m个结点，再将其删去，如此进行下去，直至全部删去为止。

2.2基本要求

分别选择顺序表和单向循环链表作为存储结构模拟整个过程，并依次输出出列的各人的编号

2.3实现提示

改进约瑟夫环问题的基本思路和原问题基本一致，只是一个采用单循环链表，另一个采用双向循环链表来解决问题。第一步是定义结构变量结点linklist，并在该结点下定义结点的元素域:data,password，指针域:lLink和rLink。然后建立一个由n个链结点，无表头结点的双向循环链表。并由构造函数对结点赋值，由随机函数rand()产生每个结点的password。由于每个结点的password是由随机函数产生的，也就是每个结点的password是后知的，所以在一开始人为地指定一个结点的顺序，由此结点开始报数。报password个数后，报到的那个结点被删除，它的password被记录下，由它的下一个结点开始逆方向报数………如此循环，直到循环链表里只剩下一个结点，那就是问题所求的结果。具体到问题上，还需要创建一个Joseph类，由构造函数来初始化，输入所有的人数，也就是表长，然后指定由第几个人开始报数。在Joseph类中定义一个GetWinner()函数，由它来实现获得最后的胜利者。并在该类中设置一个判断语句来确定先由顺时针报数并淘汰了一个人之后，再按逆时针顺序报数，如此交替进行

2.4建立结点Node

链表都是由一个个结点组成，由于结点的不同，组成的链表也不同。因此需要创建双向链表结点。由于每一个结点有一个密码和一个序号，所以可以将结点结构体定义为：

typedef struct Node

{

int data;

int password;

struct Node *next;

}Node, *LinkList;

;}

图2.4 结点Dnode

3 程序流程图

3.2子程序流程图

图4-2

图4-3

4 程序源代码

4.1约瑟夫环的操作模块

void GetOutputOrder(LinkList *L, int personNumber, int reportValue, int array[MAXPERSONNUMBER],int key[MAXPERSONNUMBER])

{

Node *p, *q;

int count = 1, i = 0,j=0;

p = (*L);

if(reportValue==1)

{

q=p;

while(q->next!=p)

q=q->next; //寻找p的头一个节点

array[i++] = p ->data;

reportValue=key[j++] = p->password;

q->next = p->next; //删除结点p

free(p); //释放p中所有数值

p = q->next;

count = 1; //重新记当前位置为1

personNumber--; //人数减1

}

while (personNumber!=0)

{

while (count != reportValue)

{

q = p;

p = p->next;

count++;

}

array[i++] = p ->data;

reportValue=key[j++]= p->password;

q->next = p->next;

free(p);

p = q->next;

count = 1; //重新记当前位置为1

personNumber--;

}

}

4.2单循环链表的建立

void CreatLinkList(LinkList *L) //构建单循环链表

{

(*L) = (LinkList)malloc(sizeof(Node));

if ((*L) == NULL)

{

printf("memory allocation failed, goodbye");

exit(1);

}

}

void InitLinkList(LinkList *L, int personNumber) //初始化单循环链表{

Node *p, *q; //定义结构体类型指针变量

int i ;

p = (*L); //初始化第一个结点,并赋值给p

p->data = 1;

p->password = GetPassword(); //调用GetPassword()输入密码

for (i = 2; i <= personNumber; i++)

{

q = (LinkList)malloc(sizeof(Node));

if (q == NULL)

{

printf("memory allocation failed, goodbye");

exit(1);

}

q->password = GetPassword();

q->data = i;

p->next = q;

p = q;

}

p->next = (*L);

}

4.3主程序

int main(void)

{

初始化；

do

{

接受命令；

处理命令；

}while(“命令”==“Y”)；

return 0;

}

4.4出列顺序和密码顺序的输出

void printResult(int array[],int personNumber) //输出出列顺序{

int i;

printf("\n出队的顺序为:");

for(i = 0; i < personNumber; i++)

{

printf("%-3d",array[i]);

}

}

void printkey(int key[],int personNumber) //输出密码顺序{

int i;

printf("\n出队的密码为:");

for(i = 0; i < personNumber; i++) {

printf("%-3d",key[i]);

}

printf("\n");

printf("\n");

}

5 程序调试与运行

2.1程序调试

运用debug调试程序，当程序提醒错误时，调试程序，直到没有错误。

5.2程序运行

运用debug运行程序，首先进入下面界面

图5-1

行如图示

图5-2

（2）当输入人数为6，密码各为2,3,4,5,6,7，第一个报号数是1时，程序运行如图

图5-3

序运行如下

图5-4

6 总结

为期一周的课程设计快结束了，通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。

在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现。

在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。

7 参考文献

［1］刘大有等，《数据结构》（C语言版），高等教育出版社

［2］严蔚敏等，《数据结构》（C语言版），清华大学出版社

［3］William Ford，William Topp，《Data Structure with C++》清华大学出版社［4］苏仕华等，《数据结构课程设计》，机械工业出版社