linket liste: Dette er en sammenkædet liste, som vi ønsker at vende.
Efter omvendt linket liste: Nedenstående vil være resultatet efter at have vendt den ovenfor linkede liste.
I ovenstående eksempeldiagram kan vi se, at hovedknuden og haleknuden ændrer deres positioner, når vi vender den lænkede liste om. Hovedknuden, som nu er en haleknude, peger på nulknuden, fordi den nu er en haleknude.
Algoritme trin
- Vi opretter en hovedmetode og erklærer nogle nødvendige variabler.
- Derefter er vores næste trin at oprette en metode, der kan oprette en linket liste. Denne metode hjælper os med at oprette en linket liste.
- Det næste trin er at oprette en metode til at vende den linkede liste. I denne metode sender vi hele den linkede liste, og denne metode vil vende den linkede liste.
- Nu har vi brug for en anden metode til at vise vores resultat efter at have vendt det.
- Vi vil kombinere alle disse ovenstående metoder i vores hovedmetode.
Vi vil forklare omvendt linket liste ved hjælp af en billedform for at gøre det lettere at forstå. Så lad os starte med eksemplet.
Nedenstående er en linket liste, som vi ønsker at vende.
Trin 1 . Den grønfarvede knude er en hovedknude, som peger på den første knude i opstarten.
Trin 2. I det næste trin vil vi krydse hele den linkede liste, indtil vi ikke får nul-markøren ved siden af header-noden. Til det vil vi tildele den næste node et midlertidigt navn, som vist i nedenstående diagram.
Trin 3. Da vi har en ny referenceknude ved navn 'midlertidig', som kan hjælpe os med at krydse hele den linkede liste, indtil vi ikke får nul-markøren, så vi kan indstille det næste link i header-noden som null, hvilket ikke vil påvirke den linkede liste som vist nedenfor i diagrammet. Nul-markøren ved siden af den aktuelle node kaldes den forrige node.
Trin 4. Nu flytter vi den midlertidige node til den næste node og den nuværende node til den forrige midlertidige node. Så nu er vi flyttet til næste knudepunkt. Vi ændrer også den forrige node fra null til kun den forrige node i den nuværende node. Så nu vil den midlertidige node tage sig af alle gennemløbene indtil nul-markøren, så vi kan sætte linket af den nuværende node til den forrige node, og nu peger den på den forrige node, som vist i nedenstående diagram.
Så vi følger de samme trin, og til sidst får vi en omvendt linket liste.
Trin 5 .
Trin 6.
Trin 7.
Trin 8.
Trin 9.
Trin 10.
Trin 11.
Trin 12.
Trin 13.
Trin 14. På dette trin vendte vores linkede liste.
C++ Program til at vende en sammenkædet liste
#includeved brug af navneområde std ;
// Metode til at oprette noden
struktur node {
int værdi ;
node * næsteNodePtr ;
} * nodeObject ;
ugyldig opretteLinkedList ( int n ) ;
ugyldig reverseLinkedList ( node ** nodeObject ) ;
ugyldig Skærm ( ) ;
int vigtigste ( ) {
int n,værdi,vare ;
cout << 'Hvor mange noder vil du oprette =>: ' ;
spise >> n ;
opretteLinkedList ( n ) ;
cout << ' \n Oplysninger i den linkede liste: \n ' ;
Skærm ( ) ;
cout << ' \n Linket liste efter omvendt \n ' ;
reverseLinkedList ( & nodeObject ) ;
Skærm ( ) ;
Vend tilbage 0 ;
}
// Denne metode vil oprette den linkede liste
ugyldig opretteLinkedList ( int n ) {
struktur node * frontNode, * tempNode ;
int værdi, dvs ;
nodeObject = ( struktur node * ) malloc ( størrelse på ( struktur node ) ) ;
hvis ( nodeObject == NUL )
cout << 'Ikke nok til at samle hukommelsen' ;
andet {
cout << 'Indtast venligst oplysningerne for node 1 (kun nummer): ' ;
spise >> værdi ;
nodeObject - > værdi = værdi ;
nodeObject - > næsteNodePtr = NUL ;
tempNode = nodeObject ;
til ( jeg = to ; jeg <= n ; jeg ++ ) {
frontNode = ( struktur node * ) malloc ( størrelse på ( struktur node ) ) ;
// Når ingen node i den sammenkædede liste
hvis ( frontNode == NUL ) {
cout << 'Hukommelse kan ikke tildeles' ;
pause ;
}
andet {
cout << 'Indtast venligst info for node' << jeg << ':' ;
spise >> værdi ;
frontNode - > værdi = værdi ;
frontNode - > næsteNodePtr = NUL ;
tempNode - > næsteNodePtr = frontNode ;
tempNode = tempNode - > næsteNodePtr ;
}
}
}
}
ugyldig reverseLinkedList ( node ** nodeObject ) {
struktur node * tempNode = NUL ;
struktur node * forrige Node = NUL ;
struktur node * nuværende Node = ( * nodeObject ) ;
mens ( nuværende Node ! = NUL ) {
tempNode = nuværende Node - > næsteNodePtr ;
nuværende Node - > næsteNodePtr = forrige Node ;
forrige Node = nuværende Node ;
nuværende Node = tempNode ;
}
( * nodeObject ) = forrige Node ;
}
ugyldig Skærm ( ) {
struktur node * tempNode ;
hvis ( nodeObject == NUL ) {
cout << 'Linket liste er tom' ;
}
andet {
tempNode = nodeObject ;
mens ( tempNode ! = NUL )
{
cout << tempNode - > værdi << ' \t ' ;
tempNode = tempNode - > næsteNodePtr ;
}
}
cout << endl ;
}
Produktion
Hvor mange noder vil du oprette =>: 6Indtast venligst oplysningerne for node 1 (kun nummer): 101
Indtast venligst oplysningerne for node 2: 95
Indtast venligst oplysningerne for node 3: 61
Indtast venligst oplysningerne for node 4: 19
Indtast venligst oplysningerne for node 5: 12
Indtast venligst oplysningerne for node 6: 11
Oplysninger i den linkede liste:
101 95 61 19 12 11
Linket liste efter omvendt
11 12 19 61 95 101
Konklusion
Denne LinuxHint-artikel har gennemgået, hvordan man vender en linket liste i C++. Der er nogle andre metoder til at vende en linket liste, men dette er en meget almindelig metode til at vende en linket liste. Det er op til dig at beslutte, hvordan du vil løse dine problemer, men generelt bør den omvendte linkede liste-funktion være en simpel løkke med pointer-swaps.