首页 > 代码库 > 数据结构之猴王问题
数据结构之猴王问题
#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;
}
数据结构之猴王问题