约瑟夫问题算法.cpp

数据结构算法之 约瑟夫算法

#include <malloc.h>
#include <stdio.h>
#define LEN sizeof(struct student)
struct student
{int num;
 struct student * next;
 };
struct student *creat(int n)
{struct student *head,*p,*q;
 int i;
 p = (struct student*)malloc (LEN);
 head =p;
 p->next= p;
 p->num=1;
 for(i=2;i<=n;i++)
  {q = (struct student*)malloc (LEN);
   q->num=i;
   q->next = p->next;
   p->next =q;
   p= q;

  }
return (head);
}
struct student *start(struct student *head,int n,int k,int m)
{struct student *newhead, *p,*q,*temp;
 int i,j;
 p=head;
 while(p->num!=k)
   {p=p->next;}
 for(i=1;i<=n;i++)
  { for (j=1;j<m-1;j++)
	{p=p->next;
	 }
	 temp=p->next;
	 p->next=temp->next;
	 if(i==1){newhead=temp;q=temp;}
	 else
		{q->next =temp;
		 q=temp;
		}
	 p=p->next;
 }
 return(newhead);
}
void print(struct student *head,int n)
{struct student *p;
 int i;
 p=head;
 for(i=1;i<=n ;i++)
  {printf("%d " ,p->num);
   p=p->next;}
}
void main()
{struct student *oldhead,*newhead,stu;
 int n,m,k;
 printf("\n");
 printf("please enter the number of student in the game:\n");
 scanf("%d",&n);
 printf("please enter the start number:\n");
 scanf("%d",&k);
 printf("please enter the count number:\n");
 scanf("%d",&m);
 oldhead=creat(n);
 printf("the original sequence is:\n");
 print(oldhead,n);
 printf("\n");
 newhead=start(oldhead,n,k,m);
 printf("after the game,the sequence is:");
 print(newhead,n);
}