首页 > 代码库 > 数据结构之猴王问题

数据结构之猴王问题

 

#include <stdio.h>
#include <stdlib.h>
#define NULL 0
#define ERROR 0
#define OVERFLOW -2
#define OK 1
typedef int Status ;
typedef int ElemType;
typedef struct CNode
{

ElemType data;
struct CNode *next;
}CNode;

CNode *joseph;
int monky;
Status Create_clist(CNode *clist,int n)
{

CNode *p,*q;
int i;
clist=NULL;

for(i=n;i>=1;i--)
{
p=(CNode *)malloc(sizeof(CNode));
if(!p) return OVERFLOW;

p->data=http://www.mamicode.com/i;

p->next=clist;

clist=p;

if(i==n)
q=p;

}
q->next=clist;

joseph=clist;
return OK;


}

Status Joseph(CNode *clist,int m,int n,int k)
{

int i;
CNode *p,*q,*q13;

if(m>n) return ERROR;


p=joseph;

for(i=1;i<m;i++)
{
p=p->next;
}
while(p)
{

for(i=1;i<k-1;i++)
{
p=p->next;

}
if(k==2)
{
q13=p;
}
if(k==1)
{
p=q13;
}
q=p->next;
printf("%d\t",q->data);

if(p->next==p)
{
monky=p->data;
p=NULL;
}
else{

p->next=q->next;
p=p->next;
free(q);
}

k=k-1;
if(k==0) k=13;

}

clist=NULL;


}
int main()
{

int m,n,k,i;
printf("\n----------------------------------------------------------------");
printf("\ninput the count of monky:");
scanf("%d",&n);
printf("\ninput the number of start:");
scanf("%d",&m);
CNode *clist;
clist=NULL;
k=13;
printf("\n----------------------------------------------------------------\n");
Create_clist(clist,n);
Joseph(clist,m,n,k);
printf("\n----------------------------------------------------------------\n");
printf("the king of monky is %d .",monky);
printf("\n----------------------------------------------------------------\n");
return 0;
}

数据结构之猴王问题