资源描述：
《约瑟夫环-课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、目录1题目11.1问题描述11.2功能要求12算法思想描述：12.1算法概述：12.2算法具体分析23程序结构33.1主函数流程图33.2josephus()函数流程图44实验结果与分析54.1实验测试中的关键代码与各模块测试结果的分析与说明54.2试验过程中所遇到的问题分析与解决115课程设计总结12参考文献131题目约瑟夫环1.1问题描述编号为1，2…n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始
2、重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。1.2功能要求A利用单循环链表作为存储结构模拟此过程；B键盘输入总人数、初始报数上限值m及各人密码；C按照出列顺序输出各人的编号。2算法思想描述：2.1算法概述：建立一个循环单链表,然后输入要建立结点的个数,在每个结点输入一个密码,同时按输入时的顺序进行编号:1,2,3,4,……n.任选一个正整数x作为初始报数上限值.从定义的那个头结点开始,数到x,输出该结点所储存的编号和密码.并将该密码作为新的x值,同时还将该密码所在的结点删除.如此循环链表还剩最后一个数据的时候停止此循环.再将最后一个没在循环里面的编号和
3、密码另外输出.循环链表如图1所示:13图22.2算法具体分析（1）window(),switch(),upbar（）,downbar（）,key()这几个函数是构建本程序菜单所必须的函数.window()用于开窗口,以坐标的形式开辟一个窗口,并且可以在窗口里面储存数据.switch()创建菜单选项,key()主要用于获取键盘上的字符(包括字母和方向键,enter键),upbar()和downbar()实现光条的上移和下移.textbackground()，textcolor()。窗口背景颜色和里面文本颜色的设置。（2）InitList()初始化循环链表,开辟一个空间作为头结点,并让
4、L=L->next先让它指向自己,令链表循环起来.ListInsert()向循环链表里面插入数据(包括编号和密码),DispList()以定义的头结点为第一个数,输出循环链表.（3）josephus()主要用于解决约瑟夫环问题,首先调用InitList()建立循环链表,再调用ListInsert()插入数据,再调用DispList()把储存的数据输出来.定义两个指针s和q,再定义count作为计数器,此时需要任意输入一个正整数x作为初始报数上限值,当计数器count=x时就把该指针所指向的数据输出并把该数据赋给x,作为新的报数上限值.然后删除该结点,s和q的主要作用是在把输出数据之
5、后的结点删除.如此循环,直到还剩最后一个结点,同时定义a[i],b[i]用来储存编号和密码。（4）passcode（）把josephus()里所储存到数组a[i],b[i]的数据传递到passcode（）,方便在退出josephus()函数之后还可以再次查看。（5）about()约瑟夫环问题的解析说明，增强使用者对本程序的理解。133程序结构3.1主函数流程图流程图1开始选择选项quitJosephus()About()Passcode()结束等待进入程序Welcome主菜单输出所储存的编号和密码选Ｙ退出选Ｎ返回选Ｙ退出选Ｎ返回程序说明解决约瑟夫环问题并储存密码和编号133.2jo
6、sephus()函数流程图流程图2134实验结果与分析上述程序在win-TC环境下加以实现，经过多次的测试，程序运行正确。4.1实验测试中的关键代码与各模块测试结果的分析与说明do{ky=key();/*检查按键*/switch(ky){caseKey_Q:{y=5,ky=Key_ENTER;}break;caseKey_A:{y=6,ky=Key_ENTER;}break;caseKey_B:{y=7,ky=Key_ENTER;}break;caseKey_C:{y=8,ky=Key_ENTER;}break;caseKey_DOWN:if(y<8){upbar(y);y++;}
7、break;caseKey_UP:if(y>5){downbar(y);y--;}break;}}{/*创建一个弹出式主菜单*/system("cls");/*清屏*/window(2,2,30,10);/*创建主菜单并设置好字体颜色*/textbackground(13);textcolor(15);clrscr();window(3,3,29,9);textbackground(1);textcolor(4);clrscr();gotoxy(3,3);cprint
