数据结构 约瑟夫环实验报告

一、需求分析 1、以单项循环链表存储结构模拟约瑟夫环问题。即编号为1、2、3…、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。按出列顺序印出各人编号。 2、 演示程序以用户与计算机的对话方式执行，用户输入相应的数据，输出结果显示在其后。 3、 测试数据：m初始值20，n=7，7个人密码依次为：3，1，7，2，4，8，4。正确出列顺序为6，1，4，7，2，3，5。 二、概要设计 1. 抽象数据类型的定义为： ADT LNode { 数据对象：D={ai | ai∈CharSet，i= 1，2，…，n，n≥0} 数据关系：R1={< ai-1 ，ai > | ai ∈D， I=2，…，n} 基本操作： initList(Linklist &L)