צומת הקצה של רשימה מקושרת שיש לה לולאה יפנה לצומת אחר באותה רשימה ולא ל-NULL. אם יש צומת ברשימה מקושרת שניתן לגשת אליו שוב ושוב על ידי ביצוע המצביע הבא, הרשימה אמורה להיות לעשות מחזור.
בדרך כלל, הצומת האחרון של הרשימה המקושרת מתייחס להפניה NULL לציון מסקנת הרשימה. עם זאת, ברשימה מקושרת עם לולאה, צומת הסיום של הרשימה מתייחס לצומת התחלה, לצומת פנימי או לעצמו. לכן, בנסיבות כאלה, עלינו לזהות ולסיים את הלולאה על ידי הגדרת ההתייחסות של הצומת הבא ל-NULL. חלק הזיהוי של הלולאה ברשימה מקושרת מוסבר במאמר זה.
ב-C++, ישנן דרכים רבות למצוא לולאות ברשימה מקושרת:
גישה מבוססת טבלאות Hash : גישה זו מאחסנת את הכתובות של צמתים שביקרו בטבלת גיבוב. לולאה ברשימה המקושרת קיימת אם צומת כבר קיים בטבלת ה-hash כאשר מבקרים בו שוב.
גישת המחזור של פלויד : אלגוריתם ה'צב והארנבת', המכונה בדרך כלל אלגוריתם מציאת המחזור של פלויד: טכניקה זו עושה שימוש בשני מצביעים, האחד נע לאט יותר מהשני והשני זז מהר יותר. המצביע המהיר יותר יעקוף בסופו של דבר את המצביע האיטי יותר אם יש לולאה ברשימה המקושרת, וחושף את קיומה של הלולאה.
שיטה רקורסיבית : שיטה זו עוברת על הרשימה המקושרת על ידי קריאה לעצמה שוב ושוב. הרשימה המקושרת מכילה לולאה אם הצומת הנוכחי ביקר בעבר.
גישה מבוססת מחסנית : גישה זו מאחסנת את הכתובות של צמתים שביקרו בערימה. לולאה ברשימה המקושרת קיימת אם צומת כבר קיים בערימה כאשר מבקרים בו שוב.
בואו נסביר כל גישה בפירוט כדי להבין את הרעיון.
גישה 1: גישת HashSet
שימוש בגיבוב הוא השיטה הפשוטה ביותר. כאן, אנו עוברים על הרשימה בזה אחר זה תוך שמירה על טבלת hash עם כתובות הצומת. לכן, קיימת לולאה אם אי פעם נתקל בכתובת הבאה של הצומת הנוכחי שכבר כלול בטבלת ה-hash. אחרת, אין לולאה ברשימה המקושרת אם אנו נתקלים ב-NULL (כלומר, מגיעים לסוף הרשימה המקושרת).
זה יהיה די קל ליישם את האסטרטגיה הזו.
בזמן מעבר ברשימה המקושרת, נשתמש במפת hashmap unordered_ ונמשיך להוסיף לה צמתים.
כעת, ברגע שנתקל בצומת שכבר מוצג במפה, נדע שהגענו לתחילת הלולאה.
-
- בנוסף, שמרנו על שני מצביעים בכל שלב, headNode מצביע על הצומת הנוכחי ו lastNode הצבעה על הצומת הקודם של הצומת הנוכחי, תוך כדי איטרציה.
- כמו שלנו headNode כעת מצביע על צומת ההתחלה של הלולאה ו-as lastNode הצביע על הצומת שאליו הצביע הראש (כלומר, הוא מתייחס ל lastNode של הלולאה), שלנו headNode כרגע מצביע על צומת ההתחלה של הלולאה.
- הלולאה תישבר על ידי הגדרת l astNode->next == NULL .
על ידי כך, צומת לולאת הסיום במקום להתייחס לצומת הראשוני של הלולאה, מתחיל להצביע על NULL.
מורכבות הזמן והמרחב הממוצעת של שיטת הגיבוב היא O(n). הקורא תמיד צריך להיות מודע לכך שהטמעת ה-Hashing DataStructure המובנית בשפת התכנות תקבע את מורכבות הזמן הכוללת במקרה של התנגשות ב-hashing.
יישום תוכנית C++ עבור השיטה לעיל (HashSet):
#include
שימוש במרחב שמות std;
struct Node {
ערך int;
struct Node * הַבָּא;
} ;
צוֹמֶת * newNode ( ערך int )
{
צוֹמֶת * tempNode = צומת חדש;
tempNode- > ערך = ערך;
tempNode- > next = NULL;
לַחֲזוֹר tempNode;
}
// זהה והסר כל לולאות פוטנציאליות
// ב רשימה מקושרת עם פונקציה זו.
void functionHashMap ( צוֹמֶת * headNode )
{
// יצר מפת unordered_map ליישום מפת Hash
unordered_map < צוֹמֶת * , int > מפת גיבוב;
// מצביע ל-lastNode
צוֹמֶת * lastNode = NULL;
בזמן ( headNode ! = NULL ) {
// אם חסר צומת במפה, הוסף אותו.
אם ( hash_map.find ( headNode ) == hash_map.end ( ) ) {
מפת גיבוב [ headNode ] ++;
lastNode = headNode;
headNode = headNode- > הַבָּא;
}
// אם קיים מחזור, מַעֲרֶכֶת הצומת הסופי המצביע הבא של NULL.
אחר {
lastNode->next = NULL;
לשבור;
}
}
}
// הצג רשימה מקושרת
תצוגה ריקה (Node* headNode)
{
while (headNode != NULL) {
cout << headNode->ערך << ' ';
headNode = headNode->הבא;
}
cout << endl;
}
/* פונקציה ראשית*/
int main()
{
Node* 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);
/* צור לולאה ב-linkedList */
headNode->next->next->next->next->next = headNode->next->next;
functionHashMap(headNode);
printf('רשימה מקושרת ללא לולאה \n');
display(headNode);
החזר 0;
}
תְפוּקָה:
רשימה מקושרת ללא לולאה
48 18 13 2 8
ההסבר שלב אחר שלב של הקוד מסופק להלן:
-
- קובץ הכותרת bits/stdc++.h>, המכיל את כל ספריות C++ הנפוצות, כלול בקוד.
- מבנה שנקרא 'צומת' נבנה, ויש לו שני איברים: הפניה לצומת הבא ברשימה ומספר שלם שנקרא 'ערך'.
- עם ערך מספר שלם כקלט והמצביע 'הבא' מוגדר ל-NULL, הפונקציה 'newNode' יוצרת צומת חדש עם הערך הזה.
- הפונקציה ' functionHashMap' מוגדר, אשר לוקח מצביע לצומת הראש של הרשימה המקושרת כקלט.
- בתוך ה ' functionHashMap ', נוצרת מפה לא-סדרה בשם 'hash_map', המשמשת ליישום מבנה נתוני מפת hash.
- מצביע לצומת האחרון ברשימה מאותחל ל-NULL.
- לולאת while משמשת כדי לעבור את הרשימה המקושרת, שמתחילה מצומת הראש וממשיכה עד שצומת הראש הוא NULL.
- מצביע lastNode מתעדכן לצומת הנוכחי בתוך לולאת while אם הצומת הנוכחי (headNode) אינו קיים כבר במפת הגיבוב.
- אם הצומת הנוכחי נמצא במפה, זה אומר שקיימת לולאה ברשימה המקושרת. כדי להסיר את הלולאה, המצביע הבא של ה- lastNode נקבע ל ריק ולולאת ה-while נשברת.
- צומת הראש של הרשימה המקושרת משמש כקלט לפונקציה הנקראת 'תצוגה', המפיקה את הערך של כל צומת ברשימה מתחילתה ועד סופה.
- בתוך ה רָאשִׁי פונקציה, יצירת לולאה.
- הפונקציה 'functionHashMap' נקראת עם מצביע headNode כקלט, מה שמסיר את הלולאה מהרשימה.
- הרשימה ששונתה מוצגת באמצעות הפונקציה 'תצוגה'.
גישה 2: מחזור פלויד
אלגוריתם זיהוי המחזור של פלויד, הידוע לרוב בשם אלגוריתם הצב והארנבת, מספק את הבסיס לשיטה זו של איתור מחזורים ברשימה מקושרת. המצביע 'האיטי' והמצביע 'המהיר', שחוצים את הרשימה במהירויות שונות, הם שני המצביעים המשמשים בטכניקה זו. המצביע המהיר מתקדם שני שלבים ואילו המצביע האיטי מתקדם צעד אחד בכל איטרציה. מחזור ברשימה המקושרת קיים אם שתי הנקודות יגיעו פעם אל פנים.
1. עם צומת הראש של הרשימה המקושרת, אנו מאתחלים שני מצביעים הנקראים מהיר ואיטי.
2. כעת אנו מפעילים לולאה כדי לעבור ברשימה המקושרת. יש להזיז את המצביע המהיר שני מיקומים לפני המצביע האיטי בכל שלב של איטרציה.
3. לא תהיה לולאה ברשימה המקושרת אם המצביע המהיר יגיע לסוף הרשימה (fastPointer == NULL או fastPointer->next == NULL). אם לא, המצביעים המהירים והאיטיים ייפגשו בסופו של דבר, מה שאומר שלרשימה המקושרת יש לולאה.
יישום תוכנית C++ עבור השיטה שלעיל (מחזור פלויד):
#include
שימוש במרחב שמות std;
/* צומת רשימת קישורים */
struct Node {
int נתונים;
struct Node * הַבָּא;
} ;
/* פונקציה להסרת לולאה. */
void deleteLoop ( struct Node * , struct Node * ) ;
/* זֶה פוּנקצִיָה מאתר ומבטל לולאות רשימה. זה מניב 1
אם הייתה לולאה ב הרשימה; אַחֵר , זה חוזר 0 . */
int detectAndDeleteLoop ( struct Node * רשימה )
{
struct Node * slowPTR = רשימה, * fastPTR = רשימה;
// חזור כדי לבדוק אם הלולאה קיימת.
בזמן ( PTR איטי && fastPTR && fastPTR- > הַבָּא ) {
slowPTR = slowPTR- > הַבָּא;
fastPTR = fastPTR- > הַבָּא- > הַבָּא;
/* אם slowPTR ו-fastPTR נפגשים בשלב מסוים לאחר מכן שם
הוא לולאה */
אם ( slowPTR == fastPTR ) {
deleteLoop ( slowPTR, רשימה ) ;
/* לַחֲזוֹר 1 כדי לציין שהתגלתה לולאה. */
לַחֲזוֹר 1 ;
}
}
/* לַחֲזוֹר 0 כדי לציין שלא התגלתה לולאה. */
לַחֲזוֹר 0 ;
}
/* פונקציה למחיקת לולאה מהרשימה המקושרת.
loopNode מצביע על אחד מצמתי הלולאה ו-headNode מצביע
לצומת ההתחלה של הרשימה המקושרת */
void deleteLoop ( struct Node * loopNode, struct Node * headNode )
{
struct Node * ptr1 = loopNode;
struct Node * ptr2 = loopNode;
// ספור כמה צמתים יש ב הלולאה.
unsigned int k = 1 , אני;
בזמן ( ptr1- > הַבָּא ! = ptr2 ) {
ptr1 = ptr1- > הַבָּא;
k++;
}
// תקן מצביע אחד ל-headNode
ptr1 = headNode;
// והמצביע השני ל-k צמתים אחרי headNode
ptr2 = headNode;
ל ( אני = 0 ; אני < ק; i++ )
ptr2 = ptr2- > הַבָּא;
/* כאשר שתי הנקודות מוזזות בו זמנית,
הם יתנגשו בלולאה צומת ההתחלה של. */
while (ptr2 != ptr1) {
ptr1 = ptr1->הבא;
ptr2 = ptr2->הבא;
}
// השג את הצומת' ס אחרון מַצבִּיעַ.
בזמן ( ptr2- > הַבָּא ! = ptr1 )
ptr2 = ptr2- > הַבָּא;
/* כדי לסגור את הלולאה, מַעֲרֶכֶת הבא
צומת ללולאה הצומת המסיים של. */
ptr2->next = NULL;
}
/* פונקציה להצגת רשימה מקושרת */
void displayLinkedList(צומת struct Node*)
{
// הצג את הרשימה המקושרת לאחר מחיקת הלולאה
while (צומת != NULL) {
cout << node->נתונים << ' ';
node = node->הבא;
}
}
struct Node* newNode(int key)
{
struct Node* temp = new Node();
temp->נתונים = מפתח;
temp->next = NULL;
טמפ' החזרה;
}
// קוד ראשי
int main()
{
struct Node* 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);
/* צור לולאה */
headNode->next->next->next->next->next = headNode->next->next;
// הצג את הלולאה ברשימה מקושרת
//displayLinkedList(headNode);
detectAndDeleteLoop(headNode);
cout << 'רשימה מקושרת לאחר ללא לולאה \n';
displayLinkedList(headNode);
החזר 0;
}
תְפוּקָה:
רשימה מקושרת לאחר ללא לולאה
48 18 13 2 8
הֶסבֵּר:
-
- הכותרות הרלוונטיות, כגון 'bits/stdc++.h' ו-'std::cout', נכללות תחילה.
- לאחר מכן מוכרז מבנה ה'צומת', המייצג צומת ברשימה המקושרת. מצביע הבא שמוביל לצומת הבא ברשימה כלול יחד עם שדה נתונים שלמים בכל צומת.
- לאחר מכן, הוא מגדיר 'deleteLoop' ו-'detectAndDeleteLoop', שתי פונקציות. לולאה מוסרת מרשימה מקושרת בשיטה הראשונה, לולאה מזוהה ברשימה באמצעות הפונקציה השנייה, אשר לאחר מכן קוראת להליך הראשון להסרת הלולאה.
- רשימה מקושרת חדשה עם חמישה צמתים נוצרת בפונקציה הראשית, ולולאה נוצרת על ידי הגדרת המצביע הבא של הצומת האחרון לצומת השלישי.
- לאחר מכן הוא מבצע קריאה לשיטת 'detectAndDeleteLoop' תוך העברת צומת הראש של הרשימה המקושרת כארגומנט. כדי לזהות לולאות, פונקציה זו השתמש בגישת 'מצביעים איטיים ומהירים'. הוא משתמש בשני מצביעים שמתחילים בראש הרשימה, slowPTR ו-fastPTR. בעוד שהמצביע המהיר מזיז שני צמתים בבת אחת, המצביע האיטי מזיז רק צומת אחד בכל פעם. המצביע המהיר בסופו של דבר יעקוף את המצביע האיטי אם הרשימה מכילה לולאה, ושתי הנקודות יתנגשו באותו צומת.
- הפונקציה מפעילה את הפונקציה 'deleteLoop' אם היא מוצאת לולאה, ומספקת את צומת הראש של הרשימה ואת ההצטלבות של המצביעים האיטיים והמהירים כקלט. הליך זה קובע שני מצביעים, ptr1 ו- ptr2, לצומת הראש של הרשימה וסופר את מספר הצמתים בלולאה. לאחר מכן, הוא מקדם מצביע אחד k צמתים, כאשר k הוא המספר הכולל של צמתים בלולאה. לאחר מכן, עד שהם נפגשים בתחילת הלולאה, הוא מקדם את שתי הנקודות צומת אחד בכל פעם. לאחר מכן, הלולאה נשברת על ידי הגדרת המצביע הבא של הצומת בסוף הלולאה ל-NULL.
- לאחר הסרת הלולאה, הוא מציג את הרשימה המקושרת כשלב אחרון.
גישה 3: רקורסיה
רקורסיה היא טכניקה לפתרון בעיות על ידי חלוקה לבעיות משנה קטנות וקלות יותר. ניתן להשתמש ברקורסיה כדי לעבור רשימה מקושרת בודדת במקרה שנמצא לולאה על ידי הפעלת פונקציה מתמשכת עבור הצומת הבא ברשימה עד שמגיעים לסוף הרשימה.
ברשימה מקושרת בודדת, העיקרון הבסיסי מאחורי השימוש ברקורסיה למציאת לולאה הוא להתחיל בראש הרשימה, לסמן את הצומת הנוכחי כמו ביקר בכל שלב, ולאחר מכן להמשיך לצומת הבא על ידי הפעלת הפונקציה עבור הצומת הזה. השיטה תחזור על הרשימה המקושרת המלאה מכיוון שהיא נקראת רקורסיבית.
הרשימה מכילה לולאה אם הפונקציה נתקלת בצומת שסומן בעבר כמבקר; במקרה זה, הפונקציה יכולה להחזיר true. השיטה יכולה להחזיר false אם היא מגיעה לסוף הרשימה מבלי לרוץ על פני צומת ביקר, מה שמצביע על כך שאין לולאה.
למרות שהטכניקה הזו לניצול רקורסיה כדי למצוא לולאה ברשימה מקושרת אחת היא פשוטה לשימוש והבנה, ייתכן שהיא לא היעילה ביותר מבחינת מורכבות זמן ומרחב.
יישום תוכנית C++ עבור השיטה שלעיל (רקורסיה):
#include
שימוש במרחב שמות std;
struct Node {
int נתונים;
צוֹמֶת * הַבָּא;
bool ביקר;
} ;
// זיהוי לולאה של רשימה מקושרת פוּנקצִיָה
bool detectLoopLinkedList ( צוֹמֶת * headNode ) {
אם ( headNode == NULL ) {
לַחֲזוֹר שֶׁקֶר ; // אם הרשימה המקושרת ריקה, הבסיס מקרה
}
// יש לולאה אם לצומת הנוכחי יש
// כבר ביקר.
אם ( headNode- > ביקר ) {
לַחֲזוֹר נָכוֹן ;
}
// הוסף סימן ביקור לצומת הנוכחי.
headNode- > ביקר = נָכוֹן ;
// מתקשר לקוד ל הצומת שלאחר מכן שוב ושוב
לַחֲזוֹר detectLoopLinkedList ( headNode- > הַבָּא ) ;
}
int main ( ) {
צוֹמֶת * headNode = צומת חדש ( ) ;
צוֹמֶת * secondNode = צומת חדש ( ) ;
צוֹמֶת * ThirdNode = צומת חדש ( ) ;
headNode- > נתונים = 1 ;
headNode- > next = secondNode;
headNode- > ביקר = שֶׁקֶר ;
secondNode- > נתונים = 2 ;
secondNode- > next = thirdNode;
secondNode- > ביקר = שֶׁקֶר ;
צומת שלישי- > נתונים = 3 ;
צומת שלישי- > next = NULL; // אין לולאה
צומת שלישי- > ביקר = שֶׁקֶר ;
אם ( detectLoopLinkedList ( headNode ) ) {
cout << 'זוהתה לולאה ברשימה מקושרת' << endl;
} אַחֵר {
cout << 'לא זוהתה לולאה ברשימה המקושרת' << endl;
}
// יצירת לולאה
צומת שלישי- > next = secondNode;
אם ( detectLoopLinkedList ( headNode ) ) {
cout << 'זוהתה לולאה ברשימה מקושרת' << endl;
} אַחֵר {
cout << 'לא זוהתה לולאה ברשימה המקושרת' << endl;
}
לַחֲזוֹר 0 ;
}
תְפוּקָה:
לא זוהתה לולאה ב רשימה מקושרת
זוהתה לולאה ב רשימה מקושרת
הֶסבֵּר:
-
- הפונקציה detectLoopLinkedList() בתוכנית זו מקבל את ראש הרשימה המקושרת כקלט.
- הרקורסיה משמשת את הפונקציה כדי לחזור על הרשימה המקושרת. כמקרה הבסיסי לרקורסיה, זה מתחיל בקביעה אם הצומת הנוכחי הוא NULL. אם כן, השיטה מחזירה false, מה שמציין שלא קיימת לולאה.
- לאחר מכן נבדק הערך של מאפיין ה'ביקור' של הצומת הנוכחי כדי לראות אם ביקר בו בעבר. זה מחזיר נכון אם ביקר בו, מה שמצביע על כך שנמצאה לולאה.
- הפונקציה מסמנת את הצומת הנוכחי כמו ביקר אם כבר ביקר בו על ידי שינוי המאפיין 'ביקר' שלו ל-true.
- הערך של המשתנה שביקר נבדק לאחר מכן כדי לראות אם הצומת הנוכחי ביקר בעבר. אם נעשה בו שימוש בעבר, חייבת להתקיים לולאה, והפונקציה מחזירה true.
- לבסוף, הפונקציה קוראת לעצמה עם הצומת הבא ברשימה על ידי מעבר headNode->הבא בתור טיעון. באופן רקורסיבי , פעולה זו מתבצעת עד שנמצאת לולאה או עד שכל הצמתים ביקרו. פירוש הדבר, הפונקציה מגדירה את המשתנה ביקר ל-true אם הצומת הנוכחי מעולם לא ביקר לפני שהוא קורא לעצמו באופן רקורסיבי עבור הצומת הבא ברשימה המקושרת.
- הקוד בונה שלושה צמתים ומצטרף אליהם כדי לייצר רשימה מקושרת ב- פונקציה עיקרית . השיטה detectLoopLinkedList() לאחר מכן מופעל בצומת הראש של הרשימה. התוכנית מפיקה ' לולאה מנוכה ברשימה מקושרת ' אם detectLoopLinkedList() מחזיר אמת; אחרת, זה מוציא ' לא זוהתה לולאה ברשימה המקושרת '.
- לאחר מכן, הקוד מכניס לולאה לרשימה המקושרת על ידי הגדרת המצביע הבא של הצומת האחרון לצומת השני. לאחר מכן, בהתאם לתוצאה של הפונקציה, היא פועלת detectLoopLinkedList() שוב ומייצר או ' לולאה מנוכה ברשימה מקושרת ' או ' לא זוהתה לולאה ברשימה המקושרת .'
גישה 4: שימוש ב-Stack
ניתן למצוא לולאות ברשימה מקושרת באמצעות מחסנית ושיטת 'חיפוש עומק ראשון' (DFS). הרעיון הבסיסי הוא לחזור על הרשימה המקושרת, לדחוף כל צומת לערימה אם עדיין לא ביקר בו. לולאה מזוהה אם נתקלים שוב בצומת שכבר נמצא בערימה.
להלן תיאור קצר של ההליך:
-
- צור מחסנית ריקה ומשתנה כדי להקליט את הצמתים שביקרו בהם.
- דחוף את הרשימה המקושרת אל הערימה, החל מלמעלה. רשום שהראש עבר ביקור.
- דחוף את הצומת הבא ברשימה אל הערימה. הוסף סימן ביקור לצומת זה.
- בזמן שאתה חוצה את הרשימה, דחוף כל צומת חדש אל הערימה כדי לציין שביקר בו.
- בדוק אם צומת שביקר בו בעבר נמצא בראש הערימה אם נתקלים בו. אם כן, נמצאה לולאה, והלולאה מזוהה על ידי הצמתים בערימה.
- הוציאו את הצמתים מהערימה והמשיכו לחצות את הרשימה אם לא נמצא לולאה.
יישום תוכנית C++ עבור השיטה לעיל (Stack)
#include
#include <מחסנית>
שימוש במרחב שמות std;
struct Node {
int נתונים;
צוֹמֶת * הַבָּא;
} ;
// פונקציה לזיהוי לולאה ב רשימה מקושרת
bool detectLoopLinkedList ( צוֹמֶת * headNode ) {
לַעֲרוֹם < צוֹמֶת *> לַעֲרוֹם;
צוֹמֶת * tempNode = headNode;
בזמן ( tempNode ! = NULL ) {
// אם הרכיב העליון של הערימה תואם
// הצומת הנוכחי והמחסנית אינם ריקים
אם ( ! מחסנית.ריק ( ) && stack.top ( ) == tempNode ) {
לַחֲזוֹר נָכוֹן ;
}
מחסנית.דחיפה ( tempNode ) ;
tempNode = tempNode- > הַבָּא;
}
לַחֲזוֹר שֶׁקֶר ;
}
int main ( ) {
צוֹמֶת * headNode = צומת חדש ( ) ;
צוֹמֶת * secondNode = צומת חדש ( ) ;
צוֹמֶת * ThirdNode = צומת חדש ( ) ;
headNode- > נתונים = 1 ;
headNode- > next = secondNode;
secondNode- > נתונים = 2 ;
secondNode- > next = thirdNode;
צומת שלישי- > נתונים = 3 ;
צומת שלישי- > next = NULL; // אין לולאה
אם ( detectLoopLinkedList ( headNode ) ) {
cout << 'זוהתה לולאה ברשימה מקושרת' << endl;
} אַחֵר {
cout << 'לא זוהתה לולאה ברשימה המקושרת' << endl;
}
// יצירת לולאה
צומת שלישי- > next = secondNode;
אם ( detectLoopLinkedList ( headNode ) ) {
cout << 'זוהתה לולאה ברשימה מקושרת' << endl;
} אַחֵר {
cout << 'לא זוהתה לולאה ברשימה המקושרת' << endl;
}
תְפוּקָה:
לא זוהתה לולאה ב רשימה מקושרת
זוהתה לולאה ב רשימה מקושרת
הֶסבֵּר:
תוכנית זו משתמשת במחסנית כדי לגלות אם לרשימה עם קישור יחיד יש לולאה.
- 1. ספריית זרם הקלט/פלט וספריית המחסנית נמצאים שניהם בשורה הראשונה.
2. מרחב השמות הסטנדרטי כלול בשורה השנייה, מה שמאפשר לנו לגשת לפונקציות של ספריית זרם הקלט/פלט מבלי שנצטרך להקדים אותן עם 'std::.'
3. השורה הבאה מגדירה את ה-struct Node, המורכב משני איברים: מספר שלם הנקרא 'נתונים' ומצביע לצומת אחר בשם 'הבא'.
4. ראש הרשימה המקושרת הוא קלט עבור השיטה detectLoopLinkedList(), המוגדרת בשורה הבאה. הפונקציה מייצרת ערך בוליאני המציין אם נמצאה לולאה או לא.
5. ערימה של מצביעי Node הנקראת 'stack' ומצביע ל-Node בשם 'tempNode' שמאוחל עם הערך של headNode, שניהם נוצרים בתוך הפונקציה.
6. לאחר מכן, כל עוד tempNode אינו מצביע null, אנו נכנסים ללולאת while.
(א) האלמנט העליון של המחסנית חייב להתאים לצומת הנוכחי כדי שנוכל לקבוע שהוא לא ריק. נחזיר אמת אם זה המקרה כי נמצאה לולאה.
(ב) אם התנאי האמור לעיל הוא שקרי, מצביע הצומת הנוכחי נדחף אל המחסנית, ו-tempNode מוגדר לצומת הבא ברשימה המקושרת.
7. נחזיר false לאחר לולאת ה-while כי לא נצפתה לולאה.
8. אנו בונים שלושה אובייקטי Node ומאתחלים אותם בפונקציה main() . מכיוון שאין לולאה בדוגמה הראשונה, אנו מגדירים את המצביעים 'הבאים' של כל צומת כראוי.
סיכום:
לסיכום, השיטה הטובה ביותר לזיהוי לולאות ברשימה מקושרת תלויה במקרה השימוש הספציפי ובאילוצים של הבעיה. Hash Table ואלגוריתם מציאת המחזור של פלויד הן שיטות יעילות והן נמצאות בשימוש נרחב בפועל. סטאק ורקורסיה הן שיטות פחות יעילות אבל הן אינטואיטיביות יותר.