Josephus定义：假设N个人编号1－N，围成圈。从1号开始报数，报到M时，此人退出，然 后继续从1开始报数，直到所有人退出为止。简单的实现是使用循环单链表，设置一个计数器 count，当count == M ，删除当前节点，并将count重置。
假设M = 9,N = 5;
这里有两处地方可以优化：
1.当M>N时，取M`= M mod N，即M` = 9 % 5 = 4；报数到9与报数到4效果一致，但少遍历一次链表；
2.当M` > N / 2时，可逆 向走N - M'' + 1步，此时反向走比正向走距离更近，但需要将数据结构设置为循环双链 表。
对于M = 9,N = 5，实现优化后流程如下：
---
链表:1 2 3 4 5
N = 5
M` = 9 mod 5 = 4
M` = 4 > N / 2 = 2
反走(5 - 4 + 1) = 2 步，删除节点4，此时起点在节点3;
---
链表:1 2 3 5
N = 4
M` = 9 mod 4 = 1
M'' = 1 < N / 2 = 2
正走1步，删除节点5，此时起点在节点3;
---
链 表:1 2 3
N = 3
M` = 9 mod 3 = 0
M` = 0 < N / 2 = 1
正走0步，删除节点3，此时起点在节点2;
---
链表:1 2
N = 2
M` = 9 mod 2 = 1
M` = 1 = N / 2 = 1
正 走1步，删除节点1，此时起点在节点2;
---
链表:2
N = 1
M` = 9 mod 1 = 0
M` = 0 = N / 2 = 0
正走0步，删除节点2，此时 链表空;
算法C实现：
#include <stdio.h>
#include "dlinkedlist.h"
#define SIZE 5
#define N SIZE
#define M 9
static List init();
void print(List l);
void process(List l);
int main()
{
List josephus = init();
print (josephus);
process(josephus);
return 0;
}
/* 初始化链表 */
static List init()
{
int i;
List josephus = CreateList(1);
Position p = josephus;
for (i = 2; i <= SIZE; i++)
{
Insert(i, josephus, p);
p = NextPosition(p);
}
return josephus;
}
/* 打印链表 */
void print(List l)
{
if (l == NULL)
return;
printf ("%d ",Retrieve(l));
Position p = NextPosition(l);
while (p != l)
{
printf("%d ",Retrieve(p));
p = NextPosition(p);
}
printf("\n");
}
/* Josephus处理 */
void process(List l)
{
int n = N;
int m = M % n;
int i;
Position p = l;
while (n > 1)
{
if (m > n / 2)
{
for (i = 0; i < n - m + 1; i++)
p = PreviousPosition(p);
}
else
{
for (i = 0; i < m; i++)
p = NextPosition(p);
}
p = PreviousPosition(p);
printf ("%d out\n",Retrieve(NextPosition(p)));
Remove (NextPosition(p), &l);
n--;
m = M % n;
printf("current: ");
print(l);
}
}
测试结果：
1 2 3 4 5
4 out
current: 1 2 3 5
5 out
current: 1 2 3
3 out
current: 1 2
1 out
current: 2
这里给出循环双链表数据结构 ADT和实现
假定链表不带哨兵节点。
dlinkedlist.h
typedef int ElementType;
#ifndef DLINKEDLIST_H_INCLUDED
#define DLINKEDLIST_H_INCLUDED
struct Node;
typedef struc
|
