Откриване на цикъл в свързан списък в C++

Крайният възел на свързан списък, който има цикъл, ще препраща към друг възел в същия списък, а не към NULL. Ако има възел в свързан списък, който може да бъде многократно достъпен чрез следване на следващия указател, се казва, че списъкът има цикъл.

Обикновено последният възел на свързания списък се отнася до NULL препратка, за да обозначи заключението на списъка. Въпреки това, в свързан списък с цикъл, крайният възел на списъка се отнася до начален възел, вътрешен възел или самия него. Следователно при такива обстоятелства трябва да идентифицираме и прекратим цикъла, като зададем препратката на следващия възел към NULL. Частта за откриване на цикъла в свързан списък е обяснена в тази статия.

В C++ има много начини за намиране на цикли в свързан списък:

Подход, базиран на хеш таблица : Този подход съхранява адресите на посетените възли в хеш таблица. Съществува цикъл в свързания списък, ако даден възел вече присъства в хеш-таблицата, когато бъде посетен отново.

Подходът на цикъла на Флойд : Алгоритъмът „костенурка и заек“, известен като алгоритъм за намиране на цикъл на Флойд: Тази техника използва два указателя, единият се движи по-бавно от другия, а другият се движи по-бързо. По-бързият указател в крайна сметка ще изпревари по-бавния указател, ако има цикъл в свързания списък, разкривайки съществуването на цикъла.

Рекурсивен метод : Този метод преминава през свързания списък, като се извиква отново и отново. Свързаният списък съдържа цикъл, ако текущият възел е бил посетен преди това.

Подход, базиран на стека : Този подход съхранява адресите на посетените възли в стек. Налице е цикъл в свързания списък, ако възел вече е там в стека, когато бъде посетен отново.

Нека обясним подробно всеки подход, за да разберем концепцията.

Подход 1: Подход на HashSet

Използването на хеширане е най-простият метод. Тук преминаваме през списъка един по един, като запазваме хеш таблица с адресите на възлите. Следователно съществува цикъл, ако някога преминем към следващия адрес на текущия възел, който вече се съдържа в хеш-таблицата. В противен случай няма цикъл в свързания списък, ако се сблъскаме с NULL (т.е. стигнем до края на свързания списък).

Ще бъде доста лесно да приложите тази стратегия.

Докато обикаляме свързания списък, ще използваме unordered_hashmap и ще продължим да добавяме възли към него.

Сега, след като попаднем на възел, който вече е показан на картата, ще знаем, че сме пристигнали в началото на цикъла.

• • Освен това запазихме два указателя на всяка стъпка, главен възел сочещи към текущия възел и lastNode сочещи към предишния възел на текущия възел, докато итерирате.
  • Като нашите главен възел сега сочи към началния възел на цикъла и as lastNode сочеше към възела, към който сочеше главата (т.е. отнася се до lastNode на цикъла), нашият главен възел в момента сочи към началния възел на цикъла.
  • Цикълът ще бъде прекъснат чрез настройка на l astNode->следващ == NULL .

Правейки това, крайният възел на цикъла, вместо да препраща към началния възел на цикъла, започва да сочи към NULL.

Средната времева и пространствена сложност на хеширащия метод е O(n). Читателят винаги трябва да е наясно, че внедряването на вградената Hashing DataStructure в езика за програмиране ще определи общата времева сложност в случай на сблъсък в хеширането.

Реализация на C++ програма за горния метод (HashSet):

Изход:

Обяснението стъпка по стъпка на кода е дадено по-долу:

1. 1. Заглавният файл bits/stdc++.h>, който съдържа всички често срещани C++ библиотеки, е включен в кода.
   2. Конструира се структура, наречена „Възел“, и има два члена: препратка към следващия възел в списъка и цяло число, наречено „стойност“.
   3. С целочислена стойност като вход и указател „следващ“, зададен на NULL, функцията „newNode“ създава нов възел с тази стойност.
   4. Функцията ' functionHashMap' е дефиниран, който приема указател към главния възел на свързания списък като вход.
   5. Вътре в функцияHashMap ‘ се създава unordered_map с име ‘hash_map’, който се използва за внедряване на структура от данни за хеш карта.
   6. Указател към последния възел на списъка се инициализира на NULL.
   7. Използва се цикъл while за преминаване през свързания списък, който започва от главния възел и продължава, докато главният възел стане NULL.
   8. Указателят lastNode се актуализира до текущия възел вътре в цикъла while, ако текущият възел (headNode) вече не присъства в хеш картата.
   9. Ако текущият възел е намерен в картата, това означава, че има цикъл в свързания списък. За да премахнете цикъла, следващият указател на lastNode е настроен на НУЛА и цикълът while е прекъснат.
   10. Главният възел на свързания списък се използва като вход за функция, наречена „дисплей“, която извежда стойността на всеки възел в списъка от началото до края.
   11. В основен функция, създавайки цикъл.
   12. Функцията „functionHashMap“ се извиква с указателя headNode като вход, което премахва цикъла от списъка.
   13. Модифицираният списък се показва с помощта на функцията „дисплей“.

Подход 2: Цикълът на Флойд

Алгоритъмът за откриване на цикли на Флойд, често известен като алгоритъм на костенурката и заека, осигурява основата за този метод за локализиране на цикли в свързан списък. „Бавният“ указател и „бързият“ указател, които обикалят списъка с различни скорости, са двата указателя, използвани в тази техника. Бързият показалец напредва с две стъпки, докато бавният показалец напредва с една стъпка на всяка итерация. Цикъл в свързания списък съществува, ако двете точки някога се срещнат лице в лице.

1. С главния възел на свързания списък инициализираме два указателя, наречени бърз и бавен.

2. Сега изпълняваме цикъл, за да преминем през свързания списък. Бързият показалец трябва да бъде преместен на две места пред бавния показалец на всяка стъпка на итерация.

3. Няма да има цикъл в свързания списък, ако бързият показалец достигне края на списъка (fastPointer == NULL или fastPointer->next == NULL). Ако не, бързият и бавният указател в крайна сметка ще се срещнат, което означава, че свързаният списък има цикъл.

Реализация на C++ програма за горния метод (цикъл на Floyd):

Изход:

Обяснение:

1. 1. Съответните заглавки, като „bits/stdc++.h“ и „std::cout“, първо се включват.
   2. След това се декларира структурата „Node“, която означава възел в свързания списък. Следващ указател, който води до следващия възел в списъка, е включен заедно с поле за целочислени данни във всеки възел.
   3. След това дефинира „deleteLoop“ и „detectAndDeleteLoop“, две функции. Цикъл се премахва от свързан списък с помощта на първия метод и цикъл се открива в списъка с помощта на втората функция, която след това извиква първата процедура за премахване на цикъла.
   4. Нов свързан списък с пет възела се създава в основната функция и се установява цикъл чрез задаване на следващия указател на последния възел към третия възел.
   5. След това прави извикване на метода „detectAndDeleteLoop“, като същевременно предава главния възел на свързания списък като аргумент. За идентифициране на цикли тази функция използва подхода „Бавни и бързи указатели“. Той използва два указателя, които започват в горната част на списъка, slowPTR и fastPTR. Докато бързият показалец премества два възела наведнъж, бавният показалец премества само един възел наведнъж. Бързият указател в крайна сметка ще изпревари бавния указател, ако списъкът съдържа цикъл и двете точки ще се сблъскат в един и същи възел.
   6. Функцията извиква функцията „deleteLoop“, ако намери цикъл, предоставяйки главния възел на списъка и пресечната точка на бавния и бързия указател като входове. Тази процедура установява два указателя, ptr1 и ptr2, към главния възел на списъка и брои броя на възлите в цикъла. След това той придвижва напред един указател k възли, където k е общият брой възли в цикъла. След това, докато се срещнат в началото на цикъла, той придвижва напред двете точки един възел наведнъж. След това цикълът се прекъсва чрез задаване на следващия указател на възела в края на цикъла на NULL.
   7. След премахване на цикъла, той показва свързания списък като последна стъпка.

Подход 3: Рекурсия

Рекурсията е техника за решаване на проблеми чрез разделянето им на по-малки, по-лесни подпроблеми. Рекурсията може да се използва за преминаване на единично свързан списък в случай, че бъде открит цикъл чрез непрекъснато изпълнение на функция за следващия възел в списъка, докато се достигне краят на списъка.

В единично свързан списък основният принцип зад използването на рекурсия за намиране на цикъл е да започнете от началото на списъка, да маркирате текущия възел като посетен на всяка стъпка и след това да преминете към следващия възел чрез рекурсивно извикване на функцията за този възел. Методът ще обхожда пълния свързан списък, защото се извиква рекурсивно.

Списъкът съдържа цикъл, ако функцията срещне възел, който преди това е бил маркиран като посетен; в този случай функцията може да върне true. Методът може да върне false, ако достигне края на списъка, без да премине през посетен възел, което показва, че няма цикъл.

Въпреки че тази техника за използване на рекурсия за намиране на цикъл в единичен свързан списък е лесна за използване и разбиране, тя може да не е най-ефективната от гледна точка на времева и пространствена сложност.

Реализация на C++ програма за горния метод (рекурсия):

Изход:

Обяснение:

1. 1. Функцията detectLoopLinkedList() в тази програма приема главата на свързания списък като вход.
   2. Рекурсията се използва от функцията за итерация в свързания списък. Като основен случай за рекурсията, тя започва с определяне дали текущият възел е NULL. Ако е така, методът връща false, което показва, че не съществува цикъл.
   3. Стойността на свойството „посетен“ на текущия възел след това се проверява, за да се види дали е бил посещаван преди това. Той връща true, ако е бил посетен, което предполага, че е намерен цикъл.
   4. Функцията маркира текущия възел като посетен, ако вече е бил посетен, като промени свойството си „посетен“ на true.
   5. След това стойността на посетената променлива се проверява, за да се види дали текущият възел е бил посетен преди това. Ако е бил използван преди, трябва да съществува цикъл и функцията връща true.
   6. И накрая, функцията се извиква със следващия възел в списъка чрез преминаване headNode->следващ като аргумент. Рекурсивно , това се извършва до намирането на цикъл или докато не бъдат посетени всички възли. Означава, че функцията задава посетената променлива на true, ако текущият възел никога не е бил посещаван, преди рекурсивно да се извика за следващия възел в свързания списък.
   7. Кодът изгражда три възела и ги свързва, за да създаде свързан списък в Главна функция . Методът detectLoopLinkedList() след това се извиква в главния възел на списъка. Програмата произвежда „ Цикълът е приспаднат в свързания списък ” ако detectLoopLinkedList() връща true; в противен случай извежда „ Не е открит цикъл в свързания списък “.
   8. След това кодът вмъква цикъл в свързания списък, като задава следващия указател на последния възел към втория възел. След това, в зависимост от резултата от функцията, тя се изпълнява detectLoopLinkedList() отново и произвежда или „ Цикълът е приспаднат в свързания списък ' или ' Не е открит цикъл в свързания списък .”

Подход 4: Използване на стек

Циклите в свързан списък могат да бъдат намерени с помощта на стек и метода „търсене първо в дълбочина“ (DFS). Основната концепция е да преминете през свързания списък, като избутате всеки възел в стека, ако вече не е бил посетен. Цикълът се разпознава, ако възел, който вече е в стека, се срещне отново.

Ето кратко описание на процедурата:

1. 1. Създайте празен стек и променлива за запис на посетените възли.
   2. Избутайте свързания списък върху стека, като започнете от върха. Отбележете, че главата е посетена.
   3. Натиснете следващия възел в списъка върху стека. Добавете знак за посещение към този възел.
   4. Докато обикаляте списъка, избутвайте всеки нов възел в стека, за да посочите, че е бил посетен.
   5. Проверете дали възел, който е бил посетен преди това, е в горната част на стека, ако бъде открит. Ако е така, е намерен цикъл и цикълът се идентифицира от възлите в стека.
   6. Извадете възлите от стека и продължете да обхождате списъка, ако не бъде открит цикъл.

Реализация на C++ програма за горния метод (Стек)

Изход:

Обяснение:

Тази програма използва стек, за да разбере дали единично свързан списък има цикъл.

• 1. Библиотеката на входно/изходния поток и библиотеката на стека присъстват в първия ред.

  2. Стандартното пространство от имена е включено във втория ред, което ни позволява достъп до функциите на библиотеката на входно/изходния поток, без да се налага да ги поставяме като префикс с „std::“.

  3. Следният ред дефинира структурния възел, който се състои от два члена: цяло число, наречено „данни“, и указател към друг възел, наречен „следващ“.

  4. Главата на свързания списък е вход за метода detectLoopLinkedList(), който е дефиниран на следващия ред. Функцията генерира булева стойност, която показва дали е намерен цикъл или не.

  5. Стек от указатели на възел, наречен „stack“, и указател към възел, наречен „tempNode“, който се инициализира със стойността на headNode, се създават във функцията.

  6. След това, докато tempNode не е нулев указател, влизаме в цикъл while.

  (a) Горният елемент на стека трябва да съответства на текущия възел, за да можем да определим, че не е празен. Връщаме true, ако това е така, защото е открит цикъл.

  (b) Ако гореспоменатото условие е невярно, указателят на текущия възел се избутва в стека и tempNode се задава на следващия възел в свързания списък.

  7. Връщаме false след цикъла while, защото не е наблюдаван цикъл.

  8. Създаваме три обекта Node и ги инициализираме във функцията main(). Тъй като в първия пример няма цикъл, ние задаваме правилно указателите „следващ“ на всеки възел.

Заключение:

В заключение, най-добрият метод за откриване на цикли в свързан списък зависи от конкретния случай на употреба и ограниченията на проблема. Хеш таблицата и алгоритъмът на Floyd за намиране на цикъл са ефективни методи и се използват широко в практиката. Стекът и рекурсията са по-малко ефективни методи, но са по-интуитивни.