Question

猴子选大王问题 我有代码，且可运行，帮我解释下。

#include <stdio.h>
#include <malloc.h>

struct monkey{
int num;
struct monkey* next;
};//定义节点结构体
struct monkey* CreateLink(int n);
int KingOfMonkeys(struct monkey* head, int m);

struct monkey* CreateLink(int n)
{
int i=0;
struct monkey *head=NULL;
struct monkey *temp=NULL;
struct monkey *newNode=NULL;
for(i=0; i<n; i++)
{
if(head==NULL)
{
head=(struct monkey*)malloc(sizeof(struct monkey));
head->num=i+1;
head->next=head;
temp=head;
}
else
{
newNode=(struct monkey*)malloc(sizeof(struct monkey));
newNode->num=i+1;
temp->next=newNode;
newNode->next=head;
temp=newNode;
}
}
return head;
}

int KingOfMonkeys(struct monkey* head, int m)
{
int i;
struct monkey *temp=head;
for(i=1;temp->next!=temp;i++)
{
if(i%m==0)
{
if(head==temp)
{
while(temp!=head->next)
head=head->next;
}
head->next=temp->next;//到n前面那个节点停，然后删除第n个节点
free(temp);//释放内存，防止内存泄露
temp=head->next;
}
else
{
head=temp;
temp=temp->next;
}
}
return temp->num;
}

void main()
{
int m, n, king;//定义m,n还有最后的大王
struct monkey *head=NULL;//初始化猴子大王的位子
printf("Please enter the number of the monkeys(m):\n");
scanf("%d",&m);//输入猴子数
printf("Please enter the value of n:\n");
scanf("%d",&n);//输入N
/*确保输入的m大于n的值且符合题意*/
if(m<n||m==n||m==0||n==0||m<0||n<0)
printf("Wrong enter!\n");
else
{
head=CreateLink(m);
king=KingOfMonkeys(head, n);
printf("The king of the monkeys is number: %d\n", king);
}
}

Answer 1

CreateLink 函数 建立了一个循环链表
每次生成一个新节点，将尾指针指向新节点，并将新节点指向head

KingOfMonkeys函数 就是计算出第N个猴子，然后通过修改指针指向从循环链表中剔除该节点
之后free掉此节点回收内存，最后只剩余1个节点是就是所求。