Diskuze: swap node v double linked liste

C++ C a C++ swap node v double linked liste

Avatar
saeQ
Člen
Avatar
saeQ:

Ahoj , ucim sa spojove zoznamy a snazim sa spravit metodu , ktora swapne dva nody. Kedze sa mi nedarilo , hladal som spravne riesenie a nasiel som jedno ktore si neviem vysvetlit.
Node vyrera nasledovne

struct Node{
     string name;
     string value;
     Node * next_node;
     Node * prev_node;
}

Riesenie ktore som nasiel je nasledovne

Node *first;   // ukazuje na prvy prvovk v liste
Node *last;  // ukauje na posledny prvok v liste
void swapNodes( string name ){
        Node *one = first;
        Node *two = first;
        while( one ){
        if( one -> name == name ){
                return;
        }
        one = one -> next_node;
        }
        while( two ){
        if( two-> name == name ){
                return;
        }
        two = two -> next_node;
        }

        Node **pnpone;   // ptr to next ptr to one
        Node **pppone;   // ptr to prev ptr to one
        Node **pnptwo;   // ptr to next ptr to two
        Node **ppptwo;   // ptr to prev ptr to two

        if(one->prev_node)
              pnpone = &(one->prev_node->next_node);
        else
                pnpone = &first;
        if(one->next_node)
                pppone = &(one->next_node->prev_node);
        else
                pppone = &last;
        if(two->prev_node)
                pnptwo = &(two->prev_node->next_node);
        else
                pnptwo = &first;
        if(two->next_node)
                ppptwo = &(two->next_node->prev_node);
        else
                ppptwo = &last;
        std::swap(*pnpone, *pnptwo);
        std::swap(*pppone, *ppptwo);
        std::swap(one->prev_node, two->prev_node);
        std::swap(one->next_node, two->next_node);
}

Nejako si neviem vysvetlit ten pointer na pointer a swap.

ak zobereme list ktory vyzera

name : jedna                name:dva                name:tri                name:styri
value ; 1           value:2         value:3         value:4

a chcem swapnut 1 a 3 tak potom
pnpone = ukazuje na pamat kde je pointer ktory ukazuje na first
pppone = ukazuje na pamat kde je pointer ktory ukazuje na 1
pnptwo = ukazuje na pamat kde je pointer ktory ukazuje 3
ppptwo = ukazuje na pamat kde je pointer ktory ukazuje 3

Ked teraz pouzijeme swap
tak

std::swap(*pnpone, *pnptwo);

spravi to , ze pamat v ktorej bolo first je teraz 3

std::swap(*pppone, *ppptwo);

spravi to , iste , preto nechapem preco je to tam dva krat , teda tu to reversuje prvy swap takze akoby tam ani jeden swap nebol? Prvy swapne , druhy swapne naspat?

std::swap(one->prev_node, two->prev_node);
std::swap(one->next_node, two->next_node);

toto swapne vnutorne pointeri , toto chapem.
Co mi vsak do hlavy nejde pri liste ktory som znazornl hore ak swpanem tymto kodom 1 a 3 , tak 2 -> next_node stale ukazuje na 3 a nie na 1 takze sa cely spojak neprejde. Nikde sa tu nemanipuluje s s next nodami prev a prev nodeami next nodov.

Ale tento kod funguje ako ma , preto usudzujem ze ho chapem zle. Moze mi niekto prosim vysvetlit prosim kde som v mojom pochopeni spravil chybu?
Dik :)

 
Odpovědět 28. května 17:01
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 1 zpráv z 1.