jhuan.cpp

约瑟夫环的问题一定要顶啊 大家快来顶

#include<stdio.h> 
#include<stdlib.h> 
#define MAX_NODE_NUM 30 
#define TRUE 1
#define FALSE 0 

typedef struct NodeType {   //定义结点
	int id; /* 编号 */ 
	int scnum; /* 密码 */ 
	struct NodeType *next; 
} NodeType; 

/* 创建单向循环链表 */ 
void CreaList(NodeType **, int); 
/* 运行"约瑟夫环"问题 */ 
void StatGame(NodeType **, int); 
/* 打印循环链表 */ 
//void PrntList(NodeType *); 
/* 得到一个结点 */ 
NodeType *GetNode(int, int); 
/* 测试链表是否为空, 空为TRUE，非空为FALSE */ 
//unsigned EmptyList(NodeType *); 

int main(void) { 
	int n, m; 
	NodeType *pHead=NULL; 
	while(1) {
		printf("please input the number of the person n(<=%d):",MAX_NODE_NUM); 
		scanf("%d",&n); 
		printf("and Initial password m:"); 
		scanf("%d",&m); 
		if(n>MAX_NODE_NUM) {
			printf("The number is too big, please input again!\n"); 
			continue; 
		} 
		else 
			break; 
	} 
	CreaList(&pHead,n); 
	//printf("\n----Circulation chain table primitive printing-----\n"); 
	//PrntList(pHead); 
	printf("出队的顺序\n"); 
	StatGame(&pHead, m); 
	printf("\n环问题结束\n"); 
	return 0; 
} 
/* 用头插法创建单向循环链表 */ 
void CreaList(NodeType **ppHead, int n) 
{ 
	int i,scnum; 
	NodeType *pNew, *pCur; 
	for(i=1;i<=n;i++) 
	{ 
		printf("input the %d person's password:",i); 
		scanf("%d", &scnum); 
		pNew=GetNode(i,scnum);    //生成一个第i个结点 
		if(*ppHead==NULL)         //判断是否是头结点
		{ 
			*ppHead=pCur=pNew; 
			pCur->next=*ppHead; 
		} 
		else                     //非头结点
		{ 
			pNew->next=pCur->next; 
			pCur->next=pNew; 
			pCur=pNew; 
		} 
	} 
	printf("用头插法创建单向循环链表完成\n"); 
} 
/* 运行"约瑟夫环"问题 */ 
void StatGame(NodeType **ppHead, int iscnum) 
{ 
	int iCounter, iFlag=1; 
	NodeType *pPrv, *pCur, *pDel; 
	pPrv=pCur=*ppHead; 
//	/* 将pPrv初始为指向尾结点，为删除作好准备 */ 
//	while(pPrv->next!=*ppHead) //判断是否运行完毕
//		pPrv=pPrv->next; 
	while(iFlag) /* 开始数数,并删除结点! */ 
	{ 
		/* 这里是记数，无非是移动iCipher-1趟指针! */ 
		for(iCounter=1;iCounter<iscnum;iCounter++) 
		{ 
			pPrv=pCur; 
			pCur=pCur->next; 
		} 
		if(pPrv==pCur) /* 是否为最后一个结点了 */ 
			iFlag=0; 
		pDel=pCur; /* 删除pCur指向的结点，即有人出列 */ 
		pPrv->next=pCur->next; 
		pCur=pCur->next; 
		iscnum=pDel->scnum; 
		printf("第%d 人出队,密码是: %d\n", 
			pDel->id, /* 这个编号标识出列的顺序 */ 
			pDel->scnum); 
		free(pDel); 
	} 
	*ppHead=NULL; /* 删除完毕,环中的人全部出列！
	                  为了安全就给个空值 */ 
} 
/*void PrntList(NodeType *pHead) { 
	NodeType *pCur=pHead; 
	if (EmptyList(pHead)) 
		return; 
	do { 
		printf("The %d person, password: %d\n",pCur->id,pCur->scnum); 
		pCur=pCur->next; 
	} while (pCur!=pHead); 
} */

NodeType *GetNode(int iId,int iCipher) 
{ 
	NodeType *pNew; 
	pNew=(NodeType *)malloc(sizeof(NodeType)); 
	if(!pNew) 
	{ 
		printf("Error,the memory is not enough!\n"); 
		exit(-1); 
	} 
	pNew->id=iId; 
	pNew->scnum=iCipher; 
	pNew->next=NULL; 
	return pNew; 
} 

/*unsigned EmptyList(NodeType *pHead) 
{ 
	if(!pHead) 
	{
		printf("The list is empty!\n"); 
		return TRUE; 
	} 
	return FALSE; 
} */