yuesefu.cpp

本代码是约瑟夫环的循环链表实现方法,可以帮助理解约瑟夫环的基本原理,及其实现

#include"iostream.h"
#include"malloc.h"
typedef struct node{
	int num;
	struct node* next;
}lnode;

lnode* creat_link(int n);//创建循环链表
void print_link(lnode* head);//输出循环链表
void yuesefu(lnode* head,int n,int m);//约瑟夫环的实现
int main()
{
	int n,m;//n是总的人数，m是数的个数
	lnode* head;
	cin>>n;
	head=creat_link(n);
    // print_link(head);
	cin>>m;
    yuesefu(head,n,m);
	return 0;
}

lnode* creat_link(int n)
{
	lnode* head;
	lnode* p;
	lnode* s;
	int i;
	head=(lnode*)malloc(sizeof(lnode));
    head->num=1;
	p=head;
	for(i=2;i<=n;i++)
	{
      s=(lnode*)malloc(sizeof(lnode));
	  s->num=i;
	  p->next=s;
	  p=s;
	}
	p->next=head;
	return head;
}

void print_link(lnode* head)
{
	lnode* p;
	p=head;
	cout<<p->num<<endl;
	p=p->next;
	while(p!=head)
	{
		cout<<p->num<<endl;
        p=p->next;
	}
}



void yuesefu(lnode* head,int n,int m)
{
	int count;//用于循环计数
	lnode* pre;
	lnode* p=head;
	do 
	{	
	count=1;
	while(count<m-1)
	{
		p=p->next;
		count++;
	}//此时count为m-1，p为要删除的节点的前一节点
	pre=p;
	p=p->next;//找到要删除的点的位置
    pre->next=p->next;
	cout<<p->num<<endl;
	free(p);
	head=pre->next;
	p=head;
	n--;
	}while(n>=1);
}