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

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}

结果为：