问题描述：设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到m的人又出列，如此重复，直到所有的人全部出列为止。Josephus问题是：对于任意给定的n，m，s，求出按出列次序得到的n个人员的顺序表。

输入：（第一行为圆桌上人数s，第二行为出列数m，即报数报到几出列，第三行输入人数代表的数字）

5

4

1 2 3 4 5

输出：（第一行打印循环链表，第二行打印出列序号）

1 2 3 4 5

4 3 5 2 1

存储结构：单项循环链表

算法思想：按照游戏规则一个个报数，报到m的人出局，使用循环链表，依次循环可得到出列顺序

#include <stdio.h>  
#include <stdlib.h>  
#include <windows.h>//在c++中如果用到system("pause")需要使用这个头文件，后面程序同理   
#define NULL 0  
/* 
    1.首先要进行循环链表的创建，createCircularList（）  
    2.进行单项链表输出，注意结束条件，printCircularList（） 
    3.进行约瑟夫环的实现，并打印出列序号，josephRing（）  
*/  
typedef struct LNode{  
    int data;//数据元素   
    int sequence;//顺序号   
    LNode *next;  
}LNode,*LinkList;  
  
void createCircularList(LinkList &L, int s);//创建一个不带头节点的循环单向链表   
void printCircularList(LinkList L);//打印输出单项循环链表   
void josephRing(LinkList L, int m, int s);//约瑟夫环的实现,L对应题中n,m、s各代表m、s   
  
int s,m;   
  
int main(){  
    printf("请输入圆桌上的人数:");  
    scanf("%d",&s);   
    printf("n请输入出列数:");  
    scanf("%d",&m);   
    LinkList L;  
    createCircularList(L, s);  
    printCircularList(L);  
    josephRing(L, m, s);   
    system("pause");  
    return 0;  
}  
  
void createCircularList(LinkList &L, int n){  
    printf("n请输入数据元素(%d个)：n",s);  
    //输入第一个元素，即头节点  
    LinkList head = (LinkList)malloc(sizeof(LNode));  
    head->sequence = 1;  
    head->next = NULL;  
    scanf("%d", &head->data);  
    L = head;  
    LinkList p = head;  
    int i = 2;  
    while(i <= n){  
        LinkList s = (LinkList)malloc(sizeof(LNode));  
        s->sequence = i;  
        s->next = NULL;  
        scanf("%d", &s->data);  
        p->next = s;  
       p = s;  
        i++;  
    }  
    p->next = L;  
}  
  
  
void printCircularList(LinkList L){  
    printf("打印单项循环链表：");  
    LinkList head = L;  
    LinkList p = L->next;  
    printf("%d ",head->data);  
    while(p!=head){//因为为循环链表，所以条件为p!=head而不是p!=null   
        printf("%d ", p->data);  
        p = p->next;  
    }  
    printf("n");  
}  
   
void josephRing(LinkList L, int m, int s){  
    int *outNum = new int[s], num=0;//按退出顺序记录编号  
    int count = 1;//报数  
    LinkList p = L, q = L;  
    while(p->next!=p){  
        if(count%m == 0){//满足出列条件，出列并将序号赋给outNum数组   
            q->next = p->next;  
            outNum[num] = p->sequence;  
            num++;  
            free(p);  
           p = q->next;  
            count = 1;  
        } else{  
            q = p;  
            p = p->next;  
            count++;  
        }  
    }  
    outNum[num] = p->sequence;//最后一位留在圆桌上的序号   
    printf("退出的编号顺序是：");  
    for(int i = 0; i < s; i++){  
        printf("%d ", outNum[i]);  
    }  
    printf("n");  
}