约瑟夫环（链表表示）.cpp

约瑟夫环

#include<iostream>
using namespace std;

typedef struct {
	int num;//位号
	int m;//密码
}elemtype;

typedef struct lnode{
	elemtype data;
	struct lnode *next;
}lnode, *linklist;

linklist p;
void create_l(linklist &l,int n){
//输入n个元素的值，建立不带表头的循环链表l
	l=(linklist)malloc(sizeof(lnode));
	p=l;
	for(int i=0;i<n;i++){
		cin>>p->data.m;
		p->data.num=i+1;
		if(i==n-1) break;
		p->next=(linklist)malloc(sizeof(lnode));
		p=p->next;
	}
	p->next=l;
}

void jos(int m,int n){
	linklist l;
	cout<<"请依次输入"<<n<<"个密码:";
	create_l(l,n);
	cout<<"出列顺序为:";
	p=l;
	linklist r;
	while(p->next!=l) p=p->next;
	linklist q=p;  p=l;
	do{
		for(int i=1;i<m;i++){
			q=p;  p=p->next;
		}
		q->next=p->next;
		r=p;  p=p->next;
		cout<<r->data.num<<" ";
		m=r->data.m;
		free (r);
	}while(p->next!=p);
	cout<<p->data.num<<endl;
}

void main()
{

	int n,m; 
	cout<<"请输入初始密码m和人数n：";
	cin>>m>>n;
	jos(m,n);
}