基于单向循环链表的约瑟夫环设计

长春建筑学院

基于单向循环链表的约瑟夫环设计

Design of Joseph ring way circular linked list based on

学 院： 电气信息学院 班 级： 计算机1201班 学 号： 121500140 姓 名： 卢玉琨

指导老师: 常大俊

摘 要

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

【关键词】约瑟夫环；单循环链表；数据结构；删除结点

Abstract

Josephus ring problem is evolved by the question that raised by Josephus,the famous historican of ancient Rome.SO it always be called Josephus Problem.The description of improving Josephus problem is :people was numbered 1,2,3,...,n sitted as a clockwise direction around circle,each with a password of K(integer),reserved for the ring should be reported K out of the ring .The report adapted the method that changed alternately with the clockwise and anticlockwise, the initial password can be determined.Solving the number of the last person.This is the real sense of the Joseph central problems. Joseph central problems can be well-solved if it adapted the circular linked list .The configuration of the list is just pointed to the first team elements with the Omoto So pointer. P->link=head.The core process to solving the problem is:Firstly established a no-head-node circular linked list which have n chain nodes.Then determined the location of the first person.And striked out the chain nodes constantly until the chain table was empty.

[Keywords] Joseph ring; circular linked list; data structure; deleting node

目 录

前言 ......................................................................................................................................... 5 第一章 问题分析............................................................................................................ 6

1.1 设计目的 ...................................................................................................................... 2 1.2 设计内容 ...................................................................................................................... 2 1.3 设计要求 ...................................................................................................................... 2 1.4 设计思想 ........................................................................................................................

第二章 逻辑设计 ......................................................................................................... 9

2.1 循环链表抽象数据类型定义 .................................................................................... 9 2.2本程序包含的模块设计 .............................................................................................. 9

第三章 详细设计 ....................................................................................................... 11

3.1 主函数 ........................................................................................................................... 11 3.2 链表的创建 .................................................................................................................. 12 3.3 出队处理 ........................................................................................................................ 9 3.4 约瑟夫环说明模块 .................................................................................................... 10 3.5菜单模块 ....................................................................................................................... 10

第四章 程序调试与测试.......................................................................................... 16 第五章 结论 .................................................................................................................... 19 参考文献 ............................................................................................................................ 20 致谢 ....................................................................................................................................... 21 附录 ....................................................................................................................................... 21

前 言

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。该课程设计的目的是通过课程设计的综合训练，以培养分析和编程等实际动手能力，是系统掌握数据结构这门课程的主要内容。

本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接的链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活。约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。

通过该课程设计，能运用所学知识，上机解决一些实际问题，了解并初步掌握设计，实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

第一章 问题分析

1.1 设计目的

1、掌握单向循环链表的建立。 2、掌握单向循环链表的操作。

1.2 设计内容

编号是1,2,??,n的n个人按照顺时针方向围坐一圈,每个人

只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。请设计一个程序求出出列顺序。

1.3 设计要求1、利用单向循环链表存储结构模拟此过程,按照

出列的顺序输出各个人的编号。

2、测试数据：m的初值为20,n=7,7个人的密码依次为3,1,7,2,4,7,4,首先m=6,则正确的输出是什么？

3、输入数据：建立输入函数处理输入的数据,输入m的初值n,输入每个人的密码,建立单向循环链表。

4、输出形式：建立一个输出函数,将正确的出列顺序输出。

1.4 设计思想

约瑟夫环问题描述的是：设编号为1，2，?，n的n（n>0）个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起按顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他的顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。具体描述如图1和图2所示：图1 约瑟夫环问题

这这这这这这这这这这这这这这这这这这这这m这这这m=4这这这这这这这这这这这这4这4这这这这这这4这这9这这这这这这这这这这这这这1这2这3这5这6这7这8这9这0这34这这这这这这这这这这这这“1”这这这这这m这这这这m=3这这这这这这这这这3这10298这这这这这这这这这这这这这这这这这这这这m这这这m=9这这这这这这这这这这这这9这9这这这这这这9这这这这这这这这这这这这这这这这这这这这1这2这3这5这6这7这8这9这图解567t 这这这这这这这这1这这这13127324458 这这这这这这这这这这这这这这这这20这这这这这这这这20这这这6这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这4这这这这这这这这这这这这这这这这这这6这这这这这这这这这这这这这m=8这这7这这这这这这这这8这这这1这这这这64786312447127345

图2 约瑟夫环原理演示图

第二章 逻辑设计

2.1 循环链表抽象数据类型定义

typedef struct LNode//定义单循环链表中结点的结构 {

int num;//编号 int pwd;//password struct LNode *next;//指向下一结点的指针 }LNode;

2.2本程序包含的模块设计

（1）构造结点模块

LNode *createNode(int m_num,int m_pwd) {

LNode *p; p=(LNode *)malloc(sizeof(LNode));//生成一个结点 p->num=m_num;//把实参赋给相应的数据域 p->pwd=m_pwd;

p->next=NULL;//指针域为空 return p; } （2）创建链表模块

void createList(LNode *ppHead,int n) （3）出队处理模块

void jose(LNode *ppHead,int m_pwd) （4）约瑟夫环说明输出模块 void instruction() （5）菜单模块 void menu() （6）主函数模块 int main（）

函数的调用关系图如图3所示：

Casel这这这这这这这这这这这这这这这这这这这这void instruction这这这这这这这这这这main这这这这这这这void emun这这Case2这这这这这这这这这这这这这这这这这这这这这createList这LNode**这这Head这int n这这这这这这这这这这这这这这这这这这这这这LNode*ppHead这int m-pwd这Case 0这default 这这0这这这exit这0这

第三章 详细设计

3.1 主函数

Main()这这Menu这这这这这这这这1这这这这这这这这这2这这这这这这这这这这这这这这这这这这这这3这这这这这这这这这这n这这这这这这这这n这这这这这这这这这这这这这这这这这这这这这这这这这这这cresteLise(&ppHead,n) jose(ppHead,m);这这这这这这这这这这这

图4 主函数数据流程图

根据图4，主函数程序如下： int main() {

int n,m,x;

LNode *ppHead=NULL; menu(); for(;;) {

printf(\请选择要执行的操作：\ scanf(\

system(\ switch(x) {

case 1:

printf(\ printf(\约瑟夫环:\\n\

printf(\编号为1,2,3,4?,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始按顺序报数,报到m时停止.报m的人出列，将他的密码m作为新的m值,从他的顺时针方向上的下一人开始重新从1报数,如此下去,直到所有人全部出列为止.编程打印出列顺序.\\n\

printf(\ main(); break; case 2:

printf(\请输入总人数n：\\n\ scanf(\

printf(\请输入开始上限数m:\ scanf(\

createList(&ppHead,n); printf(\

printf(\出队顺序：\\n\ jose(ppHead,m);

printf(\约瑟夫环游戏结束!\\n\ main(); break; case 0: exit(0); default:

system(\

printf(\您选择的操作有误，请重新选择...\\n \ main(); } } return 0; }

3.2 链表的创建

这这这这这这这这这这这这这这这这Main()这这createList();这这这这这这这这这这这n这这n>0这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这main()

图5 创建链表函数的数据流程图

/*创建单向循环链表ppHead，参加人数个数为n，并输入每人的密码值，若建立失败则生成头结点，让cur指向他，若建立成功则插入结点P，cur指向的数据元素为p,后续为\空\的结点，再把P插入循环链表ppHead中*/ 根据图5，创建链表函数程序如下：

void createList(LNode **ppHead,int n) { int i,m_pwd;

LNode *p,*cur;//cur:浮标指针 for(i=1;i<=n;i++) {

printf(\输入第%d个人的密码：\

scanf(\输入持有密码 p=createNode(i,m_pwd);//调用构造结点函数 if(*ppHead==NULL)//如果头结点为空 { *ppHead=cur=p;//生成头结点，让cur指向他 cur->next=*ppHead;//cur的指针域指向自身 } else//如果不为空，则插入结点 { p->next = cur->next; cur->next = p; cur= p;//cur指向新插入结点 } } printf(\完成创建！\\n\提示链表创建完成 }

3.3 出队处理

Main()这这Jose():这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这这i=ppHead->pwd;j=ppHead->num;这这这这这这m_pwd=ppHead->pwd;这这这这这这这这这这这这这这这这这这这这这这这这free(ppHead);ppHead=p->next;这这这这这这这这这

图6 出对函数的数据流程图

/*p指向要删除结点的前一个结点，ppHead指向要删除的结点，使p=ppHead，ppHead再指向要删除结点的下一个结点，使p和ppHead链接，输出p指向结点的编号和密码值，释放ppHead，如此循环，直至把所有结点都打印和删除为止！*/

根据图6，出队函数程序如下：

void jose(LNode *ppHead,int m_pwd) {

int i,j;

LNode *p;//定义指针变量 for(i=1;p!=ppHead;i++) {

for(j=1;j

{ p=ppHead;//p赋值为ppHead，p指向要删除结点的前一个结点 ppHead=ppHead->next;//ppHead指向下一个元素 } p->next = ppHead->next;//p结点与头结点链接 i=ppHead->pwd;//i赋值为ppHead->pwd

j=ppHead->num;//j赋值为ppHead->num，j为要删除的密码值 printf(\第%d个人出列，密码：%d\\n\

m_pwd=ppHead->pwd;//m_pwd赋值为ppHead->pwd free(ppHead);//释放头结点

ppHead=p->next;//ppHead重新赋值给p->next,即释放前的ppHead->pwd指针//删除报数结点 }

i=ppHead->pwd;//i赋值为ppHead->pwd j=ppHead->num;//j赋值为ppHead->num

printf(\最后一个出列是%d号，密码是:%d\\n\ free(ppHead);//释放头结点 }

3.4 约瑟夫环说明模块

void instruction() {

printf(\ printf(\约瑟夫环:\\n\

printf(\编号为1,2,3,4?,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始按顺序报数,报到m时停止.报m的人出列，将他的密码m作为新的m值,从他的顺时针方向上的下一人开始重新从1报数,如此下去,直到所有人全部出列为止.编程打印出列顺序.\\n\

printf(\}

3.5菜单模块

void menu() {

printf(\约瑟夫环***********************\\n\

printf(\ printf(\约瑟夫环问题的阐述 \\n\ printf(\按要求求解约瑟夫环 \\n\ printf(\退出 \\n\ printf(\欢迎使用！*********************\\n\}

致 谢

这次的课程设计，我们四人一小组完成自己所选的课题，但是还是得到了来自很多方面的帮助。在此首先要感谢学院提供给我这次实践的机会，让我们有机会贴近现实，感受成功的喜悦；其次要感谢实验机房的老师提供优良的实验设备供我们做课程设计，正是这种良好的课程设计的环境让我们整个课程设计过程心情都非常愉快。再次要感谢指导老师的辛勤指导，每当我们遇到疑难问题时，是他一次次不厌其烦地解释和悉心地指导，我们才能闯过一个个难关，到达胜利的彼岸，是他给我们提供了一次宝贵的检验自己的机会。最后也要感谢同伴们的帮助，有了他们的支持使我遇到任何困难都觉得不是一个人在战斗。感谢所有在课程设计过程中帮助过我的人！

附 录

源代码：

#include //输入输出函数头文件

#include //字符串转短整形函数的头文件 typedef struct LNode//定义单循环链表中结点的结构 { int num;//编号 int pwd;//password

struct LNode *next;//指向下一结点的指针 }LNode; /*构造结点*/

LNode *createNode(int m_num,int m_pwd) { LNode *p;

p=(LNode *)malloc(sizeof(LNode));//生成一个结点 p->num=m_num;//把实参赋给相应的数据域 p->pwd=m_pwd;

p->next=NULL;//指针域为空 return p; }

/*创建循环链表*/

void createList(LNode **ppHead,int n)

{/*创建单向循环链表ppHead，人数个数为n，并输入每个人的密码值，若建立失败则生成头结点，让cur指向他，若建立成功则插入结点P，cur指 向的数据元素为p,后续为\空\的结点，再把P插入循环链表ppHead中*/ int i,m_pwd;

LNode *p,*cur;//cur:浮标指针 for(i=1;i<=n;i++)

{ printf(\输入第%d个人的密码：\ scanf(\输入持有密码

p=createNode(i,m_pwd);//调用构造结点函数 if(*ppHead==NULL)//如果头结点为空 { *ppHead=cur=p;//生成头结点，让cur指向他 cur->next=*ppHead;//cur的指针域指向自身 } else//如果不为空，则插入结点 { p->next = cur->next; cur->next = p; cur= p;//cur指向新插入结点 } }

printf(\完成创建！\\n\提示链表创建完成 }

/*出队处理*/

void jose(LNode *ppHead,int m_pwd)

{/*p指向要删除结点的前一个结点，ppHead指向要删除的结点，使p=ppHead，ppHead再指向要删除结点的下一个结点，使p和ppHead链接，输出p指向结点的编号和密码值，释放ppHead，如此循环，直至把所有结点都打印和删除为止！*/

int i,j;

LNode *p;//定义指针变量 for(i=1;p!=ppHead;i++) { for(j=1;j

{ p=ppHead;//p赋值为ppHead，p指向要删除结点的前一个结点

ppHead=ppHead->next;//ppHead指向下一个元素 }

p->next = ppHead->next;//p结点与头结点链接 i=ppHead->pwd;//i赋值为ppHead->pwd

j=ppHead->num;//j赋值为ppHead->num，j为要删除的密码值 printf(\第%d个人出列，密码：%d\\n\

m_pwd=ppHead->pwd;//m_pwd赋值为ppHead->pwd free(ppHead);//释放头结点

ppHead=p->next;//ppHead重新赋值给p->next,即释放前的ppHead->pwd指针//删除报数结点

}

i=ppHead->pwd;//i赋值为ppHead->pwd j=ppHead->num;//j赋值为ppHead->num

printf(\最后一个出列是%d号，密码是:%d\\n\ free(ppHead);//释放头结点 }

void instruction()

{ printf(\

printf(\约瑟夫环:\\n\

printf(\ 编号为1,2,3,4?,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到时停止.报m的人出列，将他的密码m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去, 直到所有人全部出列为止.编程打印出列顺序.\\n\

printf(\ }

void menu()

{ printf(\约瑟夫环*************************\\n\

printf(\

printf(\ [1]约瑟夫环问题的阐述 \\n\ printf(\ [2]按要求求解约瑟夫环 \\n\ printf(\ [0]退出 \\n\ printf(\欢迎使用！**********************\\n\}

/*主函数模块*/

int main()

{ int n,m,x;

LNode *ppHead=NULL; menu(); for(;;)

{ printf(\请选择要执行的操作：\

scanf(\ system(\ switch(x) { case 1:

printf(\

printf(\约瑟夫环:\\n\

printf(\ 编号为1,2,3,4?,n的n个人按顺时针方向围坐一圈,

每人持有一个密码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止.报m的人出列，将他的密码m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,

直到所有人全部出列为止.编程打印出列顺序.\\n\

printf(\ main();

break; case 2:

printf(\请输入总人数n：\ scanf(\

printf(\请输入开始上限数m：\ scanf(\

createList(&ppHead,n); printf(\

printf(\出队顺序：\\n\ jose(ppHead,m);

printf(\约瑟夫环游戏结束!\\n\ main(); break; case 0: exit(0); default:

system(\

printf(\您选择的操作有误，请重新选择...\\n\\n\\n\ main(); } }

return 0; }

本文来源：https://www.bwwdw.com/article/pzo.html