prepojený zoznam: Toto je prepojený zoznam, ktorý chceme zvrátiť.
Po obrátení prepojeného zoznamu: Nižšie uvedený bude výsledok po obrátení vyššie uvedeného zoznamu.
Vo vyššie uvedenom príklade diagramu môžeme vidieť, že hlavný uzol a koncový uzol menia svoje pozície, keď otočíme prepojený zoznam. Hlavný uzol, ktorý je teraz koncovým uzlom, ukazuje na nulový uzol, pretože je teraz koncovým uzlom.
Kroky algoritmu
- Vytvoríme hlavnú metódu a deklarujeme niektoré požadované premenné.
- Potom je naším ďalším krokom vytvorenie metódy, ktorá dokáže vytvoriť prepojený zoznam. Táto metóda nám pomáha vytvoriť prepojený zoznam.
- Ďalším krokom je vytvorenie metódy na zvrátenie prepojeného zoznamu. Pri tejto metóde prejdeme celý prepojený zoznam a táto metóda obráti prepojený zoznam.
- Teraz potrebujeme inú metódu na zobrazenie nášho výsledku po jeho obrátení.
- Všetky tieto vyššie uvedené metódy skombinujeme do našej hlavnej metódy.
Obrátený prepojený zoznam vysvetlíme pomocou obrázkovej formy, aby sme ho ľahšie pochopili. Začnime teda príkladom.
Nižšie je uvedený prepojený zoznam, ktorý chceme vrátiť späť.
Krok 1 . Uzol zelenej farby je hlavný uzol, ktorý ukazuje na prvý uzol pri spustení.
Krok 2. V ďalšom kroku budeme prechádzať celým prepojeným zoznamom, kým nedostaneme nulový ukazovateľ vedľa uzla hlavičky. Na tento účel priradíme ďalšiemu uzlu dočasný názov, ako je znázornené na obrázku nižšie.
Krok 3. Keďže máme nový referenčný uzol s názvom „dočasný“, ktorý nám môže pomôcť prejsť celým prepojeným zoznamom, kým nezískame nulový ukazovateľ, môžeme teda nastaviť ďalší odkaz uzla hlavičky na hodnotu null, čo neovplyvní prepojený zoznam, ako je znázornené na obrázku nižšie. Nulový ukazovateľ vedľa aktuálneho uzla sa nazýva predchádzajúci uzol.
Krok 4. Teraz presunieme dočasný uzol na nasledujúci uzol a aktuálny uzol na predchádzajúci dočasný uzol. Takže teraz sme sa presunuli do ďalšieho uzla. Tiež zmeníme predchádzajúci uzol z null na predchádzajúci uzol aktuálneho uzla. Takže teraz sa dočasný uzol postará o všetky prechody až po nulový ukazovateľ, aby sme mohli nastaviť prepojenie aktuálneho uzla na predchádzajúci uzol a teraz ukazuje na predchádzajúci uzol, ako je znázornené na obrázku nižšie.
Takže postupujeme podľa rovnakých krokov a nakoniec dostaneme obrátený prepojený zoznam.
Krok 5 .
Krok 6.
Krok 7.
Krok 8.
Krok 9.
Krok 10.
Krok 11.
Krok 12.
Krok 13.
Krok 14. V tomto kroku sa náš prepojený zoznam obrátil.
C++ Program na zvrátenie prepojeného zoznamu
#includepoužitím menný priestor std ;
// Metóda na vytvorenie uzla
štrukturovať uzol {
int hodnotu ;
uzol * nextNodePtr ;
} * nodeObject ;
neplatné vytvoriťLinkedList ( int n ) ;
neplatné reverseLinkedList ( uzol ** nodeObject ) ;
neplatné displej ( ) ;
int hlavné ( ) {
int n,hodnota,položka ;
cout << 'Koľko uzlov chcete vytvoriť =>: ' ;
jedenie >> n ;
vytvoriťLinkedList ( n ) ;
cout << ' \n Informácie v prepojenom zozname: \n ' ;
displej ( ) ;
cout << ' \n Prepojený zoznam po obrátení \n ' ;
reverseLinkedList ( & nodeObject ) ;
displej ( ) ;
vrátiť 0 ;
}
// Táto metóda vytvorí prepojený zoznam
neplatné vytvoriťLinkedList ( int n ) {
štrukturovať uzol * frontNode, * tempNode ;
int hodnota, t.j ;
nodeObject = ( štrukturovať uzol * ) malloc ( veľkosť ( štrukturovať uzol ) ) ;
ak ( nodeObject == NULOVÝ )
cout << 'Nie je dosť na to, aby som si zapamätal' ;
inak {
cout << 'Zadajte informácie o uzle 1 (iba číslo): ' ;
jedenie >> hodnotu ;
nodeObject - > hodnotu = hodnotu ;
nodeObject - > nextNodePtr = NULOVÝ ;
tempNode = nodeObject ;
pre ( i = dva ; i <= n ; i ++ ) {
frontNode = ( štrukturovať uzol * ) malloc ( veľkosť ( štrukturovať uzol ) ) ;
// Keď v prepojenom zozname nie je žiadny uzol
ak ( frontNode == NULOVÝ ) {
cout << 'Nedá sa prideliť pamäť' ;
prestávka ;
}
inak {
cout << 'Zadajte informácie o uzle' << i << ':' ;
jedenie >> hodnotu ;
frontNode - > hodnotu = hodnotu ;
frontNode - > nextNodePtr = NULOVÝ ;
tempNode - > nextNodePtr = frontNode ;
tempNode = tempNode - > nextNodePtr ;
}
}
}
}
neplatné reverseLinkedList ( uzol ** nodeObject ) {
štrukturovať uzol * tempNode = NULOVÝ ;
štrukturovať uzol * predchádzajúciUzol = NULOVÝ ;
štrukturovať uzol * currentNode = ( * nodeObject ) ;
zatiaľ čo ( currentNode ! = NULOVÝ ) {
tempNode = currentNode - > nextNodePtr ;
currentNode - > nextNodePtr = predchádzajúciUzol ;
predchádzajúciUzol = currentNode ;
currentNode = tempNode ;
}
( * nodeObject ) = predchádzajúciUzol ;
}
neplatné displej ( ) {
štrukturovať uzol * tempNode ;
ak ( nodeObject == NULOVÝ ) {
cout << 'Prepojený zoznam je prázdny' ;
}
inak {
tempNode = nodeObject ;
zatiaľ čo ( tempNode ! = NULOVÝ )
{
cout << tempNode - > hodnotu << ' \t ' ;
tempNode = tempNode - > nextNodePtr ;
}
}
cout << endl ;
}
Výkon
Koľko uzlov chcete vytvoriť =>: 6Zadajte informácie o uzle 1 (len číslo): 101
Zadajte informácie o uzle 2: 95
Zadajte informácie o uzle 3: 61
Zadajte informácie o uzle 4: 19
Zadajte informácie o uzle 5: 12
Zadajte informácie o uzle 6: 11
Informácie v prepojenom zozname:
101 95 61 19 12 11
Prepojený zoznam po obrátení
11 12 19 61 95 101
Záver
Tento článok LinuxHint zhodnotil, ako zvrátiť prepojený zoznam v C++. Existuje niekoľko ďalších metód na zvrátenie prepojeného zoznamu, ale toto je veľmi bežná metóda na zvrátenie prepojeného zoznamu. Je na vás, aby ste sa rozhodli, ako chcete vyriešiť svoje problémy, ale vo všeobecnosti by funkcia spätného prepojeného zoznamu mala byť jednoduchá slučka s výmenou ukazovateľov.