循环单链表解决约瑟夫环_用链表解决约瑟夫环问题

全栈程序员-站长 • 2022年8月18日上午9:00 • 未分类 • 阅读 5

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

已知有5个人围坐在一张圆桌的周围，从编号为3的人开始顺时针数数，数到2的那个人出列淘汰，然后从出列的下个一人继续数，依次循环，直到只剩下最后一个人。（使用循环链表实现约瑟夫环）

在这里插入图片描述
代码如下：

#include "pch.h"
#include<string>
#include<fstream>
#include<Windows.h>
#include <iostream>

using namespace std;

//循环链表基本实现

//typedef struct LNode
//{ 
   
// int date;
// LNode* next;
//}*LinkList;
//
新建单链表
//void InitList(LinkList &L)
//{ 
   
// L = new LNode;
// L->next = NULL;
//}
//
给链表增加节点
//void GetLinkList(LinkList &L, int n)
//{ 
   
// LNode *p;
// LNode *r;
// r = L;
// char filename[20] = { 0 };
//
// cout << "请输入单向有序链表"
// <<"数据文件名字（文件名+“.txt”），例如List.txt"
// << ".txt" << endl;
//
// gets_s(filename);
// fstream file;
// file.open(filename);
// if (!file)
// { 
   
// cout << "文件数据打开失败！" << endl;
// Sleep(5000);
// exit(0);
// }
// 
// while (!file.eof())
// { 
   
// p = new LNode;
// file >> p->date;
// p->next = NULL; //前插插
// r->next = p;
// r = p;
// n++;
//
// }
//
// file.close();
//}
//
//void OutPutList(LinkList L)
//{ 
   
// LNode *p;
// p = L->next;
// while (p)
// { 
   
// cout << p->date << " ";
// p = p->next;
// }
//}
//
链表合并函数
//void MergeLinkList(LinkList &la, LinkList &lb, LinkList &lc)
//{ 
   
// LinkList pa, pb, pc;
// pa = la->next;
// pb = lb->next;
// 
// lc = la;
// pc = lc;
// 
// //两段链表都有节点
// while (pa&&pb)
// { 
   
// if (pa->date<=pb->date)
// { 
   
// pc->next = pa;
// pc = pa;
// pa = pa->next;
// }
// else
// { 
   
// pc->next = pb;
// pc = pb; 
// pb=pb->next;
// }
//
// pc->next = pa ? pa : pb;
//
// }
//}
//
//int main()
//{ 
   
// LinkList la,lb, lc;
//
// InitList(la);
// GetLinkList(la, 1);
// OutPutList(la);
// cout << endl;
//
// InitList(lb);
// GetLinkList(lb, 1);
// OutPutList(lb);
// cout << endl;
//
// InitList(lc);
// MergeLinkList(la, lb, lc);
// OutPutList(lc);
//
// return 0;
//}
//


//约瑟夫环实现
typedef struct Person
{ 
   
	int numberdate;
	Person *next;
}*LinkPerson;

LinkPerson initList(int n)
{ 
   
	LinkPerson L = new Person;
	L->numberdate = 1;
	L->next = NULL;
	Person*p = L;

	for (int i = 2; i <= n; i++)
	{ 
   
		Person*body = new Person;
		body->numberdate = i;
		body->next = NULL;
		p->next = body;
		p = p->next;
	}
	p->next = L;		//首尾相接
	return L;
}

void KillPerson(LinkPerson L, int a, int b)
{ 
   	//a是编号，b是数几淘汰
	LinkPerson tail = L;
	while (tail->next != L)
	{ 
   
		tail = tail->next;
	}

	LinkPerson p = L;
	//把链表的开头给开始的那个人
	while (p->numberdate != a)
	{ 
   
		tail = p;
		p = p->next;
	}
	//当p->next=p时说明只剩下一个人，游戏结束
	while (p->next != p)
	{ 
   
		//重新写入剩下的游戏玩家
		for (int i = 1; i < b; i++)
		{ 
   
			tail = p;
			p = p->next;
		}
		//从链表上将p结点就删除了
		tail->next = p->next;
		cout << "被杀的人是" << p->numberdate << "号" << endl;
		delete p;
		p = tail->next;

	}
	cout << "最后胜出的是：" << p->numberdate << endl;
	delete p;
}

int main()
{ 
   
	int n, a, b;
	cout << "请输入玩家数：";
	cin >> n;
	cout << "请输入从几号玩家开始：";
	cin >> a;
	cout << "请输入每次步数：";
	cin >> b;

	Person *L= initList(n);
	KillPerson(L, a, b);
	return 0;
}