linkitetty lista: Tämä on linkitetty luettelo, jonka haluamme muuttaa.
Käänteisen linkitetyn luettelon jälkeen: Alla on tulos, kun yllä linkitetty luettelo on käännetty.
Yllä olevassa esimerkkikaaviossa näemme, että pääsolmu ja häntäsolmu vaihtavat sijaintiaan, kun käännämme linkitettyjen luettelon. Pääsolmu, joka on nyt häntäsolmu, osoittaa nollasolmuun, koska se on nyt häntäsolmu.
Algoritmin vaiheet
- Luomme päämenetelmän ja määrittelemme joitain vaadittuja muuttujia.
- Sitten seuraava askel on luoda menetelmä, jolla voidaan luoda linkitetty luettelo. Tämä menetelmä auttaa meitä luomaan linkitetyn luettelon.
- Seuraava vaihe on luoda menetelmä linkitetyn luettelon kääntämiseksi. Tässä menetelmässä välitämme koko linkitetyn luettelon, ja tämä menetelmä kumoaa linkitetyn luettelon.
- Nyt tarvitsemme toisen menetelmän tuloksemme näyttämiseksi sen kääntämisen jälkeen.
- Yhdistämme kaikki edellä mainitut menetelmät päämenetelmäämme.
Selitämme käänteisen linkitettyjen luettelon käyttämällä jotain kuvallista muotoa, jotta se olisi helpompi ymmärtää. Aloitetaan siis esimerkistä.
Alla on linkitetty luettelo, jonka haluamme muuttaa.
Vaihe 1 . Vihreä solmu on pääsolmu, joka osoittaa käynnistyksen ensimmäiseen solmuun.
Vaihe 2. Seuraavassa vaiheessa kuljemme koko linkitetyn luettelon läpi, kunnes emme saa nolla-osoitinta otsikkosolmun viereen. Tätä varten aiomme antaa seuraavalle solmulle väliaikaisen nimen alla olevan kaavion mukaisesti.
Vaihe 3. Koska meillä on uusi viitesolmu nimeltä 'väliaikainen', joka voi auttaa meitä kulkemaan koko linkitetyn luettelon läpi, kunnes emme saa nollaosoitinta, joten voimme asettaa otsikkosolmun seuraavan linkin tyhjäksi, mikä ei vaikuta linkitettyyn luettelo alla olevan kaavion mukaisesti. Nykyisen solmun vieressä olevaa nollaosoitinta kutsutaan edelliseksi solmuksi.
Vaihe 4. Nyt siirrämme väliaikaisen solmun seuraavaan solmuun ja nykyisen solmun edelliseen väliaikaiseen solmuun. Joten nyt olemme siirtyneet seuraavaan solmuun. Muutamme myös edellisen solmun nollasta vain nykyisen solmun edelliseen solmuun. Joten nyt väliaikainen solmu hoitaa kaikki poikkikäynnit nollaosoittimeen asti, jotta voimme asettaa nykyisen solmun linkin edelliseen solmuun, ja nyt se osoittaa edelliseen solmuun, kuten alla olevasta kaaviosta näkyy.
Joten noudatamme samoja vaiheita ja viimein saamme käänteisen linkitettyjen luettelon.
Vaihe 5 .
Vaihe 6.
Vaihe 7.
Vaihe 8.
Vaihe 9.
Vaihe 10.
Vaihe 11.
Vaihe 12.
Vaihe 13.
Vaihe 14. Tässä vaiheessa linkitetty luettelomme muuttui päinvastaiseksi.
C++-ohjelma kääntääksesi linkitetyn luettelon
#includekäyttämällä nimiavaruus std ;
// Solmun luontimenetelmä
struct solmu {
int arvo ;
solmu * nextNodePtr ;
} * nodeObject ;
mitätön CreateLinkedList ( int n ) ;
mitätön reverseLinkedList ( solmu ** nodeObject ) ;
mitätön näyttö ( ) ;
int pää ( ) {
int n,arvo,tuote ;
cout << 'Kuinka monta solmua haluat luoda =>: ' ;
syöminen >> n ;
CreateLinkedList ( n ) ;
cout << ' \n Tiedot linkitetyssä listassa: \n ' ;
näyttö ( ) ;
cout << ' \n Linkitetty lista kääntämisen jälkeen \n ' ;
reverseLinkedList ( & nodeObject ) ;
näyttö ( ) ;
palata 0 ;
}
// Tämä menetelmä luo linkitetyn luettelon
mitätön CreateLinkedList ( int n ) {
struct solmu * frontNode, * tempNode ;
int arvo, ts ;
nodeObject = ( struct solmu * ) malloc ( koko ( struct solmu ) ) ;
jos ( nodeObject == TYHJÄ )
cout << 'Ei riitä muistin keräämiseen' ;
muu {
cout << 'Anna solmun 1 tiedot (vain numero): ' ;
syöminen >> arvo ;
nodeObject - > arvo = arvo ;
nodeObject - > nextNodePtr = TYHJÄ ;
tempNode = nodeObject ;
varten ( i = kaksi ; i <= n ; i ++ ) {
etusolmu = ( struct solmu * ) malloc ( koko ( struct solmu ) ) ;
// Kun linkitetyssä luettelossa ei ole solmua
jos ( etusolmu == TYHJÄ ) {
cout << 'Muistia ei voi varata' ;
tauko ;
}
muu {
cout << 'Anna solmun tiedot' << i << ':' ;
syöminen >> arvo ;
etusolmu - > arvo = arvo ;
etusolmu - > nextNodePtr = TYHJÄ ;
tempNode - > nextNodePtr = etusolmu ;
tempNode = tempNode - > nextNodePtr ;
}
}
}
}
mitätön reverseLinkedList ( solmu ** nodeObject ) {
struct solmu * tempNode = TYHJÄ ;
struct solmu * edellinenSolmu = TYHJÄ ;
struct solmu * nykyinenSolmu = ( * nodeObject ) ;
sillä aikaa ( nykyinenSolmu ! = TYHJÄ ) {
tempNode = nykyinenSolmu - > nextNodePtr ;
nykyinenSolmu - > nextNodePtr = edellinenSolmu ;
edellinenSolmu = nykyinenSolmu ;
nykyinenSolmu = tempNode ;
}
( * nodeObject ) = edellinenSolmu ;
}
mitätön näyttö ( ) {
struct solmu * tempNode ;
jos ( nodeObject == TYHJÄ ) {
cout << 'Linkitetty lista on tyhjä' ;
}
muu {
tempNode = nodeObject ;
sillä aikaa ( tempNode ! = TYHJÄ )
{
cout << tempNode - > arvo << ' \t ' ;
tempNode = tempNode - > nextNodePtr ;
}
}
cout << endl ;
}
Lähtö
Kuinka monta solmua haluat luoda =>: 6Anna solmun 1 tiedot (vain numero): 101
Anna solmun 2 tiedot: 95
Anna solmun 3 tiedot: 61
Anna solmun 4 tiedot: 19
Anna solmun 5 tiedot: 12
Anna solmun 6 tiedot: 11
Tiedot linkitetyssä listassa:
101 95 61 19 12 11
Linkitetty lista kääntämisen jälkeen
11 12 19 61 95 101
Johtopäätös
Tässä LinuxHint-artikkelissa on tarkasteltu, kuinka linkitetty luettelo voidaan kääntää C++:ssa. Linkitetyn luettelon kumoamiseen on joitakin muita menetelmiä, mutta tämä on hyvin yleinen tapa peruuttaa linkitetty luettelo. On sinun päätettävissäsi, kuinka haluat ratkaista ongelmasi, mutta yleensä käänteisen linkityksen luettelotoiminnon tulisi olla yksinkertainen silmukka, jossa on osoittimen vaihto.