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 struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
List CreateList (ElementType X);
void DisposeList(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
void Remove(Position P, List * L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
Position NextPosition(Position P);
Position PreviousPosition (Position P);
ElementType Retrieve(Position P);
#endif // DLINKEDLIST_H_INCLUDED
fatal.h
#ifndef FATAL_H_INCLUDED
#define FATAL_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#define Error(Str) FatalError(Str)
#define FatalError(Str) fprintf(stderr, "%s\n", Str), exit(1)
#endif // FATAL_H_INCLUDED
dlist.c
#include "dlinkedlist.h"
#include "fatal.h"
struct Node
{
ElementType Element;
Position Next;
Position Prev;
};
List CreateList(ElementType X)
{
List L;
L = malloc(sizeof(struct Node));
if(L == NULL)
FatalError("Out of space!!!");
L- >Next = L->Prev = L;
L->Element = X;
return L;
}
void DisposeList(List L)
{
if(L->Next != L)
DeleteList(L);
free(L);
}
/* Return true if L is empty */
int IsEmpty(List L)
{
return L == NULL;
}
/* Return true if P is the last position in list L */
/* Parameter L is unused in this implementation */
int IsLast(Position P, List L)
{
return P == L;
}
/* Return Position of X in L; NULL if not found */
Position Find(ElementType X, List L)
{
if (L->Element == X)
return L;
Position P;
P = L->Next;
while(P != L && P- >Element != X)
P = P->Next;
if (P == L) //not found
P = NULL;
return P;
}
/* Delete from a list */
/* Cell pointed to by P->Next is wiped out */
/* Assume that the position is legal */
void Delete(ElementType X, List L)
{
Position P;
P = Find(X, L);
if (P != NULL)
Remove(P, &L);
}
void Remove (Position P, List * L)
{
if(P == *L)
{
if ((*L)->Next == *L)
{
free(*L);
*L = NULL;
return;
}
*L = (*L)->Next;
}
P->Prev->Next = P->Next;
P->Next ->Prev = P->Prev;
free(P);
}
/* Insert (after legal position P) */
/* Tailer implementation assumed */
/* Parameter L is unused in this implementation */
void Insert(ElementType X, List L, Position P)
{
Position TmpCell;
TmpCell = malloc(sizeof (struct Node));
if(TmpCell == NULL)
FatalError ("Out of space!!!");
TmpCell->Element = X;
TmpCell->Next = P->Next;
P->Next->Prev = TmpCell;
TmpCell->Prev = P;
P->Next = TmpCell;
}
void DeleteList(List L)
{
Position P, Tmp;
P = L->Next; /* Tailer assumed */
L->Next = L;
L- >Prev = L;
while(P != L)
{
Tmp = P->Next;
free( P );
P = Tmp;
}
}
Position NextPosition(Position P)
{
return P->Next;
}
Position PreviousPosition(Position P)
{
return P->Prev;
}
ElementType Retrieve(Position P)
{
return P->Element;
}
這裡要注意的是函數Remove()
void Remove(Position P, List * L)
{
if(P == *L)
{
if ((*L)->Next == *L)
{
free(*L);
*L = NULL;
return;
}
*L = (*L)->Next;
}
P->Prev->Next = P- >Next;
P->Next->Prev = P->Prev;
free(P);
}
List本身是一個指針，而這裡選擇List的指針，即指針的指針作為行參， 目的是當刪除的節點是首元節點時，需要修改指針的值，即地址，所以傳遞指針的指針。就 好比如果需要修改int的值，則行參傳遞int *；同樣如果需要修改int *的值，則行參傳遞 int **。
