约瑟夫环课程的设计.docVIP

《数据结构》 目录? 目录?........................................................................................................1 正文?........................................................................................................2 题目.................................................................................................2 、问题描述?..................................................................................2 、基本要求...................................................................................2 、测试数据...................................................................................2 二、概要设计.........................................................................................2 三、详细设计?.......................................................................................3 四、调试分析.......................................................................................5 五、用户使用说明?...............................................................................5 六、测试结果?.......................................................................................6 七、参考文献?........................................................................................7 题目：Joseph环 1）问题描述 约瑟夫环问题描述的是：编号是1，2，??,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。如下图分析： 2） 基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 3） 测试数据 m的初值：20 ；n=7； 7个人的密码依次为：3,1,7,2,4,8,4； 首先m值为6（正确的出列顺序为 6,1,4,7,2,3,5） 概要设计 1：算法思想 ?利用单向循环链表存储结构模拟此过程，因为循环链表最后一个结点的指针域指向头结点，整个链表形成一人环，刚好和题中的“n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）”内容要求一致，而且，循环链表中任一结点出发均可找到表中其他结点，利用这一优点可较容易地找出报数的人及下一个报数的人，最后按照出列的顺序用一个for语句实现。? joseph环的组成成员由密码（password）和序号(No)组成，循环链表的存储结构如下： typedef?struct?LNode?{? ?int?password;??//密码??int?No;?????//序号?? ?struct?LNode?*next;??//下一成员指针?}mem