lan.c

数据结构实验 循环链表josephus问题 N人围坐循环报数出列

#include "stdio.h"
#include "malloc.h"
typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode, * LinkList;

LinkList Createlist_L(int n)        //此部分有改动
{
	LinkList L,P,Mark;
	int i;
	L=(LinkList )malloc(sizeof(LNode));
	L->data=1;             
	L->next=NULL;
	Mark=L;                     //增加了此行，为了处理n=1时的情况
	for(i=n;i>1;i--)
	{
		P=(LinkList)malloc(sizeof(LNode));
		P->data=i;
		if(i==n) Mark=P;
		P->next=L->next;L->next=P;	 
	}
	Mark->next=L;
	return L; //L->1 2 3 4...n->L
}
LinkList GetElem_L(LinkList L,int s,int n)//寻找第S的前一个节点
{
	int j=2,i;
	if(s==1)
		for(i=1;i<n;i++)
			L=L->next;
	else	
		while(j++<s)		
			L=L->next;	
	return L;
}
Delete(LinkList P,int m,int n)
{
	LinkList q;
	int j,i;
	printf("出列顺序为：");
	for(j=0;j<n;j++)
	{
		for(i=1;i<m;i++)  P=P->next;
		printf("%d ",P->next->data);
		q=P->next;
		P->next=q->next;
		free(q);
	}
}

main()
{
	int n,s,m;
	LinkList L,P;
	printf("请按序输入围圈人数n,开始报数人位置s,出列人位置m：");
	scanf("%d,%d,%d",&n,&s,&m);
	L=Createlist_L(n);
	P=GetElem_L(L,s,n);
	Delete(P,m,n);  
}