C++語言判斷單鏈表是否有環(huán)鏈表程序源碼

ID:618366 · 發(fā)表于 2021-9-12 11:25

1.問題：如果給定一個(gè)單鏈表，如何判斷其是否為有環(huán)鏈表
2.方法：
（1）從給定鏈表的第一個(gè)節(jié)點(diǎn)開始遍歷，每遍歷至一個(gè)節(jié)點(diǎn)，都將其和所有的前驅(qū)節(jié)點(diǎn)進(jìn)行比對(duì)，如果為同一個(gè)節(jié)點(diǎn)，則表明當(dāng)前鏈表中有環(huán)；反之，如果遍歷至鏈表最后一個(gè)節(jié)點(diǎn)，仍未找到相同的節(jié)點(diǎn)，則證明該鏈表中無環(huán)。

如上所示，當(dāng)函數(shù)的返回值為 True，表示該鏈表有環(huán)；反之若函數(shù)返回值為 False，表明鏈表中無環(huán)。顯然，此實(shí)現(xiàn)方案的時(shí)間復(fù)雜度為O(n2)。
（2）在一個(gè)鏈表中，如果 2 個(gè)指針（假設(shè)為 H1 和 H2）都從表頭開始遍歷鏈表，其中 H1 每次移動(dòng) 2 個(gè)節(jié)點(diǎn)的長度（H1 = H1->next->next）,而 H2 每次移動(dòng) 1 個(gè)節(jié)點(diǎn)的長度（H2 = H2->next），如果該鏈表為有環(huán)鏈表，則 H1、H2 最終必定會(huì)相等；反之，如果該鏈表中無環(huán)，則 H1、H2 永遠(yuǎn)不會(huì)相遇。

本算法的時(shí)間復(fù)雜度為 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;
}
}
}
//鏈表中無環(huán)
printf("this links no ring\n");
return False;
}
#else
Bool HaveRing(link *H)
{
link * Htemp = H;
//存儲(chǔ)所遍歷節(jié)點(diǎn)所有前驅(qū)節(jié)點(diǎn)的存儲(chǔ)地址，64位環(huán)境下地址占 8 個(gè)字節(jié)，所以這里用 long long 類型
long long addr[20] = { 0 };
int length = 0, i = 0;
if(Htemp==NULL||Htemp->next==NULL)
{
return False;
}
//逐個(gè)遍歷鏈表中各個(gè)節(jié)點(diǎn)
while (Htemp) {
//依次將 Htemp 和 addr 數(shù)組中記錄的已遍歷的地址進(jìn)行比對(duì)
for (i = 0; i < length; i++) {
//如果比對(duì)成功，則證明有環(huán)
if (Htemp == (link*)addr[i]) {
return True;
}
}
//比對(duì)不成功，則記錄 Htemp 節(jié)點(diǎn)的存儲(chǔ)地址
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;
}

復(fù)制代碼

3.以上源碼：

有環(huán)鏈表判定.7z (1.09 KB, 下載次數(shù): 5)

帳號(hào)		自動(dòng)登錄	找回密碼
密碼			立即注冊(cè)

C++語言判斷單鏈表是否有環(huán)鏈表程序源碼

評(píng)分

瀏覽過的版塊

C++語言判斷單鏈表是否有環(huán)鏈表 程序源碼

評(píng)分

瀏覽過的版塊

C++語言判斷單鏈表是否有環(huán)鏈表程序源碼