数据结构专业课程设计方案报告约瑟夫环.doc

*实践教学* 兰州理工大学软件职业技术学院春季学期算法和数据结构课程设计题 目： 约瑟夫环 专业班级： 姓 名： 学 号： 指导老师： 成 绩： 摘要约瑟夫环问题是经典线性表应用实例，其开发关键包含后台数据库建立和维护和前端应用程序开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好库。而对于后者则要求应用程序功效完备，易使用等特点。 经过分析，我们使用 MICROSOFT企业Microsoft Visual C+6.0开发工具，利用其提供多种面向对象开发工具，尤其是数据窗口这一能方便而简练操纵数据库智能化对象，首先在短时间内建立系统应用原型，然后，对初始原型系统进行需求迭代，不停修正和改善，直到形成用户满意可行系统。关键词：单循环链表；c语言；约瑟夫环； 序言数据结构是研究数据元素之间逻辑关系一门课程，和数据元素及其关系在计算机中存放表示和对这些数据所施加运算。该课程设计目标是经过课程设计综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程关键内容。此次课程设计内容是用单循环链表模拟约瑟夫环问题，循环链表是一个首尾相接链表，其特点是无须增加存放容量，仅对表链接方法稍作改变，使表处理愈加灵活，约瑟夫环问题就是用单循环链表处理一个实际应用。经过这个设计实例，了解单链表和单循环链表相同和不一样之处，深入加深对链表结构类型及链表操作了解。经过该课程设计，能利用所学知识，能上机处理部分实际问题，了解并初步掌握设计、实现较大程序完整过程，包含系统分析、编码设计、系统集成、和调试分析，熟练掌握数据结构选择、设计、实现和操作方法，为深入应用开发打好基础。目录摘要1序言2目录3正文4一、问题描述4二、逻辑设计5三、具体设计7四、程序代码13五、程序调试和测试13设计总结18参考文件19致谢20附录21正文一、问题描述约瑟夫环问题描述是：设编号为1，2，nn（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约瑟夫环问图解3271484约瑟夫环原理演示图1234567第二部：第一次停下位置，此时6号出列，并将她值作为新m值，即：新m=8；从7好开始继续向下走8次，到1号位置最终排序后密码序列：（本图只演示前两步）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(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 *ppHead,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);函数求解所需密码序列选择要实施操作程序运行完，自动返回到功效菜单图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,nn个人按顺时针方向围坐一圈,每人持有一个密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(%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. 链表创建否是createList（）;从主函数中获取玩家信息n假如n0创建循环单链表，储存各个玩家密码退出创建链表完成返回主函数main()创建储存玩家密码循环单链表方法Main()函数图5 创建链表函数数据步骤图/*创建单向循环链表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;/cur指向新插入结点 printf(完成创建！n); /提醒链表创建完成 3. 出队处理Main()函数从循环链表中按初始密码依次扫描，找出对应玩家序列输出其持有密码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 *ppHead,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;/ppHead重新赋值给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,nn个人按顺时针方向围坐一圈,每人持有一个密n); printf(码(正整数).一开始任选一个正整数作为报数上限值m,从第一个人开始n); printf(按顺时针方向自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); 四、程序代码见附录源程序。五、程序调试和测试1. 调用模块时，结点结构调用和其它模块产生冲突，造成每一行全部出现两次错误，加入子函数申明后错误消失。2 . 刚开始时曾忽略了部分变量参数标识&和“*”，使调试程序时费时不少。以后应重视确定参数变量和赋值属性区分和标识。3. 此次课程设计采取数据抽象程序设计方法，将程序划分为三个层次结构：元素节点、单向循环链表，主控制模块。思绪较为清楚，实现调用顺利。 经过此次试验，使我对数据结构这门课程有了深入了解，每一个程序经过需求分析、概要设计、具体设计以后，思绪即清楚展现，程序也很快就出来了，最终经过调试、运行又有新体验。这是一个使用循环链表经典问题。本程序开始运行界面以下：图7 约瑟夫环开始运行界面选择1进入约瑟夫环问题叙述。图8 约瑟夫环问题叙述选择2，输入下列数据测试：请输入总人数n：7请输入开始上限数m：20；请依次输入每个人密码：3 1 7 2 4 8 4出队次序：6 1 4 7 2 3 5图9 约瑟夫环测试1继续选择2，输入下列数据测试：请输入总人数n：5请输入开始上限数m：30请依次输入每个人密码：3 4 5 6 7 出队次序：5 3 1 2 4图10 约瑟夫环测试2继续选择2，输入下列数据测试：请输入总人数n：8请输入开始上限数m：14请依次输入每个人密码：3 4 5 6 7 8 9 10出队次序：6 7 2 8 3 5 1 4图11 约瑟夫环测试3测试完成，选择0退出。 设计总结我这次数据结构课程设计题目是:约瑟夫环,经过对该题目标设计,我加深了对数据结构及存放结构了解,深入地了解和掌握了书本中所学多种数据结构，尤其是对单循环链表上基础运算实现,学会了怎样把学到知识用于处理实际问题,锻炼了自己动手能力。经过这次数据结构课程设计，我感受最深就是对于循环链表使用，能够说对循环链表有了比以前更深入认识，以前只是一知半解，假如只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大收获就在于对循环链表有了一定了解，包含其中一系列操作，如建立一个循环链表，删除链表中一个结点，增加一个结点等。在调试程序时候我也有所体会，即使约瑟夫环问题不是极难，但调试时候还是会出现很多错误，所以我们不能认为轻易就不认真对待。在以后学习中，要能不停发觉问题，提出问题，处理问题，从不足之处出发，在不停学习中提升自己。两周课程设计很短暂，但其间内容是很充实，在其中我学习到了很多平时书本中无法学到东西，积累了经验，锻炼了自己分析问题，处理问题能力，并学会了怎样将所学各课知识融会，组织起来进行学习，总而言之这两周中我学到很多，受益匪浅。参考文件1严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社.2严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社.3DATA STRUCTURE WITH C+. William Ford,William Topp .清华大学出版社（影印版）. 4谭浩强.c语言程序设计. 清华大学出版社. 致谢这次课程设计，我们两人一个小组去完成我们自己课程，不过还是得到了来自很多方面帮助。在此首先要感谢学院提供给我这次实践机会，让我们有机会贴近现实，感受成功喜悦；其次要感谢试验机房老师提供优良试验设备供我们做课设，正是这种良好课设环境让我们整个课设过程心情全部很愉快。再次要感谢指导老师们辛勤指导，每当我们碰到疑难问题时，是她们一次次不厌其烦解释和悉心指导，我们才能闯过一个个难关，抵达胜利彼岸，是她们给我们提供了一次宝贵检验自己机会。最终也要感谢同学们帮助，有了她们支持使我碰到任何困难全部不是一个人在战斗。感谢全部在我课程设计过程中帮助过我人！附录 源代码：#include /输入输出函数头文件#include /字符串转短整形函数头文件10140219/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;/指针域为空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指向新插入结点 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;/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号，密码是:%dn,j,i); free(ppHead);/释放头结点void instruction() printf(*n); printf(约瑟夫环:n); printf( 编号为1,2,3,4,nn个人按顺时针方向围坐一圈,每人持有一个密n); printf(码(正整数).一开始任选一个正整数作为报数上限值m,从第一个人开始n); printf(按顺时针方向自1开始次序报数,报到时停止.报m人出列，将她密码n); printf(m作为新m值,从她在顺时针方向上下一人开始重新从1报数,如此下去,n); printf(直到全部些人全部出列为止.编程打印出列次序.n); printf(*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( 编号为1,2,3,4,nn个人按顺时针方向围坐一圈,每人持有一个密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(%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;