[数据结构与算法]强！！基于C++实现约瑟夫环plus版本

一.实验目的(Objects)

1.掌握循环单链表的生成及插入删除的实现方法和应用。

二.实验内容(Contents)

1.约瑟夫环（改造版）描述

编号为 1,2，…，n的 n个人按顺时针方向围坐在一圈，每人持有一个密码（正整数）。一开始任选一 个正整数作为报数值 m，从第一个人开始按顺时针方向自 1开始顺序报数，报到 m时停止报数。报 m 的人出列，将他的密码作为新的 m值，从他在顺时针方向上的下一个人开始重新从 1报数，如此下去， 直至所有人都出列为止。请设计一个程序求出出列顺序。

2.基本要求（BasicRequirements）

利用单项循环链表存储结构模拟次过程，按照出列的顺序打印出个人的编号。

3.测试数据（testdata）

m的初值为 20；n=7,7个人的密码一次为：3,1,7,2,4,8,4，首次 m值为 20（正确的出列顺序应为 6,1,4,7,2,3,5）。

4.实现提示(implementationtips)

程序运行后，首先要求用户指定初始报数值，然后读取个人的密码。

三.实验步骤(Yourstepsorcodes)

1st.整体设计(Overalldesign)

基本设计思想是，使用两个简单链表 tt，t，t存储编号和对应的密码，tt存储出位顺序，对 t进行约瑟夫规 则处理，逐次找到出位顺序的编号依次存入 tt链表中，在 t链表中的节点处理完成后，对 tt链表进行遍历， 即可得到出位顺序。

整体的类变量声明和基本函数声明如下：

/*****************************************链表的结构体的构建****************************************/
template<typenameT>
structnode{
public:
	T number;//存编号；
	T password;//存密码；
	node<T>*next;//指向下一个节点的地址；
};
/********************************************链表类的建立*******************************************/
template<typenameT>
classlink{//链表类；
	node<T>*header;//只有一个属性值；其保存链表的头部节点的头地址；
public:
	link();//无参构造函数；
	~link();//析构函数；
	node<T>*back()const;//返回链表的头节点地址；
	int len_link()const;//计算链表的长度；
	void trave_two()const;//对节点的两个变量进行遍历；
	void trave_one()const;//对节点的一个变量进行遍历；
	void create_new_node(const int a,const int b);//创建向节点加入两个变量的新节点；
	void create_new_node(const int a);//创建向节点加入一个变量的新节点；
	void replace_password(const int a,int password);//改变编号为 a的节点的密码；
	void delete_link();//删除链表；
	void remove_one_node(node<T>*p);//删除一个节点；
	int remove_more(const int x);//删除编号为 x的所有节点；
	node<T>*find_id(const int x);//查找编号为 x的用户，不存在则返回 null；
	node<T>*loaction(int x);//返回第 x节点的内存地址；
	voidinsert(node<T>*p,node<T>*q);//在 p节点后加入 q节点，不存在 p节点则输出操作失败；
	intback_name(const int t);//返回编号为 t的密码；
};
/********************************************约瑟夫环类的创建**************************************/
template<typenameT>
classJoseph_ring{
private:
	link<T>t;//保存初始每位成员编号和密码的链表；
	link<T>tt;//保存出位顺序编号的链表；
	node<T>*q;//辅助指针；
	node<T>*p;//辅助指针；
	int m;
public:
	Joseph_ring(int a);
	~Joseph_ring();
	void pro_system();//对生成的约瑟夫环进行处理操作，算出出位顺序并存在 tt链表中
	void Generate_list(T*a,T n);//生成储存每位成员的编号和密码的函数
	void trave_tw(){
		t.trave_two();
	}
	void trave_on(){
		tt.trave_one()
	}
};	

关于 link类和 Joseph_ring的核心函数，我会在算法框架里具体分析，这里不做赘述。

2nd.算法框架(Algorithm Framework)

1.关于 link类核心函数的算法框架

主要核心函数如下：

void create_new_node(const int a,const int b);//创建向节点加入两个变量的新节点；
void insert(node<T>*p,node<T>*q);//在 p节点后加入 q节点，不存在 p节点则输出操作失败；
void remove_one_node(node<T>*p);//删除一个节点；
int len_link()const;//计算链表的长度；
void trave_two()const;//对节点的两个变量进行遍历；

1>.关于创建节点的函数

函数的具体定义如下：

//创建向节点加入两个变量的新节点；
template<typenameT>
voidlink<T>::create_new_node(constinta,constintb){
	/*分两种情况，一种为链表为空，直接加入元素到头节点即可 另一种是链表不为空时，使用两个指针 q,p使用 q保存头节点地址 p去开辟新节点，让 q连接。*/
	if(header==nullptr){
		header=new node<T>;
		header->number=a;
		header->password=b;
		header->next=nullptr;
	}
	else{
		node<T>*q;
		q=header;
		while(q->next!=nullptr){
			q=q->next;
		}
		node<T>*p;
		p=new node<T>;
		p->number=a;
		p->password=b;
		q->next=p;
		p->next=nullptr;
	}
}	

正如上面注释部分写的那样，考虑两种情况，链表为空和链表不为空。链表为空直接加入头节点，不为空，借助两个辅助指针 p，q完成。这个基本算法很简单。

2>.关于插入节点的函数

//在p节点后加入q节点，不存在p节点则输出操作失败；
template<typename T>
void link<T>::insert(node1<T>*p, node1<T>*q) {
	/****
	判断两种情况，
	1.插入头部
	2.插入一般部位
	插入头部直接即可插
	插入一般部位，应先让q连接p后面的节点
	即：q->next = p->next
	然后：p->next = q;
	****/
	node1<T>*tt = new node1<T>;
	tt = header;
	if (p->next == nullptr) {
		p->next = q;
		q->next = nullptr;
	}
	else {
		while (tt != p) {
			tt = tt->next;
			if (tt == nullptr)
				break;
		}
		if (tt) {
			q->next = tt->next;
			tt->next = q;
		}
		else
			cout << "不存在p节点!\n";
	}
}

在 p节点后插入 q节点，首先应该先连接 q节点与 p后面的节点，然后再连接 p与 q节点。这是需要注 意的地方，不然很可能会让原 p节点后面的节点丢失找不到。

3>.关于删除节点的函数

//删除一个节点；
template<typename T>
void link<T>::remove_one_node(node1<T>*p) {
	/*****
	创建一个prve指针
	用prve指针寻找所要删除的p节点的
	前面一个节点的地址；
	*****/
	node1<T>*prve;
	prve = header;
	if (p == prve)
		header = p->next;
	else
	{
		while (prve->next != p) {
			prve = prve->next;
		}
		prve->next = p->next;
	}
	delete p;
}

在找到想要删除的节点 p时，为了不让在删除 p节点后链表断裂，应该先让 p前节点与 p后节点接在一 起。

4>.计算链表的长度

//计算链表的长度；
template<typename T>
int link<T>::len_link()const {
	node1<T>*p;
	p = header;
	int k = 0;
	while (p != nullptr) {
		k++;
		p = p->next;//指向下一个节点；
	}
	return k;
}

使用 k值计算链表的节点个数，对链表进行遍历，每次碰到不为空的节点则 k++，直到节点为空为止。

5>.链表的遍历函数

//对节点的两个变量进行遍历；
template<typename T>
void link<T>::trave_two()const {
	node1<T> *cour;
	cour = header;
	if (cour == nullptr)
		;
	else {
		while (cour != nullptr) {
			cout << "Number: \t" << cour->number << "\t";
			cout << "Password: \t" << cour->password << "\n";//输出每个节点的值；
			cour = cour->next;
		}
		cout << endl;
	}
}

2.关于 Joseph_ring类核心函数的算法框架

主要核心函数如下：

void pro_system();//对生成的约瑟夫环进行处理操作，算出出位顺序并存在 tt链表中
void Generate_list(T*a,T n);//生成储存每位成员的编号和密码的函数

1>.关于 pro_system 函数

//生成储存每位成员的编号和密码的函数
template<typename T>
void Joseph_ring<T>::Generate_list(T *a, T n) {
	int i, j = 1;
	for (i = 0; i < n; j++, i++)
		t.create_new_node(j, a[i]);
	p = t.back();
}

在这里调用链表的创建函数。

2>.关于 Generate_list函数

//对生成的约瑟夫环进行处理操作，算出出位顺序并存在tt链表中
template<typename T>
void Joseph_ring<T>::pro_system() {
	int i = 2;
	while (i <= m) {
		/*查找数到m时的人的编号*/
		if (p->next == nullptr)
			p = t.back();
		else
			p = p->next;
		i++;
	}
	//将数到m时的编号放入tt链表中；
	tt.create_new_node(p->number);
	//如果到达链表末尾，返回表头；
	if (p->next != nullptr)
		q = p->next;
	else
		q = t.back();
	//更新密码m值；
	m = p->password;
	t.remove_one_node(p);
	p = q;
	//链表不空，接着调用该函数再处理；
	//为空截止；
	if (t.back() != nullptr) {
		pro_system();
	}
}

正如上述注释所说，首先对初始 m值进行操作，使用循环，查询到 m时的人的编号放入 tt链表内。然后 加入判断，如果查询到 t链表尾部，返回头部接着进行。并且更新 m值为此时 p->password。然后删除 t 链表中的 p。

四.测试用例(Results)

测试用例为：
m的初值为 20；n=7,7个人的密码一次为：3,1,7,2,4,8,4，首次 m值为 20（正确的出列顺序应为 6,1,4,7,2,3,5）。

五.源程序(SourceProgram)

// 约瑟夫环（加强版）.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include<iostream>
using namespace std;

/*************************************链表的节点*****************************/
template<typename T>
struct node1 {
public:
	T number;//存编号；
	T password;//存密码；
	node1<T> *next;//指向下一个节点的地址；
};

/*************************************************************************************/

/*************************************链表类的建立************************************/
template<typename T>
class link {//链表类；
	node1<T> *header;//只有一个属性值；其保存链表的头部节点的头地址；
public:
	link();//无参构造函数；
	~link();//析构函数；
	node1<T>* back()const;//返回链表的头节点地址；
	int len_link()const;//计算链表的长度；
	void trave_two()const;//对节点的两个变量进行遍历；
	void trave_one()const;//对节点的一个变量进行遍历；
	void create_new_node(const int a, const int b);//创建向节点加入两个变量的新节点；
	void create_new_node(const int a);//创建向节点加入一个变量的新节点；
	void replace_password(const int a, int password);//改变编号为a的节点的密码；
	void delete_link();//删除链表；
	void remove_one_node(node1<T>*p);//删除一个节点；
	int remove_more(const int x);//删除编号为x的所有节点；
	node1<T>*find_id(const int x);//查找编号为x的用户，不存在则返回null；
	node1<T>*loaction(int x);//返回第x节点的内存地址；
	void insert(node1<T>*p, node1<T>*q);//在p节点后加入q节点，不存在p节点则输出操作失败；
	int back_name(const int t);//返回编号为t的密码；
};

template<typename T>
link<T>::link() {
	header = nullptr;
}

template<typename T>
link<T>::~link() {
	delete_link();
}

//返回链表的头地址；
template<typename T>
node1<T>* link<T>::back()const {
	return header;
}

//计算链表的长度；
template<typename T>
int link<T>::len_link()const {
	node1<T>*p;
	p = header;
	int k = 0;
	while (p != nullptr) {
		k++;
		p = p->next;//指向下一个节点；
	}
	return k;
}

//对节点的两个变量进行遍历；
template<typename T>
void link<T>::trave_two()const {
	node1<T> *cour;
	cour = header;
	if (cour == nullptr)
		;
	else {
		while (cour != nullptr) {
			cout << "Number: \t" << cour->number << "\t";
			cout << "Password: \t" << cour->password << "\n";//输出每个节点的值；
			cour = cour->next;
		}
		cout << endl;
	}
}

//对节点的一个变量进行遍历；
template<typename T>
void link<T>::trave_one()const {
	node1<T> *cour;
	cour = header;
	if (cour == nullptr)
		;
	else {
		while (cour != nullptr) {
			cout << cour->number << ' ';
			//输出每个节点的值；
			cour = cour->next;
		}
		cout << endl;
	}
}

//创建向节点加入两个变量的新节点；
template<typename T>
void link<T>::create_new_node(const int a, const int b) {
	if (header == nullptr) {
		header = new node1<T>;
		header->number = a;
		header->password = b;
		header->next = nullptr;
	}
	else {
		node1<T>*q;
		q = header;
		while (q->next != nullptr) {
			q = q->next;
		}
		node1<T>*p;
		p = new node1<T>;
		p->number = a;
		p->password = b;
		q->next = p;
		p->next = nullptr;
	}
}

//创建向节点加入一个变量的新节点；
template<typename T>
void link<T>::create_new_node(const int a) {
	if (header == nullptr) {
		header = new node1<T>;
		header->number = a;
		header->next = nullptr;
	}
	else {
		node1<T>*q;
		q = header;
		while (q->next != nullptr) {
			q = q->next;
		}
		node1<T>*p;
		p = new node1<T>;
		p->number = a;
		q->next = p;
		p->next = nullptr;
	}
}

//改变编号为a的节点的密码；
template<typename T>
void link<T>::replace_password(const int a, int password) {
	node1<T>*p;
	p = header;
	while (p != nullptr) {
		if (p->number == a) {
			p->password = password;
			break;
		}
		p = p->next;
	}
}

//删除一个节点；
template<typename T>
void link<T>::remove_one_node(node1<T>*p) {
	/*****
	创建一个prve指针
	用prve指针寻找所要删除的p节点的
	前面一个节点的地址；
	*****/
	node1<T>*prve;
	prve = header;
	if (p == prve)
		header = p->next;
	else
	{
		while (prve->next != p) {
			prve = prve->next;
		}
		prve->next = p->next;
	}
	delete p;
}

//删除链表；
template<typename T>
void link<T>::delete_link() {
	/*****
	创建两个node*类型的变量，p&q
	q帮助协助连接链表，p保存链表头，对p进行删除处理；
	*****/
	node1<T>*p;
	node1<T>*q = nullptr;
	p = header;
	while (p != nullptr) {
		q = p->next;
		remove_one_node(p);
		p = q;
	}
	header = nullptr;
}

//删除编号为x的所有节点；
template<typename T>
int link<T>::remove_more(const int x) {
	/****
	q连接节点，p判断是否删除节点，
	并进行删除处理；
	****/
	int k = 0;
	node1<T>* p;
	node1<T>* q = nullptr;
	p = header;
	while (1)
	{
		if (p->number == x) {
			q = p->next;
			remove_one_node(p);
			p = q;
			k++;
		}
		else
			p = p->next;
		if (p == nullptr)
			break;
	}
	return k;
}

//查找编号为x的用户，不存在则返回null；
template<typename T>
node1<T>* link<T>::find_id(const int x) {
	/****
	创建两个指针，pq
	p判断是否p->n == x
	q返回满足条件的地址；
	****/
	node1<T>* p;
	node1<T>* q;
	q = p = header;
	while (1) {
		if (p->number == x) {
			return q;
			break;
		}
		p = p->next;
		q = q->next;
		if (q == nullptr) {
			return q;
			break;
		}
	}
}

//返回第x节点的内存地址；
template<typename T>
node1<T>* link<T>::loaction(int x) {
	/****
	先用 int m保存链表的总长度；
	然后遍历寻找；
	返回P即可；
	****/
	node1<T>*p;
	p = header;
	int m = 0;
	while (p != nullptr)
	{
		m++;
		p = p->next;
	}
	p = header;
	if (x <= m) {
		int i;
		if (x == 1)
			;
		else {
			for (i = 2; i <= x; i++)
				p = p->next;
		}
		return p;
	}
	else
		return nullptr;
}

//返回编号为t的密码；
template<typename T>
int link<T>::back_name(const int t) {
	node1<T>*p;
	p = header;
	while (p != nullptr) {
		if (p->number == t) {
			return p->mi;
			break;
		}
		p = p->next;
	}
}

//在p节点后加入q节点，不存在p节点则输出操作失败；
template<typename T>
void link<T>::insert(node1<T>*p, node1<T>*q) {
	/****
	判断两种情况，
	1.插入头部
	2.插入一般部位
	插入头部直接即可插
	插入一般部位，应先让q连接p后面的节点
	即：q->next = p->next
	然后：p->next = q;
	****/
	node1<T>*tt = new node1<T>;
	tt = header;
	if (p->next == nullptr) {
		p->next = q;
		q->next = nullptr;
	}
	else {
		while (tt != p) {
			tt = tt->next;
			if (tt == nullptr)
				break;
		}
		if (tt) {
			q->next = tt->next;
			tt->next = q;
		}
		else
			cout << "不存在p节点!\n";
	}
}


/*************************************************************************************/


/*********************************约瑟夫环类的创建********************************/
template<typename T>
class Joseph_ring {
private:
	link<T> t;//保存初始每位成员编号和密码的链表；
	link<T> tt;//保存出位顺序编号的链表；
	node1<T>* q;//辅助指针；
	node1<T>* p;//辅助指针；
	int m;
public:
	Joseph_ring(int a);
	~Joseph_ring();
	void pro_system();//对生成的约瑟夫环进行处理操作，算出出位顺序并存在tt链表中
	void Generate_list(T *a, T n);//生成储存每位成员的编号和密码的函数
	void trave_tw() {
		t.trave_two();
	}
	void trave_on() {
		tt.trave_one();
	}
};

template<typename T>
Joseph_ring<T>::Joseph_ring(int a) :m(a) {
	q = nullptr;
	p = nullptr;
}

template<typename T>
Joseph_ring<T>::~Joseph_ring() {
	//delete q;
	//delete p;
}

//生成储存每位成员的编号和密码的函数
template<typename T>
void Joseph_ring<T>::Generate_list(T *a, T n) {
	int i, j = 1;
	for (i = 0; i < n; j++, i++)
		t.create_new_node(j, a[i]);
	p = t.back();
}

//对生成的约瑟夫环进行处理操作，算出出位顺序并存在tt链表中
template<typename T>
void Joseph_ring<T>::pro_system() {
	int i = 2;
	while (i <= m) {
		/*查找数到m时的人的编号*/
		if (p->next == nullptr)
			p = t.back();
		else
			p = p->next;
		i++;
	}
	//将数到m时的编号放入tt链表中；
	tt.create_new_node(p->number);
	//如果到达链表末尾，返回表头；
	if (p->next != nullptr)
		q = p->next;
	else
		q = t.back();
	//更新密码m值；
	m = p->password;
	t.remove_one_node(p);
	p = q;
	//链表不空，接着调用该函数再处理；
	//为空截止；
	if (t.back() != nullptr) {
		pro_system();
	}
}
/*************************************************************************************/

int main()
{
	int m;
	cout << "Please input your numbers that you want to test: " << endl;
	int n;
	cin >> n;
	if (n > 0) {
		int *a;
		a = new int[n];
		cout << "Please enter everyone's password in turn: \n";
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		cout << "Please enter the initial password [m]: \n";
		cin >> m;
		Joseph_ring<int> Jose(m);
		Jose.Generate_list(a, n);
		cout << "We will perform the Joseph loop operation for the initial password m: [" << " " << m << " ]\n";
		cout << "Everyone's number and password om order as follows: \n";
		Jose.trave_tw();
		Jose.pro_system();
		cout << "The following is the order in which people are out: \n";
		Jose.trave_on();
		delete[]a;
	}
	else {
		cout << "There was a mistake in the number of people entered!\n";
	}
	return 0;
}

使用源程序的小伙伴支持一下，给个赞和收藏，最好也评论下。谢谢 作者大大深夜发文也不容易 哈哈哈！！