DOMANDA Indirezione Doppia (C)

[JDany]

Salve. Sto studiando le liste, pile, code e alberi in C.
Nel mio libro utilizza queste strutture dinamiche con un puntatore a puntatore, ma non riesco a capire il motivo per cui lo usa.

Perchè una indirezione doppia al posto di una singola indirezione?

 

[rodhellas]

Senza un esempio è difficile darti una motivazione precisa del perchè..

 

[JDany]

Come esempio prendo una funzione creata nell'esempio del mio libro:

// header ...

struct listNode{
    char data;
    struct listNode *nextPtr; // puntatore al nodo
};

typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

void insert(ListNodePtr *sPtr, char value);

int main(void){
   
    // codice
   
    return 0;
}

void insert(ListNodePtr *sPtr, char value){
    ListNodePtr newPtr = malloc(sizeof(ListNode)); // Crea il nodo, ma viene usato una sola indirezione
   
    if(newPtr != NULL){
        newPtr->data = value;
        newPtr->nextPtr = NULL; // il nodo non è collegato ad altri nodi
       
        ListNodePtr previousPtr = NULL;
        ListNodePtr currentPtr = *sPtr;
       
        while(currentPtr != NULL && value > currentPtr->data){
            previousPtr = currentPtr;
            currentPtr = currentPtr->nextPtr; // nodo successivo
        }
       
        // Inserisci il nuovo nodo all'inizio della lista
        if(previousPtr == NULL){
            newPtr->nextPtr = *sPtr;
            *sPtr = newPtr;
        }else{
            previousPtr->nextPtr = newPtr;
            newPtr->nextPtr = currentPtr;
        }
    }else{
        printf("%s: %c %s", "Memoria esaurita!", value, "non e' stato inserito.");
    }
}

 

[_Achille]

Scusami ma non vedo alcun puntatore a puntatore...

 

[JDany]

Scusami ma non vedo alcun puntatore a puntatore...

Il puntatore a puntatore in questo caso non è dichiarato in questo modo: const void ** (esempio).

Nel mio caso è dichiarato così:
Puntatore alla struttura listNode: "typedef ListNode *ListNodePtr";
Puntatore a puntatore: void insert(ListNodePtr *sPtr, char value) {}

Già ListNodePtr è un puntatore ad una struttura, mentre nella funzione insert() è dichiarato un puntatore a un puntatore a una struct listNode.

Spero di essermi spiegato.

 

[_Achille]

Il puntatore a puntatore in questo caso non è dichiarato in questo modo: const void ** (esempio).

Nel mio caso è dichiarato così:
Puntatore alla struttura listNode: "typedef ListNode *ListNodePtr";
Puntatore a puntatore: void insert(ListNodePtr *sPtr, char value) {}

Già ListNodePtr è un puntatore ad una struttura, mentre nella funzione insert() è dichiarato un puntatore a un puntatore a una struct listNode.

Spero di essermi spiegato.

Ah si scusami non lo avevo notato.

In realtà non mi pare necessario a meno di funzioni tipo init(datatypePtr *, ...).

 

[rodhellas]

Sperando di aver capito bene, il doppio puntatore serve per puntare al primo nodo. Personalmente io ho sempre creato una struct "testa" per puntare al primo nodo.
In generale, entrambi gli approcci hanno due vantaggi principali: 1) l'inserimento in testa è molto semplice (infatti
newPtr->nextPtr = *sPtr;
*sPtr = newPtr; )
2) hai salvato sempre un puntatore al primo nodo, quindi l'uso come in questo caso di funzioni è comodo (e in caso di cambiamenti pesanti alla lista incorri in meno problemi).

 

[JDany]

Ah si scusami non lo avevo notato.

In realtà non mi pare necessario a meno di funzioni tipo init(datatypePtr *, ...).

Anche a me pare non necessario, però credo che la spiegazione di @rodhellas sia corretta.
Nel mio libro dice semplicemente che è un concetto avanzato, senza dare una motivazione valida.

 

[Andretti60]

Poiche' la funzione insert() puo' cambiare il valore del primo parametro (sPtr, nel caso inserisci all'inizio della lista) e' ovvio che debba essere un puntarore (ossia passi il suo indirizzo invece che il suo valore). Poiche' il tipo stesso e' un puntatore, ecco che hai un puntatore di un puntatore. Questo non ha nulla a che vedere con liste o pile.

 

[JDany]

Poiche' la funzione insert() puo' cambiare il valore del primo parametro (sPtr, nel caso inserisci all'inizio della lista) e' ovvio che debba essere un puntarore (ossia passi il suo indirizzo invece che il suo valore). Poiche' il tipo stesso e' un puntatore, ecco che hai un puntatore di un puntatore. Questo non ha nulla a che vedere con liste o pile.

E' spiegato nella sezione delle strutture dati dinamiche. L'esempio che ho scritto all'inizio serve per inserire dati in una lista.