约瑟夫环是一个经典的数学的应用问题：已知N个人（以编号1，2，3...N分别表示）围坐在一张圆桌周围。从编号为1的人开始报数，数到M的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
这里使用循环单链表解决约瑟夫环问题，该循环单链表不带哑元头结点，相比于带有哑元头结点的循环单链表，对不带带有哑元头结点的循环单链表的相关操作，包括插入，删除，销毁等操作相对麻烦一点，稍不注意可能就有bug,所以一定要细心才对。
下面的求解约瑟夫问题的核心算法思想来自于《算法：C语言实现》这本书，代码的重点部分已经标注，当然有时间还会对代码优化。假设已经建立长度为N的链表。
/*---------------------------约瑟夫问题核心代码：--------------------------------*/
ListNode *p=head;
while(p->next!=head)//循环的目的是让p指向链表的尾节点
{
p=p->next;
}
while(p!=p->next)//循环开始时，p指向链表的尾节点
{
for(i=1;i<M;i++)
p=p->next;
ListNode *targetnode=p->next;
cout<<targetnode->item<<"出局"<<endl;
p->next=p->next->next;
free(targetnode);
}
cout<<p->item<<"胜出"<<endl;
free(p);
不带哑元头结点的一些基本操作：
链表节点类型
typedef struct Node
{
int item;
struct Node *next;
}ListNode,*List;
1.插入——头插法
List InsertNodeToFront(List head,int data)//------------头插法
{
ListNode *newnode=(List)malloc(sizeof(ListNode));//创建新节点
assert(newnode);
newnode->item=data;
newnode->next=NULL;
if(head==NULL)
{
head=newnode;
head->next=head;
}
else
{
/*--------------------------------------------------*/
ListNode *p=head;//由于是头插法，插入一个节点，表头指针head的指向就会改变
while(p->next!=head)//由于是循环链表，链表的尾节点的next指针指向也会改变，
{ //需要指向新的表头，因此，需要在改变表头前，将尾节点找到
p=p->next;
}
/*---------------------------------------------------*/
newnode->next=head;
head=newnode;
p->next=head;
}
return head;
}
2.插入——尾插法
List InsertNodeToTail(List head,int data)//--------尾插法
{
ListNode *newnode=(List)malloc(sizeof(ListNode));//创建新节点
assert(newnode);
newnode->item=data;
newnode->next=NULL;
if(head==NULL)
{
head=newnode;
head->next=head;//
}
else
{
ListNode *p=head;
while(p->next!=head)
{
p=p->next;
}
p->next=newnode;
newnode->next=head;//
}
return head;
}
3.查找：
bool FindNode(List head,int data)//查找链表中含有某元素的节点是否存在
{
if(head==NULL)
{
cout<<"the Dlist is NULL"<<endl;
return false;
}
ListNode *p=head;
do
{
if(p->item==data)
return true;
p=p->next;
}while(p!=head);
return false;
}
4.删除：
List DeleteNode(List head,int data)//删除节点
{
assert(head);
ListNode *p=head;
ListNode *pre=NULL;
for(;p!=head;pre=p,p=p->next)
{
if(p->item==data)
break;
}
if(p==head && pre!=NULL)//没找到节点
{
cout<<"the target listnode DOESN'T exist!"<<endl;
}
if(p==head && pre==NULL)//当表头就是目标节点时
{
/*------------------------------------------------------*/
ListNode *temp=head;
while(p->next!=temp)//找到链表中的尾节点p,由于链表的头结点要变，所以p->next所指向肯定要变（指向新的头结点）
{
p=p->next;
}
/*--------------------------------------------------------*/
head=head->next;
p->next=head;//尾节点指向新的头结点
free(temp);
}
else
{
ListNode *tmp=p;
pre->next=p->next;
free(tmp);
}
return head;
}
5.打印和销毁
void PrintList(List head)//打印
{
if(head==NULL)
{
cout<<"the list is NULL"<<endl;
return ;
}
ListNode *p=head->next;
cout<<head->item<<" ";
while(p!=head)
{
cout<<p->item<<" ";
p=p->next;
}
cout<<endl<<endl;
}
void DestroyList(List head)
{
while(head!=head->next)//释放内存，直到链表中只剩下一个节点
{
head=DeleteNode(head,head->item);//从表头开始释放
}
cout<<head->item<<endl;
free(head);//将链表中剩下的最后一个节点进行释放
head=NULL;
}
完整代码：M=5，N=9，9个人的编号分别为1,2,3,4,5,6,7,8,9,（1处为链表头），从编号1按规则进行约瑟夫选举，最终8胜出
/***************************************************************************
*name:jae chia *
*date:2014.8.30 *
*version: 1.0 *
*********************循环链表解决约瑟夫环问题******************************/
#include<iostream>
#include<cassert>
using namespace std;
typedef struct Node
{
int item;
struct Node *next;
}ListNode,*List;
List InsertNodeToTail(List head,int data)//--------尾插法
{
ListNode *newnode=(List)malloc(sizeof(ListNode));//创建新节点
assert(newnode);
newnode->item=data;
newnode->next=NULL;
if(head==NULL)
{
head=newnode;
head->next=head;//
}
else
{
ListNode *p=head;
while(p->next!=head)
{
p=p->next;
}
p->next=newnode;
newnode->next=head;//
}
return head;
}
List InsertNodeToFront(List head,int data)//------------头插法
{
ListNode *newnode=(List)malloc(sizeof(ListNode));//创建新节点
assert(newnode);
newnode->item=data;
newnode->next=NULL;
if(head==NULL)
{
head=newnode;
head->next=head;
}
else
{
/*--------------------------------------------------*/
ListNode *p=head;//由于是头插法，插入一个节点，表头指针head的指向就会改变
while(p->next!=head)//由于是循环链表，链表的尾节点的next指针指向也会改变，
{ //需要指向新的表头，因此，需要在改变表头前，将尾节点找到
p=p->next;
}
/*---------------------------------------------------*/
newnode->next=head;
head=newnode;
p->next=head;
}
return head;
}
bool FindNode(List head,int data)//查找链表中含有某元素的节点是否存在
{
if(head==NULL)
{
cout<<"the Dlist is NULL"<<endl;
return false;
}
ListNode *p=head;
do
{
if(p->item==data)
return true;
p=p->next;
}while(p!=head);
return false;
}
List DeleteNode(List head,int data)//删除节点
{
assert(head);
ListNode *p=head;
ListNode *pre=NULL;
for(;p!=head;pre=p,p=p->next)
{
if(p->item==data)
break;
}
if(p==head && pre!=NULL)//没找到节点
{
cout<<"the target listnode DOESN'T exist!"<<endl;
}
if(p==head && pre==NULL)//当表头就是目标节点时
{
/*------------------------------------------------------*/
ListNode *temp=head;
while(p->next!=temp)//找到链表中的尾节点p,由于链表的头结点要变，所以p->next所指向肯定要变（指向新的头结点）
{
p=p->next;
}
/*--------------------------------------------------------*/
head=head->next;
p->next=head;//尾节点指向新的头结点
free(temp);
}
else
{
ListNode *tmp=p;
pre->next=p->next;
free(tmp);
}
return head;
}
void PrintList(List head)//打印
{
if(head==NULL)
{
cout<<"the list is NULL"<<endl;
return ;
}
ListNode *p=head->next;
cout<<head->item<<" ";
while(p!=head)
{
cout<<p->item<<" ";
p=p->next;
}
cout<<endl<<endl;
}
void DestroyList(List head)
{
while(head!=head->next)//释放内存，直到链表中只剩下一个节点
{
head=DeleteNode(head,head->item);//从表头开始释放
}
cout<<head->item<<endl;
free(head);//将链表中剩下的最后一个节点进行释放
head=NULL;
}
void JosephRingTest1()
{
int M,N;
int a;//编号
cout<<"input M（规则） and N(人数）:"<<endl;
cin>>M>>N;
List head=NULL;
int i;
for(i=0;i<N;i++)
{
cin>>a;
head=InsertNodeToTail(head,a);//尾插
}
cout<<"初始化后的链表:"<<endl;;
PrintList(head);
/*---------------------------约瑟夫问题核心代码：--------------------------------*/
ListNode *p=head;
while(p->next!=head)//循环的目的是让p指向链表的尾节点
{
p=p->next;
}
while(p!=p->next)//循环开始时，p指向链表的尾节点
{
for(i=1;i<M;i++)
p=p->next;
ListNode *targetnode=p->next;
cout<<targetnode->item<<"出局"<<endl;
p->next=p->next->next;
free(targetnode);
}
cout<<p->item<<"胜出"<<endl;
free(p);
/*---------------------------------------------------------------------------------*/
}
int main(void)
{
JosephRingTest1();
}
运行：
