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<iostream>//引入输入输出流

#include"约瑟夫环.h"//引入约瑟夫环头文件

using namespace std;

Josephus::Josephus(int n)

{

first=rear = new Node;//将头指针和尾指针指向第一个新建的结点,也就是初始化指针

rear->data = 1;//首先,将第一个结点数据域赋值为1

for (int i = 2; i <= n; i++) //从2开始

{

Node* s = new Node;//定义一个Node形指针s,指向新建的一个结点

rear->next = s;//将指向头结点的尾指针指向下一个结点,也就是s所指的结点

s->data = i;//将新建的结点数字域赋值为i

rear = 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来保存被摘去的结点p

cout << 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<iostream>//引入输入输出流

#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;

}

下面是运行截图:

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

以上是 C++实现约瑟夫环的循环单链表 的全部内容, 来源链接: utcz.com/p/247490.html

回到顶部