jose.c

约瑟夫问题。能够实现最基本的约瑟夫问题操作

#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TRUE 1
#define NULL0
typedef int DataType;
struct Node;
typedef struct Node *PNode;
struct Node{
	DataType info;
	PNode link;
};
typedef struct Node*LinkList;
typedef LinkList*PLinkList;
int init_clist(PLinkList pclist,int n)
{PNode p,q;
int i;
q=(PNode)malloc(sizeof(struct Node));
if (q==NULL)return (FALSE);
*pclist=q;
q->info=1;
q->link=q;
if (n==1)return (TRUE);
for (i=2;i<n+1;i++)
{p=(PNode)malloc(sizeof(struct Node));
if (p==NULL)return (FALSE);
p->info=i;
p->link=q->link;
q->link=p;
q=p;
}
return (TRUE);
}
void josephus_clist(PLinkList pclist,int s,int m)
{PNode p,pre;
int i;
p=*pclist;
if(s==1){
	pre=p;
	p=p->link;
	while (p!=*pclist){
		pre=p;
		p=p->link;
	}
}
else for (i=1;i<s;i++){
	pre=p;
	p=p->link;
}
while (p!=p->link){
	for (i=1;i<m;i++)
	{pre=p;
	p=p->link;
	}
	printf("Out element:%d \n",p->info);
	if (*pclist==p)
		*pclist=p->link;
	pre->link=p->link;
	free(p);
	p=pre->link;}
printf("Out element:%d \n",p->info);
*pclist=NULL;
free(p);
}
main()
{LinkList jos_clist;
int n,s,m;
do {
	printf("\n please input the valuesof n=");
	scanf("% d",&n);
}while (n<1);
do {
	printf("please input the values of s=");
	scanf("% d",&s);
}while (s<1);
do {
	printf("please input the values of m=");
	scanf("% d",&m);
}while (m<1);
if (init_clist(&jos_clist,n))
josephus_clist(&jos_clist,s,m);
else
printf("Out of space! \n");
}