约瑟夫环.cpp

约瑟夫环：编号为1,2,3,…,n的n个人按顺时针方向围坐一圈

/**约瑟夫环：编号为1,2,3,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选
一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人出列，
将他的密码作为新的m值，从他在顺时针方向上的下一人开始重新从1报数，如此下去，直到所有人全部出列为
止。编程打印出列顺序。
**/
#include "stdio.h"
#include "malloc.h"

#define ok 1
#define error 0

typedef struct node{
	int num,data;
	struct node *next;
}Lnode,*LinkList;//定义一个结点

LinkList head,p,pt;

int CreatList(int n){
	int i;
	if (n<0) return error; 
	head=(LinkList)malloc(sizeof(Lnode));
	p=head;
	for(i=1;i<n;i++){
		pt=(LinkList)malloc(sizeof(Lnode));
		p->next=pt;
		p=p->next;
	}
	pt->next=head;
	p=pt=head;
	return ok;
}//创建一个链表

int DeleteList(int n,int m){
    int i,j;
	p=pt=head;
	for(i=1;i<=n;i++){
		pt=p;
		for(j=1;j<m-1;j++)
			p=p->next;
		pt=p->next;
		m=pt->data;
		printf(" %d\n",pt->num);
		p->next=pt->next;
		p=pt->next;
		free(pt);
	}
	return ok;
}//按要求删除链表并输出删除值
void main(){
	int m,n,k,i;
    printf("请输入总人数：\n");
	scanf("%d",&n);
	CreatList(n);
	printf("请输入密码：\n\n");
	for(i=1;i<=n;i++){
		printf("第%d个人的密码: ",i);;
		scanf("%d",&k);
		printf("\n");
		p->num=i;
		p->data=k;
		p=p->next;
	}
	printf("请输入报数初值:\n");
	scanf("%d",&m);
	printf("出列顺序为:\n");
	DeleteList(n,m);
}