文档介绍：上海电力学院
数据结构Java课程设计
题目: 约瑟夫环
学生姓名:
学号:
院系: 计算机与信息工程学院
专业年级: 软件工程级
2010 年 7 月 13 日
目录
1. 需求分析 3
运行环境 3
输入的形式和输入的范围 3
输出的形式描述 3
功能描述 4
测试数据 4
2. 概要设计 4
抽象数据类型定义描述 4
功能模块设计 5
模块层次调用关系图 5
3. 详细设计 6
类函数解析 6
主函数解析 8
4. 调试分析 9
所遇问题 9
实验心得 10
5. 用户使用说明 10
每一步操作说明 10
6. 测试结果 11
7. 附录:程序源代码 11
需求分析
【问题描述】
约瑟夫(Joseph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。
【基本要求】
利用单向循环链表存储结构或顺序存储结构模拟此过程,按照出列的顺序印出各人的编号。
【测试数据】
m的初值为20;n=7,7个人的密码依次为:3,1,7,2,4,8,4,首先m值为6(正确的出列顺序应为6,1,4,7,2,3,5)。
运行环境(软、硬件环境)
开发工具:
运行环境:Windows XP及其以上系统
2、输入的形式和输入值的范围
本个实验所输入的值都强制转化为Int数据类型,因为人数一定是个正整数,而每个人所持的密码将会作为下一次循环的步数,所以也一定是一个整数;初始密码也是步数,所以也是一个正整数。在输入值的取值范围上,每人的密码是一个大于零的整数,初始密码也是一个大于零的整数,人数同样也是一个正整数。
输出的形式描述

①在DOS环境中编译“”文件
②
、每人密码、初始密码等一些数据()
(图)
功能描述
约瑟夫环代码约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提出的,他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法守住了裘达伯特城达47天之久,在城市沦陷之后,他和40名死硬的将士在附近的一个洞穴中避难。在那里,这些叛乱者表决说“要投降毋宁死”。于是,约瑟夫建议每个人轮流杀死他旁边的人,而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签,并且,作为洞穴中的两个幸存者之一,他说服了他原先的牺牲品一起投降了罗马。
本次试验的不同点在于有一个初始密码M、每人又有个密码,在他死后(出局)之后将作为下一个循环的步数,这样以此类推得出最后一个幸存者。这个实验主要是模仿约瑟夫环的意思模拟约瑟夫环。差别在与每人的密码将作为下一个循环步数继续开始另一个约瑟夫环的循环处理。最后得到一个出此链表的数字下标代号。
测试数据
①初始密码M=20
②人数为7
③7个人的密码依次为:3,1,7,2,4,8,4
最后得到一个出此链表顺序,用每个链表中元素的下标输出数据。
二、概要设计
1、抽象数据类型定义描述
(对各类的成员及成员函数进行抽象描述)
创建Node和LinkList这两个类,在Node类中定义一些函数,为主程序中调用这些函数所服务;LinkList类Head指针调用SetLink函数,然后遍历结点,一次删除结点,使得指针后移。
在主函数中运用一个For循环作为足要算法,一次实现约瑟夫环的功能。
功能模块设计(如主程序模块设计)
先创建了一个linklist对象,然后分别申明inCount和resultIncount这两个私有成员变量。然后通过inCount = (());把输入的内容转化成INT类型,赋值给inCount。通过一个For循环语句作为其主要算法实现。
Node p = , q = ;
int i = 0;//每个人的密码
int j = 0;//人数
for (;;) {i++;
if (i == m) {
i = 0;
m = ();