#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct node {
int data ;
struct node *next ;
} node ;
node *init_clink_head (node *head , int num);
node *init_clink_tail (node *head , int num);
void display_head (node *head);
void display_tail (node *head);
int loopcheck (node *head);
int loopcheck2 (node *head);
int main ()
{
node *head = NULL ;
int option ;
printf("1.使用头插法生成无环单链表\n");
printf("2.使用尾插法生成有环单链表\n");
printf("3.用快慢指针判断链表是否有环\n");
printf("4.用比较步数判断链表是否有环\n");
printf("0.退出\n");
printf("请选择你的操作\n");
while (1)
{
scanf("%d",&option);
switch (option)
{
case 1 :
head = init_clink_head(head, 10);
printf("链表生成如下：\n");
display_head(head);
break ;
case 2 :
head = init_clink_tail(head, 10);
printf("链表生成如下：\n");
display_tail(head);
break ;
case 3 :
if (loopcheck(head))
{
printf("链表存在环！\n");
}
else
{
printf("链表没有环！\n");
}
break ;
case 4 :
if (loopcheck2(head))
{
printf("链表存在环！\n");
}
else
{
printf("链表没有环！\n");
}
break ;
case 0 :
exit(0);
}
}
}
// 关于头插法尾插法的初始化，往期的日志有做介绍，可以前往查阅
node *init_clink_head (node *head , int num)
{
srand(time(0));
node *new = NULL ;
head = (node *)malloc(sizeof(node));
head->next = NULL ;
for (int i = 0 ; i < num ; i++)
{
new = (node *)malloc(sizeof(node));
new->data = rand() % 100 ;
new->next = head->next ;
head->next = new ;
}
return head->next ;
}
node *init_clink_tail (node *head , int num)
{
srand(time(0));
node *tmp = NULL ;
node *new = NULL ;
head = (node *)malloc(sizeof(node));
tmp = head ;
for (int i = 0 ; i < num ; i++)
{
new = (node *)malloc(sizeof(node));
new->data = rand() % 100 ;
tmp->next = new ;
tmp = new ;
}
new->next = head->next ;
return new->next ;
}
void display_head (node *head) // 无环的打印终止条件就是访问到NULL结点
{
node *tmp = NULL ;
for (tmp = head ; tmp->next != NULL ; tmp = tmp->next)
{
printf("%d ",tmp->data);
}
printf("%d\n",tmp->data);
}
void display_tail (node *head) // 有环的打印终止条件就是访问到其头结点（如果头结点为循环点）
{
node *tmp = NULL ;
for (tmp = head ; tmp->next != head ; tmp = tmp->next)
{
printf("%d ",tmp->data);
}
printf("%d\n",tmp->data);
}
int loopcheck (node *head) // 快慢指针检测是否存在环
// 如果存在环，说明没有终点，那么快指针一定会经过未知的时间撞见慢指针
// 就像在赛道上，如果要求选手一直跑，那么快的选手一定会撞见慢的选手，然后超过
{
node *fast = head ;
node *slow = head ;
while (fast != NULL && fast->next != NULL) // 遇到NULL结点跳脱
{
printf("slow：%d fast：%d\n",slow->data,fast->data); // 访问记录，方便在控制台观察其步进轨迹
slow = slow->next ;
fast = fast->next->next ;
if (slow == fast)
{
return 1 ;
}
}
return 0 ;
}
int loopcheck2 (node *head) // 利用步数侦测是否存在环
{
node *cur_out = head ; // 定义不回家的指针，家的定义为头结点，下文称"野指针"
int pos_out = 1 ; // 定义其位置标记
while (cur_out) // 撞到NULL结点跳脱
{
node *cur_home = head ; // 定义每次都从家出发的指针，下文称"巢指针"
int pos_home = 1 ; // 这个摆放非常关键，循环过后重计
while (1)
{
if (cur_home == cur_out) // 指针撞见了
{
if (pos_home == pos_out) // 查看步数是否一样
{
break ; // 跳脱，巢指针继续步进
}
else // 步数不一样，说明有环
{
printf("环的位置在第%d个结点处\n",pos_home); // 打印的必须是巢指针位置，这才是环进去的起点
return 1 ;
}
}
cur_home = cur_home->next ; // 巢指针步进
pos_home++ ; // 巢指针位置增加
}
cur_out = cur_out->next ; // 野指针步进
pos_out++ ; // 野指针位置增加
}
return 0 ; // 没有环便会遇到NULL结点而跳脱while循环，然后返回0
}
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
