[C++知识库]C语言数据结构——————约瑟夫环

经典例题如下：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（n个）按照1-n的顺序围坐一圈，从第1开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。请设计算法编写程序输出为大王的猴子的编号。

分析完之后，无非是解决循环到间隔之后的删除指针操作，和循环队列的创建这两个问题

首先来解决循环队列的问题，代码如下（如有错误，还请指正！）：

void add(Node*head)//增加结点 
{int num;//定义总数 
int count=2;
Node*pd=head; 
printf("输入猴子总数\n");
scanf("%d",&num);
pd->d=1;
for(int i=0;i<num-1;i++)//遍历总数创建结点 
{Node*pn=(Node*)malloc(sizeof(Node));
pn->d=count++;//分配序号 
pn->next=NULL;
pd->next=pn;
pd=pn;

if(num-2==i)
{pn->next=head;//实现循环队列 
}
}
}

接下来是到一定间隔后的删除指针操作

void search(Node*head)//查找函数 
{Node*pd=head;
int interval;//定义间隔 
printf("输入间隔\n");
scanf("%d",&interval);
while(pd!=pd->next)
{for(int i=0;i<interval-2;i++)
{pd=pd->next;
}
Node*e=pd->next;
pd->next=e->next;
free(e);//释放删除的空间 
e=NULL;//删除找到的结点 
pd=pd->next;}
printf("找到的号码为%d",pd->d);//输出找到的结点 
}

完整代码如下

#include"stdio.h"
#include"stdlib.h"
typedef struct node
{
	int d;
	struct node*next;
}Node;
Node*ctlist()//创建头指针 
{Node*head=(Node*)malloc(sizeof(Node));//分配空间 
head->next=NULL;//指针指向空 
return head;

}
void add(Node*head)//增加结点 
{int num;//定义总数 
int count=2;
Node*pd=head; 
printf("输入猴子总数\n");
scanf("%d",&num);
pd->d=1;
for(int i=0;i<num-1;i++)//遍历总数创建结点 
{Node*pn=(Node*)malloc(sizeof(Node));
pn->d=count++;//分配序号 
pn->next=NULL;
pd->next=pn;
pd=pn;

if(num-2==i)
{pn->next=head;//实现循环队列 
}
}
}
void search(Node*head)//查找函数 
{Node*pd=head;
int interval;//定义间隔 
printf("输入间隔\n");
scanf("%d",&interval);
while(pd!=pd->next)
{for(int i=0;i<interval-2;i++)
{pd=pd->next;
}
Node*e=pd->next;
pd->next=e->next;
free(e);//释放删除的空间 
e=NULL;//删除找到的结点 
pd=pd->next;}
printf("找到的号码为%d",pd->d);//输出找到的结点 
}
int main()//执行主函数 
{Node*Pd=ctlist();
 add(Pd);
 search(Pd);
}