połączona lista: To jest połączona lista, którą chcemy odwrócić.
Po odwróconej połączonej liście: Poniższy będzie wynikiem po odwróceniu powyższej listy.
Na powyższym przykładowym diagramie widzimy, że węzeł główny i węzeł końcowy zmieniają swoje pozycje, gdy odwracamy połączoną listę. Węzeł główny, który jest teraz węzłem ogonowym, wskazuje na węzeł zerowy, ponieważ jest teraz węzłem ogonowym.
Kroki algorytmu
- Tworzymy główną metodę i deklarujemy kilka wymaganych zmiennych.
- Następnie naszym następnym krokiem jest utworzenie metody, która może utworzyć połączoną listę. Ta metoda pomaga nam stworzyć połączoną listę.
- Następnym krokiem jest utworzenie metody odwracającej połączoną listę. W tej metodzie przekazujemy całą połączoną listę, a ta metoda odwróci połączoną listę.
- Teraz potrzebujemy innej metody, aby wyświetlić nasz wynik po jego odwróceniu.
- Połączymy wszystkie powyższe metody w naszą główną metodę.
Zamierzamy wyjaśnić odwróconą listę powiązań za pomocą obrazkowej formy, aby ułatwić zrozumienie. Zacznijmy więc od przykładu.
Poniżej znajduje się połączona lista, którą chcemy odwrócić.
Krok 1 . Węzeł w kolorze zielonym jest węzłem głównym, który wskazuje pierwszy węzeł w starcie.
Krok 2. W następnym kroku będziemy przechodzić przez całą połączoną listę, aż nie otrzymamy pustego wskaźnika obok węzła nagłówka. W tym celu przypiszemy następnemu węzłowi tymczasową nazwę, jak pokazano na poniższym diagramie.
Krok 3. Ponieważ mamy nowy węzeł referencyjny o nazwie „tymczasowy”, który może nam pomóc w przechodzeniu przez całą połączoną listę, dopóki nie otrzymamy pustego wskaźnika, możemy więc ustawić następne łącze węzła nagłówka jako puste, co nie wpłynie na połączone listę, jak pokazano na poniższym schemacie. Wskaźnik zerowy obok bieżącego węzła nazywany jest poprzednim węzłem.
Krok 4. Teraz przenosimy węzeł tymczasowy do następnego węzła, a bieżący węzeł do poprzedniego węzła tymczasowego. Więc teraz przeszliśmy do następnego węzła. Zmieniamy również poprzedni węzeł z null na poprzedni węzeł bieżącego węzła. Teraz tymczasowy węzeł zajmie się wszystkimi przejściami do wskaźnika zerowego, abyśmy mogli ustawić łącze bieżącego węzła do poprzedniego węzła, a teraz wskazuje na poprzedni węzeł, jak pokazano na poniższym diagramie.
Wykonujemy te same kroki iw końcu otrzymamy odwróconą listę powiązań.
Krok 5 .
Krok 6.
Krok 7.
Krok 8.
Krok 9.
Krok 10.
Krok 11.
Krok 12.
Krok 13.
Krok 14. Na tym etapie nasza połączona lista została odwrócona.
Program C++ do odwrócenia połączonej listy
#includeza pomocą przestrzeń nazw standardowe ;
// Metoda tworzenia węzła
struktura węzeł {
int wartość ;
węzeł * nextNodePtr ;
} * węzełObiekt ;
próżnia utwórz połączoną listę ( int n ) ;
próżnia odwrócona lista połączona ( węzeł ** węzełObiekt ) ;
próżnia wyświetlacz ( ) ;
int Główny ( ) {
int n,wartość,pozycja ;
cout << 'Ile węzłów chcesz utworzyć =>: ' ;
jedzenie >> n ;
utwórz połączoną listę ( n ) ;
cout << ' \n Informacje na połączonej liście: \n ' ;
wyświetlacz ( ) ;
cout << ' \n Połączona lista po odwróceniu \n ' ;
odwrócona lista połączona ( & węzełObiekt ) ;
wyświetlacz ( ) ;
zwrócić 0 ;
}
// Ta metoda utworzy połączoną listę
próżnia utwórz połączoną listę ( int n ) {
struktura węzeł * Węzeł przedni, * tempNode ;
int wartość, tj ;
węzełObiekt = ( struktura węzeł * ) mallok ( rozmiar ( struktura węzeł ) ) ;
jeśli ( węzełObiekt == ZERO )
cout << „Za mało, by przyswoić pamięć” ;
w przeciwnym razie {
cout << „Proszę wprowadzić informacje o węźle 1 (tylko numer):” ;
jedzenie >> wartość ;
węzełObiekt - > wartość = wartość ;
węzełObiekt - > nextNodePtr = ZERO ;
tempNode = węzełObiekt ;
dla ( i = dwa ; i <= n ; i ++ ) {
Węzeł przedni = ( struktura węzeł * ) mallok ( rozmiar ( struktura węzeł ) ) ;
// Gdy nie ma żadnego węzła na połączonej liście
jeśli ( Węzeł przedni == ZERO ) {
cout << „Nie można przydzielić pamięci” ;
przerwanie ;
}
w przeciwnym razie {
cout << „Proszę wprowadzić informacje o węźle” << i << ':' ;
jedzenie >> wartość ;
Węzeł przedni - > wartość = wartość ;
Węzeł przedni - > nextNodePtr = ZERO ;
tempNode - > nextNodePtr = Węzeł przedni ;
tempNode = tempNode - > nextNodePtr ;
}
}
}
}
próżnia odwrócona lista połączona ( węzeł ** węzełObiekt ) {
struktura węzeł * tempNode = ZERO ;
struktura węzeł * poprzedniWęzeł = ZERO ;
struktura węzeł * bieżący węzeł = ( * węzełObiekt ) ;
podczas gdy ( bieżący węzeł ! = ZERO ) {
tempNode = bieżący węzeł - > nextNodePtr ;
bieżący węzeł - > nextNodePtr = poprzedniWęzeł ;
poprzedniWęzeł = bieżący węzeł ;
bieżący węzeł = tempNode ;
}
( * węzełObiekt ) = poprzedniWęzeł ;
}
próżnia wyświetlacz ( ) {
struktura węzeł * tempNode ;
jeśli ( węzełObiekt == ZERO ) {
cout << „Połączona lista jest pusta” ;
}
w przeciwnym razie {
tempNode = węzełObiekt ;
podczas gdy ( tempNode ! = ZERO )
{
cout << tempNode - > wartość << ' \t ' ;
tempNode = tempNode - > nextNodePtr ;
}
}
cout << koniec ;
}
Wyjście
Ile węzłów chcesz utworzyć =>: 6Wprowadź informacje o węźle 1 (tylko liczba): 101
Wprowadź informacje o węźle 2: 95
Wprowadź informacje o węźle 3: 61
Wprowadź informacje o węźle 4: 19
Wprowadź informacje o węźle 5: 12
Wprowadź informacje o węźle 6: 11
Informacje na połączonej liście:
101 95 61 19 12 11
Lista połączona po odwróceniu
11 12 19 61 95 101
Wniosek
W tym artykule LinuxHint omówiono, jak odwrócić połączoną listę w C++. Istnieje kilka innych metod odwracania połączonej listy, ale jest to bardzo powszechna metoda odwracania połączonej listy. To Ty decydujesz, jak chcesz rozwiązać swoje problemy, ale generalnie funkcja listy z odwróconymi linkami powinna być prostą pętlą z zamianą wskaźników.