双向循环链表解决约瑟夫实验报告
需积分: 16 200 浏览量
2010-08-29
18:05:57
上传
评论 1
收藏 124KB DOC 举报
题目一： 约瑟夫环问题
一、需求分析
1． 编号为 1,2,3,4,5……n 的 n 个人按顺时针围成一圈，每个人持有一个密码（正整数),
一开始任意选择一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自 1
开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，
从他的顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部
出列为止。
2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，
由用户在键盘上输入相应数据（即每个人所持的密码），每个人的序号由程序自
动分配。
3． 程序执行的命令包括：
1、观看视频 2、开始游戏 3、退出游戏
4． 测试数据
n＝7，7 个人的密码依次为：3，1，7，2，4，8，4，首先 m 值为 6，则这正确的
出列顺序为 6，1，4，7，2，3，5。
二、概要设计
1、抽象数据类型线性表的定义：
ADT List {
数据对象：
D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }
{ 称 n 为线性表的表长;
称 n=0 时的线性表为空表。}
数据关系：
R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n }
{ 设线性表为 (a1，a2, . . . ，ai，. . . ，an),
称 i 为 ai 在线性表中的位序。}
基本操作：
结构初始化操作： Listinit( &L )
操作结果：构造一个空的线性表 L。
建立循环链表：Createlist(&L, n)
初始条件：链表已经初始化，人的个数 n 已知。
操作结果：构造一个一个含 n 个节点的循环链表。
清空链表操作：Cleariist( &L )
初始条件：线性表 L 已存在。
操作结果：销毁线性表 L。
} ADT List
2． 本程序包含三个模块：
第一模块：主函数模块，包含主函数及选择函数；
第二模块：循环单链表模块；
第三模块：解决约瑟夫模块；
主程序模块
循环单链表模块
解 决 约 瑟 夫 模
块
资源评论
