数据结构实验约瑟夫环问题实验报告
本实验报告旨在解决约瑟夫环问题，并提供了 experiment 报告的详细内容。
一、实验目的及要求
实验目的：设有编号为 1，2，...，n 的 n(n>0)个人围成一个圈，每个人持有一个密码 m，从第 1 个人开始报数，报到 m 时停止报数，报m 的人出圈，再从他的下一个人起重新报数，报到 m 时停止报数，报 m 的出圈，......直到所有人全部出圈为止。当任意给定 n 和 m后，求 n 个人出圈的次序。
实验要求：
（1）建立数据模型，确定存储结构；
（2）对任意 n 个人，密码为 m，实现约瑟夫环问题；
（3）出圈的顺序可以依次输出，也可以用一个数组存储。
二、实验步骤
（1）约瑟夫环问题的存储结构。
由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：
struct Node{
int data;//编号
Node *next;
};
（2）建立约瑟夫环。
建立一个不带头结点的循环链表并由头指针 first 指示，如下所示：
pre p,count=2
...
first
建立约瑟夫环。
（3）设计约瑟夫环算法实现出圈。
出圈伪代码如下所示：
1：工作指针 pre 和 p 初始化，计数器 count 初始化；
pre=first；
p=first->next；
count=2；
2：循环直到 p 等于 pre
2.1 如果 count 等于 m，则
2.1.1 输出结点 p 的编号；
2.1.2 删除结点 p；
p=pre->next；
2.1.3 计数器 count 重新开始计数；
2.2 否则，执行
2.2.1 工作指针 pre 和 p 后移；
2.2.2 计数器 count++；
3：退出循环，链表中只剩下一个结点 p，输出结点 p 后将结点 p 删除；
三、实验内容代码
#include <iostream>
using namespace std;
//定义结构体 Node
struct Node{
int Data;
struct Node *next;
};
class JosephRing{
public:
JosephRing(int n); //初始化 n 个结点的循环单链表
~JosephRing(){}
void Joseph(int m);//输出时含有间隔数字的函数
private:
Node *rear; //建立一个 Node 类型指针
};
//实现 n 个结点的循环单链表构造函数
JosephRing::JosephRing(int n){
Node *s = nullptr;
rear = new Node;
rear->Data = 1;
rear->next = rear;
for(int i = 2; i <= n; i++){
s = new Node;
s->Data = i;
s->next = rear->next;
rear->next = s;
rear = s;
}
}
//实现出环功能
void JosephRing::Joseph(int m){
Node *pre = rear;
Node *p = rear->next;
int count = 1;//计密码数
while(p->next != p){//如果环中不止一个结点
if(count < m){//如果 count 还没到密码数 m
pre = p;
p = p->next;
count++;
}else{
cout<<p->Data<<endl;
Node *q = p;
pre->next = p->next;
delete q;
p = pre->next;
count = 1;
}
}
cout<<p->Data<<endl;
delete p;
}
四、实验结果
通过实验，我们可以看到约瑟夫环问题的解决方案。实验结果显示，约瑟夫环问题可以使用循环链表和算法来解决。
五、结论
本实验报告解决了约瑟夫环问题，并提供了实验报告的详细内容。实验结果显示，约瑟夫环问题可以使用循环链表和算法来解决。
- 1
- 2
前往页