C++实现约瑟夫环的循环单链表 C++实现约瑟夫环的循环单链表

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知 n 个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。. 从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。. 例如：有10个人围成一圈进行此游戏，每个人编号为 1-10 。. 若规定数到 3 的人出圈。. 则游戏过程如下。. （1）开始报数，第一个数到 3 的人为 3 号，3 号出圈。. 1， 2，【 3 】， 4， 5， 6， 7， 8， 9， 10。. （2）从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈。
废话不多说，直接上代码：
下面是头文件，命名为”约瑟夫环.h“

#ifndef Josephus_circle//判断是否被定义过Josephus_circle#define Josephus_circle struct Node//定义一个结构体，用来表示每一个结点 { int data; //表示每一个结点的数字，也就是序号Node* next; //定义一个结构体指针，用来指向后一个结点}; class Josephus//定义一个类，里面包含有三个接口，和两个私有成员变量{public : Josephus(int n); //定义一个构造函数，用来创建一个约瑟夫环 ~Josephus(); //析构函数，用以销毁一个约瑟夫环 void ResultShow(int m); //展示出圈顺序private : Node * rear,*first; //定义一个节点形指针，用来指向最后一个结点}; #endif

下面是接口的具体实现，命名为“约瑟夫环.cpp”

#include//引入输入输出流#include"约瑟夫环.h"//引入约瑟夫环头文件 using namespace std; Josephus::Josephus(int n) {first=rear = new Node; //将头指针和尾指针指向第一个新建的结点，也就是初始化指针rear->data = https://www.it610.com/article/1; //首先，将第一个结点数据域赋值为1for (int i = 2; i <= n; i++) //从2开始{Node* s = new Node; //定义一个Node形指针s，指向新建的一个结点rear->next = s; //将指向头结点的尾指针指向下一个结点，也就是s所指的结点s->data = https://www.it610.com/article/i; //将新建的结点数字域赋值为irear = s; //将尾结点移动到新建结点s}rear->next = first; //在循环过后，将尾结点和头节点连接起来，构成循环链表}Josephus::~Josephus(){ if (first!=rear)//判断环是否为空 {while (first != rear)//每次循环都是当头节点不等于尾结点时候，开始删除：……{Node * p = first; //定义一个新的节点形指针，指向头节点，用作暂存要删去的结点first = first->next; //将头节点移动到下一个结点delete p; //删除之前头节点所指向的结点}delete rear; //在删除完成后，剩下的最后就只有尾结点了，删除即可 } else {cout << "约瑟夫环为空，请先建立新环！" << endl; //空表提示 }}void Josephus::ResultShow(int m){ cout << "出环顺序为：" << endl; Node * p = first; //定义一个Node类型的p，等于first Node * pre=first,* reserve=nullptr; //定义pre等于first，和一个代替p指针被删除的结点的指针 int count = 1; //定义一个计数的count使其为一 while (p->next != p)//如果p->next所指向的结点是p的话，表示，这已经是最后一个结点了，该节点为最后出圈 {if (count < m)//count来计数，每次到了m就出圈对应结点{pre = p; //将pre等于p，以便于表示p变换前的结点p = p->next; //p向下一结点移动count++; //移动一次count加一次}else//每次count=m时候就开始删除对应结点{pre->next = p->next; //首先从环中摘去要删除的p所指的结点reserve = p; //使用reserve来保存被摘去的结点pcout << p->data << "\t"; //输出结点p所数据域，输出在屏幕上表示p结点的出圈p = p->next; //p指向下一结点，以便于下一轮的循环delete reserve; //删除保存p的reserve所对应的结点count = 1; //将计数恢复为1，以便下一轮计数} } cout << p->data << endl; //这最后一个就是最后出圈的结点，也就是所谓的胜利者，最后单独输出屏幕 delete p; //输出最后再删除这一结点，释放内存 pre=first=rear=p = NULL; //避免野指针出现使其指向空}

下面是main函数，命名为“约瑟夫环_main.cpp”

#include//引入输入输出流#include"约瑟夫环.h"//引入头文件 using namespace std; //主函数区域int main() { int m, n; cout << "请输入约瑟夫环人数以及密码\n"; cout << "人数n："; cin >> n; cout << endl << "密码m："; cin >> m; Josephus L(n); //创建一个约瑟夫环，环数为10 L.ResultShow(m); //定义密码m，输出出圈顺序 return 0; }

下面是运行截图：