数据结构课程设计约瑟夫环.docx

1、目录约瑟夫环1约瑟夫环2【问题描述】2【基本要求】2【算法思想】2【模块划分】3【数据结构】4【源程序清单】5【测试数据】5【测试情况】51.输入玩儿游戏的总人数m：52.输入作为队首的人的初值m：63.依次输入每个人的密码：64.出列的结果为：6约瑟夫环课程设计题目约瑟夫环学院专业年级已知参数和设计要求：问题描述约瑟夫（Joeph）问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重

2、新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。学生应完成的工作：基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。测试数据m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。实现提示程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n30。目前资料收集情况（含指定参考资料）：1 Robert L.Kruse Alexander J.Ryba编著.数据结构与程序设计C+语言描述(影印版) .高等教育出版社.2001年5月2 郑慧 范忠诚等编著.零基础学Visual C+.机械工业出版社.2

3、009年1月课程设计的工作计划：2014.6.6-2014.6.10思考完成此文档的问题描述、基本要求、算法思想、模块划分、数据结构内容，形成一个初步设计架构。2014.6.11-2014.6.22李嘉诚完成此任务各模块功能的编码和实现。2014.6.22-2014.7.2李嘉诚负责对此任务程序进行测试，并记录测试内容。2014.7.2-2014.7.10李嘉诚完成此任务界面设计与实现，做相应修改、并完成此任务的文档编写。任务下达日期 2014 年 6 月 6 日完成日期 2014 年 7 月 10日指导教师 （签名）学 生 （签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技

4、术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。约瑟夫环【问题描述】约瑟夫（Joeph）问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。【基本要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号【算法思想】游戏实现的关键是游戏信息的储存。包括玩家座位

5、信息，玩家所报数信息以及密码信息。我们通过自定义单向循环链表Joeph_list存储结构来实现游戏过程的模拟。链表以结点连接。结点Node存储的信息包括每个人手中的密码、每个人的位置以及下一个结点在计算机中的存储位置，及指向下一个结点的指针。值得注意的是，信息“每个人的位置”是必不可少的，因为他不等同于结点在链表中的位置但一个玩家被移除之后，链表后的元素位置会“前进”，而我们需要的玩家的位置始终是不变的。玩家的报数，我们通过循环中计数器的递增实现，当顺序递增到链表中最后一个结点，而循环仍没有结束时，我们继续从第一个元素开始递增及相当于最后一个玩家仍没有报数到m我们就从第一个玩家重头开始报数。直

6、到计数器累加到m，则发现我们要移除的结点，记录并输出移出结点的信息，继续游戏。直到链表中元素被清空，程序结束。算法的关键是将实际游戏场景抽象到链表中的元素的查找和移除上，要掌握清楚哪些数据代表哪些信息，并熟悉程序运行中各种判断的流程。具体流程图见下一页。【模块划分】【数据结构】Member *Joseph:Index(int i) if(i=0)return frist; Member *p=frist-next; int j=1; while(jnext; j+; return p; int Joseph:Delete(int i) Member *s,*p=Index(i-1); s=p-next; p-next=p-next-next;int x=s-number; coutxpassword; delete s; size-; return y;【源程序清单】ysfh.cpp【测试数据】输入给定数字：N = 7,测定数据为3，1，7，2，4，8，4，m = 20【测试情况】1.输入玩儿游戏的总人数m：2.输入作为队首的人的初值m：3.依次输入每个人的密码：4.出列的结果为：9