koblet liste: Dette er en lenket liste som vi ønsker å reversere.
Etter omvendt lenket liste: Nedenstående vil være resultatet etter å ha reversert listen ovenfor.
I eksempeldiagrammet ovenfor kan vi se at hodenoden og halenoden endrer sine posisjoner når vi reverserer den koblede listen. Hodeknuten, som nå er en halennode, peker på nullnoden fordi den nå er en halennode.
Algoritmetrinn
- Vi lager en hovedmetode og deklarerer noen nødvendige variabler.
- Deretter er vårt neste trinn å lage en metode som kan lage en koblet liste. Denne metoden hjelper oss å lage en koblet liste.
- Det neste trinnet er å lage en metode for å reversere den koblede listen. I denne metoden sender vi hele den koblede listen, og denne metoden vil reversere den koblede listen.
- Nå trenger vi en annen metode for å vise resultatet etter å ha reversert det.
- Vi vil kombinere alle disse metodene ovenfor i vår hovedmetode.
Vi skal forklare omvendt lenket liste ved å bruke en eller annen billedform for å gjøre det lettere å forstå. Så la oss starte med eksempelet.
Nedenfor er en lenket liste som vi ønsker å reversere.
Trinn 1 . Den grønnfargede noden er en hodenode, som peker til den første noden i oppstarten.
Steg 2. I neste trinn vil vi krysse hele den koblede listen til vi ikke får null-pekeren ved siden av header-noden. For det skal vi tildele neste node et midlertidig navn, som vist i diagrammet nedenfor.
Trinn 3. Siden vi har en ny referansenode kalt 'midlertidig', som kan hjelpe oss å krysse hele den koblede listen til vi ikke får null-pekeren, så vi kan sette den neste lenken til toppnoden som null, noe som ikke vil påvirke den koblede liste som vist nedenfor i diagrammet. Nullpekeren ved siden av gjeldende node kalles forrige node.
Trinn 4. Nå flytter vi den midlertidige noden til neste node og den nåværende noden til den forrige midlertidige noden. Så nå har vi flyttet til neste node. Vi endrer også den forrige noden fra null til bare den forrige noden til den nåværende noden. Så nå vil den midlertidige noden ta seg av alle traversene til null-pekeren slik at vi kan sette koblingen til den nåværende noden til den forrige noden, og nå peker den til den forrige noden, som vist i diagrammet nedenfor.
Så vi følger de samme trinnene, og til slutt vil vi få en omvendt lenket liste.
Trinn 5 .
Trinn 6.
Trinn 7.
Trinn 8.
Trinn 9.
Trinn 10.
Trinn 11.
Trinn 12.
Trinn 13.
Trinn 14. På dette trinnet snudde vår koblede liste.
C++ Program for å reversere en koblet liste
#includeved hjelp av navneområde std ;
// Metode for å lage noden
struktur node {
int verdi ;
node * nesteNodePtr ;
} * nodeObject ;
tomrom opprette LinkedList ( int n ) ;
tomrom reverseLinkedList ( node ** nodeObject ) ;
tomrom vise ( ) ;
int hoved- ( ) {
int n,verdi,vare ;
cout << 'Hvor mange noder du vil opprette =>: ' ;
spiser >> n ;
opprette LinkedList ( n ) ;
cout << ' \n Informasjon i den tilknyttede listen: \n ' ;
vise ( ) ;
cout << ' \n Linket liste etter reversert \n ' ;
reverseLinkedList ( & nodeObject ) ;
vise ( ) ;
komme tilbake 0 ;
}
// Denne metoden vil lage den koblede listen
tomrom opprette LinkedList ( int n ) {
struktur node * frontNode, * tempNode ;
int verdi, dvs ;
nodeObject = ( struktur node * ) malloc ( størrelsen av ( struktur node ) ) ;
hvis ( nodeObject == NULL )
cout << 'Ikke nok til å samle minne' ;
ellers {
cout << 'Vennligst skriv inn informasjonen til node 1 (kun nummer): ' ;
spiser >> verdi ;
nodeObject - > verdi = verdi ;
nodeObject - > nesteNodePtr = NULL ;
tempNode = nodeObject ;
til ( Jeg = to ; Jeg <= n ; Jeg ++ ) {
frontNode = ( struktur node * ) malloc ( størrelsen av ( struktur node ) ) ;
// Når ingen node i den koblede listen
hvis ( frontNode == NULL ) {
cout << 'Minne kan ikke tildeles' ;
gå i stykker ;
}
ellers {
cout << 'Vennligst skriv inn informasjonen til noden' << Jeg << ':' ;
spiser >> verdi ;
frontNode - > verdi = verdi ;
frontNode - > nesteNodePtr = NULL ;
tempNode - > nesteNodePtr = frontNode ;
tempNode = tempNode - > nesteNodePtr ;
}
}
}
}
tomrom reverseLinkedList ( node ** nodeObject ) {
struktur node * tempNode = NULL ;
struktur node * forrigeNode = NULL ;
struktur node * gjeldende node = ( * nodeObject ) ;
samtidig som ( gjeldende node ! = NULL ) {
tempNode = gjeldende node - > nesteNodePtr ;
gjeldende node - > nesteNodePtr = forrigeNode ;
forrigeNode = gjeldende node ;
gjeldende node = tempNode ;
}
( * nodeObject ) = forrigeNode ;
}
tomrom vise ( ) {
struktur node * tempNode ;
hvis ( nodeObject == NULL ) {
cout << 'Linket liste er tom' ;
}
ellers {
tempNode = nodeObject ;
samtidig som ( tempNode ! = NULL )
{
cout << tempNode - > verdi << ' \t ' ;
tempNode = tempNode - > nesteNodePtr ;
}
}
cout << endl ;
}
Produksjon
Hvor mange noder vil du opprette =>: 6Vennligst skriv inn informasjonen til node 1 (kun nummer): 101
Vennligst skriv inn informasjonen til node 2: 95
Vennligst skriv inn informasjonen til node 3: 61
Vennligst skriv inn informasjonen til node 4: 19
Vennligst skriv inn informasjonen til node 5: 12
Vennligst skriv inn informasjonen til node 6: 11
Informasjon i den tilknyttede listen:
101 95 61 19 12 11
Linket liste etter reversert
11 12 19 61 95 101
Konklusjon
Denne LinuxHint-artikkelen har gjennomgått hvordan du kan reversere en koblet liste i C++. Det er noen andre metoder for å reversere en koblet liste, men dette er en veldig vanlig metode for å reversere en koblet liste. Det er opp til deg å bestemme hvordan du vil løse problemene dine, men generelt bør funksjonen for omvendt lenket liste være en enkel sløyfe med pekerbytte.