约瑟夫环问题 实验报告完整版.pdfVIP

穷则独善其身，达则兼善天下。——《孟子》

实验报告

实验课名称：数据结构实验一

实验名称：约瑟夫环问题

班级000学号000姓名神刀公时间

子

1.问题描述

约瑟夫环问题

（1）问题描述

设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。

从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人

起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人

全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。

（2）基本要求

建立模型，确定存储结构。

对任意n个人，密码为m，实现约瑟夫环问题。

出圈的顺序可以依次输出，也可以用一个数组存储。

（3）思考：

采用顺序存储结构如何实现约瑟夫环问题？

如果每个人持有的密码不同，应如何实现约瑟夫环问题？

2.

数据结构设计

由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中

任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：

structNode

{

intdata;//数据域

Node*next;//next指针指向下一个结点

};

3.

算法设计

问题要求建立模型，确定存储结构，之后对任意n个人，密码为m，实现约

瑟夫环问题，出圈的顺序可以依次输出，也可以用一个数组存储。

1

穷则独善其身，达则兼善天下。——《孟子》

设计流程图如图1.1所示。

开始

输出提示语

输入所需参数

创建链表，计算，得出结果

输出结果

结束

图1.1设计流程图

（1）创建循环链表

由于内容的要求以及问题的方便，用循环链表作为本次实验的抽象数据类

型。申请一个结点作为第一个结点，之后调用creat_list函数将后续结点一次插

入链接，构造为循环链表。

NODE*link(intnumber)

{

NODE*head=NULL,*p=NULL,*q=NULL;

inti=1;

head=(structnode*)malloc(sizeof(structnode));

head-value=i;

p=head;

for(i=2;i=number;i++)