约瑟夫环-课程设计

《约瑟夫环-课程设计》由会员分享，可在线阅读，更多相关《约瑟夫环-课程设计（14页珍藏版）》请在毕设资料网上搜索。

1、 目 录 1 题目 . 1 1.1 问题描述 1 1.2 功能要求 1 2 算法思想描述： . 1 2.1 算法概述： 1 2.2 算法具体分析 2 3 程序结构 3 3.1 主函数流程图 3 3.2 josephus()函数流程图 . 4 4 实验结果与分析 5 4.1 实验测试中的关键代码与各模块测试结果的分析与说明 5 4.2 试验过程中所遇到的问题分析与解决 .11 5 课程设计总结 . 12 参 考 文 献 13 1 1 题目题目 约瑟夫环 1.11.1 问题描述问题描述 编号为 1，2 n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数） 。 一开始任选一个正整数作为报

2、数的上限值 m， 从第一个人开始按顺时针方向自 1 开始顺序 报数，报到 m 时停止报数，报 m 的人出列，将他的密码作为新的 m 值，从他的顺时针方 向上的下一个开始重新从 1 报数，如此下去，直至所有人全部出列为止，设计一个程序 求出出列顺序。 1.21.2 功能要求功能要求 A 利用单循环链表作为存储结构模拟此过程； B 键盘输入总人数、初始报数上限值 m 及各人密码； C 按照出列顺序输出各人的编号。 2 算法思想描述：算法思想描述： 2.12.1 算法概述算法概述： 建立一个循环单链表,然后输入要建立结点的个数,在每个结点输入一个密码,同时 按输入时的顺序进行编号:1,2,3,4,

3、n.任选一个正整数x作为初始报数上限值.从定 义的那个头结点开始,数到 x,输出该结点所储存的编号和密码.并将该密码作为新的 x 值, 同时还将该密码所在的结点删除.如此循环链表还剩最后一个数据的时候停止此循环.再 将最后一个没在循环里面的编号和密码另外输出.循环链表如图 1 所示: 2 图 2 2.22.2 算法具体分析算法具体分析 （1） window(),switch(),upbar（）, downbar（）,key()这几个函数是构建本程序菜单 所必须的函数.window()用于开窗口,以坐标的形式开辟一个窗口,并且可以在窗口里面 储存数据.switch()创建菜单选项,key()主要

4、用于获取键盘上的字符(包括字母和方向 键,enter 键),upbar()和 downbar()实现光条的上移和下移. textbackground()， textcolor()。窗口背景颜色和里面文本颜色的设置。 （2） InitList()初始化循环链表,开辟一个空间作为头结点,并让L=L-next先 让它指向自己,令链表循环起来. ListInsert()向循环链表里面插入数据(包括编号和密 码), DispList()以定义的头结点为第一个数,输出循环链表. （3） josephus()主要用于解决约瑟夫环问题,首先调用 InitList()建立循环链 表,再调用 ListInsert()插入数据,再调用 DispList()把储存的数据输出来.定义两个指 针s和q,再定义count作为计数器,此时需要任意输入一个正整数x作为初始报数上限值, 当计数器 count=x 时就把该指针所指向的数据输出并把该数据赋给 x,作为新的报数上限 值.然后删除该结点,s 和 q 的主要作用是在把输出数据之后的结点删除.如此循环,直到 还剩最后一个结点,同时定义 ai