C++语言判断单链表是否有环链表程序源码

ID:618366 · 发表于 2021-9-12 11:25

1.问题：如果给定一个单链表，如何判断其是否为有环链表
2.方法：
（1）从给定链表的第一个节点开始遍历，每遍历至一个节点，都将其和所有的前驱节点进行比对，如果为同一个节点，则表明当前链表中有环；反之，如果遍历至链表最后一个节点，仍未找到相同的节点，则证明该链表中无环。
NBQ(S_`2~N$F_E2A_CB`P[2.png

如上所示，当函数的返回值为 True，表示该链表有环；反之若函数返回值为 False，表明链表中无环。显然，此实现方案的时间复杂度为O(n2)。
（2）在一个链表中，如果 2 个指针（假设为 H1 和 H2）都从表头开始遍历链表，其中 H1 每次移动 2 个节点的长度（H1 = H1->next->next）,而 H2 每次移动 1 个节点的长度（H2 = H2->next），如果该链表为有环链表，则 H1、H2 最终必定会相等；反之，如果该链表中无环，则 H1、H2 永远不会相遇。

本算法的时间复杂度为 O(n)。

#include<stdio.h>
#include<stdlib.h>
//自定义 bool 类型
typedef enum Bool
{
False=0,
True=1
}Bool;
typedef struct link{
int data;
struct link* next;
}link;
link *linkIint(int n)
{
link *head=(link*)malloc(sizeof(link));
head->data=1;
head->next=NULL;
link *phead=head;
int i;
for(i=2;i<=n;i++)
{
link *temp=(link*)malloc(sizeof(link));
temp->data=i;
temp->next=NULL;
head->next=temp;
head=head->next;
}
head->next=phead;
return phead;
}
#if 1
Bool HaveRing(link *temp)
{
link *H2=temp;
link *H1=temp->next;
if(H2==NULL||H2==NULL)
{
return False;
}
while(H1)
{
if(H1==H2)
{
printf("this links have a ring\n");
return True;
}
else
{
H1=H1->next;
if (!H1)
{
printf("this links no ring\n");
return False;
}
else
{
H1=H1->next;
H2=H2->next;
}
}
}
//链表中无环
printf("this links no ring\n");
return False;
}
#else
Bool HaveRing(link *H)
{
link * Htemp = H;
//存储所遍历节点所有前驱节点的存储地址，64位环境下地址占 8 个字节，所以这里用 long long 类型
long long addr[20] = { 0 };
int length = 0, i = 0;
if(Htemp==NULL||Htemp->next==NULL)
{
return False;
}
//逐个遍历链表中各个节点
while (Htemp) {
//依次将 Htemp 和 addr 数组中记录的已遍历的地址进行比对
for (i = 0; i < length; i++) {
//如果比对成功，则证明有环
if (Htemp == (link*)addr[i]) {
return True;
}
}
//比对不成功，则记录 Htemp 节点的存储地址
addr[length] = (long long)Htemp;
length++;
Htemp = Htemp->next;
}
return False;
}
#endif
void linkPrint(link *temp)
{
link *phead=temp;
if(!temp)
printf("the link is empty\n");
else
{
while(temp)
{
printf("%d\t",temp->data);
temp=temp->next;
if(temp==phead)
{
printf("\r\n");
break;
}
}
}
}
int main()
{
link *head=linkIint(6);
linkPrint(head);
if(HaveRing(head)==True)
{
printf("the link has a ring\r\n");
}
else
{
printf("the link no rave\r\n");
}
return 0;
}

复制代码

3.以上源码：

有环链表判定.7z (1.09 KB, 下载次数: 5)

帐号		自动登录	找回密码
密码			立即注册

C++语言判断单链表是否有环链表 程序源码

评分

C++语言判断单链表是否有环链表程序源码