gekoppelde lijst: Dit is een gekoppelde lijst die we willen omkeren.
Na omgekeerde gelinkte lijst: Het onderstaande is het resultaat na het omkeren van de hierboven gelinkte lijst.
In het bovenstaande voorbeelddiagram kunnen we zien dat het hoofdknooppunt en het staartknooppunt van positie veranderen wanneer we de gekoppelde lijst omdraaien. Het hoofdknooppunt, dat nu een staartknooppunt is, wijst naar het nulknooppunt omdat het nu een staartknooppunt is.
Algoritme stappen
- We maken een hoofdmethode en declareren enkele vereiste variabelen.
- Vervolgens is onze volgende stap het maken van een methode die een gekoppelde lijst kan maken. Deze methode helpt ons om een gelinkte lijst te maken.
- De volgende stap is het creëren van een methode om de gekoppelde lijst om te keren. Bij deze methode geven we de hele gekoppelde lijst door en deze methode zal de gekoppelde lijst omkeren.
- Nu hebben we een andere methode nodig om ons resultaat weer te geven nadat we het hebben omgedraaid.
- We zullen al deze bovenstaande methoden combineren in onze hoofdmethode.
We gaan de omgekeerde gelinkte lijst uitleggen met behulp van een grafische vorm om het gemakkelijker te begrijpen. Dus laten we beginnen met het voorbeeld.
Het onderstaande is een gekoppelde lijst die we willen omkeren.
Stap 1 . Het groengekleurde knooppunt is een hoofdknooppunt, dat verwijst naar het eerste knooppunt bij het opstarten.
Stap 2. In de volgende stap zullen we de hele gekoppelde lijst doorlopen totdat we de nulwijzer naast het kopknooppunt niet krijgen. Daarvoor gaan we het volgende knooppunt een tijdelijke naam geven, zoals weergegeven in het onderstaande diagram.
Stap 3. Omdat we een nieuw referentieknooppunt hebben met de naam 'tijdelijk', dat ons kan helpen de hele gekoppelde lijst te doorzoeken totdat we de nulwijzer niet krijgen, kunnen we dus de volgende link van het kopknooppunt instellen als null, wat geen invloed heeft op de gekoppelde lijst zoals hieronder weergegeven in het diagram. De nulwijzer naast het huidige knooppunt wordt het vorige knooppunt genoemd.
Stap 4. Nu verplaatsen we het tijdelijke knooppunt naar het volgende knooppunt en het huidige knooppunt naar het vorige tijdelijke knooppunt. Dus nu zijn we verhuisd naar het volgende knooppunt. We veranderen ook het vorige knooppunt van null in alleen het vorige knooppunt van het huidige knooppunt. Dus nu zorgt het tijdelijke knooppunt voor alle traverses tot de nulwijzer, zodat we de link van het huidige knooppunt naar het vorige knooppunt kunnen instellen, en nu wijst het naar het vorige knooppunt, zoals weergegeven in het onderstaande diagram.
We volgen dus dezelfde stappen en uiteindelijk krijgen we een omgekeerde gelinkte lijst.
Stap 5 .
Stap 6.
Stap 7.
Stap 8.
Stap 9.
Stap 10.
Stap 11.
Stap 12.
Stap 13.
Stap 14. Bij deze stap is onze gekoppelde lijst omgekeerd.
C++ Programma om een gelinkte lijst om te keren
#includegebruik makend van naamruimte soa ;
// Methode om het knooppunt te maken
structuur knooppunt {
int waarde ;
knooppunt * volgendeNodePtr ;
} * nodeObject ;
leegte createLinkedList ( int n ) ;
leegte reverseLinkedList ( knooppunt ** nodeObject ) ;
leegte Scherm ( ) ;
int hoofd ( ) {
int n,waarde,item ;
cout << 'Hoeveel knooppunten je wilt maken =>: ' ;
aan het eten >> n ;
createLinkedList ( n ) ;
cout << ' \n Informatie in de gekoppelde lijst: \n ' ;
Scherm ( ) ;
cout << ' \n Gekoppelde lijst na omkering \n ' ;
reverseLinkedList ( & nodeObject ) ;
Scherm ( ) ;
opbrengst 0 ;
}
// Deze methode maakt de gekoppelde lijst
leegte createLinkedList ( int n ) {
structuur knooppunt * frontNode, * tempNode ;
int waarde, ik ;
nodeObject = ( structuur knooppunt * ) malloc ( De grootte van ( structuur knooppunt ) ) ;
als ( nodeObject == NUL )
cout << 'Niet genoeg om het geheugen te beoordelen' ;
anders {
cout << 'Voer de info van knooppunt 1 in (alleen nummer): ' ;
aan het eten >> waarde ;
nodeObject - > waarde = waarde ;
nodeObject - > volgendeNodePtr = NUL ;
tempNode = nodeObject ;
voor ( i = twee ; i <= n ; i ++ ) {
frontNode = ( structuur knooppunt * ) malloc ( De grootte van ( structuur knooppunt ) ) ;
// Als er geen knooppunt in de gekoppelde lijst staat
als ( frontNode == NUL ) {
cout << 'Geheugen kan niet worden toegewezen' ;
pauze ;
}
anders {
cout << 'Voer de info van het knooppunt in' << i << ':' ;
aan het eten >> waarde ;
frontNode - > waarde = waarde ;
frontNode - > volgendeNodePtr = NUL ;
tempNode - > volgendeNodePtr = frontNode ;
tempNode = tempNode - > volgendeNodePtr ;
}
}
}
}
leegte reverseLinkedList ( knooppunt ** nodeObject ) {
structuur knooppunt * tempNode = NUL ;
structuur knooppunt * vorigeNode = NUL ;
structuur knooppunt * huidigeNode = ( * nodeObject ) ;
terwijl ( huidigeNode ! = NUL ) {
tempNode = huidigeNode - > volgendeNodePtr ;
huidigeNode - > volgendeNodePtr = vorigeNode ;
vorigeNode = huidigeNode ;
huidigeNode = tempNode ;
}
( * nodeObject ) = vorigeNode ;
}
leegte Scherm ( ) {
structuur knooppunt * tempNode ;
als ( nodeObject == NUL ) {
cout << 'Gelinkte lijst is leeg' ;
}
anders {
tempNode = nodeObject ;
terwijl ( tempNode ! = NUL )
{
cout << tempNode - > waarde << ' \t ' ;
tempNode = tempNode - > volgendeNodePtr ;
}
}
cout << eindel ;
}
Uitgang
Hoeveel nodes wil je aanmaken =>: 6Voer de info van knooppunt 1 in (alleen nummer): 101
Voer de info van knooppunt 2: 95 in
Voer de info in van knooppunt 3: 61
Voer de info van knooppunt 4: 19 in
Voer de info van knooppunt 5: 12 in
Voer de info van knooppunt 6: 11 in
Informatie in de gekoppelde lijst:
101 95 61 19 12 11
Gekoppelde lijst na omkering
11 12 19 61 95 101
Conclusie
Dit LinuxHint-artikel heeft besproken hoe een gekoppelde lijst in C++ kan worden omgekeerd. Er zijn enkele andere methoden om een gelinkte lijst ongedaan te maken, maar dit is een veelgebruikte methode om een gelinkte lijst ongedaan te maken. Het is aan jou om te beslissen hoe je je problemen wilt oplossen, maar over het algemeen zou de omgekeerde gekoppelde lijstfunctie een eenvoudige lus moeten zijn met pointer-swaps.