约瑟夫环（循环列表实现）

约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈。每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，令其出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新报数，如此下去，直到所有人全部出列为止。试设计一个程序求出出列顺序。

实验要求

利用无头结点的单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。

测试数据：

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

实验提示：

程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码，可设n<=30，此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。

#include<iostream>//用链表实现约瑟夫环问题 （循环链表）
using namespace std;
typedef struct node  
{int num;int pwd;struct node* next;
}Node ,*list;
list Createlist(int n)//创建循环列表
{list head = NULL,rear=NULL, temp = NULL;head = rear;for (int i = 1; i <= n; i++){temp = new node;temp->num = i;cin >> temp->pwd;if (head == NULL)//若为空则赋给头指针{head = temp;}else{rear->next = temp;//接在尾指针后}rear = temp;}rear->next = head;//尾指针指向头指针return head;
}
//void Printlist(list l)//打印输出
//{//list p = l;//for (int i = 0; i < 14; i++)//{//cout << p->num << p->pwd << " ";//p = p->next ;//}//cout << endl;
//}
void Getlist(list l,int n,int m)//约瑟夫环
{list p = l, q = NULL;while (p->next != p)//循环直到只剩一个 头尾相指{for (int i = 1; i < m; i++){q = p;//保留离开点的上一个节点p = p->next;}cout << p->num<<" ";m = p->pwd;q->next = p->next;//剔除该点p = p->next;//从下一节点重新计数}cout << p->num;
}
int main()
{list l;int n, m;cin >> n >> m;l = Createlist(n);//Printlist(l);Getlist(l, n, m);
}