数据结构课程设计报告约瑟夫环

1、课 程 设 计课程名称： 程序设计、数据结构 课题名称： 约瑟夫环 班 级： 学 号： 姓 名： 指导教师： 湖南理工学院计算机学院2011年12月一、问题描述约瑟夫环问题描述的是：设编号为1，2，n的n（n0）个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。如下图分析：1234567890这是第一个人，他的密码是“1”

2、，个他输一个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号出列，并将他的值作为新的m值，即：新的m=8；从7好开始继续向下走8次，到1号的位置最后排序后的密码序列：（

3、本图只演示前两步）8第三步：第二次，1号出列第四步：第三次，4号出列3第一步：给第一个人赋初始密码为：20则从它开始向下走20次，到6号位置241746147235图2 约瑟夫环原理演示图二、逻辑设计1、循环链表抽象数据类型定义typedef struct LNode/定义单循环链表中节点的结构 int num;/编号 int pwd;/passwordstruct LNode *next;/指向下一结点的指针LNode;2、本程序包含一下几个模块（1）构造结点模块LNode *createNode(int m_num,int m_pwd)LNode *p;p=(LNode *)malloc(

4、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 main（）函数的调用关系图如下：Case 2:建立的约瑟夫环,并输出已建立的约瑟夫环：createList(LNode *ppH

5、ead,int n)输出该约瑟夫环的每个人的出列顺序: jose(LNode *ppHead,int m_pwd)图3 约瑟夫环函数调用关系图菜单函数；void menu()主函数调用函数；main()Case 1：一个简单的输出函数，用于说明约瑟夫环；void instruction()Case 0:default : 输入0，退出 exit(0)；三、详细设计1. 主函数Main()开始Menu()功能菜单功能1：约瑟夫环说明功能2：按要求求解约瑟夫环功能3：退出系统输入总人数n输入开始上线数：m输入每个玩家的密码调用：createList(&ppHead,n);jose(ppHead,m

6、);函数求解所需的密码序列选择要执行的操作程序运行完，自动返回到功能菜单图4 主函数数据流程图根据流程图，主函数程序如下：int main() int n,m,x; LNode *ppHead=NULL; menu(); for(;) printf(n请选择要执行的操作：); scanf(%d,&x); system(cls); switch(x)case 1: printf(*n); printf(约瑟夫环:n); printf( 编号为1,2,3,4,n的n个人按顺时针方向围坐一圈,每人持有一个密n); printf(码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始n)

7、; printf(按顺时针方向自1开始顺序报数,报到m时停止.报m的人出列，将他的密码n); printf(m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,n); printf(直到所有人全部出列为止.编程打印出列顺序.n); printf(*n); 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约

8、瑟夫环游戏结束!n); main();break; case 0: exit(0); default: system(cls); printf(n您选择的操作有误，请重新选择.nnn); main(); return 0; 2. 链表的创建否是createList（）;从主函数中获取玩家信息n如果n0创建循环单链表，储存各个玩家密码退出创建链表完成返回主函数main()创建储存玩家密码的循环单链表的方法Main()函数图5 创建链表函数的数据流程图/*创建单向循环链表ppHead，人数个数为n，并输入每个人的密码值，若建立失败则生成头结点，让cur指向他，若建立成功则插入结点P，cur指向的数

9、据元素为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; /cur指向新插入结点 printf(完成创建！n); /提示链表创建完成 3. 出队处理Main()函数从循环链表中按初始密码依次扫描，找出对应的玩家序列输出其持有的密码

10、i=ppHead-pwd; j=ppHead-num;移动浮标指针m_pwd=ppHead-pwd;输出密码后，删除相应的结点，并释放所占的储存空间free(ppHead); ppHead=p-next;执行完后返回主函数jose()；出队函数出队处理的方法图6 出队函数的数据流程图/*p指向要删除节点的前一个节点，ppHead指向要删除的节点，使p=ppHead，ppHead再指向要删除节点的下一个节点，使p和ppHead链接，输出p指向节点的编号和密码值，释放ppHead，如此循环，直至把所有节点都打印和删除为止！*/根据流程图，出队函数程序如下：void jose(LNode *ppHe

11、ad,int m_pwd)int i,j;LNode *p,*p_del; /定义指针变量for(i=1;p!=ppHead;i+)for(j=1;jnext; /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-pwdfree(ppHead); /释放头结点ppHead=p-next; /ppHea

12、d重新赋值给p-next,即释放前的ppHead-pwd指针/删除报数结点 i=ppHead-pwd; /i赋值为ppHead-pwdj=ppHead-num; /j赋值为ppHead-numprintf(最后一个出列是%d号，密码是:%dn,j,i); free(ppHead); /释放头结点4. 约瑟夫环说明模块void instruction() printf(*n); printf(约瑟夫环:n); printf( 编号为1,2,3,4,n的n个人按顺时针方向围坐一圈,每人持有一个密n); printf(码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始n); pri

13、ntf(按顺时针方向自1开始顺序报数,报到时停止.报m的人出列，将他的密码n); printf(m作为新的m值,从他在顺时针方向上的下一人开始重新从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); 四、程序代码 (根据前面的思想分析，算法整理得到完整的可编译可调试的程

14、序)源代码：#include /输入输出函数头文件#include /字符串转短整形函数的头文件typedef struct LNode /定义单循环链表中节点的结构 int num;/编号 int pwd;/passwordstruct 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;p-next=NULL; /指针域为

15、空return p; /*创建循环链表*/void createList(LNode *ppHead,int n) /*创建单向循环链表ppHead，人数个数为n，并输入每个人的密码值，若 建立失败则生成头结点，让cur指向他，若建立成功则插入结点P，cur指 向的数据元素为p,后续为空的节点，再把P插入循环链表ppHead中*/int i,m_pwd;LNode *p,*cur;/cur: 浮标指针for(i=1;inext=*ppHead; /cur的指针域指向自身 else /如果不为空，则插入结点 p-next = cur-next;cur-next = p;cur= p; /cur指

16、向新插入结点 printf(完成创建！n); /提示链表创建完成 /*出队处理*/void jose(LNode *ppHead,int m_pwd) /*p指向要删除节点的前一个节点，ppHead指向要删除的节点，使p=ppHead，ppHead再指向要删除节点的下一个节点，使p和ppHead链接，输出p指向节点的编号和密码值，释放ppHead，如此循环，直至把所有节点都打印和删除为止！*/int i,j;LNode *p,*p_del; /定义指针变量for(i=1;p!=ppHead;i+)for(j=1;jnext; /ppHead指向下一个元素p-next = ppHead-next

17、; /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-pwdfree(ppHead);/释放头结点ppHead=p-next; /ppHead重新赋值给p-next,即释放前的ppHead-pwd指针/删除报数结点 i=ppHead-pwd; /i赋值为ppHead-pwdj=ppHead-num; /j赋值为ppHead-numprintf(最后一个出列是%d号，密

18、码是:%dn,j,i); free(ppHead); /释放头结点void instruction() printf(*n); printf(约瑟夫环:n); printf( 编号为1,2,3,4,n的n个人按顺时针方向围坐一圈,每人持有一个密n); printf(码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始n); printf(按顺时针方向自1开始顺序报数,报到时停止.报m的人出列，将他的密码n); printf(m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,n); printf(直到所有人全部出列为止.编程打印出列顺序.n); printf(

19、*n); return 0;void menu()printf(*约瑟夫环 *n);printf( n);printf( 1约瑟夫环问题的阐述 n);printf( 2按要求求解约瑟夫环 n);printf( 0退出 n);printf(* 欢迎使用！ *n); /*主函数模块*/int main() int n,m,x; LNode *ppHead=NULL; menu(); for(;) printf(n请选择要执行的操作：); scanf(%d,&x); system(cls); switch(x) case 1: printf(*n); printf(约瑟夫环:n); printf(

20、编号为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; case 2: printf(n请输入总人数n：); scanf(%d,&n); printf(请输入开始上限数m：); scanf(

21、%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; 。五、程序调试与测试1. 调用模块时，结点结构的调用与其他模块产生冲突，导致每一行都出现两次错误，加入子函数的声明后错误消失。2 . 刚开始时曾忽略了一些变量参数的标识&和“*”，使调试程序时费时不少。今后应重视

22、确定参数的变量和赋值属性的区分和标识。3. 本次课程设计采用数据抽象的程序设计方法，将程序划分为三个层次结构：元素节点、单向循环链表，主控制模块。思路较为清晰，实现调用顺利。 经过本次实验，使我对数据结构这门课程有了进一步的了解，每一个程序经过需求分析、概要设计、详细设计之后，思路即清晰呈现，程序也很快就出来了，最后经过调试、运行又有新的体验。这是一个使用循环链表的经典问题。本程序开始运行界面如下：图7 约瑟夫环开始运行界面选择1进入约瑟夫环问题阐述。图8 约瑟夫环问题阐述选择2，输入下列数据测试：请输入总人数n：7请输入开始上限数m：20；请依次输入每个人的密码：3 1 7 2 4 8 4出队顺序：6 1 4 7 2 3 5图9