1、 数 据 结 构 课 程 设 计 报 告数 据 结 构 课 程 设 计 报 告 班班 级：级：信息安全 101 班 学学 号：号： 02 姓姓 名：名： 时时 间：间： 2011 年 12 月 25 日 2012 年 1 月 6 日 2012 年年 01 月月 06 日日 josephjoseph 环环 一、一、问题描述问题描述 任务：编号是 1，2，,n 的 n 个人按照顺时针方向围坐一 圈，每个人只有一个密码（正整数） 。一开始任选一个正整数作为报 数上限值 m,从第一个仍开始顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时 针
2、方向的下一个人开始重新从 1 报数，如此下去， 直到所有人全部出 列为止。设计一个程序来求出出列顺序。 要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出 各个人的编号。 测试数据： m 的初值为 20，n=7 ,7 个人的密码依次为 3，1，7，2，4，7，4，首 先 m=6,则正确的输出是什么？ 要求： 输入数据：建立输入处理输入数据，输入 m 的初值，n ，输入每个人 的密码，建立单循环链表。 输出形式：建立一个输出函数，将正确的输出序列 二、二、 需求分析需求分析 利用单向循环链表存储结构模拟此过程， 按照出列的顺序输出 各个人的编号。首先创建一个空链表，初始化链表，构造出一
3、个只有 头结点的空链表，建立好一个约瑟夫环。 1. 输入的形式和输入值的范围 本程序中，输入报数上限值 m 和人数上限 l，密码，均限定为 正整数，输入的形式为一个以“回车符”为结束标志的正整数。 2. 输出的形式 从屏幕显示出列顺序。 3. 程序功能 提供用户从键盘输入，Joseph 约瑟夫环的必要数据，并显示出 列顺序。 三、三、概要设计概要设计 以单向循环链表实现该结构。 1. 抽象数据类型的定义为： ADT LNode 数据对象：D=ai | aiCharSet，i= 1，2，n，n0 数据关系：R1= ai-1 ，ai | ai D， I=2， n 四、源程序四、源程序 #inclu
4、de #include typedef struct Node int key;/每个人持有的密码 int num;/这个人的编号 struct Node *next;/指向下一个节点 Node,*Link; void InitList(Link if(!L) exit(1); L-key=0; L-num=0; L-next=L; void Creater(int n,Link q=L; for(int i=1;ikey); p-num=i; L-next=p; L=p; L-next=q-next; free(q); void main() Link L,p,q; int n,x; L=NULL; InitList(L);/构造出一个只有头结点的空链表 printf(“please input the totle number of people:“); scanf(“%d“,/总共的人数 n print
