判断单链表中是否有环

#define _CRT_SECURE_NO_DEPRECATE #include <iostream> #include <cstdio> #include<cstdlib> #include <time.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status;//函数结果状态代码，如OK。 typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; }Node, *LinkList; //初始化带头结点的空链表 Status InitList(LinkList *L) { *L = (LinkList)malloc(sizeof(Node));//让L指向刚生成的头结点 if (!(*L)) { return ERROR;//存储分配失败 } (*L)->next = NULL;//指针域为空 return OK; } //返回L中元素个数 int ListLength(LinkList L) { int i = 0; LinkList p = L->next;//p指向第一个结点 while (p) { i++; p = p->next; } return i; } //头插法建立有头结点的单链表 void CreateListhHead(LinkList *L, int n) { LinkList p; int i; srand(time(0)); *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; for (i = 0; i < n; i++) { p = (LinkList)malloc(sizeof(Node)); p->data = rand() % 100 + 1; p->next = (*L)->next; (*L)->next = p; } } //尾插法建立有头结点的单链表 void CreateListTail(LinkList *L, int n) { LinkList p, r; int i; srand(time(0)); *L = (LinkList)malloc(sizeof(Node)); r = *L; for (i = 0; i < n; i++) { p = (Node*)malloc(sizeof(Node)); p->data = rand() % 100 + 1; r->next = p; r = p; } r->next = (*L)->next->next; } //比较步数的方法 int HasLoop1(LinkList L) { LinkList cur1 = L;//定义结点cur1 int pos1 = 0;//cur1步数为0 while (cur1) { LinkList cur2 = L;//定义结点cur2 int pos2 = 0;//cur2步数为0 while (cur2) { if (cur2 == cur1) //cur1 cur2在相同结点 { if (pos1 == pos2)//步数一样 { break;//没有环 } //在相同结点，步数不同，代表有环 else { printf("环的位置在第%d个结点处\n\n", pos2); return OK; } } cur2 = cur2->next;//没有发现环，继续下一个结点 pos2++; } cur1 = cur1->next;//cur1向后一个节点 pos1++; } return 0; } //利用快慢指针法 int HasLoop2(LinkList L) { int step1 = 1; int step2 = 2; LinkList p = L;//定义慢指针 LinkList q = L;//定义快指针 while (p != NULL&&q != NULL&&q->next != NULL) { p = p->next; if (q->next != NULL) { q = q->next->next; } printf("p:%d,q:%d \n", p->data, q->data); if (p == q) { return OK; } } return 0; } int main() { LinkList L; Status i; char opp = '5'; ElemType e; int find; int type; i = InitList(&L); printf("\n 1.尾插法创建有环链表\n 2.头插法创建无环链表\n 3.判断链表是否有环\n 0.退出 \n\n"); while (opp != '0') { scanf("%c", &opp); switch (opp) { case'1': CreateListTail(&L, 10); printf("利用尾插法成功创建有环链表L\n"); printf("\n"); break; case'2': CreateListhHead(&L, 10); printf("利用头插法成功创建无环链表\n"); printf("\n"); break; case'3': printf("方法一：\n\n"); if (HasLoop1(L)) { printf("链表有环\n\n"); } else { printf("链表无环\n\n"); } printf("方法二：\n\n"); if (HasLoop2(L)) { printf("链表有环\n\n"); } else { printf("链表无环\n\n\n"); } printf("\n\n"); break; case'0': exit(0); } } }