《C语言课程设计报告约瑟夫环胡存夫.doc》由会员分享，可在线阅读，更多相关《C语言课程设计报告约瑟夫环胡存夫.doc（25页珍藏版）》请在金锄头文库上搜索。
1、 沈阳航空航天大学 课 程 设 计 报 告 课程设计名称：C语言课程设计 课程设计题目：约瑟夫环 院（系）：计算机学院 专 业：计算机科学与技术 班 级：3410301 学 号：2013040103023 姓 名： 胡存夫 指导教师： 丁一军沈阳航空航天大学课程设计报告 目 录1 课程设计介绍11.1 课程设计内容及要求11.2 系统需求12 课程设计原理32.1 课设题目粗略分析32.2.1 功能模块图52.2.2 流程图分析53 调试与分析103.1 调试过程10参考文献16附 录（关键部分程序清单）16 I 1 课程设计介绍1.1 课程设计内容及要求设计程序，实现算术表达式求值，系统主要
2、功能如下：1.问题描述 约瑟夫环问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。2.分析约瑟夫问题： n个人围成圈，每人各持一个密码，任选一个正整数作为报数上限值m，从第一个人开始，数到第m个人，删除并以出列者密码作为新的m值，从下一个人开始进行第二轮操作，直到所有人都出列。设计1.2 系统需求1.需求 此程
3、序最终目的是要求出所有人的出列顺序2.功能描述 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.1 约瑟夫环功能示图沈阳航空航天大学课程设计报告 2 课程设计原理2.1 课设题目粗略分析根据课设题目
4、要求，拟将整体程序分为四大模块。此四个模块相互独立，没有嵌套调用的情况，以下是五个模块：（1）创建链表模块void createList(LNode *ppHead,int n)（2）出队处理模块void jose(LNode *ppHead,int m_pwd)（3）约瑟夫环说明输出模块void instruction()（4）菜单模块void menu()（5）主函数模块int main（）原理图介绍3271484约瑟夫环原理演示图1234567第二部：第一次停下的位置，此时6号出列，并将他的值作为新的m值，即：新的m=8；从7好开始继续向下走8次，到1号的位置最后排序后的密码序列：（本图
5、只演示前两步）8第三步：第二次，1号出列第四步：第三次，4号出列3第一步：给第一个人赋初始密码为：20则从它开始向下走20次，到6号位置241746147235图2.1 约瑟夫环原理演示图2.2.1 功能模块图Case 2:建立的约瑟夫环,并输出已建立的约瑟夫环：createList(LNode *ppHead,int n)输出该约瑟夫环的每个人的出列顺序: jose(LNode *ppHead,int m_pwd)图2.2 约瑟夫环函数调用关系图菜单函数；void menu()主函数调用函数；main()Case 1：一个简单的输出函数，用于说明约瑟夫环；void instruction()
6、Case 0:default : 输入0，退出 exit(0)；2.2.2 流程图分析 1. 否是createList（）;从主函数中获取玩家信息n如果n0创建循环单链表，储存各个玩家密码退出创建链表完成返回主函数main()创建储存玩家密码的循环单链表的方法Main()函数图2.3 创建链表函数的数据流程图2. Main()函数从循环链表中按初始密码依次扫描，找出对应的玩家序列输出其持有的密码i=ppHead-pwd; j=ppHead-num;移动浮标指针m_pwd=ppHead-pwd;输出密码后，删除相应的结点，并释放所占的储存空间free(ppHead); ppHead=p-next
7、;执行完后返回主函数jose()；出队函数出队处理的方法图2.4出队函数的数据流程图3. 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(直到所有人全部出列为止.编程打印出列顺序
8、.n); printf(*n); return 0;4菜单模块void menu()printf(*约瑟夫环 *n);printf( n);printf( 1约瑟夫环问题的阐述 n);printf( 2按要求求解约瑟夫环 n);printf( 0退出 n);printf(* 欢迎使用！ *n);5. Main()开始Menu()功能菜单功能1：约瑟夫环说明功能2：按要求求解约瑟夫环功能3：退出系统输入总人数n输入开始上线数：m输入每个玩家的密码调用：createList(&ppHead,n);jose(ppHead,m);函数求解所需的密码序列选择要执行的操作程序运行完，自动返回到功能菜单图2
9、.5 主函数数据流程图3 调试与分析3.1 调试过程在调试程序是主要遇到一下几类问题： 这是一个使用循环链表的经典问题。本程序开始运行界面如下：图3.1 约瑟夫环开始运行界面选择1进入约瑟夫环问题阐述。图3.2约瑟夫环问题阐述选择2，输入下列数据测试：请输入总人数n：7请输入开始上限数m：20；请依次输入每个人的密码：3 1 7 2 4 8 4出队顺序：6 1 4 7 2 3 5图3.3 约瑟夫环测试1继续选择2，输入下列数据测试：请输入总人数n：5请输入开始上限数m：30请依次输入每个人的密码：3 4 5 6 7 出队顺序：5 3 1 2 4图3.4 约瑟夫环测试2继续选择2，输入下列数据测
10、试：请输入总人数n：8请输入开始上限数m：14请依次输入每个人的密码：3 4 5 6 7 8 9 10出队顺序：6 7 2 8 3 5 1 4图3.5 约瑟夫环测试3测试完成，选择0退出。.沈阳航空航天大学课程设计报告 参考文献1 严蔚敏，吴伟民.数据结构M.北京：清华大学出版社，2007.2 张长海，陈娟.C程序设计M.北京：高等教育出版社，2004. 3 谭浩强.C程序设计M.北京：清华大学出版社，2005.4严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社.5DATA STRUCTURE WITH C+. William Ford,William Topp .清华大学出版社（影印
11、版）. 附 录（关键部分程序清单）程序代码#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; /*创建循环链表*/
