1.问题描述：

设有n个人围坐在一个圆桌周围，现在从第s个人开始从1开始报数，数到m的人出列然后从出列的下一个人重新开始从1报数，数到m的人再出列······如此反复直到所有人出列，求出出列的顺序？

2.算法思路：

采用顺序表存储结构，将n个人编号存放在顺序表中，从顺序表中的第s个元素开始寻找s+m-1个元素，找到后输出（在寻找的过程中若到表尾，则跳到开始位置，通过取模实现），再删除元素，下一次从该位置重复上述过程。

3.算法描述：

int josephus_SeqList(PSeqList josephus_seq,int s,int m)
{ /*求解约瑟夫问题的出列元素序列的入口参数：已经存放数据的顺序表josephus_seq，起始序号s，计数值m*/
/*出口参数：1表示成功，0表示表中无元素*/

    int s1,i,w;
    if(!josephus_seq->length)
    {
         printf("表中无元素!\n");
         return 0;
    }
     s1=s-1;/*--------------------------------------------------data数组中的下标从0开始*/
     printf("输出约瑟夫序列：\n");
     for(i=josephus_seq->length;i>0;i--)
    {
       s1=(s1+m)%i;/*----------------------------------------找到出列元素的下标*/
      w=josephus_seq->data[s1];
      printf("%d\t",w);
      Delete_SeqList(josephus_seq,s1+1);/*-----------删除出列元素*/
    }
    return 1;/*---------------------------------------------------返回成功*/-

4.具体程序实现：

#include<cstdio>
#include<cstdlib>
#define MAXSIZE 100
typedef struct node
{
int data[MAXSIZE];
int length;
}SeqList,*PSeqList;
PSeqList Init_SeqList(void)
{
PSeqList PL;
PL=(PSeqList)malloc(sizeof(SeqList));
if(PL)
    PL->length=0;
return PL;
}
/*
int Location_SeqList(PSeqList L,int x)
{
int i=0;
while(i<L->length&&L->data[i]!=x)
{
  i++;
}
if(i>=L->length)
  return 0;
else
  return i;
}
int Insert_SeqList(PSeqList PL,int i,int x)
{
int j;
if(!PL)
{
  printf("表不存在!\n");
}
if(PL->length>=MAXSIZE)
{
  printf("表溢出!\n");
}
if(i<1||i>PL->length+1)
{
  printf("表插入的位置不合法!\n");
}
for(j=PL->length-1;j>=i-1;j--)
{
  PL->data[j+1]=PL->data[j];
}
  PL->data[i-1]=x;
  PL->length++;
}*/
int Delete_SeqList(PSeqList PL,int i)
{
int j;
if(!PL)
{
  printf("表不存在!\n");
}
if(i<1||i>PL->length)
{
  printf("表删除的位置不合法!\n");
}
for(j=i;j<PL->length;j++)
{
  PL->data[j-1]=PL->data[j];
}
PL->length--;
return (1);
}
int josephus_SeqList(PSeqList josephus_seq,int s,int m)
{
int s1,i,w;
if(!josephus_seq->length)
{
  printf("表中无元素!\n");
  return 0;
}
s1=s-1;
printf("输出约瑟夫序列：\n");
for(i=josephus_seq->length;i>0;i--)
{
  s1=(s1+m)%i;
  w=josephus_seq->data[s1];
  printf("%d\t",w);
  Delete_SeqList(josephus_seq,s1+1);
}
return 1;
}
void main()
{
int s,m,n,i;
PSeqList josephus_seq;
josephus_seq=Init_SeqList();
printf("输入约瑟夫问题中的人数: n= ");
    scanf("%d",&n);
josephus_seq->length=n;
putchar('\n');
printf("输入约瑟夫问题中的编号: \n");
for(i=0;i<josephus_seq->length;i++)
{
  scanf("%d",&josephus_seq->data[i]);
}
printf("输入起始序号: s= ");
scanf("%d",&s);
    putchar('\n');
printf("输入计数值: m= ");
scanf("%d",&m);
putchar('\n');
josephus_SeqList(josephus_seq,s,m);
putchar('\n');
}

5.运行结果截图：

6.算法评价：

该算法运行的主要时间耗费在求出列元素（总共需要出n个元素），每求出一个出列元素调出Delete_SeqList()函数一次，所以时间复杂度O(n^2)。

数据结构之顺序表应用-----《约瑟夫问题》