โหนดท้ายของรายการที่เชื่อมโยงซึ่งมีลูปจะอ้างถึงโหนดอื่นในรายการเดียวกันแทนที่จะเป็น NULL หากมีโหนดในรายการที่เชื่อมโยงซึ่งสามารถเข้าถึงได้ซ้ำๆ โดยทำตามตัวชี้ถัดไป รายการนั้นจะถูกกล่าวถึง มีวงจร
โดยปกติแล้ว โหนดสุดท้ายของรายการที่เชื่อมโยงจะอ้างถึงการอ้างอิงที่เป็น NULL เพื่อแสดงถึงข้อสรุปของรายการ อย่างไรก็ตาม ในรายการที่เชื่อมโยงด้วยการวนซ้ำ โหนดท้ายของรายการจะอ้างอิงถึงโหนดเริ่มต้น โหนดภายใน หรือตัวมันเอง ดังนั้น ในสถานการณ์ดังกล่าว เราต้องระบุและยุติการวนซ้ำโดยตั้งค่าการอ้างอิงของโหนดถัดไปเป็น NULL อธิบายส่วนการตรวจจับของการวนซ้ำในรายการที่เชื่อมโยงในบทความนี้
ใน C++ มีหลายวิธีในการค้นหาลูปในรายการที่เชื่อมโยง:
วิธีการตามตารางแฮช : วิธีการนี้จัดเก็บที่อยู่ของโหนดที่เยี่ยมชมในตารางแฮช การวนซ้ำในรายการที่เชื่อมโยงนั้นมีอยู่หากมีโหนดอยู่ในตารางแฮชอยู่แล้วเมื่อมีการเยี่ยมชมอีกครั้ง
แนวทางวัฏจักรของฟลอยด์ : อัลกอริธึม “เต่ากับกระต่าย” หรือที่เรียกกันทั่วไปว่าอัลกอริทึมการหาวัฏจักรของฟลอยด์: เทคนิคนี้ใช้พอยน์เตอร์สองตัว ตัวแรกเคลื่อนที่ช้ากว่าตัวอื่น และอีกตัวเคลื่อนที่เร็วกว่า ตัวชี้ที่เร็วกว่าจะแซงตัวชี้ที่ช้ากว่าในท้ายที่สุดหากมีลูปในรายการที่เชื่อมโยง ซึ่งเผยให้เห็นการมีอยู่ของลูป
วิธีเรียกซ้ำ : วิธีการนี้ผ่านรายการที่เชื่อมโยงโดยการเรียกตัวเองซ้ำแล้วซ้ำอีก รายการที่เชื่อมโยงมีการวนซ้ำหากโหนดปัจจุบันได้รับการเยี่ยมชมก่อนหน้านี้
วิธีการตามสแต็ก : วิธีการนี้จัดเก็บที่อยู่ของโหนดที่เยี่ยมชมในสแต็ก การวนซ้ำในรายการที่เชื่อมโยงจะแสดงขึ้นหากมีโหนดอยู่ในสแต็กอยู่แล้วเมื่อมีการเยี่ยมชมอีกครั้ง
มาอธิบายรายละเอียดแต่ละวิธีเพื่อทำความเข้าใจแนวคิด
แนวทางที่ 1: แนวทาง HashSet
การใช้แฮชเป็นวิธีที่ตรงไปตรงมาที่สุด ที่นี่ เราจะผ่านรายการทีละรายการในขณะที่เก็บตารางแฮชด้วยที่อยู่โหนด ดังนั้น การวนซ้ำจะเกิดขึ้นหากเราเรียกใช้ข้ามที่อยู่ถัดไปของโหนดปัจจุบันที่มีอยู่ในตารางแฮช มิฉะนั้น จะไม่มีการวนซ้ำในรายการที่เชื่อมโยงหากเราพบค่าว่าง (เช่น ไปถึงจุดสิ้นสุดของรายการที่เชื่อมโยง)
มันจะค่อนข้างง่ายที่จะใช้กลยุทธ์นี้
ในขณะที่สำรวจรายการที่เชื่อมโยง เราจะใช้ unordered_hashmap และเพิ่มโหนดต่อไป
เมื่อเราเจอโหนดที่แสดงอยู่ในแผนที่แล้ว เราจะรู้ว่าเรามาถึงจุดเริ่มต้นของลูปแล้ว
-
- นอกจากนี้ เรายังมีตัวชี้สองตัวในแต่ละขั้นตอน หัวโหนด ชี้ไปที่โหนดปัจจุบันและ โหนดสุดท้าย ชี้ไปที่โหนดก่อนหน้าของโหนดปัจจุบัน ในขณะที่วนซ้ำ
- เป็นของเรา หัวโหนด กำลังชี้ไปที่โหนดเริ่มต้นของลูปและเป็น โหนดสุดท้าย กำลังชี้ไปที่โหนดที่ส่วนหัวชี้อยู่ (เช่น อ้างถึงไฟล์ โหนดสุดท้าย ของลูป) ของเรา หัวโหนด กำลังชี้ไปที่โหนดเริ่มต้นของลูป
- ลูปจะถูกทำลายโดยการตั้งค่า l astNode->ถัดไป == NULL .
เมื่อทำเช่นนี้ โหนดลูปสิ้นสุดแทนที่จะอ้างถึงโหนดเริ่มต้นของลูป จะเริ่มชี้ไปที่ NULL
ความซับซ้อนของเวลาและพื้นที่โดยเฉลี่ยของวิธีการแฮชคือ O(n) ผู้อ่านควรทราบเสมอว่าการใช้โครงสร้างข้อมูลการแฮชในตัวในภาษาการเขียนโปรแกรมจะเป็นตัวกำหนดความซับซ้อนของเวลาทั้งหมดในกรณีที่เกิดการชนกันในการแฮช
การใช้งานโปรแกรม C++ สำหรับวิธีการข้างต้น (HashSet):
#รวม
ใช้เนมสเปซ std;
โครงสร้างโหนด {
ค่า int;
โครงสร้างโหนด * ต่อไป;
} ;
โหนด * โหนดใหม่ ( ค่า int )
{
โหนด * tempNode = โหนดใหม่;
tempNode- > ค่า = ค่า;
tempNode- > ถัดไป = NULL;
กลับ โหนดชั่วคราว;
}
// ระบุและกำจัดลูปที่อาจเกิดขึ้น
// ใน รายการที่เชื่อมโยงกับฟังก์ชันนี้
เป็นโมฆะ functionHashMap ( โหนด * หัวโหนด )
{
// สร้าง unordered_map เพื่อใช้แผนที่แฮช
unordered_map < โหนด * , ใน > hash_map;
// ตัวชี้ไปที่โหนดสุดท้าย
โหนด * โหนดสุดท้าย = NULL;
ในขณะที่ ( หัวโหนด ! = โมฆะ ) {
// หากไม่มีโหนดในแผนที่ ให้เพิ่มโหนดนั้น
ถ้า ( hash_map.find ( หัวโหนด ) == hash_map.end ( ) ) {
hash_map [ หัวโหนด ] ++;
โหนดสุดท้าย = โหนดหัว;
headNode = หัวโหนด- > ต่อไป;
}
// หากมีวัฏจักรอยู่ ชุด โหนดสุดท้าย ตัวชี้ถัดไปของ NULL
อื่น {
โหนดสุดท้าย->ถัดไป = NULL;
หยุดพัก;
}
}
}
// แสดงรายการที่เชื่อมโยง
การแสดงผลเป็นโมฆะ (Node* headNode)
{
ในขณะที่ (headNode != NULL) {
ศาล << headNode->value << ' ';
headNode = headNode->ถัดไป;
}
ศาล << endl;
}
/* ฟังก์ชั่นหลัก*/
int หลัก ()
{
โหนด* headNode = newNode(48);
headNode->ถัดไป = headNode;
headNode->ถัดไป = newNode(18);
headNode->next->next = newNode(13);
headNode->ถัดไป->ถัดไป->ถัดไป = newNode(2);
headNode->ถัดไป->ถัดไป->ถัดไป->ถัดไป = newNode(8);
/* สร้างลูปในลิงค์ลิสต์ */
headNode->next->next->next->next->next = headNode->ถัดไป->ถัดไป;
functionHashMap(หัวโหนด);
printf('ลิงค์ลิสต์ที่ไม่มีลูป \n');
จอแสดงผล (หัวโหนด);
กลับ 0;
}
เอาท์พุต:
รายการที่เชื่อมโยงโดยไม่มีการวนซ้ำ
48 18 13 2 8
คำอธิบายทีละขั้นตอนของโค้ดมีดังต่อไปนี้:
-
- ไฟล์ส่วนหัว bits/stdc++.h> ซึ่งมีไลบรารี C++ ทั่วไปทั้งหมดรวมอยู่ในโค้ด
- มีการสร้างโครงสร้างที่เรียกว่า 'โหนด' และมีสมาชิกสองตัว: การอ้างอิงไปยังโหนดถัดไปในรายการและจำนวนเต็มที่เรียกว่า 'ค่า'
- ด้วยค่าจำนวนเต็มเป็นอินพุตและตัวชี้ 'ถัดไป' ตั้งค่าเป็น NULL ฟังก์ชัน 'newNode' จะสร้างโหนดใหม่ด้วยค่านั้น
- ฟังก์ชั่น ' ฟังก์ชันHashMap’ ถูกกำหนดซึ่งใช้ตัวชี้ไปยังโหนดส่วนหัวของรายการที่เชื่อมโยงเป็นอินพุต
- ข้างใน ' ฟังก์ชันHashMap ' ฟังก์ชัน unordered_map ชื่อ 'hash_map' ถูกสร้างขึ้น ซึ่งใช้ในการปรับใช้โครงสร้างข้อมูลแผนที่แฮช
- ตัวชี้ไปยังโหนดสุดท้ายของรายการเริ่มต้นเป็น NULL
- การวนรอบ while ใช้เพื่อสำรวจรายการที่เชื่อมโยง ซึ่งเริ่มต้นจากโหนดส่วนหัวและดำเนินต่อไปจนกว่าโหนดส่วนหัวจะเป็น NULL
- ตัวชี้โหนดสุดท้ายถูกอัพเดตเป็นโหนดปัจจุบันภายในลูป while ถ้าโหนดปัจจุบัน (headNode) ไม่อยู่ในแมปแฮช
- หากพบโหนดปัจจุบันในแผนที่ แสดงว่ามีลูปอยู่ในรายการที่เชื่อมโยง หากต้องการลบลูป ตัวชี้ถัดไปของ โหนดสุดท้าย ถูกตั้งค่าเป็น โมฆะ และลูป while เสีย
- โหนดส่วนหัวของรายการที่เชื่อมโยงจะใช้เป็นอินพุตสำหรับฟังก์ชันที่เรียกว่า 'จอแสดงผล' ซึ่งจะส่งออกค่าของแต่ละโหนดในรายการตั้งแต่ต้นจนจบ
- ใน หลัก ฟังก์ชันสร้างลูป
- ฟังก์ชัน 'functionHashMap' ถูกเรียกใช้โดยมีตัวชี้ headNode เป็นอินพุต ซึ่งจะลบการวนซ้ำออกจากรายการ
- รายการที่แก้ไขจะแสดงโดยใช้ฟังก์ชัน 'แสดง'
วิธีที่ 2: วัฏจักรของฟลอยด์
อัลกอริธึมการตรวจจับวัฏจักรของฟลอยด์ ซึ่งมักรู้จักกันในชื่ออัลกอริทึมเต่าและกระต่าย เป็นพื้นฐานสำหรับวิธีการค้นหาวัฏจักรในรายการที่เชื่อมโยงนี้ ตัวชี้ 'ช้า' และตัวชี้ 'เร็ว' ซึ่งเคลื่อนที่ไปตามรายการด้วยความเร็วต่างๆ คือตัวชี้สองตัวที่ใช้ในเทคนิคนี้ ตัวชี้แบบเร็วจะเลื่อนไปสองขั้นในขณะที่ตัวชี้แบบช้าจะเลื่อนไปหนึ่งขั้นในทุก ๆ การวนซ้ำ วงจรในรายการที่เชื่อมโยงจะเกิดขึ้นหากจุดสองจุดเผชิญหน้ากัน
1. ด้วยโหนดส่วนหัวของรายการที่เชื่อมโยง เราจะเริ่มต้นพอยน์เตอร์สองตัวที่เรียกว่าเร็วและช้า
2. ตอนนี้เราเรียกใช้การวนซ้ำเพื่อเลื่อนผ่านรายการที่เชื่อมโยง ควรย้ายตัวชี้แบบเร็วสองตำแหน่งหน้าตัวชี้แบบช้าในแต่ละขั้นตอนของการวนซ้ำ
3. จะไม่มีการวนซ้ำในรายการที่เชื่อมโยงหากตัวชี้แบบเร็วถึงจุดสิ้นสุดของรายการ (fastPointer == NULL หรือ fastPointer->next == NULL) ถ้าไม่เช่นนั้น พอยน์เตอร์เร็วและช้าจะมาบรรจบกันในที่สุด ซึ่งหมายความว่ารายการที่เชื่อมโยงจะมีการวนซ้ำ
การใช้งานโปรแกรม C++ สำหรับวิธีการข้างต้น (Floyd’s Cycle):
#รวม
ใช้เนมสเปซ std;
/* โหนดรายการลิงก์ */
โครงสร้างโหนด {
ข้อมูล int;
โครงสร้างโหนด * ต่อไป;
} ;
/* ฟังก์ชันลบลูป */
เป็นโมฆะ deleteLoop ( โครงสร้างโหนด * โครงสร้างโหนด * ) ;
/* นี้ การทำงาน ค้นหาและกำจัดการวนซ้ำของรายการ มันยอม 1
ถ้า มีการวนซ้ำ ใน รายการ; อื่น มันกลับมา 0 . */
int ตรวจจับและลบลูป ( โครงสร้างโหนด * รายการ )
{
โครงสร้างโหนด * slowPTR = รายการ * fastPTR = รายการ;
// ย้ำเพื่อตรวจสอบ ถ้า ห่วงอยู่ที่นั่น
ในขณะที่ ( PTR ช้า && เร็วPTR && fastPTR- > ต่อไป ) {
slowPTR = ช้าPTR- > ต่อไป;
fastPTR = fastPTR- > ต่อไป- > ต่อไป;
/* ถ้า slowPTR และ fastPTR พบกันที่จุดใดจุดหนึ่ง แล้ว ที่นั่น
เป็นห่วง */
ถ้า ( slowPTR == fastPTR ) {
ลบลูป ( slowPTR รายการ ) ;
/* กลับ 1 เพื่อระบุว่าพบลูปแล้ว */
กลับ 1 ;
}
}
/* กลับ 0 เพื่อระบุว่าไม่พบการวนซ้ำ */
กลับ 0 ;
}
/* ฟังก์ชั่นลบลูปออกจากลิงค์ลิสต์
loopNode กำลังชี้ไปที่หนึ่งในโหนดลูป และ headNode กำลังชี้
ไปยังโหนดเริ่มต้นของรายการที่เชื่อมโยง */
เป็นโมฆะ deleteLoop ( โครงสร้างโหนด * loopNode, struct โหนด * หัวโหนด )
{
โครงสร้างโหนด * ptr1 = โหนดลูป;
โครงสร้างโหนด * ptr2 = โหนดลูป;
// นับจำนวนโหนด ใน ห่วง
int ที่ไม่ได้ลงชื่อ k = 1 , ฉัน;
ในขณะที่ ( ptr1- > ต่อไป ! = ptr2 ) {
ptr1 = ptr1- > ต่อไป;
k++;
}
// แก้ไขตัวชี้หนึ่งตัวไปที่ headNode
ptr1 = หัวโหนด;
// และอีกตัวชี้ไปที่ k โหนดหลัง headNode
ptr2 = โหนดหัว;
สำหรับ ( ฉัน = 0 ; ฉัน < เค; ฉัน ++ )
ptr2 = ptr2- > ต่อไป;
/* เมื่อย้ายจุดทั้งสองพร้อมกัน
พวกเขาจะชนกันที่วง โหนดเริ่มต้น */
ในขณะที่ (ptr2 != ptr1) {
ptr1 = ptr1->ถัดไป;
ptr2 = ptr2->ถัดไป;
}
// รับโหนด ' ส ล่าสุด ตัวชี้
ในขณะที่ ( ptr2- > ต่อไป ! = ptr1 )
ptr2 = ptr2- > ต่อไป;
/* หากต้องการปิดลูป ชุด ที่ตามมา
โหนดไปยังลูป สิ้นสุดโหนด */
ptr2->ถัดไป = NULL;
}
/* ฟังก์ชั่นแสดงลิงค์ลิสต์ */
ถือเป็นโมฆะ displayLinkedList (struct Node* โหนด)
{
// แสดงรายการที่เชื่อมโยงหลังจากลบลูป
ในขณะที่ (โหนด != NULL) {
ศาล << โหนด->ข้อมูล << ' ';
โหนด = โหนด -> ถัดไป;
}
}
struct Node* newNode(คีย์ int)
{
struct Node* temp = โหนดใหม่ ();
temp->data = คีย์;
อุณหภูมิ> ถัดไป = NULL;
อุณหภูมิกลับ
}
// รหัสหลัก
int หลัก ()
{
โครงสร้าง Node* headNode = newNode(48);
headNode->ถัดไป = newNode(18);
headNode->next->next = newNode(13);
headNode->ถัดไป->ถัดไป->ถัดไป = newNode(2);
headNode->ถัดไป->ถัดไป->ถัดไป->ถัดไป = newNode(8);
/* สร้างลูป */
headNode->next->next->next->next->next = headNode->ถัดไป->ถัดไป;
// แสดงลูปในรายการที่เชื่อมโยง
//displayLinkedList(หัวโหนด);
ตรวจจับและลบลูป (หัวโหนด);
ศาล << 'รายการเชื่อมโยงหลังจากไม่มีลูป \n';
displayLinkedList (หัวโหนด);
กลับ 0;
}
เอาท์พุต:
รายการที่เชื่อมโยงหลังจากไม่มีการวนซ้ำ
48 18 13 2 8
คำอธิบาย:
-
- ส่วนหัวที่เกี่ยวข้อง เช่น “bits/stdc++.h” และ “std::cout” จะถูกรวมไว้ก่อน
- โครงสร้าง 'โหนด' ซึ่งย่อมาจากโหนดในรายการที่เชื่อมโยงจะถูกประกาศ ตัวชี้ถัดไปที่นำไปสู่โหนดต่อไปนี้ในรายการรวมอยู่ด้วยพร้อมกับฟิลด์ข้อมูลจำนวนเต็มในแต่ละโหนด
- จากนั้น จะกำหนด “deleteLoop” และ “detectAndDeleteLoop” สองฟังก์ชัน การวนซ้ำจะถูกลบออกจากรายการที่เชื่อมโยงโดยใช้วิธีแรก และตรวจพบการวนซ้ำในรายการโดยใช้ฟังก์ชันที่สอง ซึ่งจะเรียกขั้นตอนแรกเพื่อลบการวนซ้ำ
- รายการเชื่อมโยงใหม่ที่มีห้าโหนดถูกสร้างขึ้นในฟังก์ชันหลัก และสร้างการวนซ้ำโดยการตั้งค่าตัวชี้ถัดไปของโหนดสุดท้ายไปยังโหนดที่สาม
- จากนั้นทำการเรียกเมธอด “detectAndDeleteLoop” ในขณะที่ส่งโหนดส่วนหัวของรายการที่เชื่อมโยงเป็นอาร์กิวเมนต์ ในการระบุลูป ฟังก์ชันนี้ใช้วิธี 'ตัวชี้แบบช้าและเร็ว' ใช้พอยน์เตอร์สองตัวที่เริ่มต้นที่ด้านบนสุดของรายการ ได้แก่ slowPTR และ fastPTR ในขณะที่ตัวชี้แบบเร็วจะย้ายสองโหนดพร้อมกัน ตัวชี้แบบช้าจะย้ายครั้งละหนึ่งโหนดเท่านั้น ตัวชี้ที่เร็วจะแซงตัวชี้ที่ช้าในที่สุดหากรายการมีการวนซ้ำ และจุดทั้งสองจะชนกันที่โหนดเดียวกัน
- ฟังก์ชันเรียกใช้ฟังก์ชัน “deleteLoop” หากพบการวนซ้ำ โดยป้อนโหนดส่วนหัวของรายการและจุดตัดกันของตัวชี้ที่ช้าและเร็วเป็นอินพุต ขั้นตอนนี้สร้างตัวชี้สองตัว ptr1 และ ptr2 ไปยังโหนดส่วนหัวของรายการและนับจำนวนโหนดในลูป ต่อจากนั้น มันจะเลื่อนตัวชี้ k โหนดหนึ่งตัวไปข้างหน้า โดยที่ k คือจำนวนโหนดทั้งหมดในลูป จากนั้น จนกว่าจะพบกันที่จุดเริ่มต้นของลูป ทั้งสองจะชี้ไปที่โหนดทีละโหนด จากนั้นลูปจะถูกทำลายโดยการตั้งค่าตัวชี้ถัดไปของโหนดที่ส่วนท้ายของลูปเป็น NULL
- หลังจากลบการวนซ้ำแล้ว จะแสดงรายการที่เชื่อมโยงเป็นขั้นตอนสุดท้าย
วิธีที่ 3: การเรียกซ้ำ
การเรียกซ้ำเป็นเทคนิคในการแก้ปัญหาโดยการแบ่งปัญหาออกเป็นปัญหาย่อยที่เล็กลงและง่ายขึ้น การเรียกซ้ำสามารถใช้เพื่อสำรวจรายการที่เชื่อมโยงเดี่ยวในกรณีที่พบการวนซ้ำโดยการเรียกใช้ฟังก์ชันอย่างต่อเนื่องสำหรับโหนดถัดไปในรายการจนกว่าจะถึงจุดสิ้นสุดของรายการ
ในรายการที่เชื่อมโยงแบบเดี่ยว หลักการพื้นฐานเบื้องหลังการใช้การวนซ้ำเพื่อค้นหาลูปคือการเริ่มต้นที่ส่วนหัวของรายการ ทำเครื่องหมายโหนดปัจจุบันตามที่เยี่ยมชมในแต่ละขั้นตอน จากนั้นไปยังโหนดถัดไปโดยการเรียกใช้ฟังก์ชันแบบเรียกซ้ำสำหรับ โหนดนั้น เมธอดจะวนซ้ำกับรายการที่ลิงก์ทั้งหมดเพราะเรียกซ้ำ
รายการประกอบด้วยการวนซ้ำหากฟังก์ชันพบโหนดที่ทำเครื่องหมายว่าเยี่ยมชมก่อนหน้านี้ ในกรณีนี้ ฟังก์ชันสามารถคืนค่าจริงได้ เมธอดสามารถส่งคืนค่าเท็จได้หากไปถึงจุดสิ้นสุดของรายการโดยไม่เรียกใช้โหนดที่เข้าชม ซึ่งแสดงว่าไม่มีการวนซ้ำ
แม้ว่าเทคนิคนี้สำหรับการใช้การวนซ้ำเพื่อค้นหาลูปในรายการที่เชื่อมโยงเดียวนั้นใช้และเข้าใจได้ง่าย แต่อาจไม่ใช่วิธีที่ได้ผลที่สุดในแง่ของความซับซ้อนของเวลาและพื้นที่
การใช้งานโปรแกรม C++ สำหรับวิธีการข้างต้น (Recursion):
#รวมถึง
ใช้เนมสเปซ std;
โครงสร้างโหนด {
ข้อมูล int;
โหนด * ต่อไป;
บูลไปเยี่ยม;
} ;
// การตรวจจับลูปลิสต์ที่เชื่อมโยง การทำงาน
บูล DetectLoopLinkedList ( โหนด * หัวโหนด ) {
ถ้า ( เฮดโหนด == NULL ) {
กลับ เท็จ ; // หากรายการที่เชื่อมโยงว่างเปล่า แสดงว่าเป็นรายการพื้นฐาน กรณี
}
// มีห่วง ถ้า โหนดปัจจุบันมี
// เคยไปมาแล้ว
ถ้า ( หัวโหนด- > เยี่ยมชม ) {
กลับ จริง ;
}
// เพิ่มเครื่องหมายการเยี่ยมชมไปยังโหนดปัจจุบัน
หัวโหนด- > เยี่ยมชม = จริง ;
// การเรียกรหัส สำหรับ โหนดที่ตามมาซ้ำๆ
กลับ ตรวจจับลูปลิงก์รายการ ( หัวโหนด- > ต่อไป ) ;
}
int หลัก ( ) {
โหนด * headNode = โหนดใหม่ ( ) ;
โหนด * โหนดที่สอง = โหนดใหม่ ( ) ;
โหนด * โหนดที่สาม = โหนดใหม่ ( ) ;
หัวโหนด- > ข้อมูล = 1 ;
หัวโหนด- > ถัดไป = โหนดที่สอง;
หัวโหนด- > เยี่ยมชม = เท็จ ;
โหนดที่สอง- > ข้อมูล = 2 ;
โหนดที่สอง- > ถัดไป = โหนดที่สาม;
โหนดที่สอง- > เยี่ยมชม = เท็จ ;
โหนดที่สาม- > ข้อมูล = 3 ;
โหนดที่สาม- > ถัดไป = NULL; // ไม่มีลูป
โหนดที่สาม- > เยี่ยมชม = เท็จ ;
ถ้า ( ตรวจจับลูปลิงก์รายการ ( หัวโหนด ) ) {
ศาล << 'ตรวจพบการวนซ้ำในรายการที่เชื่อมโยง' << ท้าย;
} อื่น {
ศาล << 'ไม่พบการวนซ้ำในรายการที่เชื่อมโยง' << ท้าย;
}
// การสร้างลูป
โหนดที่สาม- > ถัดไป = โหนดที่สอง;
ถ้า ( ตรวจจับลูปลิงก์รายการ ( หัวโหนด ) ) {
ศาล << 'ตรวจพบการวนซ้ำในรายการที่เชื่อมโยง' << ท้าย;
} อื่น {
ศาล << 'ไม่พบการวนซ้ำในรายการที่เชื่อมโยง' << ท้าย;
}
กลับ 0 ;
}
เอาท์พุต:
ไม่พบการวนซ้ำ ใน รายการที่เชื่อมโยง
ตรวจพบลูป ใน รายการที่เชื่อมโยง
คำอธิบาย:
-
- ฟังก์ชั่น ตรวจจับลูปLinkedList() ในโปรแกรมนี้ยอมรับส่วนหัวของรายการที่เชื่อมโยงเป็นอินพุต
- ฟังก์ชันใช้การวนซ้ำเพื่อวนซ้ำในรายการที่เชื่อมโยง ในกรณีพื้นฐานสำหรับการเรียกซ้ำ จะเริ่มต้นด้วยการพิจารณาว่าโหนดปัจจุบันเป็น NULL หรือไม่ ถ้าใช่ เมธอดจะคืนค่าเป็นเท็จ แสดงว่าไม่มีการวนซ้ำ
- ค่าของคุณสมบัติ 'เยี่ยมชม' ของโหนดปัจจุบันจะถูกตรวจสอบเพื่อดูว่าเคยเยี่ยมชมมาก่อนหรือไม่ มันจะคืนค่าจริงหากมีการเข้าชม แสดงว่าพบลูปแล้ว
- ฟังก์ชันจะทำเครื่องหมายโหนดปัจจุบันว่าเยี่ยมชม หากได้รับการเยี่ยมชมแล้วโดยเปลี่ยนคุณสมบัติ 'เยี่ยมชม' ให้เป็นจริง
- จากนั้นค่าของตัวแปรที่เข้าชมจะถูกตรวจสอบเพื่อดูว่าโหนดปัจจุบันได้รับการเยี่ยมชมก่อนหน้านี้หรือไม่ หากเคยใช้มาก่อน จะต้องมีลูป และฟังก์ชันจะคืนค่าจริง
- สุดท้าย ฟังก์ชันเรียกตัวเองด้วยโหนดถัดไปในรายการโดยผ่าน headNode->ถัดไป เป็นข้อโต้แย้ง เรียกซ้ำ จะดำเนินการจนกว่าจะพบลูปหรือโหนดทั้งหมดได้รับการเยี่ยมชม หมายถึง ฟังก์ชันจะตั้งค่าตัวแปรที่เข้าชมให้เป็นจริงหากโหนดปัจจุบันไม่เคยถูกเยี่ยมชมก่อนที่จะเรียกตัวเองซ้ำสำหรับโหนดต่อไปนี้ในรายการที่เชื่อมโยง
- รหัสสร้างสามโหนดและรวมเข้าด้วยกันเพื่อสร้างรายการที่เชื่อมโยงใน ฟังก์ชั่นหลัก . วิธีการ ตรวจจับลูปLinkedList() จากนั้นจะถูกเรียกใช้บนโหนดส่วนหัวของรายการ โปรแกรมสร้าง “ วนซ้ำหักในรายการที่เชื่อมโยง ' ถ้า ตรวจจับลูปLinkedList() คืนค่าจริง; มิฉะนั้นจะแสดงผล “ ไม่พบการวนซ้ำในรายการที่เชื่อมโยง “.
- จากนั้นโค้ดจะแทรกลูปเข้าไปในรายการที่เชื่อมโยงโดยตั้งค่าตัวชี้ถัดไปของโหนดสุดท้ายไปยังโหนดที่สอง จากนั้นขึ้นอยู่กับผลลัพธ์ของฟังก์ชัน ตรวจจับลูปLinkedList() อีกครั้งและผลิตอย่างใดอย่างหนึ่ง “ วนซ้ำหักในรายการที่เชื่อมโยง ' หรือ ' ไม่พบการวนซ้ำในรายการที่เชื่อมโยง ”
วิธีที่ 4: การใช้สแต็ค
สามารถค้นหาลูปในรายการที่เชื่อมโยงได้โดยใช้สแต็กและวิธี 'การค้นหาเชิงลึกก่อน' (DFS) แนวคิดพื้นฐานคือการวนซ้ำผ่านรายการที่เชื่อมโยง ผลักแต่ละโหนดไปยังสแต็กหากยังไม่ได้เยี่ยมชม ลูปจะรับรู้หากพบโหนดที่อยู่ในสแต็กอยู่แล้วอีกครั้ง
นี่คือคำอธิบายสั้น ๆ ของขั้นตอน:
-
- สร้างสแต็กว่างและตัวแปรเพื่อบันทึกโหนดที่เคยเยี่ยมชม
- ดันรายการที่เชื่อมโยงไปยังสแต็ก โดยเริ่มจากด้านบนสุด จดบันทึกว่าเยี่ยมหัวแล้ว
- ดันโหนดถัดไปในรายการไปยังสแต็ก เพิ่มเครื่องหมายการเข้าชมไปยังโหนดนี้
- ขณะที่คุณสำรวจรายการ ให้กดโหนดใหม่แต่ละโหนดลงบนสแต็กเพื่อระบุว่ามีการเยี่ยมชมแล้ว
- ตรวจสอบเพื่อดูว่าโหนดที่เคยเยี่ยมชมนั้นอยู่ที่ด้านบนสุดของสแต็กหรือไม่ หากพบ ถ้าเป็นเช่นนั้น แสดงว่าพบการวนซ้ำ และมีการระบุการวนซ้ำโดยโหนดในสแต็ก
- นำโหนดออกจากสแต็กและสำรวจรายการต่อไปหากไม่พบการวนซ้ำ
การใช้งานโปรแกรม C++ ตามวิธีการข้างต้น (Stack)
#รวมถึง
#รวม <สแต็ค>
ใช้เนมสเปซ std;
โครงสร้างโหนด {
ข้อมูล int;
โหนด * ต่อไป;
} ;
// ฟังก์ชั่นตรวจจับลูป ใน รายการที่เชื่อมโยง
บูล DetectLoopLinkedList ( โหนด * หัวโหนด ) {
ซ้อนกัน < โหนด *> ซ้อนกัน;
โหนด * tempNode = หัวโหนด;
ในขณะที่ ( โหนดชั่วคราว ! = โมฆะ ) {
// ถ้า องค์ประกอบด้านบนของสแต็คตรงกัน
// โหนดปัจจุบันและสแต็กไม่ว่างเปล่า
ถ้า ( ! stack.empty ( ) && stack.top ( ) == โหนดชั่วคราว ) {
กลับ จริง ;
}
stack.push ( โหนดชั่วคราว ) ;
tempNode = tempNode- > ต่อไป;
}
กลับ เท็จ ;
}
int หลัก ( ) {
โหนด * headNode = โหนดใหม่ ( ) ;
โหนด * โหนดที่สอง = โหนดใหม่ ( ) ;
โหนด * โหนดที่สาม = โหนดใหม่ ( ) ;
หัวโหนด- > ข้อมูล = 1 ;
หัวโหนด- > ถัดไป = โหนดที่สอง;
โหนดที่สอง- > ข้อมูล = 2 ;
โหนดที่สอง- > ถัดไป = โหนดที่สาม;
โหนดที่สาม- > ข้อมูล = 3 ;
โหนดที่สาม- > ถัดไป = NULL; // ไม่มีลูป
ถ้า ( ตรวจจับลูปลิงก์รายการ ( หัวโหนด ) ) {
ศาล << 'ตรวจพบการวนซ้ำในรายการที่เชื่อมโยง' << ท้าย;
} อื่น {
ศาล << 'ไม่พบการวนซ้ำในรายการที่เชื่อมโยง' << ท้าย;
}
// การสร้างลูป
โหนดที่สาม- > ถัดไป = โหนดที่สอง;
ถ้า ( ตรวจจับลูปลิงก์รายการ ( หัวโหนด ) ) {
ศาล << 'ตรวจพบการวนซ้ำในรายการที่เชื่อมโยง' << ท้าย;
} อื่น {
ศาล << 'ไม่พบการวนซ้ำในรายการที่เชื่อมโยง' << ท้าย;
}
เอาท์พุต:
ไม่พบการวนซ้ำ ใน รายการที่เชื่อมโยง
ตรวจพบลูป ใน รายการที่เชื่อมโยง
คำอธิบาย:
โปรแกรมนี้ใช้สแต็กเพื่อดูว่ารายการที่เชื่อมโยงเดี่ยวมีการวนซ้ำหรือไม่
- 1. ไลบรารีสตรีมอินพุต/เอาต์พุตและไลบรารีสแต็กมีอยู่ในบรรทัดแรก
2. เนมสเปซมาตรฐานรวมอยู่ในบรรทัดที่สอง ทำให้เราสามารถเข้าถึงฟังก์ชันของไลบรารีสตรีมอินพุต/เอาต์พุตโดยไม่ต้องขึ้นต้นด้วย 'std::'
3. บรรทัดต่อไปนี้กำหนดโหนดโครงสร้างซึ่งประกอบด้วยสมาชิกสองตัว: จำนวนเต็มเรียกว่า 'ข้อมูล' และตัวชี้ไปยังโหนดอื่นเรียกว่า 'ถัดไป'
4. ส่วนหัวของรายการที่เชื่อมโยงคืออินพุตสำหรับเมธอด detectionLoopLinkedList() ซึ่งกำหนดไว้ในบรรทัดถัดไป ฟังก์ชันสร้างค่าบูลีนที่ระบุว่าพบการวนซ้ำหรือไม่
5. สแต็กของตัวชี้โหนดที่เรียกว่า 'สแต็ก' และตัวชี้ไปยังโหนดชื่อ 'tempNode' ที่เริ่มต้นด้วยค่าของ headNode จะถูกสร้างขึ้นภายในฟังก์ชัน
6. จากนั้น ตราบเท่าที่ tempNode ไม่ใช่ null pointer เราจะเข้าสู่โหมด while
(a) องค์ประกอบบนสุดของสแต็กต้องตรงกับโหนดปัจจุบัน เพื่อให้เราสามารถระบุได้ว่าไม่ว่างเปล่า เราจะคืนค่าจริงหากเป็นกรณีนี้เนื่องจากพบการวนซ้ำ
(b) หากเงื่อนไขข้างต้นเป็นเท็จ ตัวชี้โหนดปัจจุบันจะถูกผลักไปที่สแต็ก และ tempNode จะถูกตั้งค่าเป็นโหนดต่อไปนี้ในรายการที่เชื่อมโยง
7. เราคืนค่าเท็จหลังจากลูป while เนื่องจากไม่มีการวนซ้ำ
8. เราสร้าง Node object ขึ้นมา 3 อันและเริ่มต้นพวกมันในฟังก์ชั่น main() เนื่องจากตัวอย่างแรกไม่มีการวนซ้ำ เราจึงตั้งค่าพอยน์เตอร์ 'ถัดไป' ของแต่ละโหนดให้ถูกต้อง
บทสรุป:
โดยสรุป วิธีที่ดีที่สุดในการตรวจหาลูปในรายการที่เชื่อมโยงนั้นขึ้นอยู่กับกรณีการใช้งานเฉพาะและข้อจำกัดของปัญหา Hash Table และอัลกอริธึมการหาวัฏจักรของ Floyd เป็นวิธีการที่มีประสิทธิภาพและมีการใช้กันอย่างแพร่หลายในทางปฏิบัติ สแต็กและการเรียกซ้ำเป็นวิธีที่มีประสิทธิภาพน้อยกว่า แต่ใช้งานง่ายกว่า