- #include <stdio.h>
- #include <stdlib.h> //分配内存空间malloc(),eixt();
- #include <time.h>
- #define OK 1 //宏定义常用变量
- #define ERROR 0
- #define TURE 1
- #define FALSE 0
- typedef int Status; //抽象函数类型
- typedef int ElemType; //抽象数据类型
- /*抽象数据结构*/
- typedef struct LNode
- {
- ElemType data;
- struct LNode *next;
- }LNode,*LinkList;
- int main()
- {
- LinkList L;
- LinkList lp; //lp指向快慢指针相遇的结点
- LinkList lnode; //lnode指向链表的入环结点
- int N,M;
- Status InsertList_L(LinkList,int);//链表建立函数的调用
- Status FoundLoop_L(LinkList,int); //在链表中建环的函数
- LinkList IsExitLoop(LinkList); //判断链表中是否存在环
- LinkList FindLoopNode(LinkList,LinkList); //找出链表中的入环结点
- /*建立头结点*/
- L=(LinkList)malloc(sizeof(LNode));
- if(!L) exit(0); //分配内存空间失败
- L->next=NULL; //初始化头结点的人后驱
- printf("输入建立链表的结点数(头结点除外):");
- scanf("%d",&N); //链表的长度
- InsertList_L(L,N);
- LinkList p;
- p=L->next;
- while(p)
- {
- printf("%d ",p->data);
- p=p->next;
- }
- getchar(); //排除上一个scanf()对下一个的影响
- char select;
- printf("选择是否在链表中建环(y or n):");
- scanf("%c",&select);
- getchar();//排除上一个scanf()对下一个的影响
- switch(select)
- {
- case 'y':
- /*建立链表环*/
- printf("\\n输入建环位置:");
- scanf("%d",&M);
- FoundLoop_L(L,M);
- break;
- default:
- break;
- }
- /*判断是否存在链表环*/
- lp=IsExitLoop(L);
- if(lp)
- {
- printf("%d ",lp->data);
- lnode=FindLoopNode(L,lp);
- printf("\\n链表存在环,其结点的数值为:");
- printf("%d ",lnode->data);
- }
- else
- printf("链表中不存在环");
- return 0;
- }
- Status InsertList_L(LinkList L,int N)
- //L为链表头结点,非空
- //建立表长为N的链表
- //函数每个结点中的数据域,有随机种子随机生成
- //尾插法建立链表
- {
- int i;
- LinkList p;
- srand(time(NULL));
- for (i=0;i<N;i++)
- {
- p=(LinkList)malloc(sizeof(LNode));
- if(!p) exit(0);
- p->data=1+(int)rand()%100;
- p->next=L->next;
- L->next=p;
- }
- return OK;
- }//InsertList_L
- Status FoundLoop_L(LinkList L,int M)
- //1≤M≤N 链表长度(除头结点)
- //L为链表头结点
- {
- int i;
- LinkList cur,tail; //cur入环结点,tail尾结点
- LinkList p; //p为工作指针
- cur=L;
- for(i=0;i<M;i++) //寻找第M个结点
- cur=cur->next;
- p=cur; //p初始化指向入环结点
- while(p)
- {
- tail=p; //循环结束时,tail指向尾结点
- p=p->next;
- }
- tail->next=cur; //在第M个结点出建立环
- return OK;
- }//FoundLoop_L
- /*判断环是否存在的函数*/
- LinkList IsExitLoop(LinkList L)
- //判断链表中是否存在环
- //设置快慢指针的是否会相遇的方式来进行判断
- {
- LinkList fast,slow;
- fast=L; //快慢指针同时指向第一个结点
- slow=L;
- while(fast)
- {
- fast=fast->next;
- if(!fast)
- break;
- fast=fast->next;
- if(!fast)
- break;
- slow=slow->next;
- if(fast==slow)
- break;
- }
- if(fast)
- return fast;
- else
- return NULL;
- }//IsExitLoop
- /*入环结点寻找物理解释*/
- /*设非环内结点的个数为s个,环内的结点为r个
- 由于fast每次走两个结点,而slow结点每次只走一个结点
- 最后相遇的时候设slow数组链表方向经过x个结点
- 则2(s+x)-(s+x)=r
- 得 s+x=r
- 由此可得头结点到入环点的结点数同相遇点到入环点的距离相同*/
- LinkList FindLoopNode(LinkList L,LinkList lp)
- //lp为快慢指针相遇点
- //L为头结点
- {
- LinkList p,q;
- p=L;
- q=lp;
- while(p!=q)
- {
- p=p->next;
- q=q->next;
- }
- return p;
- }
- //该片段来自于http://www.codesnippet.cn/detail/250420149382.html
来源: http://www.codesnippet.cn/detail/250420149382.html