计114-3班 刘镇 201158504337--约瑟夫环游戏课程设计文档.doc

烟台大学计算机学院
数据结构课程设计
题目:约瑟夫环游戏
班级:计算机
姓名:
学号:
日期:2013年
导师:
地点:
目录
一、需求分析 3
: 3
: 3
: 3
二、概要分析 3
() : 3
主界面mainmenu(): 4
(): 4
查找search(): 4
输出序列linkout(): 5
: 5
三、程序设计主流程 5
: 5
6
四、详细设计 7
: 7
: 7
五、调试与测试 10
调试: 10
: 13
六、存在问题与体会: 14
: 14
: 14
一、需求分析
:
约瑟夫环问题描述:编号为1,2,…,n的n个人按顺时针方向坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上相值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他的顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。设计一个程序求出出列顺序。
:
约瑟夫环问题主要是涉及到数据结构中的循环单链表的内容,通过插入链表,查询链表实现序列输出。开始主界面通过分支选择实现;主要的问题分为两个大部分,其一、是对循环单链表的创建,由于涉及到结构体和指针,因此可以通过将结构体与函数单独封装在头文件中,只有引用头文件即可,结构体内是基本的链表结构;其二、是搜索算法的涉及,思路是按照问题描述中:按初始密码查找标号à修改初始密码,打印结果,改变链表结构à再次搜查,直到链表内容清空为止结束搜索。其中剔除当前查找目标并将指针转到下一目标可通过将下一目标的密码及编号完全复制,删除下一目标,修改当前目标的指针实现。
:
使用C++语言设计,windows系统,数据结构:单向循环链表
二、概要分析
() :
基本的欢迎界面打印。
主界面mainmenu():
打印选择框图,并通过输入choice以switch-case语句实现功能选择,直接调用linkout(),实现序列输出。
():
定义结构体()指针head、link、me,
head=NULL创建一个没有头结点的单向循环链表,并采for(i=1;i<=n;i++)
自动生成新的链表存储空间me=(Linklist)malloc(sizeof(Node)),通过用户输入获取当前循环编号密码,编号自动生成,暂存在me指向的空间,最后编号及密码存入link指针指向空间中;当前指针link后移,并释放me的值。直到link->head时创建单向循环链表成功,并返回head的值。
单项循环链表示意图:
num code
………
num code
num code
查找search():
形式参数传入Linklist链表L,初始密码initialcode,及总人数num,在已经构建成的链表L中,以for(int i = 1; i <= num; i++)控制人数循环,for(int j = 1; j < initialcode; j++) 实现按初始密码报数,当前循环结束时,已经遍历到要找的link指针指针指示的结点,将其密码赋值为初始密码后再将其直接后继的编号、密码完全复制,当前的节点就是与后继结点数据机构完全相同结点,改变指针next,并其删除后继结点构成新的循环链表。如此循环下去,直到最后变为空的单循环链表为止。
输出序列linkout():
声明变量,获取总人数,调用create(),构造链表,输入获取初始密码,调用search(),实现报数和结果序列输出。
:
宏定义NULL 0 ;结构体中数据是编号num,密码code,指向下一结点的结构体指针 next。
三、程序设计主流程
:
主界面
,求序列
2、退出
任务结束
任务开始

num= 0
i = 0
开始
显示主界面
操作选择?
2

1
创建约瑟夫环
输入初始数n
退出
i <= num ?
N
Y
实现报数
输入第i人密码;
i = i+1
输出出列序列
结束
四、详细设计
Joseph:
:
#define NU