约瑟夫环实习报告.pdf

约 瑟 夫 环 一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人 按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一 个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺 序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直 至所有人全部出列为止。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示"提 示信息"之后，有用户在键盘上输入演示程序中规定的运算命令，相应 的输入数据和运算结果显示在其后。 3.程序执行的命令包括： 1）输入初始密码和人数 2）输入所有人的密码 3）显示输入的所有人的 编号及相应的密码 4）输出出列密码及编号 5）结束 4.测试数据 (1)m=20, n=7, 7个人的密码依次为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需 要有一个抽象数据类型。该抽象数据类型的定义为： AD