e.cpp

时间约瑟夫问题

#include"stdlib.h"
#include"stdio.h"
#include"string.h"
typedef struct Circle
{
	int location;
	struct Circle *next;
}CircleNode,*CircleList;
CircleList CreateList(int n,CircleList R);
CircleList DeleteList(int n,int k,CircleList R);
void OutputList(CircleList R,int n);
void main()
{
	CircleList R;
	int n,k;
	R=(CircleNode *)malloc(sizeof(CircleNode));
	printf("How many people are in the liner?\n");
	scanf("%d",&n);
	printf("input the upper limitation:\n");
	scanf("%d",&k);
	R=CreateList(n,R);
	R=DeleteList(n,k,R);
	OutputList(R,n);
	printf("\t\t\tThank you for using the system!\n");
	free(R);
	system("pause");
	return;
}

CircleList CreateList(int n,CircleList R)
{
	int i=2;
	CircleNode *p,*last;
	if(n<=0)   printf("Input error!"); 
	else
	{
		last=(CircleNode *)malloc(sizeof(CircleNode));
		R->location=1;
		last=R;
		while(i<=n)
		{
			p=(CircleNode *)malloc(sizeof(CircleNode));
			p->location=i;
			last->next=p;
			last=p;
			i++;
		}
		last->next=R;
	//	free(p);
		return R;
	}
}
CircleList DeleteList(int n,int k,CircleList R)
{
	int i,j;
	CircleNode *q,*last;
	if(n<0||k<0)  { printf("Input error!") ; return 0;}
	else
	{
	   last=(CircleNode *)malloc(sizeof(CircleNode));
	   q=(CircleNode *)malloc(sizeof(CircleNode));
       last=R;
	   for(i=1;i<=n/2;i++)
	   {
		   for(j=1;j<=k-1;j++)  last=last->next;
		   q=last->next;
		   printf("%4d",q->location);
		   if(i%10==0)  printf("\n");
		   last->next=q->next;
		   //free(q);
	   }
	   //free(last);
	  // free(q);
	   system("pause");
	   return R;
	}
}
void OutputList(CircleList R,int n)
{
	int i;
	CircleNode *p;
	p=(CircleNode *)malloc(sizeof(CircleNode));
	p=R;
	printf("The survial people are following:\n");
	for(i=1;i<=n/2;i++)
	{
		printf("%4d",p->location);
		if(i%10==0)  printf("\n");
		p=p->next;
	}
//	free(p);
	printf("\n");
}





/*对malloc和free的用法还不是清楚，free(p)和free((void *)p)的区别是什么*/