Domanda incatenare nodo ad una coda con puntatori, problema logico nel incatenare un nodo ad un altro.

[l3rn]

sto da poco studiando le strutture lifo in c++, ed ho trovato un problema di natura logica mia personale che non mi da pace:
questa funzione serve per aggiungere nodi alla coda, delineando prima il nodo inizio con

if(coda_vuota(frente)){
        inizio = nuovo_nodo;
    }

dopo con else aggiungo il resto di nodi e faccio equivalere la fine a nuovo_ nodo,

else{
        fine->prossimo = nuovo_nodo;
    }
    fine = nuovo_nodo;

la mia domanda è: se facciamo fine->prossimo = nuovo_nodo, e poi fuori da else fine = nuovo_nodo; Non perderemmo ciò che abbiamo inserito in precedenza con fine-> prossimo = nuovo_nodo , poiché il nuovo valore di fine è nuovo_nodo e nuovo_nodo->prossimo è uguale a NULL?

vi lascio qui la funzione per intero:

void insertCoda(Nodo *&inizio,Nodo *&fine,int n){
    Nodo *nuovo_nodo = new Nodo();

    nuovo_nodo->dato = n;
    nuovo_nodo->prossimo = NULL;

    if(coda_vuota(inizio)){
        inizio = nuovo_nodo;
    }
    else{
        fine->prossimo = nuovo_nodo;
    }
    fine = nuovo_nodo;
}

e qui l'algoritmo completo:

#include<iostream>
#include<conio.h>
#include<stdlib.h>

using namespace std;

struct Nodo{
    int dato;
    Nodo *prossimo;
};

void insertCoda(Nodo *&,Nodo *&,int);
bool coda_vuota(Nodo *);
int main(){
    Nodo *inizio = NULL;
    Nodo *fine = NULL;

    int dato;

    cout<<"digita un numero: ";
    cin>>dato;
    insertCoda(inizio,fine,dato);

    cout<<"digita un numero: ";
    cin>>dato;
    insertCoda(inizio,fine,dato);

    cout<<"digita un numero: ";
    cin>>dato;
    insertCoda(inizio,fine,dato);




    getch();
    return 0;
}

void insertCoda(Nodo *&inizio,Nodo *&fine,int n){
    Nodo *nuovo_nodo = new Nodo();

    nuovo_nodo->dato = n;
    nuovo_nodo->prossimo = NULL;

    if(coda_vuota(inizio)){
        inizio = nuovo_nodo;
    }
    else{
        fine->prossimo = nuovo_nodo;
    }
    fine = nuovo_nodo;


}

bool coda_vuota(Nodo *inizio){
    return (inizio==NULL)? true : false;
}

 

[St3ve]

la mia domanda è: se facciamo fine->prossimo = nuovo_nodo, e poi fuori da else fine = nuovo_nodo; Non perderemmo ciò che abbiamo inserito in precedenza con fine-> prossimo = nuovo_nodo , poiché il nuovo valore di fine è nuovo_nodo e nuovo_nodo->prossimo è uguale a NULL?

1. siamo nel main e abbiamo inizio e fine che valgono NULL
2. inseriamo un nuovo elemento in coda con insertCoda(inizio, fine, 1)
   • siamo nella funzione insertCoda e creiamo nuovo_nodo che, per il momento, sta per i cavoli suoi slegato dal resto
   • dato che la coda è vuota cambiamo inizio e fine (gli stessi del main) in modo tale che siano nuovo_nodo (i.e., puntano alla stessa cosa)
3. siamo nel main e abbiamo inizio e fine (variabili distinte) che sono uguali (dato = 1 e prossimo = NULL)
4. inseriamo un nuovo elemento in coda con insertCoda(inizio, fine, 2)
   • siamo nella funzione insertCoda e creiamo nuovo_nodo che, per il momento, sta per i cavoli suoi slegato dal resto
   • dato che la coda non è vuota, facciamo fine->prossimo = nuovo_nodo
   • visto che fine e inizio puntano alla stessa cosa, ora anche inizio->prossimo = nuovo_nodo
   • cambiamo fine = nuovo_nodo (i.e., gli assegnamo un nuovo valore)

A questo punto, chiaramente, abbiamo: inizio->dato = 1, fine->dato = 2 e fine->prossimo = NULL. In inizio->prossimo, per il penultimo punto che ti ho scritto, abbiamo l'ultimo nuovo_nodo che abbiamo creato... ma questo è proprio il valore che abbiamo dato a fine, quindi inizio->prossimo = fine (i.e., inizio->prossimo e fine puntano alla stessa cosa). Se proseguiamo:

1. siamo nel main e abbiamo inizio e fine che hanno i valori che abbiamo appena discusso
2. inseriamo un nuovo elemento in coda con insertCoda(inizio, fine, 3)
   • siamo nella funzione insertCoda e creiamo nuovo_nodo che, per il momento, sta per i cavoli suoi slegato dal resto
   • dato che la coda non è vuota, facciamo fine->prossimo = nuovo_nodo
   • visto che fine e inizio->prossimo erano la (a.k.a, puntavano alla) stessa cosa, ora anche inizio->prossimo->prossimo = nuovo_nodo
   • cambiamo fine = nuovo_nodo

Chiaramente: inizio->dato = 1, fine->dato = 3 e fine->prossimo = NULL. Il secondo nodo che abbiamo inserito (con dato = 2) ce l'abbiamo ancora in inizio->prossimo; quindi inizio->prossimo->dato = 2 e, come abbiamo già notato, inizio->prossimo->prossimo = fine (ovvero: inizio->prossimo->prossimo->dato = 3 e inizio->prossimo->prossimo->prossimo = NULL).

Ora che abbiamo fatto tutte queste considerazioni, per rispondere in modo più diretto alla tua domanda, non perdiamo ciò che abbiamo inserito in precedenza perché

• inizio e fine sono due variabili mentre inizio->prossimo e fine->prossimo sono altre due variabili
• inizio e fine dentro al main sono proprio le stesse variabili chiamate inizio e fine dentro insertCoda (per via del puntatore al riferimento)
• con inizio = nuovo_nodo, fine->prossimo = nuovo_nodo e fine = nuovo_nodo stiamo assegnando un valore, non stiamo dicendo che sono la stessa variabile (e.g., a = 0, b = a e a = 7, non ti porta ad avere b = 7) quindi vale il terzo pallino nella seconda considerazione.

Pensaci su e fammi sapere se è tutto chiaro, è normale che fai un po' di fatica a capire come funzionano i puntatori.

 

[DispatchCode]

Visto che ha già detto tutto St3ve, faccio solo notare una piccolezza. La funzione coda_vuota puoi modificarla togliendo l'if, in quanto il valore risultante dal confronto è già un bool:

bool coda_vuota(Nodo *inizio){
    return (inizio==NULL);
}

 

[l3rn]

visto che fine e inizio puntano alla stessa cosa, ora anche inizio->prossimo = nuovo_nodo

grazie per la spiegazione, ma adesso ho un altro dubbio: non ho ben capito questa parte, perché inizio->prossimo dovrebbe puntare a nuovo_nodo (quello con il valore di 2..credo) solo perché fine->prossimo punta a quel valore?

Messaggio unito automaticamente: 22 Gennaio 2021

Visto che ha già detto tutto St3ve, faccio solo notare una piccolezza. La funzione coda_vuota puoi modificarla togliendo l'if, in quanto il valore risultante dal confronto è già un bool:

bool coda_vuota(Nodo *inizio){
    return (inizio==NULL);
}

grazie per il suggerimento

 

[St3ve]

grazie per la spiegazione, ma adesso ho un altro dubbio: non ho ben capito questa parte, perché inizio->prossimo dovrebbe puntare a nuovo_nodo (quello con il valore di 2..credo) solo perché fine->prossimo punta a quel valore?

Abbiamo un elemento nella lista e ne vogliamo aggiungere un altro. In questo momento abbiamo inizio e fine che puntano allo stesso nodo, quindi se modifichiamo fine->prossimo (o fine->dato) modifichiamo anche inizio->prossimo (o inizio->dato); tuttavia, ti ricordo che inizio e fine sono due variabili diverse quindi se facciamo fine = nuovo_nodo il valore di inizio non viene modificato. L'unica cosa che hanno in comune è che in quel preciso momento hanno lo stesso valore, ovvero puntano allo stesso indirizzo di memoria, ma non sarà più così man mano che aggiungiamo elementi nella lista

• inizialmente inizio = fine = NULL;
• poi aggiungiamo un nodo e inizio = fine;
• poi aggiungiamo un altro nodo e inizio->prossimo = fine;
• poi aggiungiamo un altro nodo e inizio->prossimo->prossimo = fine;
• poi aggiungiamo un altro nodo e inizio->prossimo->prossimo->prossimo = fine;
• etcetera etcetera...

Quando aggiungiamo l'ennesimo nodo prendiamo il valore di fine allo step precedente (che è lo stesso valore puntato da inizio->prossimo->prossimo->...->prossimo), gli accodiamo un prossimo e assegnamo un nuovo valore fine (che è una variabile a se stante, quindi assegnargli un valore non modifica inizio->prossimo->prossimo->...->prossimo).

Devi riflettere bene sul concetto di variabili diverse che puntano allo stesso valore: assegnare un altro valore alla variabile la porta a puntare ad un altro valore e non modifica nient'altro, ma nel momento in cui usi l'operatore -> ti stai riferendo all'area di memoria puntata (che può essere osservata da più variabili) e una modifica a quel valore viene osservata anche dalle altre variabili che puntano in quell'area di memoria.