《数据结构课程设计报告约瑟夫环.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告约瑟夫环.docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课程设计报告约瑟夫环 课程设计 课程名称：程序设计、数据结构课题名称：约瑟夫环 班级： 学号： 姓名： 指导教师： 湖南理工学院计算机学院 2022年12月 一、问题描述 约瑟夫环问题描述的是：设编号为1，2，n的n（n0）个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。如下图分析： 二、逻辑设计 1、循环链表抽
2、象数据类型定义 typedef struct LNode/定义单循环链表中节点的结构 int num;/编号 int pwd;/password struct LNode *next;/指向下一结点的指针 LNode; 2、本程序包含一下几个模块 （1）构造结点模块 LNode *createNode(int m_num,int m_pwd) 图2 约瑟夫环原理演示图 LNode *p; p=(LNode *)malloc(sizeof(LNode);/生成一个结点 p-num=m_num;/把实参赋给相应的数据域 p-pwd=m_pwd; p-next=NULL;/指针域为空 return
3、p; （2）创建链表模块 void createList(LNode *ppHead,int n) （3）出队处理模块 void jose(LNode *ppHead,int m_pwd) （4）约瑟夫环说明输出模块 void instruction() （5）菜单模块 void menu() （6）主函数模块 int main（） 函数的调用关系图如下： 三、详细设计 1.主函数 图4 主函数数据流程图 根据流程图，主函数程序如下： int main() int n,m,x; LNode *ppHead=NULL; menu(); for(;) printf(n请选择要执行的操作：); sc
4、anf(%d,&x); system(cls); switch(x) case 1: printf(* *n); printf(约瑟夫环:n); printf( 编号为1,2,3,4,n的n个人按顺时针方向围坐一圈,每人持有一个密n); printf(码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始n); printf(按顺时针方向自1开始顺序报数,报到m时停止.报m的人出列，将他的密码n); printf(m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,n); printf(直到所有人全部出列为止.编程打印出列顺序.n); printf(* *n);
5、 main(); break; case 2: 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; case 0: exit(0); default: system(cls); printf(n您选择的操作有误，请重新选择.nnn); main(); return 0; 2.链表的创建 图5 创建链表函数的数据流
6、程图 /*创建单向循环链表ppHead，人数个数为n，并输入每个人的密码值，若建立失败则生成头结点，让cur指向他，若建立成功则插入结点P，cur指向的数据元素为p,后续为空的节点，再把P插入循环链表ppHead中*/ 根据流程图，创建链表函数程序如下： void createList(LNode *ppHead,int n) int i,m_pwd; LNode *p,*cur; /cur:浮标指针 for(i=1;inext=*ppHead; /cur的指针域指向自身 else /如果不为空，则插入结点 p-next = cur-next; cur-next = p; cur= p; /c
7、ur指向新插入结点 printf(完成创建！n); /提示链表创建完成 3.出队处理 图6 出队函数的数据流程图 /*p指向要删除节点的前一个节点，ppHead指向要删除的节点，使p=ppHead， ppHead再指向要删除节点的下一个节点，使p和ppHead链接，输出p指向节点的编号和密码值，释放ppHead，如此循环，直至把所有节点都打印和删除为止！*/ 根据流程图，出队函数程序如下： void jose(LNode *ppHead,int m_pwd) int i,j; LNode *p,*p_del; /定义指针变量 for(i=1;p!=ppHead;i+) for(j=1;jnex
8、t; /ppHead指向下一个元素 p-next = ppHead-next; /p结点与头结点链接 i=ppHead-pwd;/i赋值为ppHead-pwd j=ppHead-num; /j赋值为ppHead-num，j为要删除的密码值 printf(第%d个人出列，密码：%dn,j,i); m_pwd=ppHead-pwd;/m_pwd赋值为ppHead-pwd free(ppHead); /释放头结点 ppHead=p-next; /ppHead重新赋值给p-next,即释放前的ppHead-pwd指针/删除报数结点 i=ppHead-pwd; /i赋值为ppHead-pwd j=ppH
9、ead-num; /j赋值为ppHead-num printf(最后一个出列是%d号，密码是:%dn,j,i); free(ppHead); /释放头结点 4. 约瑟夫环说明模块 void instruction() printf(* *n); printf(约瑟夫环:n); printf( 编号为1,2,3,4,n的n个人按顺时针方向围坐一圈,每人持有一个密n); printf(码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始n); printf(按顺时针方向自1开始顺序报数,报到时停止.报m的人出列，将他的密码n); printf(m作为新的m值,从他在顺时针方向上的下
10、一人开始重新从1报数,如此下去,n); printf(直到所有人全部出列为止.编程打印出列顺序.n); printf(*n); return 0; 5. 菜单模块 void menu() printf(*约瑟夫环*n); printf( n); printf( 1约瑟夫环问题的阐述n); printf( 2按要求求解约瑟夫环n); printf( 0退出n); printf(* 欢迎使用！*n); 四、程序代码(根据前面的思想分析，算法整理得到完整的可编译可调试的程序) 源代码： #include /输入输出函数头文件 #include /字符串转短整形函数的头文件10140219 typedef struct LNode /定义单循环链表中节点的结构 int num;/编号 int pwd;/password struct LNode *next; /指向下一结点的指针 LNode; /*构造结点*/ LNode *createNode(int m_num,int m_pwd) LNode *p; p=(LNode *)malloc(sizeof(LNode); /生成一个结点 p-num=m_num; /把实参赋给相应的数据域 p-pwd=m_pwd;