【原】数据结构项目——使用循环链表实现约瑟夫环（循环和双向链表实现）

已知有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;
}

结果为：