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

1、长春建筑学院基于单向循环链表的约瑟夫环设计Design of Joseph ring way circular linked list based on 学 院： 电气信息学院 班 级： 计算机1201班 学 号： 121500140 姓 名： 卢玉琨 指导老师: 常大俊 摘 要约瑟夫环问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。改进约瑟夫环问题的描述是：编号为1，2，n的n个人按顺时针方向围坐一圈, 每人有一个密码K（整数），留作其出圈后应报到K后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这

2、个就是约瑟夫环问题的实际场景。约瑟夫环问题如果采用单循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p-link=head解决问题的核心步骤是：先建立一个具有n个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。【关键词】约瑟夫环；单循环链表；数据结构；删除结点AbstractJosephus ring problem is evolved by the question that raised by Josephus,the famous historican of ancient Rome.SO it a

3、lways 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 alt

4、ernately 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

5、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

6、chain table was empty.Keywords Joseph ring; circular linked list; data structure; deleting node目 录前言1第一章 问题分析21.1 设计目的21.2 设计内容21.3 设计要求21.4 设计思想第二章 逻辑设计42.1 循环链表抽象数据类型定义42.2本程序包含的模块设计4第三章 详细设计63.1 主函数63.2 链表的创建73.3 出队处理93.4 约瑟夫环说明模块103.5菜单模块10第四章 程序调试与测试11第五章 结论14参考文献15致谢16附录17前 言数据结构是一门研究非数值计算的程序设

7、计问题中计算机的操作对象以及它们之间的关系和操作的学科。该课程设计的目的是通过课程设计的综合训练，以培养分析和编程等实际动手能力，是系统掌握数据结构这门课程的主要内容。本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接的链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活。约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。通过该课程设计，能运用所学知识，上机解决一些实际问题，了解并初步掌握设计，实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以

8、及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。第1章 问题分析1.1 设计目的1、 掌握单向循环链表的建立。 2、掌握单向循环链表的操作。 1.2 设计内容 编号是1,2,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。请设计一个程序求出出列顺序。1.3 设计要求1、利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人

9、的编号。 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（n0）个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起按顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他的顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都

10、出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。具体描述如图1和图2所示：图1 约瑟夫环问题图解t图2 约瑟夫环原理演示图第二章 逻辑设计2.1 循环链表抽象数据类型定义typedef struct LNode/定义单循环链表中结点的结构 int num;/编号 int pwd;/passwordstruct LNode *next;/指向下一结点的指针 LNode;2.2本程序包含的模块设计（1）构造结点模块LNode *createNode(int m_num,int m_pwd) LNode *p; p=(LNode *)malloc(sizeof(LNod

11、e);/生成一个结点 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所示：第三章 详细设计3.1 主函数图4 主函数数据流程图根据图4，主函数程序如下：int main() int

12、 n,m,x; LNode *ppHead=NULL; menu(); for(;) printf(n请选择要执行的操作：); scanf(%d,&x); system(cls); switch(x) case 1: printf(*n); printf(约瑟夫环:n); printf( 编号为1,2,3,4,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始按顺序报数,报到m时停止.报m的人出列，将他的密码m作为新的m值,从他的顺时针方向上的下一人开始重新从1报数,如此下去,直到所有人全部出列为止.编程打印出

13、列顺序.n); printf(*n); main(); break; case 2: printf(请输入总人数n：n); scanf(%d,&n); printf(请输入开始上限数m:); scanf(%d,&m); createList(&ppHead,n); printf(n); printf(出队顺序：n); jose(ppHead,m); printf(n约瑟夫环游戏结束!n); main(); break; case 0: exit(0); default: system(cls); printf(n您选择的操作有误，请重新选择.n ); main(); return 0; 3.2

14、 链表的创建图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;inext=*ppHead;/cur的指针域指向自身 else/如果不为空，则插入结点 p-next = cur-next; cur-next = p

15、; cur= p;/cur指向新插入结点 printf(完成创建！n); /提示链表创建完成 3.3 出队处理图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;jnext;/p

16、pHead指向下一个元素 p-next = ppHead-next;/p结点与头结点链接 i=ppHead-pwd;/i赋值为ppHead-pwd j=ppHead-num;/j赋值为ppHead-num，j为要删除的密码值 printf(第%d个人出列，密码：%dn,j,i); 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

17、赋值为ppHead-num printf(最后一个出列是%d号，密码是:%dn,j,i); free(ppHead);/释放头结点 3.4 约瑟夫环说明模块void instruction() printf(*n); printf(约瑟夫环:n); printf( 编号为1,2,3,4,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始按顺序报数,报到m时停止.报m的人出列，将他的密码m作为新的m值,从他的顺时针方向上的下一人开始重新从1报数,如此下去,直到所有人全部出列为止.编程打印出列顺序.n); prin

18、tf(*n); 3.5菜单模块void menu() printf(*约瑟夫环*n); printf(n); printf( 1约瑟夫环问题的阐述 n); printf( 2按要求求解约瑟夫环 n); printf( 0退出 n); printf(* 欢迎使用！*n);第四章 程序调试与测试1. 调用模块时，结点结构的调用与其他模块产生冲突，导致每一行都出现两个错误，加入子函数的声明后，错误消失。2. 刚开始时忽略了一些变量参数的标识，如：&和“*”，使调试程序时费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。3. 本次课程设计采用数据抽象的程序设计方法，将程序划分为三个结构：元素结

19、点、单向循环链表，主控制模块。思路较为清晰，实现调用顺利。 经过本次实验，使我对数据结构这门课程有了进一步的了解，每一个程序经过问题分析、概要设计、详细设计之后，思路清晰呈现，程序也很快就出来了，最后经过调试、运行，又有了新的体验。这是一个使用循环链表的经典问题。本程序开始运行界面如图7所示：图7 约瑟夫环开始运行界面 选择1进入约瑟夫环问题阐述，如图8所示：图8 约瑟夫环问题阐述选择2，输入下列数据测试，测试结果如图9所示：请输入总人数n：8请输入开始上限数m：9请依次输入每个人的密码：9 3 7 9 12 6 11 10 13出队顺序：1 4 3 8 2 5 7 6 图9 约瑟夫环测试1选

20、择2，输入下列数据测试，测试结果如图10所示：请输入总人数n：6请输入开始上限数m：16请依次输入每个人的密码：32 5 6 9 8 7 出队顺序：4 2 3 1 6 5图10 约瑟夫环测试2继续选择2，输入下列数据测试，测试结果如图11所示：请输入总人数n：7请输入开始上限数m：20请依次输入每个人的密码：2 4 6 3 8 4 0 出队顺序：6 3 4 1 5 2 7图11 约瑟夫环测试3第五章 结论我这次数据结构课程设计的题目是:约瑟夫环问题。通过对该题目的设计,我加深了对数据结构及存储结构的理解,进一步地理解和掌握了课本中所学的各种数据结构，尤其是对单循环链表的基本运算的实现,学会了如

21、何把学到的知识用于解决实际问题,锻炼了自己动手的能力。 在这次课程设计中，我们组四个人一同讨论这个算法的运算过程以及算法涉及的一些数据结构的知识，讨论出一个大概框架后我们四个人分工合作。在此课程设计中我主要承担画流程图以及测试的工作，通过画流程图，我更熟识了Microsoft visio 2003这个画图软件的运用。通过用visualc+ 6.0这个程序开发软件测试，我发现存在很多的错误，深知自己的不足之处，然后通过提示改正错误。两周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力。总而言之这两周中我学到很多

22、，受益匪浅。参考文献 1 严蔚敏，吴伟民 著.数据结构（C语言版）M.北京：清华大学出版社，1997.2 严蔚敏，吴伟民 著.数据结构题集（C语言版）M.北京：清华大学出版社，1997.3 William Ford,William Topp 著. DATA STRUCTURE WITH C+ M.北京：清华大学出版社，1996 .4 谭浩强 著. C语言程序设计M.北京： 清华大学出版社，2000.5 周云静 著数据结构习题解析与上机指导M北京：冶金工业出版社，2004.6 陈慧南 著数据结构C+语言描述M北京：人民邮电出版社，2005.7 Adam Drozdek 著数据结构与算法M北京：清

23、华大学出版社，2006.8 徐孝凯 著数据结构实验M北京：中央广播电视大学出版社，2001. 致 谢这次的课程设计，我们四人一小组完成自己所选的课题，但是还是得到了来自很多方面的帮助。在此首先要感谢学院提供给我这次实践的机会，让我们有机会贴近现实，感受成功的喜悦；其次要感谢实验机房的老师提供优良的实验设备供我们做课程设计，正是这种良好的课程设计的环境让我们整个课程设计过程心情都非常愉快。再次要感谢指导老师的辛勤指导，每当我们遇到疑难问题时，是他一次次不厌其烦地解释和悉心地指导，我们才能闯过一个个难关，到达胜利的彼岸，是他给我们提供了一次宝贵的检验自己的机会。最后也要感谢同伴们的帮助，有了他们的

24、支持使我遇到任何困难都觉得不是一个人在战斗。感谢所有在课程设计过程中帮助过我的人！附 录 源代码： #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_

25、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;inext=*ppHead;/cur的指针域指向自身 else/如果不为空，则插入

26、结点 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

27、=1;jnext;/ppHead指向下一个元素 p-next = ppHead-next;/p结点与头结点链接 i=ppHead-pwd;/i赋值为ppHead-pwd j=ppHead-num;/j赋值为ppHead-num，j为要删除的密码值 printf(第%d个人出列，密码：%dn,j,i); m_pwd=ppHead-pwd;/m_pwd赋值为ppHead-pwd free(ppHead);/释放头结点 ppHead=p-next;/ppHead重新赋值给p-next,即释放前的ppHead-pwd指针/删除报数结点 i=ppHead-pwd;/i赋值为ppHead-pwdj=ppHead-num;/j赋值为ppHead-numprintf(最后一个出列是%d号，密码是:%dn,j,i); free(ppHead);/释放头结点void instruction() printf(*n); printf(约瑟夫环:n); printf( 编号