C语言课程设计报告约瑟夫环胡存夫.doc

沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称：课程设计名称：C 语言课程设计语言课程设计 课程设计题目：约瑟夫环课程设计题目：约瑟夫环 院（系）：计算机学院 专 业：计算机科学与技术 班 级：3410301 学 号：2013040103023 姓 名： 胡存夫 指导教师： 丁一军 沈阳航空航天大学课程设计报告 I 目目 录录 1 课程设计介绍课程设计介绍.1 1.1 课程设计内容及要求.1 1.2 系统需求.1 2 课程设计原理课程设计原理.3 2.1 课设题目粗略分析.3 2.2.1 功能模块图5 2.2.2 流程图分析5 3 调试与分析调试与分析.10 3.1 调试过程.10 参考文献参考文献.16 附附 录（关键部分程序清单）录（关键部分程序清单）.16 沈阳航空航天大学课程设计报告 1 1 课程设计介绍 1.1 课程设计内容及要求课程设计内容及要求 设计程序，实现算术表达式求值，系统主要功能如下： 1.问题描述 约瑟夫环问题的一种描述是：编号为 1,2,n 的 n 个人按顺时针方向围坐 一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限 值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。 报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人 开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序 求出出列顺序。 2.分析约瑟夫问题： n 个人围成圈，每人各持一个密码，任选一个正整数作为报数上限值 m， 从第一个人开始，数到第 m 个人，删除并以出列者密码作为新的 m 值，从下 一个人开始进行第二轮操作，直到所有人都出列。 设计 1.2 系统需求系统需求 1.需求 此程序最终目的是要求出所有人的出列顺序 沈阳航空航天大学课程设计报告 2 2.功能描述 1 2 3 4 5 6 7 8 9 0 这是第一个人， 他的密码是 “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 约瑟夫环功能示图 沈阳航空航天大学课程设计报告 3 2 课程设计原理 2.1 课设题目粗略分析课设题目粗略分析 根据课设题目要求，拟将整体程序分为四大模块。此四个模块相互独立，没有嵌 套调用的情况，以下是五个模块： （1）创建链表模块 void createList(LNode *ppHead,int n) （2）出队处理模块 void jose(LNode *ppHead,int m_pwd) （3）约瑟夫环说明输出模块 void instruction() （4）菜单模块 void menu() （5）主函数模块 int main（） 沈阳航空航天大学课程设计报告 4 原理图介绍原理图介绍 3271484 约瑟夫环原理演示图 1 234567 第二部：第一次停下 的位置，此时 6 号出 列，并将他的值作为 新的 m 值，即：新 的 m=8；从 7 好开 始继续向下走 8 次， 到 1 号的位置 最后排序后的密 码序列： （本图只演示前 两步） 8 第三步： 第二次，1 号出列 第四步：第三 次，4 号出列 3 第一步：给第 一个人赋初始 密码为：20 则从它开始向 下走 20 次， 到 6 号位置 24 174 6147235 图 2.1 约瑟夫环原理演 示图 沈阳航空航天大学课程设计报告 5 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() Case 0:default : 输入 0，退 出 exit(0)； 2.2.2 流程图分析流程图分析 沈阳航空航天大学课程设计报告 6 1. 否 是 createList（）; 从主函数中获取 玩家信息 n 如果 n0 创建循环单链表， 储存各个玩家密 码 退出 创建链表完成返 回主函数 main() 创建储存玩家密 码的循环单链表 的方法 Main()函 数 图 2.3 创建链表函数的数据流 程图 2. 沈阳航空航天大学课程设计报告 7 Main()函 数 从循环链表中按初 始密码依次扫描， 找出对应的玩家序 列 输出其持有的密码 i=ppHead-pwd; j=ppHead-num; 移动浮标指针 m_pwd=ppHead- pwd; 输出密码后，删除相应的 结点，并释放所占的储存 空间 free(ppHead); ppHead=p-next; 执行完后返 回主函数 jose()；出队函 数出队处理 的方法 图 2.4 出队函数的数据流 程图 3. void instruction() printf(“* n“); printf(“约瑟夫环:n“); printf(“ 编号为 1,2,3,4,n 的 n 个人按顺时针方向围坐一圈,每人持有一个 密n“); printf(“码(正整数).一开始任选一个正整数作为报数的上限值 m,从第一个人开 沈阳航空航天大学课程设计报告 8 始n“); printf(“按顺时针方向自 1 开始顺序报数,报到时停止.报 m 的人出列，将他的 密码n“); printf(“m 作为新的 m 值,从他在顺时针方向上的下一人开始重新从 1 报数,如 此下去,n“); printf(“直到所有人全部出列为止.编程打印出列顺序.n“); printf(“*n“); return 0; 4 菜单模块 void menu() printf(“*约瑟夫环 *n“); printf(“ n“); printf(“ 1约瑟夫环问题的阐述 n“); printf(“ 2按要求求解约瑟夫环 n“); printf(“ 0退出 n“); printf(“* 欢迎使用！ *n“); 沈阳航空航天大学课程设计报告 9 5. 沈阳航空航天大学课程设计报告 10 Main()开始 Menu()功能菜单 功能 1：约瑟 夫环说明 功能 2：按要 求求解约瑟 夫环 功能 3：退出 系统 输入总人数 n 输入开始上线数： m 输入每个玩家的密码 调用： createList( jose(ppHead,m);函数求解所 需的密码序列 选择要执 行的操作 程序运行完， 自动返回到功 能菜单 图 2.5 主函数数据流程 图 3 调试与分析 3.1 调试过程调试过程 在调试程序是主要遇到一下几类问题： 这是一个使用循环链表的经典问题。本程序开始运行界面如下： 沈阳航空航天大学课程设计报告 11 选择 1 进入约瑟夫环问题阐述。 图 3.1 约瑟夫环开始运行 界面 图 3.2 约瑟夫环问题阐述 沈阳航空航天大学课程设计报告 12 选择 2，输入下列数据测试： 请输入总人数 n：7 请输入开始上限数 m：20； 请依次输入每个人的密码：3 1 7 2 4 8 4 出队顺序：6 1 4 7 2 3 5 图 3.3 约瑟夫环测试 1 沈阳航空航天大学课程设计报告 13 继续选择 2，输入下列数据测试： 请输入总人数 n：5 请输入开始上限数 m：30 请依次输入每个人的密码：3 4 5 6 7 出队顺序：5 3 1 2 4 图 3.4 约瑟夫环测试 2 沈阳航空航天大学课程设计报告 14 继续选择 2，输入下列数据测试： 请输入总人数 n：8 请输入开始上限数 m：14 请依次输入每个人的密码：3 4 5 6 7 8 9 10 出队顺序：6 7 2 8 3 5 1 4 沈阳航空航天大学课程设计报告 15 测试完成，选择 0 退出。. 图 3.5 约瑟夫环测试 3 沈阳航空航天大学课程设计报告 T1TJmEdtgTYWOA0I 16 参考文献 1 严蔚敏，吴伟民.数据结构M.北京：清华大学出版社，2007. 2 张长海，陈娟.C 程序设计M.北京：高等教育出版社，2004. 3 谭浩强.C 程序设计M.北京：清华大学出版社，2005 4严蔚敏，吴伟民.数据结构题集（C 语言版） .清华大学出版社. 5DATA STRUCTURE WITH C+. William Ford,William Topp .清华大学出 版社（影印版）. 附 录（关键部分程序清单） 程序代码 #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; 沈阳航空航天大学课程设计报告 T1TJmEdtgTYWOA0I 17 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; 沈阳航空航天大学课程设计报告 T1TJmEdtgTYWOA0I 18 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-pwd free(ppHead);/释放头结点 ppHead=p-next;/ppHead 重新赋值给 p-next,即释放前的 ppHead-pwd 指 针/删除报数结点 i=ppHead-pwd;/i 赋值为 ppHead-pwd 沈阳航空航天大学课程设计报告 T1TJmEdtgTYWOA0I 19 j=ppHead-num;/j 赋值为 ppHead-num printf(“最后一个出列是%d 号，密码是:%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(“*n“); return 0; void menu() printf(“*约瑟夫环 *n“); printf(“ n“); printf(“ 1约瑟夫环问题的阐述 沈阳航空航天大学课程设计报告 T1TJmEdtgTYWOA0I 20 n“); printf(“ 2按要求求解约瑟夫环 n“); printf(“ 0退出 n“); printf(“* 欢迎使用！ *n“); /*主函数模块*/ int main() int n,m,x; LNode *ppHead=NULL; menu(); printf(“n 请选择要执行的操作：“); scanf(“%d“, 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 的人出列，将他的密 沈阳航空航天大学课程设计报告 T1TJmEdtgTYWOA0I 21 码n“); printf(“m 作为新的 m 值,从他在顺时针方向上的下一人开始重新从 1 报数,如此下 去,n“); printf(“直到所有人全部出列为止.编程打印出列顺序.n“); printf(“* n“); main(); break; case 2: printf(“n 请输入总人数 n：“); scanf(“%d“, printf(“请输入开始上限数 m：“); scanf(“%d“, createList( printf(“n“); printf(“出队顺序：n“); jose(ppHead,m); printf(“n 约瑟夫环游戏结束!n“); main(); break; case 0: exit(0); default: system(“cls“); printf(“n 您选择的操作有误，请重新选择.nnn“); main(); 沈阳航空航天大学课程设计报告 T1TJmEdtgTYWOA0I 22 return 0; 沈阳航空航天大学课程设计报告 23 课程设计总结： 本次课程设计涉及到的范围很广，让本人能够比较系统的对 C 语言和数据结构 进行一次整理和复习。同时有了很多的体会和经验。 巩固了以前学过的 C 语言的知识，在这次课程设计中我体会到 C 语言超强的逻 辑性，能够熟练使用 VC+的编译环境，也对这两门课程有了新的认识，他们 既有联系，又相互区别，在编写程序过程中要灵活应用 对数据结构的理解有待加强，算法的知识面也有待于提高。不同的人会选择不 同的算法，所以即使同样的程序，不同的人必然会设计出不同的方案，所以以 后的学习生活中，一定要广泛涉猎，掌握更多更好的解决问题的方法。 此次设计让我意识到程序设计是脑力劳动和体力劳动相结合的，没有平时基础 的训练是不会写出高效的算法。 此次课程设计时间虽短，但却课设的过程是短暂的，但我所收获的是永恒的。 它让我尝到了学习的快乐，成功的喜悦，更让我懂得了不少做人的道理。要完 成一项任务或把东西学好就必须有足够的信心，持久的耐心，有面对困难无所 畏惧的精神，这对我日后的学习和生活产生了深远一个影响。 指导教师评语： 指导教师(签字)： 年 月 日 课程设计成绩