povezan seznam: To je povezan seznam, ki ga želimo obrniti.
Po obrnjenem povezanem seznamu: Spodnji rezultat bo rezultat po obračanju zgoraj povezanega seznama.
V zgornjem primeru diagrama lahko vidimo, da glavno vozlišče in repno vozlišče spremenita svoja položaja, ko obrnemo povezani seznam. Glavno vozlišče, ki je zdaj repno vozlišče, kaže na ničelno vozlišče, ker je zdaj repno vozlišče.
Koraki algoritma
- Ustvarimo glavno metodo in deklariramo nekaj zahtevanih spremenljivk.
- Nato je naš naslednji korak ustvariti metodo, ki lahko ustvari povezan seznam. Ta metoda nam pomaga ustvariti povezan seznam.
- Naslednji korak je ustvariti metodo za obračanje povezanega seznama. Pri tej metodi posredujemo celoten povezan seznam, ta metoda pa bo povezani seznam obrnila.
- Zdaj potrebujemo drugo metodo za prikaz našega rezultata po tem, ko smo ga razveljavili.
- Vse te zgornje metode bomo združili v našo glavno metodo.
Obrnjeni povezani seznam bomo razložili z neko slikovno obliko, da ga bomo lažje razumeli. Pa začnimo s primerom.
Spodaj je povezan seznam, ki ga želimo obrniti.
Korak 1 . Zeleno obarvano vozlišče je glavno vozlišče, ki kaže na prvo vozlišče v zagonu.
2. korak V naslednjem koraku bomo prečkali celoten povezani seznam, dokler ne bomo dobili ničelnega kazalca poleg vozlišča glave. Za to bomo naslednjemu vozlišču dodelili začasno ime, kot je prikazano na spodnjem diagramu.
3. korak Ker imamo novo referenčno vozlišče z imenom »začasno«, ki nam lahko pomaga prečkati celoten povezan seznam, dokler ne dobimo ničelnega kazalca, lahko naslednjo povezavo vozlišča glave nastavimo kot ničelno, kar ne bo vplivalo na povezano seznam, kot je prikazano na spodnjem diagramu. Ničelni kazalec poleg trenutnega vozlišča se imenuje prejšnje vozlišče.
4. korak Zdaj premaknemo začasno vozlišče v naslednje vozlišče in trenutno vozlišče v prejšnje začasno vozlišče. Zdaj smo se premaknili na naslednje vozlišče. Prav tako spremenimo prejšnje vozlišče iz ničelnega v samo prejšnje vozlišče trenutnega vozlišča. Tako bo zdaj začasno vozlišče poskrbelo za vsa prečkanja do ničelnega kazalca, tako da lahko nastavimo povezavo trenutnega vozlišča s prejšnjim vozliščem, zdaj pa kaže na prejšnje vozlišče, kot je prikazano na spodnjem diagramu.
Zato sledimo istim korakom in na koncu bomo dobili obrnjen povezan seznam.
5. korak .
6. korak
korak 7.
8. korak.
9. korak.
10. korak.
korak 11.
12. korak.
13. korak.
14. korak. V tem koraku se je naš povezani seznam obrnil.
Program C++ za obračanje povezanega seznama
#includeuporabo imenski prostor std ;
// Metoda za ustvarjanje vozlišča
struct vozlišče {
int vrednost ;
vozlišče * nextNodePtr ;
} * nodeObject ;
praznina createLinkedList ( int n ) ;
praznina reverseLinkedList ( vozlišče ** nodeObject ) ;
praznina zaslon ( ) ;
int glavni ( ) {
int n,vrednost,postavka ;
cout << 'Koliko vozlišč želite ustvariti =>:' ;
prehranjevanje >> n ;
createLinkedList ( n ) ;
cout << ' \n Informacije na povezanem seznamu: \n ' ;
zaslon ( ) ;
cout << ' \n Povezan seznam po obrnjenem \n ' ;
reverseLinkedList ( & nodeObject ) ;
zaslon ( ) ;
vrnitev 0 ;
}
// Ta metoda bo ustvarila povezan seznam
praznina createLinkedList ( int n ) {
struct vozlišče * frontNode, * tempNode ;
int vrednost, i ;
nodeObject = ( struct vozlišče * ) malloc ( sizeof ( struct vozlišče ) ) ;
če ( nodeObject == NIČ )
cout << 'Nezadostno, da bi se obremenjeval s spominom' ;
drugače {
cout << 'Prosimo, vnesite podatke o vozlišču 1 (samo številka): ' ;
prehranjevanje >> vrednost ;
nodeObject - > vrednost = vrednost ;
nodeObject - > nextNodePtr = NIČ ;
tempNode = nodeObject ;
za ( jaz = dva ; jaz <= n ; jaz ++ ) {
frontNode = ( struct vozlišče * ) malloc ( sizeof ( struct vozlišče ) ) ;
// Ko na povezanem seznamu ni nobenega vozlišča
če ( frontNode == NIČ ) {
cout << 'Pomnilnik ni mogoče dodeliti' ;
odmor ;
}
drugače {
cout << 'Prosimo, vnesite podatke o vozlišču ' << jaz << ':' ;
prehranjevanje >> vrednost ;
frontNode - > vrednost = vrednost ;
frontNode - > nextNodePtr = NIČ ;
tempNode - > nextNodePtr = frontNode ;
tempNode = tempNode - > nextNodePtr ;
}
}
}
}
praznina reverseLinkedList ( vozlišče ** nodeObject ) {
struct vozlišče * tempNode = NIČ ;
struct vozlišče * prejšnje vozlišče = NIČ ;
struct vozlišče * currentNode = ( * nodeObject ) ;
medtem ( currentNode ! = NIČ ) {
tempNode = currentNode - > nextNodePtr ;
currentNode - > nextNodePtr = prejšnje vozlišče ;
prejšnje vozlišče = currentNode ;
currentNode = tempNode ;
}
( * nodeObject ) = prejšnje vozlišče ;
}
praznina zaslon ( ) {
struct vozlišče * tempNode ;
če ( nodeObject == NIČ ) {
cout << 'Seznam povezav je prazen' ;
}
drugače {
tempNode = nodeObject ;
medtem ( tempNode ! = NIČ )
{
cout << tempNode - > vrednost << ' \t ' ;
tempNode = tempNode - > nextNodePtr ;
}
}
cout << konec ;
}
Izhod
Koliko vozlišč želite ustvariti =>: 6Vnesite podatke vozlišča 1 (samo številka): 101
Vnesite podatke o vozlišču 2: 95
Vnesite podatke o vozlišču 3: 61
Vnesite podatke o vozlišču 4: 19
Vnesite podatke o vozlišču 5: 12
Vnesite podatke o vozlišču 6: 11
Informacije na povezanem seznamu:
101 95 61 19 12 11
Povezan seznam po obrnjenem
11 12 19 61 95 101
Zaključek
Ta članek LinuxHint je pregledal, kako obrniti povezan seznam v C++. Obstaja nekaj drugih metod za razveljavitev povezanega seznama, vendar je to zelo pogosta metoda za razveljavitev povezanega seznama. Na vas je, da se odločite, kako želite rešiti svoje težave, vendar mora biti na splošno funkcija vzvratno povezanega seznama preprosta zanka z zamenjavami kazalcev.