1、 数据结构课程设计报告数据结构课程设计报告 题目： JosephJoseph 环环程序设计程序设计 学学 院：院： 软件学院软件学院 姓姓 名：名： * 学学 号：号： 20102010* 专专 业：业： 软件工程软件工程 年年 级：级： 指导教师：指导教师： 二二 0 0 一一一一 年年 12 月月 题目概要：题目概要：josephjoseph 环环 任务：编号是 1，2，,n 的 n 个人按照顺时针方向围坐一圈，每个人只有一个密码 （正整数）。一开始任选一个正整数作为报数上限值 m,从第一个仍开始顺时针方向自 1 开 始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的
2、m 值，从他在顺时针 方向的下一个人开始重新从 1 报数，如此下去，直到所有人全部出列为止。设计一个程序来 求出出列顺序。 要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 测试数据： m 的初值为 20，n=7 ,7 个人的密码依次为 3，1，7，2，4，7，4，首先 m=6,则正确的 输出是什么？ 要求： 输入数据：建立输入处理输入数据，输入 m 的初值，n ，输入每个人的密码，建立单循 环链表。 输出形式：建立一个输出函数，将正确的输出序列 一、一、 需求分析需求分析 1. 输入的形式和输入值的范围 本程序中，输入报数上限值 m 和人数上限 l，密码，均限定为正
3、整数， 输入的形式为一个以“回车符”为结束标志的正整数。 2. 输出的形式 从屏幕显示出列顺序。 3. 程序功能 提供用户从键盘输入，Joseph 约瑟夫环的必要数据，并显示出列顺序。 4. 测试数据 （1） 输入 20,7 输出 0 0 3 7 4 0 7 4 4 二、二、 概要设计概要设计 利用单向循环链表存储结构模拟此过程， 因为循环链表最后一个结点的指针 域指向头结点，整个链表形成一人环，刚好和题中的“n 个人按照顺时针方向围 坐一圈，每个人只有一个密码（正整数）”内容要求一致，而且，循环链表中任 一结点出发均可找到表中其他结点， 利用这一优点可较容易地找出报数的人及下 一个报数的人，最后按照出列的顺序用一个 for 语句实现。 joseph 环的组成成员由密码（password）和序号(No)组成，循环链表的存储结 构如下： typedef struct LNode int password; /密码 int No; /序号 struct LNode *next; /下一成员指针 member; /组成成员结构体 输入 m、 n m0且 n0的整数 建立含 n 个结点的链表且用head 指向 第 一 个元 素 ， 结 点 数据 域 包 含 password、No、以及指向下一结点的指 head=p n2 (m%n)=0?n:m%n= 1=i ip i+
