yueshefuhuanwenti.cpp

设计求解约瑟夫环问题的出列顺序。具体的要求和说明如下： （1）利用单向循环链表存储结构模拟此过程

/*设计求解约瑟夫环问题的出列顺序。具体的要求和说明如下： 
（1）利用单向循环链表存储结构模拟此过程，按照出列的顺序输出个人的编号。 
（2）m的初值为20；n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m的值为6（正确的出列顺序应为：6，1，4，7，2，3，5）。 
（3）程序运行后，首先要求用户指定初始报数的上限值，然后读取个人的密码。可设n<=30，此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。 
（4）将上述功能改为在顺序结构上实现。
*/



#include<stdio.h> 
#include<stdlib.h> 

#define MAX_NODE_NUM 30 
#define TRUE 1U 
#define FALSE 0U 

typedef struct NodeType 
{ int id; /* 编号 */ 
int cipher; /* 密码 */ 
struct NodeType *next; 
} NodeType; 

/* 创建单向循环链表 */ 
static void CreaList(NodeType **, const int); 
/* 运行"约瑟夫环"问题 */ 
static void StatGame(NodeType **, int); 
/* 打印循环链表 */ 
static void PrntList(const NodeType *); 
/* 得到一个结点 */ 
static NodeType *GetNode(const int, const int); 
/* 测试链表是否为空, 空为TRUE，非空为FALSE */ 
static unsigned EmptyList(const 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--------------the situation of Sets out printing---------------\n"); 
StatGame(&pHead, m); 
printf("\n\"Joseph link\"The question completes!\n"); 
return 0; 
} 
static void CreaList(NodeType **ppHead, const int n) 
{ 
int i,iCipher; 
NodeType *pNew, *pCur; 

for(i=1;i<=n;i++) 
{ 
printf("input the %d person's password:",i); 
scanf("%d", &iCipher); 
pNew=GetNode(i,iCipher); 
if(*ppHead==NULL) 
{ 
*ppHead=pCur=pNew; 
pCur->next=*ppHead; 
} 
else 
{ 
pNew->next=pCur->next; 
pCur->next=pNew; 
pCur=pNew; 
} 
} 
printf("Completes the e-way circulation chain table the foundation!\n"); 
} 

static void StatGame(NodeType **ppHead, int iCipher) 
{ 
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<iCipher;iCounter++) 
{ 
pPrv=pCur; 
pCur=pCur->next; 
} 
if(pPrv==pCur) /* 是否为最后一个结点了 */ 
iFlag=0; 
pDel=pCur; /* 删除pCur指向的结点，即有人出列 */ 
pPrv->next=pCur->next; 
pCur=pCur->next; 
iCipher=pDel->cipher; 
printf("The %d person Leaving ranks, password: %d\n", 
pDel->id, /* 这个编号标识出列的顺序 */ 
pDel->cipher); 
free(pDel); 
} 
*ppHead=NULL; /* 没人了！为了安全就给个空值 */ 
} 

static void PrntList(const NodeType *pHead) 
{ 
const NodeType *pCur=pHead; 

if (EmptyList(pHead)) 
return; 

do 
{ 
printf("The %d person, password: %d\n",pCur->id,pCur->cipher); 
pCur=pCur->next; 
} while (pCur!=pHead); 
} 

static NodeType *GetNode(const int iId,const 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->cipher=iCipher; 
pNew->next=NULL; 

return pNew; 
} 

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

return FALSE; 
}