-----------------------------Josephus.h---------------------------------------------
#include<iostream>
#include<stdlib.h>
using namespace std;
template<class T>
struct CircLinkNode
{
T data;
CircLinkNode<T> *link;
CircLinkNode(CircLinkNode<T> *next=NULL):link(next){}
CircLinkNode(T d,CircLinkNode<T>*next=NULL):data(d),link(next){}
};
template<class T>
class CircList
{
public:
CircList(){first=new CircLinkNode<T>(1),first->link=first;}//定义为循环链表
~CircList(){}
CircLinkNode<T> *getHead()const{return first;}
CircLinkNode<T> *Locate(int &i);
bool Insert(int &i);
private:
CircLinkNode<T> *first;
};
template<class T>
CircLinkNode<T> *CircList<T>::Locate(int &i)
{
if(i<0) return NULL;
CircLinkNode<T> *current=first;
int k=2;
while(current!=NULL&&k<i)
{
current=current->link;
k++;
}
return current;
};
template<class T>
bool CircList<T>::Insert(int &i)
{
CircLinkNode<T> *current=Locate(i);
if(current==NULL) return false;
CircLinkNode<T> *newNode=new CircLinkNode<T>(i);
if(newNode==NULL)
{
cerr<<"存储分配错误!"<<endl;
exit(1);
}
newNode->link=first;
current->link=newNode;
return true;
};
-------------------------------main.cpp-----------------------------------
#include"CircList.h"
template<class T>
void Josephus(CircList<T>&Js ,int n,int m)
{
CircLinkNode<T> *p=Js.getHead(),*pre=NULL;
int i,j;
for(i=0;i<n-1;i++)
{
for(j=1;j<m;j++)
{
pre=p;
p=p->link;
}
cout<<"出列的人是"<<p->data<<endl;
pre->link=p->link;
delete p;
p=pre->link;
}
};
int main()
{
CircList<int> clist;
int i,n,m;
cout<<"输入游戏人数和报数者间隔: ";
cin>>n>>m;
for(i=2;i<=n;i++)
clist.Insert(i);
Josephus(clist,n,m);
return 0;
}
刚学数据结构就应该实现的程序，呵呵，到现在才去做.
下面是以前没学数据结构之前所写的代码
#include<iostream>
using namespace std;
int main()
{
int count=0;
int s=0;//记录退出的人的个数
int i;
int N;
int key;
int a[100];
cout<<"游戏人数和数字分别是:";
cin>>N>>key;
for(i=0;i<N;i++)
a[i]=i+1;
for(i=0;i<N;i++)
{
if(a[i]==-1)
{
if(i==N-1)//防止continue使循环退出
i=-1;
continue;
}
count++;
if(count==key)
{
a[i]=-1;
s++;
count=0;
}
if(i==N-1)
i=-1;
if(s==N-1)
break;
}
cout<<"留下的人是:";
for(i=0;i<N;i++)
if(a[i]!=-1)
cout<<a[i];
cout<<endl;
return 0;
}