《 数 据 结 构》 课程设计报告书 设计题目： 约瑟夫环 专 业： 班 级： 姓 名： 指导教师： 完成日期： 目 录 一、 问题描述 ················· 1 二、 基本要求 ················· 1 三、 测试数据 ················· 1 四、 算法思想 ················· 2 五、 模块划分 ················· 3 六、 数据结构 ················· 4 七、 源程序 ·················· 4 八、 界面设计 ················· 6 九、 运行与测试 ················ 6 十、 总结 ··················· 8 十一、思考与感悟 ················ 9 《数据结构》课程设计报告书 1 课程设计设计报告书 一、问题描述 约瑟夫问题是由古罗马著名的史学家 Josephus 提出的问题演变而来，所以通常称为 Josephus 问题。改进约瑟夫问题的描述是：编号为 1，2，„，n 的 n 个人按顺时针方向围坐一圈 , 每人有一个密码（整数），留作其出圈后应报到后出圈。报数方法采用顺时针报数和逆时针报数交替进行，初始密码可任意确定。求最后剩下的人的编号。这个就是约瑟夫环问题的实际场景，后来老师要求我们对要求中的每人所持有的密码以及第一次的报数上限值要用随机数产生。因此约瑟夫环问题如果采用双向循环链表则能很好的解决。循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 p->link=head 解决问题的核心步骤：先建立一个具有 n 个链结点，无头结点的循环链表，然后确定第一个报数人的位置，并不断地从链表中删除链结点，直到链表为空。 二、基本要求 (1)输入的形式和输入值的范围：输入的形式是以数字的形式输入，输入范围为-2147483648～2147483648 (2)输出的形式：字符串形式输出 (3)程序所能达到的功能：达到符合约瑟夫环要求的响应功能。 三、测试数据 进入程序，显示“1.开始游戏 0.退出游戏”输入非 0 数进入游戏，输入0退出游戏。 进入游戏后显示“输入总人数” ，输入大于 0 的整数；若输入错误，则光标处清空，重新输入。 后提示“输入开始人的序号” ；范围是大于零，小于总人数的整数，若输入错误，则光标处清空，重新输入。 后提示“输入间隔数字” ，范围是...
