学步园

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

//用循环链表实现

 

#include

using namespace std;

typedef struct Node

{

int data;

Node* next;

}LNode,*LinkList;

LNode * create(int num)

{

  LNode *s,*r,*head;

  r=NULL;

  s=NULL;

  head=NULL;

  int i=1;

  LinkList p;

  p=NULL;

  p=(LinkList)malloc(sizeof(LNode));

p->data=i;

p->next=NULL;

head=p;

r=p;

  for(i=2;i

  {

   
p=(LinkList)malloc(sizeof(LNode));

p->data=i;

p->next=NULL;

r->next=p;

r=p;

  }

  r->next=head;

  p=head;

  cout<<"原序列：";

  for(i=0;i

  {

 
 cout<<p->data<<" ";

   p=p->next;

  }

  return head;

}

int ysf(int n,int k,int m)//共有n个人,从编号为k的人开始报数，数到m的那个人出列；

{

 int i,j;

 LinkList L,pre,s,p,r;//pre记录待删除节点前的节点

 L=create(n);

 p=L;

 r=L;

 for(i=1;i

 {

r=r->next;

 }

 pre=r;

 for(i=1;i

 {

pre=p;

 p=p->next;

 }

 cout<<"出队顺序：";

for(j=0;j

{

 for(i=1;i

 {

pre=p;

p=p->next;

 }

 pre->next=p->next;

 cout<<p->data<<" ";

  free(p);

 p=pre->next;

}

cout<<p->data<<" ";

 free(p);

cout<<endl;

 return 0;

}

void main()

{

int n,k,m;

cout<<"输入总人数："<<endl;

cin>>n;

if(n<=0)

return;

cout<<"输入开始报数的编号："<<endl;

cin>>k;

if(k<=0)

return;

cout<<"输入出队的报数号："<<endl;

cin>>m;

if(m<=0)

return;

 ysf(n,k,m);

}