Nút cuối của danh sách được liên kết có vòng lặp sẽ tham chiếu đến một nút khác trong cùng danh sách chứ không phải là NULL. Nếu có một nút trong danh sách được liên kết có thể được truy cập nhiều lần bằng cách theo con trỏ tiếp theo, thì danh sách đó được gọi là có một chu kỳ.
Thông thường, nút cuối cùng của Danh sách được liên kết đề cập đến tham chiếu NULL để biểu thị kết luận của danh sách. Tuy nhiên, trong danh sách liên kết có vòng lặp, nút cuối của danh sách đề cập đến nút bắt đầu, nút bên trong hoặc chính nó. Do đó, trong những trường hợp như vậy, chúng ta phải xác định và chấm dứt vòng lặp bằng cách đặt tham chiếu của nút tiếp theo thành NULL. Phần phát hiện vòng lặp trong danh sách liên kết được giải thích trong bài viết này.
Trong C++, có nhiều cách để tìm vòng lặp trong danh sách liên kết:
Cách tiếp cận dựa trên bảng băm : Cách tiếp cận này lưu trữ địa chỉ của các nút đã truy cập trong bảng băm. Một vòng lặp trong danh sách được liên kết tồn tại nếu một nút đã có mặt trong bảng băm khi nó được truy cập lại.
Cách tiếp cận chu kỳ của Floyd : Thuật toán “rùa và thỏ”, thường được gọi là thuật toán tìm chu kỳ của Floyd: Kỹ thuật này sử dụng hai con trỏ, một con trỏ di chuyển chậm hơn con trỏ kia và con trỏ kia di chuyển nhanh hơn. Con trỏ nhanh hơn cuối cùng sẽ vượt qua con trỏ chậm hơn nếu có một vòng lặp trong danh sách được liên kết, cho thấy sự tồn tại của vòng lặp.
phương pháp đệ quy : Phương thức này đi qua danh sách liên kết bằng cách gọi đi gọi lại chính nó. Danh sách được liên kết chứa một vòng lặp nếu nút hiện tại đã được truy cập trước đó.
Cách tiếp cận dựa trên ngăn xếp : Cách tiếp cận này lưu trữ địa chỉ của các nút đã truy cập trong một ngăn xếp. Một vòng lặp trong danh sách được liên kết xuất hiện nếu một nút đã có sẵn trong ngăn xếp khi nó được truy cập lại.
Hãy giải thích chi tiết từng cách tiếp cận để hiểu khái niệm này.
Cách tiếp cận 1: Cách tiếp cận HashSet
Sử dụng băm là phương pháp đơn giản nhất. Ở đây, chúng tôi lần lượt duyệt qua danh sách trong khi vẫn giữ một bảng băm với các địa chỉ nút. Do đó, một vòng lặp tồn tại nếu chúng ta chạy qua địa chỉ tiếp theo của nút hiện tại đã được chứa trong bảng băm. Mặt khác, sẽ không có vòng lặp nào trong Danh sách được liên kết nếu chúng ta gặp phải NULL (tức là đến cuối Danh sách được liên kết).
Sẽ khá dễ dàng để thực hiện chiến lược này.
Trong khi duyệt qua danh sách được liên kết, chúng tôi sẽ sử dụng unordered_hashmap và tiếp tục thêm các nút vào đó.
Bây giờ, khi chúng tôi bắt gặp một nút đã được hiển thị trên bản đồ, chúng tôi sẽ biết rằng chúng tôi đã đến điểm bắt đầu của vòng lặp.
-
- Ngoài ra, chúng tôi giữ hai con trỏ ở mỗi bước, đầuNode trỏ đến nút hiện tại và nút cuối cùng trỏ đến nút trước của nút hiện tại, trong khi lặp lại.
- Như là của chúng ta đầuNode hiện đang trỏ đến nút bắt đầu của vòng lặp và như nút cuối cùng đang trỏ đến nút mà đầu đang trỏ đến (nghĩa là nó đang đề cập đến nút cuối cùng của vòng lặp), của chúng tôi đầuNode hiện đang trỏ đến nút bắt đầu của vòng lặp.
- Vòng lặp sẽ bị phá vỡ bằng cách đặt l astNode->next == NULL .
Bằng cách này, nút kết thúc vòng lặp thay vì tham chiếu đến nút ban đầu của vòng lặp, bắt đầu trỏ đến NULL.
Độ phức tạp về không gian và thời gian trung bình của phương thức băm là O(n). Người đọc phải luôn lưu ý rằng việc triển khai Cấu trúc dữ liệu băm tích hợp sẵn trong ngôn ngữ lập trình sẽ xác định tổng thời gian phức tạp trong trường hợp xảy ra xung đột trong quá trình băm.
Triển khai chương trình C++ cho phương thức trên (HashSet):
#include
sử dụng không gian tên std;
nút cấu trúc {
giá trị int;
nút cấu trúc * Kế tiếp;
} ;
Nút * nút mới ( giá trị int )
{
Nút * tempNode = nút mới;
tempNode- > giá trị = giá trị;
tempNode- > tiếp theo = NULL;
trở lại nút tạm thời;
}
// Xác định và loại bỏ bất kỳ vòng lặp tiềm ẩn nào
// TRONG một danh sách được liên kết với chức năng này.
hàm voidHashMap ( Nút * đầuNode )
{
// Đã tạo một unordered_map để triển khai bản đồ Hash
unordered_map < Nút * , int > bản đồ băm;
// con trỏ tới lastNode
Nút * nút cuối cùng = NULL;
trong khi ( đầuNode ! = KHÔNG ) {
// Nếu một nút bị thiếu trên bản đồ, hãy thêm nó.
nếu như ( hash_map.find ( đầuNode ) == hash_map.end ( ) ) {
bản đồ băm [ đầuNode ] ++;
lastNode = headNode;
headNode = headNode- > Kế tiếp;
}
// Nếu có chu kỳ, bộ nút cuối cùng ' con trỏ tiếp theo tới NULL.
khác {
lastNode->next = NULL;
phá vỡ;
}
}
}
// Hiển thị danh sách liên kết
hiển thị void(Node* headNode)
{
trong khi (headNode != NULL) {
cout << headNode->value << ' ';
headNode = headNode->next;
}
cout<
/* Chức năng chính*/
int chính ()
{
Nút* headNode = newNode(48);
headNode->next = headNode;
headNode->next = newNode(18);
headNode->next->next = newNode(13);
headNode->next->next->next = newNode(2);
headNode->next->next->next->next = newNode(8);
/* Tạo vòng lặp trong LinkedList */
headNode->next->next->next->next->next = headNode->next->next;
functionHashMap(headNode);
printf('Danh sách liên kết không có vòng lặp\n');
hiển thị (headNode);
trả về 0;
}
Đầu ra:
Danh sách liên kết không có vòng lặp
48 18 13 2 số 8
Giải thích từng bước của mã được cung cấp bên dưới:
-
- Tệp tiêu đề bits/stdc++.h>, chứa tất cả các thư viện C++ phổ biến, được bao gồm trong mã.
- Một cấu trúc gọi là “Nút” được xây dựng và nó có hai thành viên: một tham chiếu đến nút tiếp theo trong danh sách và một số nguyên gọi là “giá trị”.
- Với một giá trị số nguyên làm đầu vào và con trỏ “next” được đặt thành NULL, hàm “newNode” tạo một nút mới với giá trị đó.
- Chức năng ' hàmHashMap' được xác định, lấy một con trỏ tới nút đầu của danh sách được liên kết làm đầu vào.
- Bên trong ‘ hàmHashMap ‘, một unordered_map tên là ‘hash_map’ được tạo, được sử dụng để triển khai cấu trúc dữ liệu bản đồ băm.
- Một con trỏ tới nút cuối cùng của danh sách được khởi tạo thành NULL.
- Một vòng lặp while được sử dụng để duyệt qua danh sách được liên kết, bắt đầu từ nút đầu và tiếp tục cho đến khi nút đầu là NULL.
- Con trỏ lastNode được cập nhật tới nút hiện tại bên trong vòng lặp while nếu nút hiện tại (headNode) chưa có trong bản đồ băm.
- Nếu nút hiện tại được tìm thấy trong bản đồ, điều đó có nghĩa là có một vòng lặp trong danh sách được liên kết. Để loại bỏ vòng lặp, con trỏ tiếp theo của nút cuối cùng được đặt thành VÔ GIÁ TRỊ và vòng lặp while bị hỏng.
- Nút đầu của danh sách được liên kết được sử dụng làm đầu vào cho chức năng có tên là 'hiển thị', xuất giá trị của từng nút trong danh sách từ đầu đến cuối.
- bên trong chủ yếu chức năng, tạo một vòng lặp.
- Hàm 'functionHashMap' được gọi với con trỏ headNode làm đầu vào, loại bỏ vòng lặp khỏi danh sách.
- Danh sách sửa đổi được hiển thị bằng chức năng 'hiển thị'.
Cách tiếp cận 2: Chu kỳ của Floyd
Thuật toán phát hiện chu trình của Floyd, thường được gọi là thuật toán rùa và thỏ, cung cấp nền tảng cho phương pháp định vị các chu trình này trong danh sách được liên kết. Con trỏ “chậm” và con trỏ “nhanh”, di chuyển qua danh sách với các tốc độ khác nhau, là hai con trỏ được sử dụng trong kỹ thuật này. Con trỏ nhanh tiến hai bước trong khi con trỏ chậm tiến một bước sau mỗi lần lặp. Một chu trình trong danh sách liên kết tồn tại nếu hai điểm đối mặt nhau.
1. Với nút đầu của danh sách được liên kết, chúng tôi khởi tạo hai con trỏ được gọi là nhanh và chậm.
2. Bây giờ chúng ta chạy một vòng lặp để di chuyển qua danh sách liên kết. Con trỏ nhanh phải được di chuyển hai vị trí phía trước con trỏ chậm ở mỗi bước lặp.
3. Sẽ không có vòng lặp trong danh sách liên kết nếu con trỏ nhanh đến cuối danh sách (fastPulum == NULL hoặc fastPulum->next == NULL). Nếu không, con trỏ nhanh và chậm cuối cùng sẽ gặp nhau, nghĩa là danh sách liên kết có vòng lặp.
Triển khai chương trình C++ cho phương pháp trên (Chu kỳ của Floyd):
#include
sử dụng không gian tên std;
/* Nút danh sách liên kết */
nút cấu trúc {
dữ liệu int;
nút cấu trúc * Kế tiếp;
} ;
/* Chức năng loại bỏ vòng lặp. */
void xóaLoop ( nút cấu trúc * , nút cấu trúc * ) ;
/* Cái này chức năng định vị và loại bỏ các vòng lặp danh sách. Nó mang lại 1
nếu như có một vòng lặp TRONG danh sách; khác , nó trở lại 0 . */
int detectAndDeleteLoop ( nút cấu trúc * danh sách )
{
nút cấu trúc * SlowPTR = danh sách, * fastPTR = danh sách;
// Lặp lại để kiểm tra nếu như vòng lặp ở đó.
trong khi ( chậmPTR && nhanhPTR && nhanhPTR- > Kế tiếp ) {
chậmPTR = chậmPTR- > Kế tiếp;
fastPTR = fastPTR- > Kế tiếp- > Kế tiếp;
/* Nếu slowPTR và fastPTR gặp nhau tại một số điểm sau đó ở đó
là một vòng lặp */
nếu như ( chậmPTR == nhanhPTR ) {
xóaLoop ( làm chậmPTR, danh sách ) ;
/* Trở lại 1 để chỉ ra rằng một vòng lặp đã được phát hiện. */
trở lại 1 ;
}
}
/* Trở lại 0 để chỉ ra rằng không có vòng lặp nào được phát hiện. */
trở lại 0 ;
}
/* Chức năng xóa vòng lặp khỏi danh sách liên kết.
loopNode đang trỏ đến một trong các nút vòng lặp và headNode đang trỏ đến
đến nút bắt đầu của danh sách liên kết */
void xóaLoop ( nút cấu trúc * nút vòng lặp, nút cấu trúc * đầuNode )
{
nút cấu trúc * ptr1 = loopNode;
nút cấu trúc * ptr2 = loopNode;
// Đếm xem có bao nhiêu nút TRONG vòng lặp.
không dấu int k = 1 , Tôi;
trong khi ( ptr1- > Kế tiếp ! = ptr2 ) {
ptr1 = ptr1- > Kế tiếp;
k++;
}
// Sửa một con trỏ tới headNode
ptr1 = đầuNode;
// Và con trỏ kia tới k nút sau headNode
ptr2 = đầuNode;
vì ( tôi = 0 ; Tôi < k; tôi ++ )
ptr2 = ptr2- > Kế tiếp;
/* Khi cả hai điểm được di chuyển đồng thời,
họ sẽ va chạm tại vòng lặp nút bắt đầu của. */
trong khi (ptr2 != ptr1) {
ptr1 = ptr1->tiếp theo;
ptr2 = ptr2->tiếp theo;
}
// Lấy được nút' S cuối cùng con trỏ.
trong khi ( ptr2- > Kế tiếp ! = ptr1 )
ptr2 = ptr2- > Kế tiếp;
/* Để đóng vòng lặp, bộ tiếp theo
nút vào vòng lặp nút kết thúc của. */
ptr2->tiếp theo = NULL;
}
/* Hàm hiển thị danh sách liên kết */
void displayLinkedList(struct Node* node)
{
// hiển thị danh sách liên kết sau khi xóa vòng lặp
trong khi (nút != NULL) {
cout << node->data << ' ';
nút = nút-> tiếp theo;
}
}
nút cấu trúc * nút mới (phím int)
{
cấu trúc nút * temp = nút mới ();
tạm thời-> dữ liệu = khóa;
tạm thời->tiếp theo = NULL;
trở lại nhiệt độ;
}
// Mã chính
int chính ()
{
nút cấu trúc* headNode = newNode(48);
headNode->next = newNode(18);
headNode->next->next = newNode(13);
headNode->next->next->next = newNode(2);
headNode->next->next->next->next = newNode(8);
/* Tạo một vòng lặp */
headNode->next->next->next->next->next = headNode->next->next;
// hiển thị vòng lặp trong danh sách liên kết
//displayLinkedList(headNode);
detectAndDeleteLoop(headNode);
cout << 'Danh sach lien ket sau khi khong gap \n';
displayLinkedList(headNode);
trả về 0;
}
Đầu ra:
Danh sách được liên kết sau khi không có vòng lặp
48 18 13 2 số 8
Giải trình:
-
- Các tiêu đề có liên quan, chẳng hạn như “bits/stdc++.h” và “std::cout,” được đưa vào đầu tiên.
- Cấu trúc “Nút”, viết tắt của một nút trong danh sách được liên kết, sau đó được khai báo. Một con trỏ tiếp theo dẫn đến nút sau trong danh sách được bao gồm cùng với trường dữ liệu số nguyên trong mỗi nút.
- Sau đó, nó định nghĩa hai hàm “deleteLoop” và “detectAndDeleteLoop”. Một vòng lặp được loại bỏ khỏi danh sách được liên kết bằng phương pháp đầu tiên và một vòng lặp được phát hiện trong danh sách bằng hàm thứ hai, sau đó gọi thủ tục đầu tiên để loại bỏ vòng lặp.
- Một danh sách được liên kết mới với năm nút được tạo trong hàm chính và một vòng lặp được thiết lập bằng cách đặt con trỏ tiếp theo của nút cuối cùng thành nút thứ ba.
- Sau đó, nó thực hiện cuộc gọi đến phương thức “detectAndDeleteLoop” trong khi chuyển nút đầu của danh sách được liên kết làm đối số. Để xác định các vòng lặp, chức năng này sử dụng phương pháp “Con trỏ nhanh và chậm”. Nó sử dụng hai con trỏ bắt đầu ở đầu danh sách, slowPTR và fastPTR. Trong khi con trỏ nhanh di chuyển hai nút cùng một lúc, con trỏ chậm chỉ di chuyển một nút tại một thời điểm. Con trỏ nhanh cuối cùng sẽ vượt qua con trỏ chậm nếu danh sách chứa vòng lặp và hai điểm sẽ va chạm tại cùng một nút.
- Hàm gọi hàm “deleteLoop” nếu nó tìm thấy một vòng lặp, cung cấp nút đầu của danh sách và giao điểm của các con trỏ chậm và nhanh làm đầu vào. Thủ tục này thiết lập hai con trỏ ptr1 và ptr2 tới nút đầu của danh sách và đếm số nút trong vòng lặp. Sau đó, nó tiến lên một con trỏ k nút, trong đó k là tổng số nút trong vòng lặp. Sau đó, cho đến khi chúng gặp nhau ở đầu vòng lặp, nó sẽ tiến cả hai điểm lên một nút tại một thời điểm. Vòng lặp sau đó bị phá vỡ bằng cách đặt con trỏ tiếp theo của nút ở cuối vòng lặp thành NULL.
- Sau khi loại bỏ vòng lặp, nó sẽ hiển thị danh sách liên kết như một bước cuối cùng.
Cách tiếp cận 3: Đệ quy
Đệ quy là một kỹ thuật để giải quyết các vấn đề bằng cách phân chia chúng thành các bài toán con nhỏ hơn, dễ dàng hơn. Đệ quy có thể được sử dụng để duyệt qua danh sách liên kết đơn trong trường hợp vòng lặp được tìm thấy bằng cách chạy liên tục một hàm cho nút tiếp theo trong danh sách cho đến khi đến cuối danh sách.
Trong danh sách liên kết đơn, nguyên tắc cơ bản đằng sau việc sử dụng đệ quy để tìm vòng lặp là bắt đầu từ đầu danh sách, đánh dấu nút hiện tại là đã truy cập ở mỗi bước, sau đó chuyển sang nút tiếp theo bằng cách gọi hàm đệ quy cho nút đó. Phương thức này sẽ lặp qua danh sách liên kết đầy đủ vì nó được gọi một cách đệ quy.
Danh sách chứa một vòng lặp nếu chức năng gặp phải một nút trước đó đã được đánh dấu là đã truy cập; trong trường hợp này, hàm có thể trả về true. Phương thức có thể trả về false nếu nó đến cuối danh sách mà không chạy qua nút đã truy cập, điều này cho biết rằng không có vòng lặp.
Mặc dù kỹ thuật sử dụng đệ quy để tìm một vòng lặp trong một danh sách được liên kết đơn này rất dễ sử dụng và dễ hiểu, nhưng nó có thể không phải là kỹ thuật hiệu quả nhất xét về độ phức tạp của không gian và thời gian.
Triển khai chương trình C++ cho phương thức trên (Đệ quy):
#include
sử dụng không gian tên std;
nút cấu trúc {
dữ liệu int;
Nút * Kế tiếp;
bool đã đến thăm;
} ;
// Phát hiện vòng lặp danh sách liên kết chức năng
bool detectLoopLinkedList ( Nút * đầuNode ) {
nếu như ( headNode == NULL ) {
trở lại SAI ; // Nếu danh sách liên kết rỗng, cơ bản trường hợp
}
// Có một vòng lặp nếu như nút hiện tại có
// đã được truy cập.
nếu như ( headNode- > đã đến thăm ) {
trở lại ĐÚNG VẬY ;
}
// Thêm dấu truy cập vào nút hiện tại.
headNode- > đã ghé thăm = ĐÚNG VẬY ;
// Gọi mã vì nút tiếp theo lặp đi lặp lại
trở lại detectLoopLinkedList ( headNode- > Kế tiếp ) ;
}
int chính ( ) {
Nút * headNode = nút mới ( ) ;
Nút * secondNode = nút mới ( ) ;
Nút * thirdNode = Nút mới ( ) ;
headNode- > dữ liệu = 1 ;
headNode- > tiếp theo = giâyNode;
headNode- > đã ghé thăm = SAI ;
giâyNode- > dữ liệu = 2 ;
giâyNode- > tiếp theo = nút thứ ba;
giâyNode- > đã ghé thăm = SAI ;
nút thứ ba- > dữ liệu = 3 ;
nút thứ ba- > tiếp theo = NULL; // không có vòng lặp
nút thứ ba- > đã ghé thăm = SAI ;
nếu như ( detectLoopLinkedList ( đầuNode ) ) {
cout << 'Phát hiện vòng lặp trong danh sách liên kết' << kết thúc;
} khác {
cout << 'Không phát hiện thấy vòng lặp nào trong danh sách liên kết' << kết thúc;
}
// Tạo một vòng lặp
nút thứ ba- > tiếp theo = giâyNode;
nếu như ( detectLoopLinkedList ( đầuNode ) ) {
cout << 'Phát hiện vòng lặp trong danh sách liên kết' << kết thúc;
} khác {
cout << 'Không phát hiện thấy vòng lặp nào trong danh sách liên kết' << kết thúc;
}
trở lại 0 ;
}
Đầu ra:
Không phát hiện thấy vòng lặp nào TRONG danh sách liên kết
Đã phát hiện vòng lặp TRONG danh sách liên kết
Giải trình:
-
- Chức năng detectLoopLinkedList() trong chương trình này nhận phần đầu của danh sách liên kết làm đầu vào.
- Hàm đệ quy được sử dụng để lặp qua danh sách được liên kết. Là trường hợp cơ bản cho đệ quy, nó bắt đầu bằng cách xác định xem nút hiện tại có phải là NULL hay không. Nếu vậy, phương thức trả về false, cho biết không có vòng lặp nào tồn tại.
- Sau đó, giá trị của thuộc tính “đã truy cập” của nút hiện tại được kiểm tra để xem liệu nó đã được truy cập trước đó chưa. Nó trả về true nếu nó đã được truy cập, cho thấy rằng một vòng lặp đã được tìm thấy.
- Hàm đánh dấu nút hiện tại là đã truy cập nếu nó đã được truy cập bằng cách thay đổi thuộc tính “đã truy cập” của nó thành true.
- Sau đó, giá trị của biến đã truy cập được kiểm tra xem nút hiện tại đã được truy cập trước đó chưa. Nếu nó đã được sử dụng trước đó thì phải tồn tại một vòng lặp và hàm trả về true.
- Cuối cùng, hàm gọi chính nó với nút tiếp theo trong danh sách bằng cách chuyển headNode->tiếp theo như một lý lẽ. đệ quy , điều này được thực hiện cho đến khi tìm thấy một vòng lặp hoặc tất cả các nút đã được truy cập. Có nghĩa là, hàm đặt biến đã truy cập thành true nếu nút hiện tại chưa từng được truy cập trước khi gọi đệ quy chính nó cho nút sau trong danh sách được liên kết.
- Đoạn mã này xây dựng ba nút và kết hợp chúng để tạo ra một danh sách được liên kết trong chức năng chính . phương pháp detectLoopLinkedList() sau đó được gọi trên nút đầu của danh sách. Chương trình sản xuất “ Vòng lặp bị trừ trong danh sách được liên kết ' nếu như detectLoopLinkedList() trả về đúng; nếu không, nó xuất ra “ Không phát hiện thấy vòng lặp nào trong danh sách liên kết “.
- Đoạn mã sau đó sẽ chèn một vòng lặp vào danh sách được liên kết bằng cách đặt con trỏ tiếp theo của nút cuối cùng thành nút thứ hai. Sau đó, tùy thuộc vào kết quả của hàm, nó sẽ chạy detectLoopLinkedList() một lần nữa và sản xuất một trong hai ' Vòng lặp bị trừ trong danh sách được liên kết ' hoặc ' Không phát hiện thấy vòng lặp nào trong danh sách liên kết .”
Cách tiếp cận 4: Sử dụng ngăn xếp
Có thể tìm thấy các vòng lặp trong danh sách được liên kết bằng cách sử dụng ngăn xếp và phương pháp “tìm kiếm theo chiều sâu” (DFS). Khái niệm cơ bản là lặp qua danh sách được liên kết, đẩy từng nút vào ngăn xếp nếu nó chưa được truy cập. Một vòng lặp được nhận ra nếu gặp lại một nút đã có trên ngăn xếp.
Dưới đây là một mô tả ngắn gọn về thủ tục:
-
- Tạo một ngăn xếp trống và một biến để ghi lại các nút đã được truy cập.
- Đẩy danh sách được liên kết vào ngăn xếp, bắt đầu từ trên cùng. Ghi lại rằng đầu đã được truy cập.
- Đẩy nút tiếp theo trong danh sách vào ngăn xếp. Thêm dấu truy cập vào nút này.
- Khi bạn duyệt qua danh sách, hãy đẩy từng nút mới vào ngăn xếp để cho biết rằng nó đã được truy cập.
- Kiểm tra xem một nút đã được truy cập trước đó có ở trên cùng của ngăn xếp hay không nếu nó gặp phải. Nếu vậy, một vòng lặp đã được tìm thấy và vòng lặp được xác định bởi các nút trong ngăn xếp.
- Lấy các nút ra khỏi ngăn xếp và tiếp tục duyệt qua danh sách nếu không tìm thấy vòng lặp nào.
Triển khai chương trình C++ cho phương thức trên (Stack)
#include
#bao gồm
sử dụng không gian tên std;
nút cấu trúc {
dữ liệu int;
Nút * Kế tiếp;
} ;
// Chức năng phát hiện vòng lặp TRONG một danh sách liên kết
bool detectLoopLinkedList ( Nút * đầuNode ) {
cây rơm < Nút *> cây rơm;
Nút * tempNode = headNode;
trong khi ( tempNode ! = KHÔNG ) {
// nếu như phần tử trên cùng của ngăn xếp phù hợp
// nút hiện tại và ngăn xếp không trống
nếu như ( ! stack.empty ( ) && ngăn xếp.top ( ) == tempNode ) {
trở lại ĐÚNG VẬY ;
}
ngăn xếp.push ( tempNode ) ;
tempNode = tempNode- > Kế tiếp;
}
trở lại SAI ;
}
int chính ( ) {
Nút * headNode = Nút mới ( ) ;
Nút * secondNode = Nút mới ( ) ;
Nút * thirdNode = Nút mới ( ) ;
headNode- > dữ liệu = 1 ;
headNode- > tiếp theo = giâyNode;
giâyNode- > dữ liệu = 2 ;
giâyNode- > tiếp theo = nút thứ ba;
nút thứ ba- > dữ liệu = 3 ;
nút thứ ba- > tiếp theo = NULL; // không có vòng lặp
nếu như ( detectLoopLinkedList ( đầuNode ) ) {
cout << 'Phát hiện vòng lặp trong danh sách liên kết' << kết thúc;
} khác {
cout << 'Không phát hiện thấy vòng lặp nào trong danh sách liên kết' << kết thúc;
}
// Tạo một vòng lặp
nút thứ ba- > tiếp theo = giâyNode;
nếu như ( detectLoopLinkedList ( đầuNode ) ) {
cout << 'Phát hiện vòng lặp trong danh sách liên kết' << kết thúc;
} khác {
cout << 'Không phát hiện thấy vòng lặp nào trong danh sách liên kết' << kết thúc;
}
Đầu ra:
Không phát hiện thấy vòng lặp nào TRONG danh sách liên kết
Đã phát hiện vòng lặp TRONG danh sách liên kết
Giải trình:
Chương trình này sử dụng ngăn xếp để tìm hiểu xem danh sách liên kết đơn có vòng lặp hay không.
- 1. Cả thư viện luồng đầu vào/đầu ra và thư viện ngăn xếp đều có trong dòng đầu tiên.
2. Không gian tên tiêu chuẩn được bao gồm trong dòng thứ hai, cho phép chúng tôi truy cập các chức năng của thư viện luồng đầu vào/đầu ra mà không cần phải thêm tiền tố cho chúng bằng “std::.”
3. Dòng sau đây định nghĩa Nút cấu trúc, bao gồm hai thành viên: một số nguyên có tên là “data” và một con trỏ tới một Nút khác có tên là “next”.
4. Phần đầu của danh sách được liên kết là một đầu vào cho phương thức detectLoopLinkedList(), được xác định trên dòng tiếp theo. Hàm tạo ra một giá trị boolean cho biết có tìm thấy vòng lặp hay không.
5. Một chồng các con trỏ Node được gọi là “ngăn xếp” và một con trỏ tới một Nút có tên “tempNode” được khởi tạo với giá trị của headNode đều được tạo bên trong hàm.
6. Sau đó, miễn là tempNode không phải là một con trỏ null, chúng ta nhập một vòng lặp while.
(a) Phần tử trên cùng của ngăn xếp phải khớp với nút hiện tại để chúng tôi xác định rằng nó không trống. Chúng tôi trả về true nếu đúng như vậy vì một vòng lặp đã được tìm thấy.
(b) Nếu điều kiện nói trên là sai, con trỏ nút hiện tại được đẩy vào ngăn xếp và tempNode được đặt thành nút sau trong danh sách được liên kết.
7. Chúng tôi trả về false sau vòng lặp while vì không quan sát thấy vòng lặp nào.
8. Chúng ta xây dựng ba đối tượng Node và khởi tạo chúng trong hàm main(). Vì không có vòng lặp trong ví dụ đầu tiên, nên chúng tôi đặt đúng các con trỏ “tiếp theo” của mỗi Nút.
Phần kết luận:
Tóm lại, phương pháp tốt nhất để phát hiện vòng lặp trong danh sách liên kết phụ thuộc vào trường hợp sử dụng cụ thể và các ràng buộc của vấn đề. Bảng băm và thuật toán tìm chu trình Floyd là những phương pháp hiệu quả và chúng được sử dụng rộng rãi trong thực tế. Ngăn xếp và đệ quy là những phương pháp kém hiệu quả hơn nhưng chúng trực quan hơn.