已知有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; }
结果为：
