[C] Struct, puntatori e liste

[Ryuzaki_Eru]

Sto studiando le liste e ho una situazione di questo tipo:

struct node{
int info;
struc node *next;
};

typedef struct node ElementoDiLista;
typedef ElementoDiLista* ListaDiElementi;

Ora voglio creare una lista composta da tre nodi, ma invece di dichiarare delle variabili struct node e poi usare l'operatore punto, uso i puntatori:

ListaDiElementi aux, lista;

aux = malloc(Sizeof(ElementoDiLista));
aux->info = 15;
lista = aux;
lista->next = NULL;

aux = malloc(Sizeof(ElementoDiLista));
aux->info = 10;
aux->next = lista;
lista = aux;

aux = malloc(Sizeof(ElementoDiLista));
aux->info = 5;
aux->next = lista;

lista = aux;

E fino a qua non ci sono particolari problemi, avevo solo dei dubbi riguardo l'allocazione della memoria. Nel senso: aux è di tipo ListaDiElementi, che altro non è un puntatore a struct node. malloc mi restituisce un puntatore a void che contiene l'indirizzo della memoria allocata, e come si sa il puntatore a voi lo posso applicare a variabili puntatore di qualunque tipo. Quando io faccio aux->info praticamente durante l'allocazione in memoria ho già un nodo "da riempire" giusto? Perchè l'unica spiegazione che ho trovato è questa.

Ma torniamo a noi, il problema è questo:
ho notato che in alcune funzioni, cioè in quelle che *non* devono modificare la lista, come argomento la funzione ha ListaDiElementi l. E quindi passiamo l'indirizzo alla lista. E fino a qua ci siamo.
Però, nelle funzioni che *modificano* la lista, come argomento abbiamo un puntatore a puntatore, cioè ListaDiElementi *l. Ora la mia domanda è semplice: perchè? La lista non la posso modificare usando il puntatore come nella prima funzione, invece di avere un puntatore a puntatore? Mi sa che mi sono perso qualcosa per strada.

[wingman87]

E fino a qua non ci sono particolari problemi, avevo solo dei dubbi riguardo l'allocazione della memoria. Nel senso: aux è di tipo ListaDiElementi, che altro non è un puntatore a struct node.
No, attenzione, non è un puntatore, è uno struct node, con typedef hai solo definito un nuovo nome per il tipo struct node
malloc mi restituisce un puntatore a void che contiene l'indirizzo della memoria allocata, e come si sa il puntatore a void lo posso applicare a variabili puntatore di qualunque tipo. Quando io faccio aux->info praticamente durante l'allocazione in memoria ho già un nodo "da riempire" giusto? Perchè l'unica spiegazione che ho trovato è questa.

Sì, è esatto. Forse alcuni compilatori ti danno un warning se non fai un cast esplicito da void* al tipo a cui lo vuoi convertire.

Ma torniamo a noi, il problema è questo:
ho notato che in alcune funzioni, cioè in quelle che *non* devono modificare la lista, come argomento la funzione ha ListaDiElementi l. E quindi passiamo l'indirizzo alla lista. E fino a qua ci siamo.
Però, nelle funzioni che *modificano* la lista, come argomento abbiamo un puntatore a puntatore, cioè ListaDiElementi *l. Ora la mia domanda è semplice: perchè? La lista non la posso modificare usando il puntatore come nella prima funzione, invece di avere un puntatore a puntatore? Mi sa che mi sono perso qualcosa per strada.
Dovresti chiederti cosa puoi fare in più con un doppio puntatore rispetto a un puntatore singolo. Nel primo caso la funzione potrebbe creare un nuovo nodo e assegnarlo al puntatore dereferenziato una sola volta. Nel secondo caso non è possibile fare una cosa del genere. In pratica ad esempio (esempio un po' stupido) puoi fare:
struct node* sostituisciNodo(struct node** n){
//Sostituisce il nodo passato come argomento con un nuovo nodo
//e restituisce il vecchio nodo
struct node* ret= *n;
*n=(struct node*)malloc(sizeof(struct node));
return ret;
}

void chiamante(){
...//Creo una nuova lista l
//Ora voglio sostituire la testa di l con un nuovo nodo e mettere il nodo rimosso in un'altra lista l2
addNode(&l2,sostituisciNodo(&l));
...
}

Scusa l'esempio un po' contorto ma non mi veniva nulla di meglio al momento...

[Ryuzaki_Eru]

No, attenzione, non è un puntatore, è uno struct node, con typedef hai solo definito un nuovo nome per il tipo struct node

In realtà, non vorrei dire una fesseria visto che il C lo sto studiando per l'università e non lo conosco ancora a fondo, però ListaDiElementi è un puntatore a struct node. Di conseguenza, dichiarando un ListaDiElementi aux, ottengo che aux è un puntatore a struct node.

Sì, è esatto. Forse alcuni compilatori ti danno un warning se non fai un cast esplicito da void* al tipo a cui lo vuoi convertire.


Esattamente, infatti in alcuni sorgenti che stavo studiando il prof usa il cast.
Ma la malloc in pratica mi mette in memoria il nodo "da riempire" perchè risale al fatto che aux è un puntatore a struct node?

Dovresti chiederti cosa puoi fare in più con un doppio puntatore rispetto a un puntatore singolo.

Ovviamente me lo sono chiesto, ma riguardo un doppio puntatore a int ad esempio la cosa mi è più chiara, con struct node no, perchè ho visto molti sorgenti dove in alcuni casi viene usato un solo puntatore e in altri un puntatore a puntatore.

Nel primo caso la funzione potrebbe creare un nuovo nodo e assegnarlo al puntatore dereferenziato una sola volta.

Come primo caso ti riferisci ad un solo puntatore?
In che senso potrebbe assegnarlo al puntatore dereferenziato una sola volta?

struct node* ret= *n;

n è un puntatore a puntatore giusto? Usando l'operatore di deferenziamento una sola volta, come in questo caso, ottengo un indirizzo giusto? L'indirizzo a cui punta il puntatore tecnicamente.

*n=(struct node*)malloc(sizeof(struct node));


Qua "cancelli" il puntatore a cui punta *n allocando una nuova area di memoria. Giusto?

addNode(&l2,sostituisciNodo(&l));

In questo caso hai passato l'indirizzo esplicitamente, nel caso però in cui ho una funzione con parametro ListaDiElementi l, passo semplicemente la lista, che altri non è che un indirizzo pure. Questa è la cosa che mi svia. Purtroppo non sono nella città dove studio quindi non ho nè il libro dietro, nè tutto il materiale che avevo appuntato. Sto cercando di andare a ragionamento e guardando qualche guida in rete(che fanno pena).

Però devo dirlo: il C anche se fa sbattere la testa insegna molto, infatti lo sto studiando anche per i fatti miei oltre che per l'uni :)

[wingman87]

In realtà, non vorrei dire una fesseria visto che il C lo sto studiando per l'università e non lo conosco ancora a fondo, però ListaDiElementi è un puntatore a struct node. Di conseguenza, dichiarando un ListaDiElementi aux, ottengo che aux è un puntatore a struct node.
Sì, scusa, ho detto una cazzata perché ho letto velocemente e ho pensato subito ad un errore classico



Esattamente, infatti in alcuni sorgenti che stavo studiando il prof usa il cast.
Ma la malloc in pratica mi mette in memoria il nodo "da riempire" perchè risale al fatto che aux è un puntatore a struct node?

Non proprio: malloc non sa nulla di ciò che stai andando ad allocare, solo la sua dimensione in byte, quindi quello che ti restituisce è il puntatore ad una locazione di memoria della dimensione che gli hai richiesto, come tu usi quella memoria malloc non lo sa.


Ovviamente me lo sono chiesto, ma riguardo un doppio puntatore a int ad esempio la cosa mi è più chiara, con struct node no, perchè ho visto molti sorgenti dove in alcuni casi viene usato un solo puntatore e in altri un puntatore a puntatore.

Spiego più avanti questo punto


Come primo caso ti riferisci ad un solo puntatore?
In che senso potrebbe assegnarlo al puntatore dereferenziato una sola volta?

No, doppio, come nell'esempio nell'assegnazione *n=...
Ma negli esempi sotto credo di essermi spiegato molto meglio



n è un puntatore a puntatore giusto? Usando l'operatore di deferenziamento una sola volta, come in questo caso, ottengo un indirizzo giusto? L'indirizzo a cui punta il puntatore tecnicamente.
Esatto (l'indirizzo a cui punta il puntatore puntato da n)


Qua "cancelli" il puntatore a cui punta *n allocando una nuova area di memoria. Giusto?
Diciamo che sovrascrivo l'indirizzo a cui puntava precedentemente il puntatore puntato da n(indirizzo che mi sono comunque copiato in ret)



In questo caso hai passato l'indirizzo esplicitamente, nel caso però in cui ho una funzione con parametro ListaDiElementi l, passo semplicemente la lista, che altri non è che un indirizzo pure. Questa è la cosa che mi svia. Purtroppo non sono nella città dove studio quindi non ho nè il libro dietro, nè tutto il materiale che avevo appuntato. Sto cercando di andare a ragionamento e guardando qualche guida in rete(che fanno pena).
Direi che il concetto fondamentale da capire è che in C il passaggio di parametri avviene sempre per copia. Il puntatore altro non è che un contenitore per un indirizzo, il tipo del puntatore ti dice che tipo di "oggetto" dovrebbe essere allocato a quell'indirizzo. Sia nel caso di un puntatore singolo che di un puntatore doppio questo può puntare al tipo definito a sinistra nella dichiarazione.
es:
int* p //p può puntare ad un int
struct node* p2 //p2 può puntare ad una struct node
ListaDiElementi* l //l può puntare ad una ListaDiElementi, cioè un struct node*
Ora facciamo degli esempi di chiamate di funzioni:
int a=10;
printf("%d",a);
scanf("%d",&a);
Nel primo caso quello che passo alla funzione printf è una copia del valore di a, questo comporta che il valore di a non sarà modificato in seguito alla chiamata, indipendentemente dalla funzione che ho richiamato.
Nel secondo invece ho passato la copia del suo indirizzo. La funzione scanf ha quindi accesso alla locazione di memoria in cui si trova il valore di a. Questo implica che dopo la chiamata il valore di a potrebbe essere stato modificato.
Ora invece facciamo un esempio analogo con le liste:
ListaDiElementi l=NULL; //l inizialmente è vuota (punta a NULL)
aggiungiInTesta(&l,11); //12 è l'info del nuovo nodo
aggiungiInTesta(&l,02);
aggiungiInTesta(&l,2010);
aggiungiInCoda(l,23);
Le chiamate ad aggiungiInTesta possono modificare il valore di l perché gli è stata passata la copia del suo indirizzo (quindi dopo le chiamate l non punterà più a NULL).
Al contrario l'ultima chiamata non può modificare il valore di l (questo implica che se la lista è vuota, cioè l==NULL non potrà essere aggiunto l'elemento) ma può agire sul nodo puntato da l (quindi di fatto, se l!=NULL è possibile aggiungere un elemento in fondo)


Però devo dirlo: il C anche se fa sbattere la testa insegna molto, infatti lo sto studiando anche per i fatti miei oltre che per l'uni :)
Anche a me è piaciuto studiarlo, specialmente all'università (lo conoscevo già dalle superiori ma non ce l'avevano spiegato granché bene).

[Ryuzaki_Eru]

Non proprio: malloc non sa nulla di ciò che stai andando ad allocare, solo la sua dimensione in byte, quindi quello che ti restituisce è il puntatore ad una locazione di memoria della dimensione che gli hai richiesto, come tu usi quella memoria malloc non lo sa.

Che malloc, ovviamente, non sa cosa alloca lo avevo intuito, ma allora mi chiedo: dopo aver allocato questo spazio di memoria, come fa aux ad accedere al campo info? Ha fatto un cast automatico al tipo di puntatore di aux(cioè struct list)?

Diciamo che sovrascrivo l'indirizzo a cui puntava precedentemente il puntatore puntato da n(indirizzo che mi sono comunque copiato in ret)

Si, intendevo questo.


Direi che il concetto fondamentale da capire è che in C il passaggio di parametri avviene sempre per copia.

Il "tradizionale" passaggio per valore e i puntatori vengono usati per poter effettuare un passaggio per riferimento.

Il puntatore altro non è che un contenitore per un indirizzo, il tipo del puntatore ti dice che tipo di "oggetto" dovrebbe essere allocato a quell'indirizzo. Sia nel caso di un puntatore singolo che di un puntatore doppio questo può puntare al tipo definito a sinistra nella dichiarazione.

E questo è ovvio, è la base.

Nel primo caso quello che passo alla funzione printf è una copia del valore di a, questo comporta che il valore di a non sarà modificato in seguito alla chiamata, indipendentemente dalla funzione che ho richiamato.
Nel secondo invece ho passato la copia del suo indirizzo. La funzione scanf ha quindi accesso alla locazione di memoria in cui si trova il valore di a. Questo implica che dopo la chiamata il valore di a potrebbe essere stato modificato.

Anche questo ovvio.

Al contrario l'ultima chiamata non può modificare il valore di l (questo implica che se la lista è vuota, cioè l==NULL non potrà essere aggiunto l'elemento)

Ecco, qua sta il punto: l è un puntatore, contiene quindi un indirizzo che punta ad un qualcosa, nell'ultima chiamata di funzione anche se passi semplicemente l dovresti poter modificare la lista, l è un puntatore, quindi un indirizzo alla lista(che ho modificato con aggiungi nodo). Inoltre nella funzione che aggiunge il nodo che bisogno c'è di passare un indirizzo? Dichiarando l come struct node* ho già un indirizzo. Capisci che voglio dire?

ma può agire sul nodo puntato da l (quindi di fatto, se l!=NULL è possibile aggiungere un elemento in fondo)

Può agire sul nodo puntato da l perchè otteniamo l'indirizzo al nodo successivo tramite l?

EDIT: mi è appena venuto un flash: può essere che passando semplicemente l io riesco a modificare solo il nodo successivo(perchè ho ha disposizione l'indirizzo immagazzinato nel puntatore next), ma non il primo nodo?

Guarda questi due sorgenti:

void stampalista(ListaDiElementi *l)
{
ListaDiElementi aux;
aux = l; /* riporto aux al primo elemento */
printf("\n\nLista: [ ");
while(aux->next != NULL)
{
printf("%d ", aux->info);
aux = aux->next;
}
printf("]");
};


void StampaLista(struct node *list)
{
struct node *aux;
aux=list;
while(aux != NULL)
{
printf("%d - ", aux->data);
aux = aux->next_node;
}
printf("\n");
};

Fanno la stessa cosa, ma una prende uno struct node* e l'altra uno struct node**!!!

Ma ho anche trovato questo che in pratica fa come hai fatto tu prima(passa l'indirizzo della lista, anche l è già un puntatore). E' questa la cosa che mi svia.

int main(){
ElementoLista n1, n2, n3, n4;
ListaDiElementi l = &n1;
n1.info = 1;
n1.next = &n2;
n2.info = 3;
n2.next = &n3;
n3.info = 5;
n3.next = &n4;
n4.info = 7;
n4.next = NULL;
stampalista(&l);
inser(&l, 0);
stampalista(&l);
return 0;
}


Questa cosa non è chiara:

delete_node(list, &n2);
printf(" - l'elemento 200 (INESITENTE) è in posizione %d**\n\n", get_pos(list, &n2));


int get_pos(struct node *head, struct node *nodo)
{
int conta = 1, trovato=0;
struct node *aux;
aux = head;
while(aux != NULL && trovato == 0)
{
if (aux == nodo)
trovato = 1;
else
{
aux=aux->next_node;
conta = conta+1;
}

L'elemento 200 è quello che si trova in n2. Se lo elimino, get_pos come fa a trovarlo? La funzione che elimina il nodo è questa:

void delete_node(struct node *l, struct node *delnode)
{
int trovato = 0;
struct node *aux;
aux = l;
if (l==NULL)
{
if(aux->next_node==delnode) l = aux->next_node;
}
else
{
struct node *prec, *corr;
prec=l;
corr=prec->next_node;
while(trovato==0 && corr!=NULL)
if (corr==delnode)
trovato = 1;
else
{
prec = corr;
corr=corr->next_node;
}
if(trovato==1)
{
prec->next_node=corr->next_node;
}
}
};


Mi sono fatto dare alcuni appunti, scrivo ciò che c'è messo, ma ancora non mi è chiara la questione del doppio puntatore.

"Inserire un nuovo elemento in testa ad una lista già definita"

ListaDiElementi aux;
aux = malloc(sizeof(ElementoLista));
aux->info = 25;
aux->next = l;

"In questo momento ci troviamo che sia "l" che "aux" puntano ad un elemento, ma io voglio che sia "l" solamente a puntare al primo elemento".

"Quindi facciamo puntare l al primo elemento":

l = aux;

"Ora definisco una procedura che aggiunge un nuovo elemento in testa alla lista":

void add(ListaDiElementi l, int val){
ListaDiElementi aux;
aux = malloc(sizeof(ElementoLista));
aux->info = val;
aux->next = l;
l = aux;
};

"Questa procedura non funziona perchè terminato il blocco si cancella tutto quello che si era creato e la variabile che è rimasta non viene modificata".

"Questa è quella giusta":

void add(ListaDiElementi *l, int val){
ListaDiElementi aux;
aux = malloc(sizeof(ElementoLista));
aux->info = val;
aux->next = *l;
*l = aux;
};


Questi sono gli appunti che mi hanno dato, però il dubbio non me l'hanno tolto. Se qualcuno riesce a spiegarmelo chiaramente gliene sarei grato.
Ho lo scritto tra tre giorni :D

[Ryuzaki_Eru]

Edit.

[Ryuzaki_Eru]

Edit.

[wingman87]

Che malloc, ovviamente, non sa cosa alloca lo avevo intuito, ma allora mi chiedo: dopo aver allocato questo spazio di memoria, come fa aux ad accedere al campo info? Ha fatto un cast automatico al tipo di puntatore di aux(cioè struct list)?

Il cast viene fatto dal tipo restituito da malloc (void*) al tipo del puntatore a cui assegni quell'indirizzo. Da quel momento in poi se scrivi aux->info sai già che ti stai riferendo ai primi 4 byte (o comunque la dimensione di un int) della zona di memoria puntata da aux. Questo perché la struttura node è costituita da un int seguito da un puntatore (quindi della dimensione di un indirizzo).


Il "tradizionale" passaggio per valore e i puntatori vengono usati per poter effettuare un passaggio per riferimento.

Sì, però ti consiglio (anche se non lo scrivi all'esame) di vedere tutto molto più semplicemente come un passaggio per copia.

Ecco, qua sta il punto: l è un puntatore, contiene quindi un indirizzo che punta ad un qualcosa, nell'ultima chiamata di funzione anche se passi semplicemente l dovresti poter modificare la lista, l è un puntatore, quindi un indirizzo alla lista(che ho modificato con aggiungi nodo). Inoltre nella funzione che aggiunge il nodo che bisogno c'è di passare un indirizzo? Dichiarando l come struct node* ho già un indirizzo. Capisci che voglio dire?

Per questo dicevo che è meglio vedere sempre il passaggio di parametri come un passaggio per copia... che l punta a qualcosa o meno non importa (in questo momento), sta di fatto che se passi il suo valore la funzione chiamata non potrà modificare il suo valore (ma potrà modificare il valore di ciò a cui punta l), se invece passi il suo indirizzo la funzione chiamata può anche modificare il valore di l.

Può agire sul nodo puntato da l perchè otteniamo l'indirizzo al nodo successivo tramite l?

EDIT: mi è appena venuto un flash: può essere che passando semplicemente l io riesco a modificare solo il nodo successivo(perchè ho ha disposizione l'indirizzo immagazzinato nel puntatore next), ma non il primo nodo?

Esatto

Guarda questi due sorgenti:

void stampalista(ListaDiElementi *l)
{
ListaDiElementi aux;
aux = l; /* riporto aux al primo elemento */
printf("\n\nLista: [ ");
while(aux->next != NULL)
{
printf("%d ", aux->info);
aux = aux->next;
}
printf("]");
};


void StampaLista(struct node *list)
{
struct node *aux;
aux=list;
while(aux != NULL)
{
printf("%d - ", aux->data);
aux = aux->next_node;
}
printf("\n");
};

Fanno la stessa cosa, ma una prende uno struct node* e l'altra uno struct node**!!!
Il primo mi sembra sbagliato per due motivi: c'è l'assegnamento aux=l ma aux e l hanno tipi diversi, e poi la condizione del while non va bene perché se la lista è vuota aux->next non esiste. Comunque non c'è bisogno di passare un doppio puntatore quando non devi modificare il valore del puntatore alla testa della lista.

Ma ho anche trovato questo che in pratica fa come hai fatto tu prima(passa l'indirizzo della lista, anche l è già un puntatore). E' questa la cosa che mi svia.

int main(){
ElementoLista n1, n2, n3, n4;
ListaDiElementi l = &n1;
n1.info = 1;
n1.next = &n2;
n2.info = 3;
n2.next = &n3;
n3.info = 5;
n3.next = &n4;
n4.info = 7;
n4.next = NULL;
stampalista(&l);
inser(&l, 0);
stampalista(&l);
return 0;
}

Quando si fa l'inserimento è sempre necessario passare l'indirizzo di l perché nel caso dell'inserimento in testa dopo l'inserimento l dovrà puntare alla nuova testa, nel caso di inserimento in coda è necessario per poter trattare il caso di lista vuota. Per la stampa invece non è necessario ma non è neanche sbagliato (è più difficile da leggere).

Questa cosa non è chiara:

delete_node(list, &n2);
printf(" - l'elemento 200 (INESITENTE) è in posizione %d**\n\n", get_pos(list, &n2));


int get_pos(struct node *head, struct node *nodo)
{
int conta = 1, trovato=0;
struct node *aux;
aux = head;
while(aux != NULL && trovato == 0)
{
if (aux == nodo)
trovato = 1;
else
{
aux=aux->next_node;
conta = conta+1;
}

L'elemento 200 è quello che si trova in n2. Se lo elimino, get_pos come fa a trovarlo? La funzione che elimina il nodo è questa:

void delete_node(struct node *l, struct node *delnode)
{
int trovato = 0;
struct node *aux;
aux = l;
if (l==NULL)
{
if(aux->next_node==delnode) l = aux->next_node;
}
else
{
struct node *prec, *corr;
prec=l;
corr=prec->next_node;
while(trovato==0 && corr!=NULL)
if (corr==delnode)
trovato = 1;
else
{
prec = corr;
corr=corr->next_node;
}
if(trovato==1)
{
prec->next_node=corr->next_node;
}
}
};

Nella delete_node il primo ramo dell'if non ha senso: se l è NULL, quindi anche aux lo è, controllo aux->next... Il secondo è ok, anche se non considera il primo nodo come un possibile candidato da cancellare.
Riguardo get_pos il nodo può essere trovato in due casi: o il nodo era in testa e quindi delete_node non lo ha cancellato, oppure era stato inserito due volte nella lista (che schifo però).


Mi sono fatto dare alcuni appunti, scrivo ciò che c'è messo, ma ancora non mi è chiara la questione del doppio puntatore.

Riguardo a
"Questa procedura non funziona perchè terminato il blocco si cancella tutto quello che si era creato e la variabile che è rimasta non viene modificata"
io direi che il nodo creato rimane in memoria ma non abbiamo più riferimenti ad esso (e quindi non possiamo liberare la memoria che occupa) perché l nella funzione chiamante è stato passato per copia e quindi non risente delle modifiche effettuate all'interno della funzione, in particolare non punta alla nuova testa ma alla stessa di prima.

[Ryuzaki_Eru]

Il cast viene fatto dal tipo restituito da malloc (void*) al tipo del puntatore a cui assegni quell'indirizzo. Da quel momento in poi se scrivi aux->info sai già che ti stai riferendo ai primi 4 byte (o comunque la dimensione di un int) della zona di memoria puntata da aux. Questo perché la struttura node è costituita da un int seguito da un puntatore (quindi della dimensione di un indirizzo).

Ok, e se ad esempio ci fossero due o più tipi di dati uguali? Come lo sa a quale membro mi riferisco? Tramite l'indirizzo di ogni membro? Anche se comunque gli indirizzi ho notato che nelle strutture sono continui.


Sì, però ti consiglio (anche se non lo scrivi all'esame) di vedere tutto molto più semplicemente come un passaggio per copia.


Vista cosi è facile, ma io voglio capire a fondo :D

Per questo dicevo che è meglio vedere sempre il passaggio di parametri come un passaggio per copia... che l punta a qualcosa o meno non importa (in questo momento), sta di fatto che se passi il suo valore la funzione chiamata non potrà modificare il suo valore (ma potrà modificare il valore di ciò a cui punta l), se invece passi il suo indirizzo la funzione chiamata può anche modificare il valore di l.

Il fatto è che è difficile vederlo cosi perchè io non passo il valore di l, ma un puntatore che punta all'inizio della lista o comunque un puntatore che poi faccio puntare ai nodi creati dinamicamente con malloc.

Esatto

Però se devo modificare il valore di un nodo posso farlo tranquillamente senza doppio puntatore.

Il primo mi sembra sbagliato per due motivi: c'è l'assegnamento aux=l ma aux e l hanno tipi diversi, e poi la condizione del while non va bene perché se la lista è vuota aux->next non esiste.

I tipi sono uguali, puntatori al nodo, infatti i sorgenti(che non ho scritto io) funzionano senza problemi. Anche la condizione va.

Comunque non c'è bisogno di passare un doppio puntatore quando non devi modificare il valore del puntatore alla testa della lista.


Eccoci qua: bingo! Oggi ho notato proprio questo schema, cioè che il doppio puntatore serve per poter eliminare o aggiungere un nodo in testa alla lista. Se voglio solo modificare il valore non mi serve un doppio puntatore.

Quando si fa l'inserimento è sempre necessario passare l'indirizzo di l perché nel caso dell'inserimento in testa dopo l'inserimento l dovrà puntare alla nuova testa, nel caso di inserimento in coda è necessario per poter trattare il caso di lista vuota. Per la stampa invece non è necessario ma non è neanche sbagliato (è più difficile da leggere).

In realtà però ci sono dei casi in cui, creando tutti i nodi dinamicamente, si può aggiungere in testa senza un doppio puntatore. Cioè uso due variabili di tipo struct node * e poi creo il primo nodo

Nodo1 che ha valore 1 e punta a NULL e salvo questo nodo nella variabile lista, poi in aux ad esempio creo un altro nodo e lo collego alla lista precedente e cosi via.

Nella delete_node il primo ramo dell'if non ha senso: se l è NULL, quindi anche aux lo è, controllo aux->next...

Visto anche io(non so chi abbia scritto sti sorgenti), infatti l'ho tolto.

Il secondo è ok, anche se non considera il primo nodo come un possibile candidato da cancellare.

Sistemato anche questo usando il doppio puntatore.

Riguardo get_pos il nodo può essere trovato in due casi: o il nodo era in testa e quindi delete_node non lo ha cancellato, oppure era stato inserito due volte nella lista (che schifo però).

I nodi li ho creati io per provare il codice, non era nè in testa nè era due volte nella lista. Per questo non capisco come sia possibile che lo trova dopo che l'ho cancellato.

Riguardo a
"Questa procedura non funziona perchè terminato il blocco si cancella tutto quello che si era creato e la variabile che è rimasta non viene modificata"
io direi che il nodo creato rimane in memoria ma non abbiamo più riferimenti ad esso (e quindi non possiamo liberare la memoria che occupa) perché l nella funzione chiamante è stato passato per copia e quindi non risente delle modifiche effettuate all'interno della funzione, in particolare non punta alla nuova testa ma alla stessa di prima.

Questo l'ho pensato pure io, certo che sembra strano però parla di passaggio per copia, quando invece passo in realtà un puntatore al primo nodo della lista. E' solo questa cosa che mi contorce la mente :muro:

[wingman87]

Questi post iniziano a diventare troppo lunghi... :D
Ok, e se ad esempio ci fossero due o più tipi di dati uguali? Come lo sa a quale membro mi riferisco? Tramite l'indirizzo di ogni membro? Anche se comunque gli indirizzi ho notato che nelle strutture sono continui.
Se ad esempio hai
struct prova{
int a;
int b;
int c;
};
struct prova var;

se richiedi ad esempio var.b il compilatore sa che ti riferisci ai byte dal quinto all'ottavo (salti a) della locazione di memoria a cui fa riferimento var.

Vista cosi è facile, ma io voglio capire a fondo :D

Non solo è facile, è corretto e serve proprio per capire a fondo.

Il fatto è che è difficile vederlo cosi perchè io non passo il valore di l, ma un puntatore che punta all'inizio della lista o comunque un puntatore che poi faccio puntare ai nodi creati dinamicamente con malloc.

E invece sì, passi il valore di l. l è come tutte le altre variabili, contiene un valore che, visto il tipo di l, è un indirizzo. Questo indirizzo viene copiato all'interno della variabile di tipo puntatore che hai dichiarato come parametro.

Però se devo modificare il valore di un nodo posso farlo tranquillamente senza doppio puntatore.

Sì, e tra l'altro in questo modo non modifichi il valore di l ma solo il valore di ciò a cui punta.

I tipi sono uguali, puntatori al nodo, infatti i sorgenti(che non ho scritto io) funzionano senza problemi. Anche la condizione va.

No, il primo è un doppio puntatore, il secondo è un puntatore singolo. L'assegnamento è comunque lecito perché entrambi contengono indirizzi (che hanno sempre la stessa dimensione) però dovrebbe darti almeno un warning se non un errore.

Eccoci qua: bingo! Oggi ho notato proprio questo schema, cioè che il doppio puntatore serve per poter eliminare o aggiungere un nodo in testa alla lista. Se voglio solo modificare il valore non mi serve un doppio puntatore.

Giusto

In realtà però ci sono dei casi in cui, creando tutti i nodi dinamicamente, si può aggiungere in testa senza un doppio puntatore. Cioè uso due variabili di tipo struct node * e poi creo il primo nodo

Nodo1 che ha valore 1 e punta a NULL e salvo questo nodo nella variabile lista, poi in aux ad esempio creo un altro nodo e lo collego alla lista precedente e cosi via.

Sì, esistono dei workaround per risolvere il problema anche con il puntatore singolo però è utile capire come funziona il doppio puntatore.

I nodi li ho creati io per provare il codice, non era nè in testa nè era due volte nella lista. Per questo non capisco come sia possibile che lo trova dopo che l'ho cancellato.

Se mi dai un esempio completo da compilare ed eseguire posso provare a vedere cosa c'è che non va.

Questo l'ho pensato pure io, certo che sembra strano però parla di passaggio per copia, quando invece passo in realtà un puntatore al primo nodo della lista. E' solo questa cosa che mi contorce la mente :muro:
Come dicevo sopra quello che ottieni è un puntatore al primo nodo della lista ma quello che passi è la copia del contenuto di l, cioè l'indirizzo del primo nodo della lista.

[Ryuzaki_Eru]

Questi post iniziano a diventare troppo lunghi... :D

Hai ragione, cerco di accorciare :D


Non solo è facile, è corretto e serve proprio per capire a fondo.

Per capire a fondo si deve vedere l come un puntatore, un indirizzo che punta al primo nodo della lista.

E invece sì, passi il valore di l. l è come tutte le altre variabili, contiene un valore che, visto il tipo di l, è un indirizzo. Questo indirizzo viene copiato all'interno della variabile di tipo puntatore che hai dichiarato come parametro.


Appunto, è una variabile puntatore che contiene un indirizzo, come tutti i puntatori. Quindi passo l'argomento per riferimento, non per valore.

Sì, e tra l'altro in questo modo non modifichi il valore di l ma solo il valore di ciò a cui punta.


Il valore di l è il primo nodo della lista, quindi modifico l tecnicamente.

No, il primo è un doppio puntatore, il secondo è un puntatore singolo. L'assegnamento è comunque lecito perché entrambi contengono indirizzi (che hanno sempre la stessa dimensione) però dovrebbe darti almeno un warning se non un errore.

Appunto, è lecito perchè è un indirizzo. Nessun warning.

Se mi dai un esempio completo da compilare ed eseguire posso provare a vedere cosa c'è che non va.

E' nell'altro pc, lo posto più tardi.

Come dicevo sopra quello che ottieni è un puntatore al primo nodo della lista ma quello che passi è la copia del contenuto di l, cioè l'indirizzo del primo nodo della lista.

Se io ho:

struc list n1, n2, n3;
n1.info = 2;
n2.info = 3;
n3.info = 4;

n1.next = &n2;
n2.next = &n3;
n3.next = NULL;

struct node *l = &n1;

Quando io passo l ad una funzione passo l'indirizzo del primo nodo, quindi una chiamata per riferimento, non una copia.

[wingman87]

Per capire a fondo si deve vedere l come un puntatore, un indirizzo che punta al primo nodo della lista.

Io trovo più chiaro vedere tutti i passaggi di parametri come passaggi per copia ma se ti trovi meglio così va bene, l'importante è che alla fine hai le idee chiare (e corrette).

Appunto, è una variabile puntatore che contiene un indirizzo, come tutti i puntatori. Quindi passo l'argomento per riferimento, non per valore.

Il punto è che anche l'indirizzo è un valore, ed è in quel senso che fai un passaggio per copia

Il valore di l è il primo nodo della lista, quindi modifico l tecnicamente.

No, perché se l conteneva l'indirizzo x prima della chiamata, conterrà ancora l'indirizzo x dopo. Modifichi la lista ma non l.

Appunto, è lecito perchè è un indirizzo. Nessun warning.

Sì ma se fai:

...
int a=10;
int* p=&a;
int** pp=p;
printf("%d",**p);
...

Non viene stampato il valore di a perché ho fatto un assegnamento sbagliato (pp è un puntatore doppio mentre p è singolo).

Se io ho:

struc list n1, n2, n3;
n1.info = 2;
n2.info = 3;
n3.info = 4;

n1.next = &n2;
n2.next = &n3;
n3.next = NULL;

struct node *l = &n1;

Quando io passo l ad una funzione passo l'indirizzo del primo nodo, quindi una chiamata per riferimento, non una copia.
Sì, passi il riferimento al primo nodo che altro non è che il valore di l (quindi comunque un passaggio per copia).

[Ryuzaki_Eru]

Io trovo più chiaro vedere tutti i passaggi di parametri come passaggi per copia ma se ti trovi meglio così va bene, l'importante è che alla fine hai le idee chiare (e corrette).

Io non trovo molto chiaro vedere un puntatore come passaggio per copia.

Il punto è che anche l'indirizzo è un valore, ed è in quel senso che fai un passaggio per copia

Se allora è cosi non avrebbe più senso il concetto di puntatore però :D

No, perché se l conteneva l'indirizzo x prima della chiamata, conterrà ancora l'indirizzo x dopo. Modifichi la lista ma non l.

A meno che non faccio puntare l ad un altro nodo, cioè un nodo aggiunto in testa.

Sì ma se fai:

...
int a=10;
int* p=&a;
int** pp=p;
printf("%d",**p);
...

Non viene stampato il valore di a perché ho fatto un assegnamento sbagliato (pp è un puntatore doppio mentre p è singolo).


Perchè si doveva fare int** pp = &p;

Sì, passi il riferimento al primo nodo che altro non è che il valore di l (quindi comunque un passaggio per copia)

E qua il collo di bottiglia. Capisco che vuoi dire, un indirizzo è pur sempre un valore, ma gli indirizzi servono proprio per poter fare le modifiche "reali" e non lavorare sulle copie.

[wingman87]

Io non trovo molto chiaro vedere un puntatore come passaggio per copia.

Ognuno ha i propri metodi, se ti trovi meglio così va bene

Se allora è cosi non avrebbe più senso il concetto di puntatore però :D

E perché?

A meno che non faccio puntare l ad un altro nodo, cioè un nodo aggiunto in testa.

Ma questo non lo puoi fare se hai passato l e non il suo indirizzo

Perchè si doveva fare int** pp = &p;

Stesso motivo per cui ho detto che l'assegnamento di quello spezzone di codice era sbagliato, lo riporto qui:

void stampalista(ListaDiElementi *l)
{
ListaDiElementi aux;
aux = l; /* riporto aux al primo elemento */
printf("\n\nLista: [ ");
while(aux->next != NULL)
{
printf("%d ", aux->info);
aux = aux->next;
}
printf("]");
};

l è di tipo ListaDiElementi* mentre aux è di tipo ListaDiElementi, quindi quell'assegnamento non è corretto

E qua il collo di bottiglia. Capisco che vuoi dire, un indirizzo è pur sempre un valore, ma gli indirizzi servono proprio per poter fare le modifiche "reali" e non lavorare sulle copie.
Una cosa è "cosa" fai, un'altra è "perché" lo fai. Quello che dico io è che quel "cosa" è un passaggio per copia di un indirizzo. Sul "perché" ovviamente sono d'accordo.

[Ryuzaki_Eru]

Ma questo non lo puoi fare se hai passato l e non il suo indirizzo

Per indirizzo noi intendiamo due cose diverse mi sa.

l è di tipo ListaDiElementi* mentre aux è di tipo ListaDiElementi, quindi quell'assegnamento non è corretto


Il codice però funziona.

Una cosa è "cosa" fai, un'altra è "perché" lo fai. Quello che dico io è che quel "cosa" è un passaggio per copia di un indirizzo. Sul "perché" ovviamente sono d'accordo.

Io ancora questa cosa non l'ho capita. Mi scrivi del codice che fa vedere l'uso dei due casi?

[wingman87]

Ti faccio un esempio completo di uso di doppio puntatore e puntatore singolo:

//File lista.h
typedef struct node* Lista;

Lista creaLista(); //Restituisce una lista vuota
void addElem(Lista* pL,int info); //Aggiunge un nuovo nodo con il campo info specificato in testa alla lista puntata da pL
void printLista(Lista l); //Stampa gli elementi della lista


//File lista.c
#include "lista.h"
#include <stdio.h>
#include <stdlib.h>

//Definizione della struttura nodo. Chi usa la lista (il file prova.c) non sa come è
//definito e quindi non può accedervi direttamente (incapsulamento)
struct node{
int info;
Lista next;
};

Lista creaLista(){
return NULL;
}

//creaLista(int,Lista) non è presente nell'header, è una funzione di supporto che uso solo all'interno di questo file
//(volendo potrei anche aggiungerlo all'header).
//Ritorna una lista con in testa un nodo con il campo info e next specificati
Lista creaLista(int info, Lista next){
struct node* n=(Lista)malloc(sizeof(struct node));
if(!n) return NULL;
n->info=info;
n->next=next;
return n;
}

void addElem(Lista* pL,int info){
if(*pL==NULL){ //Se la lista puntata da pL è vuota la sovrascrivo con una nuova lista di un elemento
*pL=creaLista(info,NULL);
}else{
//Se la lista puntata da pL non è vuota la sovrascrivo con una nuova lista avente in testa
//un nuovo elemento e in coda la vecchia lista
*pL=creaLista(info,*pL);
}
}

void printLista(Lista l){
while(l){
printf("%d\t",l->info);
l=l->next;
}
printf("\n");
}


//file prova.c
#include "lista.h"

int main(){
Lista l=creaLista(); //Creo una lista vuota
addElem(&l,3); //Passo l per indirizzo in modo che dopo la chiamata l conterrà una nuova lista uguale alla precedente ma con 3 in testa
addElem(&l,2);
addElem(&l,1);
printLista(l);
}


EDIT: Avevo messo la definizione della struttura nel file sbagliato. Ho anche aggiunto dei commenti e modificato alcuni nomi per rendere tutto più comprensibile.

[wingman87]

Per indirizzo noi intendiamo due cose diverse mi sa.

Io per indirizzo di una variabile intendo l'indirizzo della locazione di memoria in cui si trova il valore della variabile

Il codice però funziona.

Mi sembra strano ma mi fido.

Io ancora questa cosa non l'ho capita. Mi scrivi del codice che fa vedere l'uso dei due casi?
Vedi sopra

[Ryuzaki_Eru]

Leggo domani, intanto grazie.

Io per indirizzo di una variabile intendo l'indirizzo della locazione di memoria in cui si trova il valore della variabile

Anche io.

Mi sembra strano ma mi fido.

Non ti devi fidare, domani ti posto il codice.

[Ryuzaki_Eru]

Negli appunti c'ho scritto che questa procedura non funziona perchè terminato il blocco si cancella tutto quello che si era creato. Ma alla fine, assegnando aux ad l modifico effettivamente la lista passata. Perchè non dovrebbe funzionare?

void add(ListaDiElementi l, int val){
ListaDiElementi aux;
aux = malloc(sizeof(ElementoLista));
aux->info = val;
aux->next = l;
l = aux;
};

[Ryuzaki_Eru]

Dopo un flash(bellissimi i lampi di genio :D) ho scritto questo codice e ho capito, almeno il discorso del singolo puntatore.

#include <stdio.h>

void prova(int *num);

int main(){
int a = 10;
int *p = &a;
printf("Il valore di a e' %d\n", a);
prova(p);
printf("Ora il valore di a e' %d %d\n", a);
return 0;
}

void prova(int *num){
int b = 100;
num = &b;
printf("Il valore di a dentro la func e' %p %d\n", num, *num);
};

[Ryuzaki_Eru]

Se mi dai un esempio completo da compilare ed eseguire posso provare a vedere cosa c'è che non va.

Ecco tutto il codice per come l'ho trovato. L'elemento sembra eliminarlo, eppure quando chiamo get_pos sul nodo mi restituisce l'indice, quindi lo trova..

#include <stdio.h>
#include <stdlib.h>

/* creo la struttura del singolo record della lista */
struct node
{
int data;
struct node *next_node;
};

/* dichiaro le funzioni e le procedure che utilizzerò */
int get_pos(struct node *head, struct node *nodo);
void StampaLista(struct node *list);
void delete_node(struct node *l, struct node *delnode);
void edit_node(struct node *head, struct node *nodo, int newvalue);

/* funzione iniziale */
int main()
{
/* creo 3 nodi... */
struct node n1, n2, n3;
n1.data = 100;
n2.data = 200;
n3.data = 300;
/* ...e li collego tra loro come segue n1-->n2-->n3 */
n1.next_node = &n2;
n2.next_node = &n3;
n3.next_node = NULL;
/* creo l'elemento list che è l'indirizzo del primo valore (N1) */
struct node *list= &n1;
/* stampo la lista iniziale */
printf("\n**Lista iniziale**\n\n");
StampaLista(list);
/* inserisco un nuovo nodo (N4) tra n1 e n2 e stampo la nuova lista (n1-->*N4*-->n2-->n3) */
struct node n4;
n4.data = 150;
n4.next_node = &n2;
n1.next_node = &n4;
printf("\n**Inserisco l'elemento 150 tra il primo e il secondo**\n\n");
StampaLista(list);
/* elimino il nodo che contiene "200" e stampo la lista */
delete_node(list, &n2);
printf("\n**Elimino l'elemento 200**\n\n");
StampaLista(list);
/* modifico il valore 300 sostituendolo con 340 */
edit_node(list, &n3, 340);
printf("\n**Modifico l'elemento 300 sostituendolo con 340**\n\n");
StampaLista(list);
/* visualizzo la posizione degli elementi */
printf("\n**Posizione degli elementi:**\n");
printf(" - l'elemento 100 è in posizione %d**\n", get_pos(list, &n1));
printf(" - l'elemento 150 è in posizione %d**\n", get_pos(list, &n4));
printf(" - l'elemento 340 è in posizione %d**\n", get_pos(list, &n3));
printf(" - l'elemento 200 (INESITENTE) è in posizione %d**\n\n", get_pos(list, &n2));
/* return funzione principale */
return 0;
} /*fine funzione iniziale */

/* scrivo le procedure e le funzioni... NB IN TUTTE LE PROCEDURE VIENE UTILIZZATO UN PUNTATORE LOCALE AUX PER NON MODIFICARE IL PUNTATORE LIST*/
void StampaLista(struct node *list)
{
struct node *aux;
aux=list;
while(aux != NULL)
{
printf("%d - ", aux->data);
aux = aux->next_node;
}
printf("\n");
};

void delete_node(struct node *l, struct node *delnode)
{
int trovato = 0;
struct node *aux;
aux = l;
if (l==NULL)
{
if(aux->next_node==delnode) l = aux->next_node;
}
else
{
struct node *prec, *corr;
prec=l;
corr=prec->next_node;
while(trovato==0 && corr!=NULL)
if (corr==delnode)
trovato = 1;
else
{
prec = corr;
corr=corr->next_node;
}
if(trovato==1)
{
prec->next_node=corr->next_node;
}
}
};

void edit_node(struct node *head, struct node *nodo, int newvalue)
{
struct node *aux;
aux = head;
while(aux != nodo) aux = aux->next_node;
aux->data = newvalue;
};

int get_pos(struct node *head, struct node *nodo)
{
int conta = 1, trovato=0;
struct node *aux;
aux = head;
while(aux != NULL && trovato == 0)
{
if (aux == nodo)
trovato = 1;
else
{
aux=aux->next_node;
conta = conta+1;
}
}
if (trovato==1) return conta; else return -1; /* se l'elemento esiste restituisce la sua posizione altrimenti -1 che sta per "non trovato" */
}

[wingman87]

A me l'ultima chiamata a get_pos restituisce -1, quindi giusto... oppure ho capito male qual è il problema?

[Ryuzaki_Eru]

A me l'ultima chiamata a get_pos restituisce -1, quindi giusto... oppure ho capito male qual è il problema?

Si si è giusto, quando lo avevo eseguito la prima volta avevo dimenticato di ricompilare il codice corretto.