povezani popis: Ovo je povezani popis koji želimo obrnuti.
Nakon obrnutog povezanog popisa: Dolje će biti rezultat nakon okretanja gore povezanog popisa.
U gornjem primjeru dijagrama možemo vidjeti da glavni čvor i repni čvor mijenjaju svoje položaje kada preokrenemo povezanu listu. Glavni čvor, koji je sada repni čvor, pokazuje na nulti čvor jer je sada repni čvor.
Koraci algoritma
- Kreiramo glavnu metodu i deklariramo neke potrebne varijable.
- Zatim, naš sljedeći korak je stvaranje metode koja može stvoriti povezani popis. Ova metoda nam pomaže da stvorimo povezani popis.
- Sljedeći korak je stvaranje metode za preokretanje povezanog popisa. U ovoj metodi prosljeđujemo cijeli povezani popis, a ova metoda će obrnuti povezani popis.
- Sada nam treba druga metoda za prikaz našeg rezultata nakon što ga poništimo.
- Kombinirat ćemo sve gore navedene metode u našu glavnu metodu.
Objasnit ćemo obrnuti povezani popis koristeći neki slikovni oblik kako bismo ga lakše razumjeli. Pa počnimo s primjerom.
Dolje je povezan popis koji želimo obrnuti.
Korak 1 . Čvor zelene boje je glavni čvor koji pokazuje na prvi čvor u pokretanju.
Korak 2. U sljedećem koraku, proći ćemo kroz cijeli povezani popis sve dok ne dobijemo nulti pokazivač pored čvora zaglavlja. Za to ćemo sljedećem čvoru dodijeliti privremeno ime, kao što je prikazano na donjem dijagramu.
3. korak Budući da imamo novi referentni čvor pod nazivom 'privremeni', koji nam može pomoći da prođemo cijelim povezanim popisom dok ne dobijemo nulti pokazivač, tako da možemo postaviti sljedeću vezu čvora zaglavlja kao null, što neće utjecati na povezani popis kao što je prikazano na dijagramu ispod. Nulti pokazivač pored trenutnog čvora naziva se prethodni čvor.
Korak 4. Sada premještamo privremeni čvor na sljedeći čvor, a trenutni čvor na prethodni privremeni čvor. Sada smo prešli na sljedeći čvor. Također mijenjamo prethodni čvor iz null u samo prethodni čvor trenutnog čvora. Dakle, sada će se privremeni čvor pobrinuti za sve obilaske do nultog pokazivača tako da možemo postaviti vezu trenutnog čvora na prethodni čvor, a sada pokazuje na prethodni čvor, kao što je prikazano na donjem dijagramu.
Stoga slijedimo iste korake i na kraju ćemo dobiti obrnuti povezani popis.
Korak 5 .
Korak 6.
Korak 7.
Korak 8.
Korak 9.
Korak 10.
Korak 11.
Korak 12.
Korak 13.
Korak 14. U ovom se koraku naš povezani popis obrnuo.
C++ program za okretanje povezanog popisa
#includekorištenjem imenski prostor std ;
// Metoda za stvaranje čvora
strukturirati čvor {
int vrijednost ;
čvor * nextNodePtr ;
} * nodeObject ;
poništiti createLinkedList ( int n ) ;
poništiti reverseLinkedList ( čvor ** nodeObject ) ;
poništiti prikaz ( ) ;
int glavni ( ) {
int n,vrijednost,stavka ;
cout << 'Koliko čvorova želite stvoriti =>: ' ;
jelo >> n ;
createLinkedList ( n ) ;
cout << ' \n Informacije na povezanom popisu: \n ' ;
prikaz ( ) ;
cout << ' \n Povezani popis nakon obrnutog \n ' ;
reverseLinkedList ( i nodeObject ) ;
prikaz ( ) ;
povratak 0 ;
}
// Ova metoda će stvoriti povezani popis
poništiti createLinkedList ( int n ) {
strukturirati čvor * prednji čvor, * tempNode ;
int vrijednost, i ;
nodeObject = ( strukturirati čvor * ) malloc ( veličina ( strukturirati čvor ) ) ;
ako ( nodeObject == NULL )
cout << 'Nedovoljno za pamćenje' ;
drugo {
cout << 'Molimo unesite informacije o čvoru 1 (samo broj): ' ;
jelo >> vrijednost ;
nodeObject - > vrijednost = vrijednost ;
nodeObject - > nextNodePtr = NULL ;
tempNode = nodeObject ;
za ( ja = dva ; ja <= n ; ja ++ ) {
frontNode = ( strukturirati čvor * ) malloc ( veličina ( strukturirati čvor ) ) ;
// Kada nema niti jednog čvora na povezanom popisu
ako ( frontNode == NULL ) {
cout << 'Memorija se ne može dodijeliti' ;
pauza ;
}
drugo {
cout << 'Molimo unesite podatke o čvoru' << ja << ':' ;
jelo >> vrijednost ;
frontNode - > vrijednost = vrijednost ;
frontNode - > nextNodePtr = NULL ;
tempNode - > nextNodePtr = frontNode ;
tempNode = tempNode - > nextNodePtr ;
}
}
}
}
poništiti reverseLinkedList ( čvor ** nodeObject ) {
strukturirati čvor * tempNode = NULL ;
strukturirati čvor * prethodničvor = NULL ;
strukturirati čvor * trenutni čvor = ( * nodeObject ) ;
dok ( trenutni čvor ! = NULL ) {
tempNode = trenutni čvor - > nextNodePtr ;
trenutni čvor - > nextNodePtr = prethodničvor ;
prethodničvor = trenutni čvor ;
trenutni čvor = tempNode ;
}
( * nodeObject ) = prethodničvor ;
}
poništiti prikaz ( ) {
strukturirati čvor * tempNode ;
ako ( nodeObject == NULL ) {
cout << 'Linkedlist je prazan' ;
}
drugo {
tempNode = nodeObject ;
dok ( tempNode ! = NULL )
{
cout << tempNode - > vrijednost << ' \t ' ;
tempNode = tempNode - > nextNodePtr ;
}
}
cout << endl ;
}
Izlaz
Koliko čvorova želite stvoriti =>: 6Unesite podatke o čvoru 1 (samo broj): 101
Unesite informacije o čvoru 2: 95
Unesite informacije o čvoru 3: 61
Unesite informacije o čvoru 4: 19
Unesite informacije o čvoru 5: 12
Unesite informacije o čvoru 6: 11
Informacije na povezanom popisu:
101 95 61 19 12 11
Povezani popis nakon obrnutog
11 12 19 61 95 101
Zaključak
Ovaj LinuxHint članak je pregledao kako preokrenuti povezani popis u C++. Postoje neke druge metode za poništavanje povezanog popisa, ali ovo je vrlo uobičajena metoda za poništavanje povezanog popisa. Na vama je da odlučite kako želite riješiti svoje probleme, ali općenito funkcija obrnuto povezane liste trebala bi biti jednostavna petlja sa zamjenom pokazivača.