Usuń zduplikowane węzły z listy niepohamowanej

W tym artykule zobaczymy różne podejścia do usunięcia zduplikowanych węzłów z listy połączonej za pomocą programowania C ++. Zacznijmy od wyjaśnienia, co oznaczają „zduplikowane węzły” na połączonej liście.

W tym wyzwaniu otrzymaliśmy listę połączoną i poprosiliśmy o usunięcie dowolnych zduplikowanych członków z listy. Użyjmy kilku przykładów, aby zrozumieć problem.

Lista linków do pomieszczenia wejściowego jest następująca:

Elementy 8, 10 i 9 pojawiają się więcej niż raz na powiązanej liście, jak pokazano na poprzedniej liście. Wskazuje to, że na liście powiązanej są duplikaty 8, 10 i 9. Lista połączona wyjściowa jest następująca po usunięciu zduplikowanych wpisów z listy:

Szybkim i łatwym sposobem na znalezienie jest porównanie wszystkich możliwych par węzłów na liście, aby sprawdzić, czy mają te same informacje. Kiedy ich informacje się pokrywają, pozbywamy się drugiego węzła, usuwając go. Ale takie podejście jest bardziej czasochłonne.

Możliwe jest lepsza wydajność przy użyciu mieszanie. Celem jest praca przez dostarczoną listę i dodanie każdego węzła do zestawu. Jeśli aktualnie wyświetlony węzeł pojawi się w poprzednim zestawie, może być bezpiecznie zignorowany. Po zakończeniu procesu lista nie będzie już zawierać żadnych zduplikowanych węzłów.

Zrozumiemy szczegółowo każde podejście.

Podejście 1: Korzystanie z dwóch pętli

Kroki algorytmu

1. Utwórz funkcję listy powiązanej, „CreateLinkedList„, Który może utworzyć powiązaną listę.
2. Utwórz funkcję zwaną „DeleteduplicatesNodes”, Który może usunąć zduplikowany węzeł z listy powiązanej.
3. Utwórz dwa lokalne wskaźniki, PTR1 i PTR2, wewnątrz „DeleteduplicatesNodes”Funkcja.
4. Przypisz ptr1 = headnode I ptr2 = null Wartości, w których PTR1 jest używany do śledzenia węzła, którego duplikaty muszą być sprawdzone, a PTR2 służy do przemierzania każdego węzła połączonej listy, aby sprawdzić, czy dane węzła są takie same jak dane dotyczące węzła PTR1.
5. Zagnieżdżony wskaźnik pętli PTR2 kontynuuje przemieszczanie całego węzła Linked List, dopóki nie znajdzie NULL.
6. Jeśli dane węzła ptr1 są podobne do danych zagnieżdżonej pętli ptr2, usuń ten węzeł z listy powiązanej.
7. Jeśli nie, zwiększ ptr1-> Następnie i sprawdź dane następnego węzła pod kątem duplikatów.
8. Kroki od 4 do 7 są powtarzane, aż PTR1 nie będzie równe zerowi, co wskazuje, że dotarł do końca listy połączonej.
9. Wreszcie, drukujemy listę połączoną.
10. Koniec algorytmu.

Implementacja kodu C ++ (przy użyciu dwóch pętli)

Wyjście:

Wyjaśnienie:

Linie 21 do 52: Tworzymy funkcję o nazwie „CreateLinkedList”. W tej funkcji przekazujemy dwa parametry (wskaźnik nodowy do wskaźnika i wartość). Jak pokazano w poprzednim programie, ilekroć ta funkcja jest wywoływana, najpierw tworzy nowy węzeł o wartości (który przekazaliśmy) i adres węzła o wartości zerowej.

/* Utwórz nowy węzeł*/
Node* newNode = new Node ();
Węzeł * lastNode = * headNode;
newNode-> data = wartość; / * Dodanie danych */
/* Adres tego nowego węzła inticznie utrzymywał null*/
newNode-> następny = null;

Następnie sprawdza, czy odniesienie do głowy jest zerowe. Jeśli tak, nowo utworzony węzeł staje się głową.

/* Sprawdzanie odniesienia do headnode jest null lub nie.
Jeśli tak, wówczas newNode stanie się headnode*/
if (*headnode == null)
*headNode = newNode;
powrót;

Jeśli odniesienie do głowy nie jest null, dołącza się do ostatniego stylu listy powiązanej. Adres tego nowo utworzonego Nowego Node jest przypisany do LastNode, aby mógł zacząć wskazywać na nowo utworzony newNode.

/* Jeśli nie, to to poby
Wykonaj i znajdź ostatnią nodę połączonego
Lista, tak aby nowo utworzono newNode dołączanie do ostatniego*/
While (LastNode-> następny != Null)
lastNode = lastNode-> następny;

Teraz nowo utworzony NewNode staje się ostatnim. Proces ten trwa do tego czasu, kiedy nazywamy tę funkcję.

Poprzednie kroki Utwórz powiązaną listę zgodnie z naszymi wymaganiami. Teraz usuwamy zduplikowane węzły z listy powiązanej.

Linie 57 do 75: Tworzymy jedną funkcję o nazwie „DeletEduplicatesNodes”, która akceptuje jeden parametr, który jest wskaźnikiem listy powiązanej. Tworzymy dwie zmienne na poziomie lokalnym, PTR1 i PTR2, aby śledzić połączoną listę, gdy zapętlimy ją, aby znaleźć duplikaty na połączonej liście. Zainicjujemy PTR1 z nodem głowy, ponieważ będzie to górna pętla, a PTR2 z wartością zerową.

ptr1 = headnode;

ptr1: Ta zmienna znajduje się w zewnętrznej pętli i śledzi elementy, których duplikaty zamierzamy sprawdzić.

ptr2: Ta zmienna znajduje się wewnątrz pętli i nadal sprawdza dane każdego węzła, aby dowiedzieć się, czy pasuje do danych Hold PTR1. Jeśli się pasuje, jego duplikaty są usuwane z listy powiązanej. Jest to sprawdzane i trwa, dopóki nie dotrze do ostatniego węzła, którego wartość jest null.

Gdy ptr2-> następny == null, zagnieżdżone, gdy pętla kończy ptr1 = ptr1-> następny z następnymi danymi węzłów.

Notatka: ptr2 kończy się, gdy ptr1 pętla się skończyła, ponieważ ptr2 jest wewnątrz pętli ptr1.

podczas gdy (ptr1 != Null && ptr1-> Następnie != Null)
ptr2 = ptr1;
While (ptr2-> następny != Null)
/* Jeśli znaleziono, poniżej kodu usunie
Duplikatuje węzeł*/
if (ptr1-> data == ptr2-> następny-> data)
duplikat = ptr2-> następny;
ptr2-> next = ptr2-> następny-> następny;
delete (duplikat);
else /*, jeśli nie znaleziono, ptr2 będzie aktualizowany do
do następnego węzła*/
ptr2 = ptr2-> następny;

ptr1 = ptr1-> następny;

Linie 78 do 84: To wyświetla końcową listę połączoną bez powielania. W takim przypadku przekazujemy headNode jako parametr, który jest adresem listy powiązanej.

/* Ta funkcja wydrukuje połączoną listę*/
void wyświetlacz (węzeł* węzeł)
while (węzeł-> następny)
printf („%d ->”, węzeł-> dane);
node = węzeł-> następny;

printf („%d”, węzeł-> dane);

Podejście 2: Metoda mieszania

Kroki algorytmu

1. Utwórz funkcję listy LISTE „CreateLinkedList”, która może utworzyć połączoną listę.
2. Utwórz funkcję o nazwie „Usuń się.
3. Utwórz dwa lokalne wskaźniki, CurrentNode i poprzedni Node, wewnątrz funkcji „Usuń się.
4. Utwórz nieposortowany zestaw skrótów wewnątrz „UsuńDuplicatesNodes”.
5. Przypisz CurrentNode = HEADNODE i poprzednie wartości null, w których CurrentNode jest używany do śledzenia węzła, którego duplikaty muszą być sprawdzone, a poprzedni Node służy do śledzenia poprzedniego węzła CurrentNode.
6. While pętla przemierza cały węzeł listy połączonej, aż CurrentNode == NULL.
7. Jeśli dane CurrentNode są już w zestawie skrótu, węzeł jest usuwany.
8. Jeśli nie, dodaje dane węzła do zestawu skrótu.
9. Kroki od 5 do 8 są powtarzane, aż prąd prądowy nie będzie równy NULL, co wskazuje, że osiągnął koniec listy połączonej.
10. Wreszcie, drukujemy listę połączoną.
11. Koniec algorytmu.

Implementacja kodu C ++ (przy użyciu metody HASH)

Wyjście:

Linie 26 do 52: Tworzymy funkcję o nazwie „CreateLinkedList”. W tej funkcji przekazujemy dwa parametry (wskaźnik nodowy do wskaźnika do wskaźnika i wartość). Jak pokazano w poprzednim programie, ilekroć ta funkcja jest wywoływana, najpierw tworzy nowy węzeł o wartości (który przekazaliśmy) i adres o wartości zerowej.

/* Utwórz nowy węzeł*/
Node* newNode = new Node ();
Węzeł * lastNode = * headNode;
newNode-> data = wartość; / * Dodanie danych */
/* Adres tego nowego węzła inticznie utrzymywał null*/
newNode-> następny = null;

Następnie sprawdza, czy odniesienie do głowy jest zerowe. Jeśli tak, nowo utworzony węzeł staje się głową.

/* Sprawdzanie odniesienia do headnode jest null lub nie.
Jeśli tak, wówczas newNode stanie się headnode*/
if (*headnode == null)
*headNode = newNode;
powrót;

Jeśli odniesienie do głowy nie jest null, dołącza się do ostatniego stylu listy powiązanej. Adres tego nowo utworzonego Nowego Node jest przypisany do LastNode, aby mógł zacząć wskazywać na nowo utworzony newNode.

/* Jeśli nie, to to poby
Wykonaj i znajdź ostatnią nodę połączonego
Lista, tak aby nowo utworzono newNode dołączanie do ostatniego*/
While (LastNode-> następny != Null)
lastNode = lastNode-> następny;

Teraz nowo utworzony NewNode staje się ostatnim. Proces ten trwa do tego czasu, kiedy nazywamy tę funkcję.

Poprzednie kroki Utwórz powiązaną listę zgodnie z naszymi wymaganiami. Teraz usuwamy zduplikowane węzły z listy powiązanej.

Linie 57 do 75: Tworzymy jedną funkcję o nazwie „DeletEduplicatesNodes”, która akceptuje jeden parametr, który jest wskaźnikiem listy powiązanej. Tworzymy nieporządkowany skrót Hashset. Tworzymy również dwie zmienne na poziomie lokalnym, CurrentNode I poprzedni Node, Aby śledzić połączoną listę, gdy zapętlimy ją, aby znaleźć duplikaty na linkowanej liście. Zainicjujemy bieżącąeNode z nodą głową, ponieważ będzie to górna pętla, a poprzedni poziom z wartością zerową.

struct node* currentNode = headNode;
struct node* poprzedniNode = null;

CurrentNode: Ta zmienna znajduje się w zewnętrznej pętli i śledzi elementy, których duplikaty zamierzamy sprawdzić.

poprzedni Node: To obsługuje poprzedni węzeł CurrentNode. Tworzymy pętlę, która wykonuje się, dopóki CurrentNode nie znajdzie wartości zerowej, co oznacza na końcu listy powiązanej. Jeśli dane CurrentNode znajdują się już na mapie skrótu, przypisz wartość CurrentNode's Następny wskaźnik do poprzedni Node Następny wskaźnik.

poprzedniNode-> następny = currentNode-> następny;

Jeśli nie, dodaj dane z bieżącego modelu do mapy skrótu i ​​uczyń poprzedni Node równe CurrentNode.

w przeciwnym razie
haszysz.insert (currentNode-> dane);
poprzedniNode = currentNode;

Na końcu przypisz wartość następnego wskaźnika poprzedniego typu do bieżącego.

While (CurrentNode != Null)
/* Jeśli dane CurrentNode już odwiedzono, to to
Kod usunie ten węzeł
*/
if (hasz.Znajdź (CurrentNode-> dane) != skrót.koniec())
poprzedniNode-> następny = currentNode-> następny;
delete (currentNode);

/*
Jeśli nie odwiedzono danych CurrentNode, to
wstaw do skrótu
*/
w przeciwnym razie
haszysz.insert (currentNode-> dane);
poprzedniNode = currentNode;

currentNode = poprzedniNode-> następny;

Linie 84 do 90: To wyświetla końcową listę połączoną bez powielania. W takim przypadku przekazujemy headNode jako parametr, który jest adresem listy powiązanej.

/* Ta funkcja wydrukuje połączoną listę*/
void wyświetlacz (węzeł* węzeł)
while (węzeł-> następny)
printf („%d ->”, węzeł-> dane);
node = węzeł-> następny;

printf („%d”, węzeł-> dane);

Wniosek

W pierwszej metodzie, aby pozbyć się duplikatów, używamy dwóch pętli: zewnętrznej pętli, która iteruje połączoną listę i wybiera element, oraz drugą pętlę, która iteruje ten element, aby poszukać wszelkich możliwych duplikatów. Jak tylko wykryto duplikat, jest on usuwany z listy. Ta metoda wykorzystuje zagnieżdżoną pętlę do zbadania i wyeliminowania duplikatów z niepohamowanej listy, która zwiększa złożoność czasu procesu. Złożoność czasu wynosi O (n²).

W drugiej metodzie można zastosować mieszanie w celu zminimalizowania czasowej złożoności usuwania duplikatów z nieporządonej listy połączonej. W takim przypadku, jeśli węzeł pojawia się w hashmapie dwa razy, jest to duplikacja i pierwsze wystąpienie należy usunąć. Jeśli na mapie brakuje węzła, to dlatego, że należy dodać nowy. Przejrzenie połączonej listy długości „N” zajmuje średnio czas O (n). Czasowa złożoność poszukiwania wartości w tabeli skrótów wynosi O (1). Biorąc pod uwagę wspólnie wspomniane warunki wstępne, całkowita złożoność czasu wynosi O (n).