1、 课 程 设 计 课程名称： 程序设计、数据结构 课题名称： 约瑟夫环 班 级： 学 号： 姓 名： 指导教师： 2011 年 12 月 一、问题描述一、问题描述 约瑟夫环问题描述的是：设编号为 1，2，n 的 n（n0）个人按顺时针 方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限 m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 时停止报数，报 m 的 人出圈，将他的密码作为新的 m值，从他在顺时针方向上的下一个人起重新从 1 报数。如此下去，直到所有人都出圈为止。令 n最大值为 100。要求设计一个程 序模拟此过程，求出出圈的编号序列。如下图分析： 1 2
2、3 4 5 6 7 8 9 0 这是第一个人，他的 密码是“1” ，个他输 一个 m 值， 如果 m=3, 则从他开始向下走 3 个 这就是第二步的位置， 这时他的密码作为新 的 m 值，即 m=4,同时 得到的第一个密码为 4；4 号出去向下走 4， 到 9 这儿； （这这一步 完 了 剩 余 的 为 ： 1,2,3,5,6， ，7,8,9,0， ） 这就是第三步的位置， 这 时他的密码作为新的 m 值，即 m=9，同时得到 的第二个密码为 9；9 号 出去向下走9， 到0这儿； 继续走就行了 （这儿剩余 的就是：1，2，3，5， 6,7,8,0） 图 1 约瑟夫环问图解 1 二、逻辑设计二
3、、逻辑设计 1、循环链表抽象数据类型定义 typedef struct LNode/定义单循环链表中节点的结构 int num;/编号 int pwd;/password struct LNode *next;/指向下一结点的指针 LNode; 2、本程序包含一下几个模块 （1）构造结点模块 LNode *createNode(int m_num,int m_pwd) 3 2 7 1 4 8 4 约瑟夫环原理约瑟夫环原理演示演示图图 1 2 3 4 5 6 7 第二部： 第一次停下的位置，此 时6 号出列， 并将他的值作为新 的 m 值，即：新的 m=8；从 7 好开始继续向下走8 次， 到1
4、 号 的位置 最后排序后的密码序列： （本图只演示前两步） 8 第三步： 第二次，1 号出列 第四步：第三次， 4 号出列 3 第一步：给第一个人 赋初始密码为：20 则 从它开始向下走 20 次，到 6 号位置 2 4 1 7 4 6 1 4 7 2 3 5 图 2 约瑟夫环原理演示图 2 LNode *p; p=(LNode *)malloc(sizeof(LNode);/生成一个结点 p-num=m_num;/把实参赋给相应的数据域 p-pwd=m_pwd; p-next=NULL;/指针域为空 return p; （2）创建链表模块 void createList(LNode *ppHead,int n) （3）出队处理模块 void jose(LNode *ppHead,int m_pwd) （4）约瑟夫环说明输出模块 void instruction() （5）菜单模块 void menu() （6）主函数模块 int mai
