// Note:如要使用请注明出处
// Electrical And Information Engineering Department Of Hunan University
// 30.10.2012
// Email:hudalikm@163.com
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
//定义结构体,用于创建链表
typedef struct foxandrabbit
{
int label;// 用于表示结点序号
bool landmark;//用于指示是否被狐狸找到
struct foxandrabbit *next;//定义一个foxandrabbit指针,用于指向foxandrabbit类型的结点
} *nlist;
// 主函数
void main()
{
int n;
bool flag=false;// 用于只是兔子是否有洞可以藏身,即是否有安全洞,由于不知到是否有安全洞,所以初始化为false
nlist list,head,p,q;
printf("请输入洞数: ");
scanf("%d",&n);
// 创建有n个结点的链表,该链表为循环结构,其中每一个结点代表一个洞
if(n!=0)
{
// 创建第一个结点,也就是头结点
p=(foxandrabbit *)malloc(sizeof(foxandrabbit));
p->label=1;// 标记第一个结点顺序为1
p->landmark=true;// 在创建链表的时候,假设所有的结点,也就是所有的洞对于兔子来说都是安全的
p->next=NULL;
head=p;//头指针指向第一个结点
// 创建第2...n个结点
for(int k=2;k<=n;k++)
{
q=(foxandrabbit *)malloc(sizeof(foxandrabbit));
q->label=k;
q->landmark=true;
q->next=NULL;
p->next=q;// 指向下一个结点
p=p->next;
}
p->next=head;// 尾结点的指针域指向头结点,构成循环链表
}
list=head;// 构成链表
// 寻找安全洞,定义p为表头指针,q为活动指针
p=list;// 初始指向
q=list;// 初始指向
// 让q指向链表表尾
while(q->next!=p)
{
q=q->next;
}
// 按照题设要求,如果狐狸能够到达的洞则是不安全的洞,标记为false
// 又因为构成循环链表,也就是说当狐狸的步进长度steplength大于n的时候,总会落到已经标记为false的洞上,所以当步进长度为n时,跳出循环
for(int i=1;i<=n;i++)
{
// 按照要求,每次进i步,比如,第一次1步,第二次2步,第三次3步......
for(int j=1;j<=i;j++)
q=q->next;// 指向找到狐狸能够到达的洞
q->landmark=false;// 将狐狸能够到达的洞标记为false,代表不安全
}
// 输出安全洞
p=list;
q=list;
printf("\n");
while(p!=q->next)// 在步进长度steplength不大于n的前提下,当活动指针指向尾结点时候,结束
{
if(q->landmark)// 查看是否能够被狐狸到达,如果被标记为false则是狐狸能够到达的洞,否则是安全洞
{
printf(" 第%d个洞是安全的\n\n",q->label);
flag=true;// 将flag标记为true,表明有安全洞
}
q=q->next;
}
// 如果flag没有被标记为true,则说明没有安全洞
if(!flag)
printf(" 兔子无处可逃! \n\n\n\n\n");
printf(" \n\n 程序结束!\n\n\n");
}