Wykryj pętlę na połączonej liście w C++

Węzeł końcowy połączonej listy, który ma pętlę, będzie odwoływał się do innego węzła na tej samej liście, a nie do NULL. mieć cykl.

Zazwyczaj ostatni węzeł listy połączonej odnosi się do odwołania NULL, aby wskazać zakończenie listy. Jednak w liście połączonej z pętlą węzeł końcowy listy odnosi się do węzła początkowego, węzła wewnętrznego lub samego siebie. Dlatego w takich okolicznościach musimy zidentyfikować i zakończyć pętlę, ustawiając odwołanie do następnego węzła na NULL. Część wykrywania pętli na połączonej liście została wyjaśniona w tym artykule.

W C++ istnieje wiele sposobów znajdowania pętli na połączonej liście:

Podejście oparte na tabeli skrótów : To podejście przechowuje adresy odwiedzanych węzłów w tablicy skrótów. Pętla na połączonej liście istnieje, jeśli węzeł jest już obecny w tablicy skrótów, gdy jest ponownie odwiedzany.

Podejście oparte na cyklu Floyda : Algorytm „żółwia i zająca”, powszechnie znany jako algorytm znajdowania cykli Floyda: Ta technika wykorzystuje dwa wskaźniki, jeden porusza się wolniej niż drugi, a drugi porusza się szybciej. Szybszy wskaźnik ostatecznie wyprzedzi wolniejszy wskaźnik, jeśli na połączonej liście znajduje się pętla, ujawniając istnienie pętli.

Metoda rekurencyjna : Ta metoda przechodzi przez połączoną listę, wywołując siebie w kółko. Połączona lista zawiera pętlę, jeśli bieżący węzeł został wcześniej odwiedzony.

Podejście oparte na stosie : To podejście przechowuje adresy odwiedzanych węzłów w stosie. Pętla na połączonej liście jest obecna, jeśli węzeł jest już na stosie, gdy jest ponownie odwiedzany.

Wyjaśnijmy szczegółowo każde podejście, aby zrozumieć koncepcję.

Podejście 1: Podejście HashSet

Wykorzystanie haszowania jest najprostszą metodą. Tutaj przeglądamy listę jeden po drugim, zachowując tablicę mieszającą z adresami węzłów. Dlatego istnieje pętla, jeśli kiedykolwiek przejdziemy przez następny adres bieżącego węzła, który jest już zawarty w tablicy skrótów. W przeciwnym razie nie ma pętli na liście połączonej, jeśli napotkamy NULL (tj. dojdziemy do końca listy połączonej).

Wdrożenie tej strategii będzie dość łatwe.

Podczas przeglądania połączonej listy użyjemy unordered_hashmap i będziemy dodawać do niej węzły.

Teraz, gdy natkniemy się na węzeł, który jest już pokazany na mapie, będziemy wiedzieć, że dotarliśmy do początku pętli.

• • Ponadto trzymaliśmy dwa wskaźniki na każdym kroku, węzeł główny wskazując na bieżący węzeł i ostatniwęzeł wskazując na poprzedni węzeł bieżącego węzła podczas iteracji.
  • Jak nasz węzeł główny wskazuje teraz na węzeł początkowy pętli i as ostatniwęzeł wskazywał na węzeł, na który wskazywała głowa (tj ostatniwęzeł pętli), nasz węzeł główny aktualnie wskazuje na początkowy węzeł pętli.
  • Pętla zostanie przerwana przez ustawienie l astNode->następny == NULL .

W ten sposób końcowy węzeł pętli zamiast odnosić się do początkowego węzła pętli, zaczyna wskazywać na NULL.

Średnia złożoność czasowa i przestrzenna metody haszującej wynosi O(n). Czytelnik powinien zawsze mieć świadomość, że implementacja wbudowanej struktury Hashing DataStructure w języku programowania określi całkowitą złożoność czasową w przypadku kolizji w haszowaniu.

Implementacja programu C++ dla powyższej metody (HashSet):

Wyjście:

Wyjaśnienie kodu krok po kroku znajduje się poniżej:

1. 1. Kod zawiera plik nagłówkowy bits/stdc++.h>, który zawiera wszystkie popularne biblioteki C++.
   2. Tworzona jest struktura o nazwie „Węzeł”, która ma dwa elementy: odniesienie do następnego węzła na liście i liczbę całkowitą o nazwie „wartość”.
   3. Z wartością całkowitą jako wejściem i wskaźnikiem „next” ustawionym na NULL, funkcja „newNode” tworzy nowy węzeł z tą wartością.
   4. Funkcja ' funkcjaHashMap’ jest zdefiniowana, która przyjmuje jako dane wejściowe wskaźnik do węzła głównego połączonej listy.
   5. W środku ' funkcjaHashMap ‘, tworzona jest unordered_map o nazwie „hash_map”, która służy do implementacji struktury danych mapy hash.
   6. Wskaźnik do ostatniego węzła listy jest inicjowany na NULL.
   7. Pętla while służy do przechodzenia przez połączoną listę, która zaczyna się od węzła głównego i trwa do momentu, gdy węzeł główny będzie miał wartość NULL.
   8. Wskaźnik lastNode jest aktualizowany do bieżącego węzła wewnątrz pętli while, jeśli bieżący węzeł (headNode) nie jest już obecny na mapie skrótów.
   9. Jeśli bieżący węzeł znajduje się na mapie, oznacza to, że na połączonej liście znajduje się pętla. Aby usunąć pętlę, następny wskaźnik pliku ostatniwęzeł jest ustawione na ZERO a pętla while jest zepsuta.
   10. Węzeł główny połączonej listy jest używany jako dane wejściowe dla funkcji zwanej „display”, która wyświetla wartość każdego węzła na liście od początku do końca.
   11. w główny funkcję, tworząc pętlę.
   12. Funkcja „functionHashMap” jest wywoływana ze wskaźnikiem headNode jako wejściem, który usuwa pętlę z listy.
   13. Zmodyfikowana lista jest wyświetlana za pomocą funkcji „wyświetl”.

Podejście 2: Cykl Floyda

Algorytm wykrywania cykli Floyda, często znany jako algorytm żółwia i zająca, stanowi podstawę tej metody lokalizowania cykli na połączonej liście. Wskaźnik „wolny” i wskaźnik „szybki”, które poruszają się po liście z różnymi prędkościami, to dwa wskaźniki używane w tej technice. Szybki wskaźnik przesuwa się o dwa kroki, podczas gdy wolny wskaźnik przesuwa się o jeden krok w każdej iteracji. Cykl na połączonej liście istnieje, jeśli dwa punkty kiedykolwiek spotkają się twarzą w twarz.

1. W węźle głównym połączonej listy inicjalizujemy dwa wskaźniki zwane szybkim i wolnym.

2. Teraz uruchamiamy pętlę, aby poruszać się po połączonej liście. Szybki wskaźnik powinien zostać przesunięty o dwa miejsca przed wolnym wskaźnikiem w każdym kroku iteracji.

3. W połączonej liście nie będzie pętli, jeśli szybki wskaźnik dotrze do końca listy (fastPointer == NULL lub fastPointer->next == NULL). Jeśli nie, szybkie i wolne wskaźniki w końcu się spotkają, co oznacza, że ​​połączona lista ma pętlę.

Implementacja programu w C++ dla powyższej metody (cykl Floyda):

Wyjście:

Wyjaśnienie:

1. 1. Najpierw uwzględniane są odpowiednie nagłówki, takie jak „bits/stdc++.h” i „std::cout”.
   2. Następnie deklarowana jest struktura „Node”, która oznacza węzeł na połączonej liście. Następny wskaźnik, który prowadzi do następnego węzła na liście, jest dołączany wraz z polem danych całkowitych w każdym węźle.
   3. Następnie definiuje „deleteLoop” i „detectAndDeleteLoop”, dwie funkcje. Pętla jest usuwana z połączonej listy za pomocą pierwszej metody, a pętla jest wykrywana na liście za pomocą drugiej funkcji, która następnie wywołuje pierwszą procedurę w celu usunięcia pętli.
   4. W funkcji main tworzona jest nowa połączona lista z pięcioma węzłami, a pętla jest tworzona przez ustawienie następnego wskaźnika ostatniego węzła na trzeci węzeł.
   5. Następnie wywołuje metodę „detectAndDeleteLoop”, przekazując jako argument węzeł główny połączonej listy. Aby zidentyfikować pętle, ta funkcja wykorzystuje podejście „wolnych i szybkich wskaźników”. Wykorzystuje dwa wskaźniki, które zaczynają się na górze listy, slowPTR i fastPTR. Podczas gdy szybki wskaźnik przesuwa dwa węzły jednocześnie, wolny wskaźnik przesuwa tylko jeden węzeł na raz. Szybki wskaźnik ostatecznie wyprzedzi wolny wskaźnik, jeśli lista zawiera pętlę, a dwa punkty zderzą się w tym samym węźle.
   6. Funkcja wywołuje funkcję „deleteLoop”, jeśli znajdzie pętlę, podając jako dane wejściowe węzeł główny listy oraz przecięcie wolnych i szybkich wskaźników. Ta procedura ustanawia dwa wskaźniki, ptr1 i ptr2, do węzła głównego listy i zlicza liczbę węzłów w pętli. Następnie przesuwa jeden wskaźnik o k węzłów, gdzie k to całkowita liczba węzłów w pętli. Następnie, dopóki nie spotkają się na początku pętli, przesuwa oba punkty o jeden węzeł na raz. Pętla jest następnie przerywana przez ustawienie następnego wskaźnika węzła na końcu pętli na NULL.
   7. Po usunięciu pętli wyświetla połączoną listę jako ostatni krok.

Podejście 3: Rekurencja

Rekurencja to technika rozwiązywania problemów poprzez dzielenie ich na mniejsze, łatwiejsze podproblemy. Rekurencji można użyć do przechodzenia przez pojedynczo połączoną listę w przypadku znalezienia pętli przez ciągłe uruchamianie funkcji dla następnego węzła na liście, aż do osiągnięcia końca listy.

W przypadku listy pojedynczo połączonej podstawową zasadą używania rekurencji do znajdowania pętli jest rozpoczynanie od początku listy, oznaczanie bieżącego węzła jako odwiedzanego w każdym kroku, a następnie przechodzenie do następnego węzła poprzez rekurencyjne wywołanie funkcji for ten węzeł. Metoda będzie iterować po pełnej połączonej liście, ponieważ jest wywoływana rekurencyjnie.

Lista zawiera pętlę, jeśli funkcja napotka węzeł, który został wcześniej oznaczony jako odwiedzony; w takim przypadku funkcja może zwrócić wartość true. Metoda może zwrócić wartość false, jeśli dojdzie do końca listy bez przechodzenia przez odwiedzany węzeł, co oznacza, że ​​nie ma pętli.

Chociaż ta technika wykorzystania rekurencji w celu znalezienia pętli na pojedynczej połączonej liście jest prosta w użyciu i zrozumiała, może nie być najbardziej efektywna pod względem złożoności czasowej i przestrzennej.

Implementacja programu C++ dla powyższej metody (Rekursja):

Wyjście:

Wyjaśnienie:

1. 1. Funkcja wykryjLoopLinkedList() w tym programie akceptuje nagłówek połączonej listy jako dane wejściowe.
   2. Rekurencja jest używana przez funkcję do iteracji po połączonej liście. Podstawowy przypadek rekurencji rozpoczyna się od ustalenia, czy bieżący węzeł ma wartość NULL. Jeśli tak, metoda zwraca wartość false, wskazując, że nie istnieje żadna pętla.
   3. Następnie sprawdzana jest wartość właściwości „odwiedzony” bieżącego węzła, aby zobaczyć, czy był on wcześniej odwiedzany. Zwraca true, jeśli został odwiedzony, co sugeruje, że znaleziono pętlę.
   4. Funkcja oznacza bieżący węzeł jako odwiedzony, jeśli został już odwiedzony, zmieniając jego właściwość „visited” na true.
   5. Następnie sprawdzana jest wartość odwiedzanej zmiennej, aby zobaczyć, czy bieżący węzeł był już wcześniej odwiedzany. Jeśli była używana wcześniej, musi istnieć pętla, a funkcja zwraca wartość true.
   6. Na koniec funkcja wywołuje się z następnym węzłem na liście, przekazując headNode->następny jako argument. Rekurencyjnie , odbywa się to do momentu znalezienia pętli lub odwiedzenia wszystkich węzłów. Oznacza to, że funkcja ustawia odwiedzaną zmienną na true, jeśli bieżący węzeł nigdy nie był odwiedzany przed rekurencyjnym wywołaniem siebie dla następnego węzła na połączonej liście.
   7. Kod buduje trzy węzły i łączy je, aby utworzyć połączoną listę w główna funkcja . Metoda wykryjLoopLinkedList() jest następnie wywoływana w węźle głównym listy. Program produkuje „ Pętla odjęta na połączonej liście ' Jeśli wykryjLoopLinkedList() zwraca prawdę; w przeciwnym razie wyświetla „ Nie wykryto pętli na połączonej liście „.
   8. Następnie kod wstawia pętlę do połączonej listy, ustawiając następny wskaźnik ostatniego węzła na drugi węzeł. Następnie, w zależności od wyniku funkcji, jest ona uruchamiana wykryjLoopLinkedList() ponownie i produkuje albo „ Pętla odjęta na połączonej liście ' Lub ' Nie wykryto pętli na połączonej liście ”.

Podejście 4: Używanie stosu

Pętle na połączonej liście można znaleźć za pomocą stosu i metody „przeszukiwania w głąb” (DFS). Podstawową koncepcją jest iteracja przez połączoną listę, umieszczając każdy węzeł na stosie, jeśli nie został jeszcze odwiedzony. Pętla jest rozpoznawana, jeśli węzeł, który już znajduje się na stosie, zostanie ponownie napotkany.

Oto krótki opis procedury:

1. 1. Utwórz pusty stos i zmienną, aby rejestrować odwiedzone węzły.
   2. Umieść połączoną listę na stosie, zaczynając od góry. Zanotuj, że głowa została odwiedzona.
   3. Wepchnij następny węzeł z listy na stos. Dodaj znak odwiedzin do tego węzła.
   4. Podczas przeglądania listy umieszczaj każdy nowy węzeł na stosie, aby wskazać, że został odwiedzony.
   5. Sprawdź, czy węzeł, który został wcześniej odwiedzony, znajduje się na szczycie stosu, jeśli został napotkany. Jeśli tak, pętla została znaleziona, a pętla jest identyfikowana przez węzły w stosie.
   6. Zdejmij węzły ze stosu i kontynuuj przeglądanie listy, jeśli nie zostanie znaleziona żadna pętla.

Implementacja programu C++ dla powyższej metody (Stack)

Wyjście:

Wyjaśnienie:

Ten program używa stosu, aby dowiedzieć się, czy pojedynczo połączona lista zawiera pętlę.

• 1. Biblioteka strumienia wejścia/wyjścia i biblioteka stosu znajdują się w pierwszym wierszu.

  2. Standardowa przestrzeń nazw jest zawarta w drugim wierszu, umożliwiając nam dostęp do funkcji biblioteki strumieni wejścia/wyjścia bez konieczności poprzedzania ich przedrostkiem „std::”.

  3. Poniższy wiersz definiuje strukturę Node, która składa się z dwóch elementów: liczby całkowitej o nazwie „data” oraz wskaźnika do innego węzła o nazwie „next”.

  4. Nagłówek połączonej listy jest wejściem dla metody seekLoopLinkedList(), która jest zdefiniowana w następnym wierszu. Funkcja generuje wartość logiczną, która wskazuje, czy znaleziono pętlę.

  5. Wewnątrz funkcji tworzony jest stos wskaźników Node o nazwie „stack” oraz wskaźnik do węzła o nazwie „tempNode”, który jest inicjowany wartością headNode.

  6. Następnie, o ile tempNode nie jest wskaźnikiem zerowym, wchodzimy w pętlę while.

  (a) Górny element stosu musi pasować do bieżącego węzła, abyśmy mogli stwierdzić, że nie jest on pusty. Jeśli tak jest, zwracamy wartość true, ponieważ została znaleziona pętla.

  (b) Jeśli powyższy warunek jest fałszywy, wskaźnik bieżącego węzła jest umieszczany na stosie, a tempNode jest ustawiany na następny węzeł na połączonej liście.

  7. Po pętli while zwracamy wartość false, ponieważ nie zaobserwowano żadnej pętli.

  8. Budujemy trzy obiekty Node i inicjalizujemy je w funkcji main(). Ponieważ w pierwszym przykładzie nie ma pętli, odpowiednio ustawiamy „następne” wskaźniki każdego węzła.

Wniosek:

Podsumowując, najlepsza metoda wykrywania pętli na połączonej liście zależy od konkretnego przypadku użycia i ograniczeń problemu. Tablica mieszająca i algorytm znajdowania cykli Floyda są skutecznymi metodami i są szeroko stosowane w praktyce. Stos i rekurencja są mniej wydajnymi metodami, ale są bardziej intuicyjne.