约瑟夫环问题的二种解决方法

    约瑟夫环问题的一种描述是：编号为1，2。。。n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。测试数据：m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。

    上面为数据结构老师前些天布置的作业。下面为我的算法。第一种用引用传递参数，第二种用指针传递参数。其实实际算法是一样的。

第一种方法源码：

#include
#define null 0
using namespace std;
typedef struct node   //定义每个人结点
{
 int password;
 int num;
 node *next;
}*Link;
typedef struct //定义环形链表
{
 Link head;
}LinkList;
void InitList(LinkList &L)//初始化环形链表
{
 int n;
 Link p=L.head=new node;
 cout<<"请输入结点个数:";
 cin>>n;
 if(n<=0)
 {
  cout<<"你的输入有误，程序退出."<  exit(0);
 }
 else
 {
  for(int i=1;i<=n;i++)
  { 
   p=p->next=new node;
   p->num=i;
   cout<<"请输入第"<   cin>>p->password;
  }
  p->next=L.head->next;
 }
}
void run(LinkList &L,int n)//计算出列顺序，并输出。
{
 Link p=L.head->next;
 Link q=p;
 if(p==p->next)
 {
  cout<num;
  delete p;
  cout<  exit(0);
 }
 else
 {
  for(int i=1;i  {
   p=p->next;
  }
  while(q->next!=p)
  {
   q=q->next;
  }
  q->next=p->next;
  n=p->password;
  L.head->next=p->next;
  cout<num<<" ";
  delete p;
  run(L,n);
 }
}
int main()//主函数
{
 LinkList L;
 int t;
 InitList(L);
 cout<<"请输入初始密码:";
 cin>>t;
 run(L,t);
 return 0;
}
第二种方法源码：

#include
using namespace std;
#define null 0
class node//定义人类型
{
 public:
  node *node::creat();
  void node::run(node *,int );
 private:
  int num;
  int password;
  node *next;
};
node *node::creat()//创建环形链表
{
 node *p=null;
 node *head=null;
 int n;
 cout<<"请输入人的个数:";
 cin>>n;
 if(n==0)
 {
  cout<<"链表为空."<  exit(0);
 }
 else if(n==1)
 {
  head=new node;
  head->next=head;
  head->num=1;
 }
 else
 {
  p=head=new node;
  cout<<"请输入第1个人的密码:";
  p->num=1;
  cin>>head->password;
  for(int i=2;i<=n;i++)
   {
    p=p->next=new node;
    cout<<"请输入第"<    p->num=i;
    cin>>p->password;
   }
  p->next=head;
 }
 return head;
}
void node::run(node *head,int n)//计算出列顺序，并输出。
{
 node *p=head;
 node *q=head;
 if(head==head->next)
 { 
  cout<num;
  delete head;
 }
 else
 {
  for(int i=1;i  {p=p->next;}
  while(q->next!=p)
  {q=q->next;}
  q->next=p->next;
  n=p->password;
  head=p->next;
  cout<num<<" ";
  delete p;
  run(head,n);
 }
}
int main()//主函数
{
 node *p=null;
 int i;
 p=p->creat();
 cout<<"请输入初始密码:";
 cin>>i;
 cout<<"出列顺序为:"< p->run(p,i);
 cout< return 0;
}
由于时间匆忙，测试数据不够多，有可能存在bug。如果有哪位找到请指出。