资源描述：
《数据结构课程设计报告约瑟夫环.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、课程设计课程名称：程序设计、数据结构课题名称：约瑟夫环班级：学号：姓名：指导教师：湖南理工学院计算机学院2011年12月一、问题描述约瑟夫环问题描述的是：设编号为1，2，…，n的n（n>0）个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。如下图分析：123456
2、7890这是第一个人，他的密码是“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约瑟夫环问图解3271484约瑟夫环原理演示图1234567第二部：第一次停下的位置，此时6号出列，并
3、将他的值作为新的m值，即：新的m=8；从7好开始继续向下走8次，到1号的位置最后排序后的密码序列：（本图只演示前两步）8第三步：第二次，1号出列第四步：第三次，4号出列3第一步：给第一个人赋初始密码为：20则从它开始向下走20次，到6号位置241746147235图2约瑟夫环原理演示图二、逻辑设计1、循环链表抽象数据类型定义typedefstructLNode//定义单循环链表中节点的结构{intnum;//编号intpwd;//passwordstructLNode*next;//指向下一结点的指针}LNode;2、本程序包含一下几
4、个模块（1）构造结点模块LNode*createNode(intm_num,intm_pwd){LNode*p;p=(LNode*)malloc(sizeof(LNode));//生成一个结点p->num=m_num;//把实参赋给相应的数据域p->pwd=m_pwd;p->next=NULL;//指针域为空returnp;}（2）创建链表模块voidcreateList(LNode*ppHead,intn)（3）出队处理模块voidjose(LNode*ppHead,intm_pwd)（4）约瑟夫环说明输出模块voidinstruc
5、tion()（5）菜单模块voidmenu()（6）主函数模块intmain（）函数的调用关系图如下：Case2:建立的约瑟夫环,并输出已建立的约瑟夫环：createList(LNode**ppHead,intn)输出该约瑟夫环的每个人的出列顺序:jose(LNode*ppHead,intm_pwd)图3约瑟夫环函数调用关系图菜单函数；voidmenu()主函数调用函数；main()Case1：一个简单的输出函数，用于说明约瑟夫环；voidinstruction()Case0:default:输入0，退出exit(0)；三、详细设计1
6、.主函数Main()开始Menu()功能菜单功能1：约瑟夫环说明功能2：按要求求解约瑟夫环功能3：退出系统输入总人数n输入开始上线数：m输入每个玩家的密码调用：createList(&ppHead,n);jose(ppHead,m);函数求解所需的密码序列选择要执行的操作程序运行完，自动返回到功能菜单图4主函数数据流程图根据流程图，主函数程序如下：intmain(){intn,m,x;LNode*ppHead=NULL;menu();for(;;){printf("请选择要执行的操作：");scanf("%d",&x);syste
7、m("cls");switch(x){case1:printf("****************************************************************");printf("约瑟夫环:");printf("编号为1,2,3,4…,n的n个人按顺时针方向围坐一圈,每人持有一个密");printf("码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始");printf("按顺时针方向自1开始顺序报数,报到m时停止.报m的人出列，将他的密码");printf("
8、m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,");printf("直到所有人全部出列为止.编程打印出列顺序.");printf("****************************
