约瑟夫环问题课程设计报告

1数据结构课程设计报告设计课题：约瑟夫问题院系：计算机科学与技术学院专业班级：计算机网络技术1102班学生姓名：张利学号：1108040211指导教师：王昱哲2目录1.需求分析..................................31.1问题描述..............................31.2功能分析............................42.概要设计..................................53.详细设计..................................64.调试与操作说明...........1错误!未定义书签。总结.....................................163一．需求分析1.1问题描述约瑟夫环问题描述的是：设编号为1，2，…，n的n（n0）个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。如下图分析：1234567890这是第一个人，他的密码是“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约瑟夫环问图解41.2功能分析约瑟夫环问题是一个古老的数学问题，本次课题要求用程序语言的方式解决数学问题。此问题仅使用单循环链表就可以解决此问题。而改进的约瑟夫问题通过运用双向循环链表，同样也能方便地解决。在建立双向循环链表时，因为约瑟夫环的大小由输入决定。为方便操作，我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。进行操作时，用一个指针current指向当前的结点，指针front始终指向头结点。然后建立双向循环链表，因为每个人的密码是通过rand()函数随机生成的，所以指定第一个人的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后一个结点，通过一系列的循环就可以解决改进约瑟夫环问题。3271484约瑟夫环原理演示图1234567第二部：第一次停下的位置，此时6号出列，并将他的值作为新的m值，即：新的m=8；从7好开始继续向下走8次，到1号的位置最后排序后的密码序列：（本图只演示前两步）8第三步：第二次，1号出列第四步：第三次，4号出列3第一步：给第一个人赋初始密码为：20则从它开始向下走20次，到6号位置241746147235图2约瑟夫环原理演示图5二、概要设计1、循环链表抽象数据类型定义typedefstructLNode//定义单循环链表中节点的结构{intnum;//编号intpwd;//passwordstructLNode*next;//指向下一结点的指针}LNode;2、本程序包含一下几个模块（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）约瑟夫环说明输出模块voidinstruction()（5）菜单模块6voidmenu()（6）主函数模块intmain（）函数的调用关系图如下：三、详细设计1.主函数Case2:建立的约瑟夫环,并输出已建立的约瑟夫环：createList(LNode**ppHead,intn)输出该约瑟夫环的每个人的出列顺序:jose(LNode*ppHead,intm_pwd)图3约瑟夫环函数调用关系图菜单函数；voidmenu()主函数调用函数；main()Case1：一个简单的输出函数，用于说明约瑟夫环；voidinstruction()Case0:default:输入0，退出exit(0)；7根据流程图，主函数程序如下：intmain(){intn,m,x;LNode*ppHead=NULL;menu();for(;;){printf(\n请选择要执行的操作：);scanf(%d,&x);system(cls);switch(x){case1:printf(****************************************************************\n);printf(约瑟夫环:\n);Main()开始Menu()功能菜单功能1：约瑟夫环说明功能2：按要求求解约瑟夫环功能3：退出系统输入总人数n输入开始上线数：m输入每个玩家的密码调用：createList(&ppHead,n);jose(ppHead,m);函数求解所需的密码序列选择要执行的操作程序运行完，自动返回到功能菜单图4主函数数据流程图8printf(编号为1,2,3,4…,n的n个人按顺时针方向围坐一圈,每人持有一个密\n);printf(码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\n);printf(按顺时针方向自1开始顺序报数,报到m时停止.报m的人出列，将他的密码\n);printf(m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,\n);printf(直到所有人全部出列为止.编程打印出列顺序.\n);printf(****************************************************************\n);main();break;case2:printf(\n请输入总人数n：);scanf(%d,&n);printf(请输入开始上限数m：);scanf(%d,&m);createList(&ppHead,n);printf(\n);printf(出队顺序：\n);jose(ppHead,m);printf(\n约瑟夫环游戏结束!\n);main();break;case0:exit(0);default:system(cls);printf(\n您选择的操作有误，请重新选择...\n\n\n);main();}}return0;}2.链表的创建9/*创建单向循环链表ppHead，人数个数为n，并输入每个人的密码值，若建立失败则生成头结点，让cur指向他，若建立成功则插入结点P，cur指向的数据元素为p,后续为空的节点，再把P插入循环链表ppHead中*/根据流程图，创建链表函数程序如下：voidcreateList(LNode**ppHead,intn){inti,m_pwd;LNode*p,*cur;//cur:浮标指针for(i=1;i=n;i++){printf(输入第%d个人的密码：,i);scanf(%d,&m_pwd);//输入持有密码p=createNode(i,m_pwd);//调用构造结点函数if(*ppHead==NULL)//如果头结点为空{否是createList（）;从主函数中获取玩家信息n如果n0创建循环单链表，储存各个玩家密码退出创建链表完成返回主函数main()创建储存玩家密码的循环单链表的方法Main()函数图5创建链表函数的数据流程图10*ppHead=cur=p;//生成头结点，让cur指向他cur-next=*ppHead;//cur的指针域指向自身}else//如果不为空，则插入结点{p-next=cur-next;cur-next=p;cur=p;//cur指向新插入结点}}printf(完成创建！\n);//提示链表创建完成}3.出队处理Main()函数从循环链表中按初始密码依次扫描，找出对应的玩家序列输出其持有的密码i=ppHead-pwd;j=ppHead-num;移动浮标指针m_pwd=ppHead-pwd;输出密码后，删除相应的结点，并释放所占的储存空间free(ppHead);ppHead=p-next;执行完后返回主函数jose()；出队函数出队处理的方法图6出队函数的数据流程图11/*p指向要删除节点的前一个节点，ppHead指向要删除的节点，使p=ppHead，ppHead再指向要删除节点的下一个节点，使p和ppHead链接，输出p指向节点的编号和密码值，释放ppHead，如此循环，直至把所有节点都打印和删除为止！*/根据流程图，出队函数程序如下：voidjose(LNode*ppHead,intm_pwd){inti,j;LNode*p,*p_del;//定义指针变量for(i=1;p!=ppHead;i++){for(j=1;jm_pwd;++j){p=ppHead;//p赋值为ppHead，p指向要删除结点的前一个结点ppHead=ppHead-next;//ppHead指向下一个元素}p-next=ppHead-next;//p结点与头结点链接i=ppHead-pwd;//i赋值为ppHead-pwdj=ppHead-num;//j赋值为ppHead-num，j为要删除的密码值printf(第%d个人出列，密码：%d\n,j,i);m_pwd=ppHead-pwd;//m_pwd赋值为ppHead-pwdfree(ppHead);//释放头结点ppHead=p-next;//ppHead重新赋值给p-next,即释放前的ppHead-pwd指针//删除报数结点}i=ppHead-pwd;//i赋值为ppHead-pwdj=ppHead-num;//j赋值为ppHead-numprintf(最后一个出列是%d号，密码是:%d\n,j,i);free(ppHead);//释放头结点}4.约瑟夫环说明模块voidinstruction(){printf(****************************************************************\n);printf(约瑟夫环:\n);printf(编号为1,2,3,4…,n的n个人按顺时针方向围坐一圈,每人持有一个密\n);printf(码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\n);printf(按顺时针方向自1开始顺序报数,报到时停止.报m的人出列，将他的密码\n);12printf(m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,\n);printf(直到所有人全部出列为止.编程打印出列顺序.\n);printf(******************************************************\n);return0;}5.菜单模块voidmenu(){printf(**************************约瑟夫环*****************************\n);printf(\n);printf([1]约瑟夫环问题的阐述\n);printf([2]按要求求解约瑟夫环\n);printf([0]退出\n);printf(**************************欢迎使用！****************************\n);}四、程