[C] Doppio puntatore

[Fenix797]

Ciao a tutti. Vi propongo un esempio di un esercizio svolto, riuscite a spiegarmi qui, ma anche in generale, quando devo usare il doppio puntatore e quindi quando serve la lista di appoggio??



void pari_dispari_insert(struct list **ptr) {
struct list *tmp_ptr;//lista di appoggio init(&tmp_ptr);
*ptr = NULL;
while (tmp_ptr != NULL) {
if (tmp_ptr->value == 0)
suf_insert(ptr, 0); //lo inserisco

else{
if (tmp_ptr->value % 2 == 0) { //è pari
suf_insert(ptr, 0);
suf_insert(ptr, tmp_ptr->value);
} //void suf_insert(struct list ** ptrptr, int value);

else{
suf_insert(ptr, tmp_ptr->value);
suf_insert(ptr, 0);
} //void pre_insert(struct list ** ptrptr, int value);
}
tmp_ptr = tmp_ptr->next_ptr;
}
}


in sostanza deve inserire 0 prima di un valore pari, dopo se è dispari.
Grazie!

[apatriarca]

In generale, si usa un doppio puntatore come parametro di una funzione quando si vuole modificare il puntatore passato come argomento. Nel caso delle liste concatenate, la lista viene passata usando un doppio puntatore quando il nodo di testa potrebbe cambiare. Hai quindi bisogno di modificare il puntatore passato come argomento in modo che punti al nodo corretto.

C'è un punto poco chiaro nel tuo codice. Vuoi creare una nuova lista oppure modificare la lista passata come argomento? Il tipo della funzione sembra suggerire che stai cercando di modificare la lista inserendo i valori al suo interno, mentre il codice sembra cercare di creare una copia (il codice contiene numerosi errori). C'è in particolare un grosso errore all'inizio della funzione. Hai dichiarato la variabile tmp_ptr ma non l'hai inizializzata. Hai inoltre settato *ptr a NULL cancellando quindi l'unico puntatore alla tua lista.. Non comprendo il significato del commento nella prima riga, ma suppongo che volessi inizializzarla al valore di *ptr? Cosa fa la funzione suf_insert? Dall'utilizzo sembra essere un modo per inserire un elemento alla fine della lista? Si tratta dell'operazione più inefficiente che potresti in realtà fare su una lista.. Perché tratti separatamente il caso in cui il valore sia uguale a zero? Era nel testo dell'esercizio?

Alcuni commenti sul codice:
1. Credo che non abbia senso chiamare la struttura list. La struttura rappresenta infatti un nodo della lista e non la lista stessa. La lista è in effetti il puntatore al nodo. Sinceramente credo che molti dei codici sulle liste sarebbero più chiari se questa distinzione venisse rispettata, come nel seguente codice:

Codice:

typedef struct list_node_t list_node_t;
typedef list_node_t *list_t;

struct list_node_t
{
    int value; // Suppongo che si voglia una lista di interi
    list_t next;
};


Scrivendo il codice in questo modo il doppio puntatore sarebbe un singolo puntatore a list_t diventando quindi del tutto equivalente a qualsiasi altra situazione in cui passiamo un puntatore alla funzione.
2. La formattazione è spesso molto importante per la leggibilità del codice. E' quindi opportuno cercare di formattare il codice in modo da renderlo più leggibile e usare il tag CODE per inserire il codice nel forum.
3. Anche se non necessario (e credo sia un errore permetterlo) cerca di mettere sempre le parentesi graffe negli if. Può sembrare superfluo ma ci sono un sacco di errori che possono essere evitati in questo modo.
4. Non credo che sia granché utile chiamare ptr qualsiasi puntatore. E' spesso già evidente dal suo tipo e sarebbe più utile sapere cosa rappresenta.

[vict85]

Concordo con Antonio (apatriarca). Un nodo non è una lista, e risulta importante fare la distinzione. Un'altro modo per separare le due cose è definire la lista come una struct che contiene il puntatore al primo nodo. Insomma così:

Codice:

struct nodo
{
  struct nodo * successivo;
  int valore;
};

struct lista
{
  struct nodo * testa;
};

eventualmente puoi mettere i typedef se vuoi evitare di dover sempre scrivere struct prima del nome.

Suppongo che suf_insert aggiunga l'elemento alla fine della lista. Ho già espresso il mio dissenso verso questa funzione nella discussione precedente. Ogni volta che chiami suf_insert su una lista, la scorri tutta dalla testa alla coda e infine aggiungi un elemento. Una lista non sa quanto è lunga e conosce la posizione solo del suo elemento iniziale, ma questo non vuol dire che il tuo programma non possa memorizzarti il valore della coda e riutilizzarlo.

Il mio suggerimento consiste nell'avere le seguenti 3 funzioni:

Codice:

/*!
 * @brief Crea una nuova lista da un'altra lista aggiungendo un elemento in
 *        testa
 * @param[in] Valore il valore che verrà salvato nel nuovo primo elemento
 * @param[in] Lista  la lista che verra' accodata al nuovo elemento creato
 * @return    la nuova lista con il nuovo valore in testa e la vecchia lista in
 *            coda
 */
struct lista aggiungi_in_testa(int Valore, struct lista Lista);

/*!
 * @brief Aggiunge un nuovo elemento tra un nodo e il suo successivo
 * @param[in] Nodo  il nodo a cui vuoi collegare il nuovo elemento creato
 * @param[in] Valore il valore del nuovo elemento creato
 * @return    un puntatore al nuovo elemento creato
 *
 * @note il nodo a cui punta la variabile Nodo sarà modificato per contenere in
 *       successivo l'indirizzo al nuovo elemento creato. Il nuovo elemento
 *       creato avra' come successivo l'attuale successivo al nodo puntato da
 *       Nodo
 */
struct nodo * aggiungi_dopo(struct nodo * Nodo, int Valore);

/*!
 * @brief trova l'ultimo elemento di una lista
 * @param[in] Lista  la lista in cui si cerca l'ultimo elemento
 * @return    il nodo in coda alla lista
 */
struct nodo * trova_ultimo_elemento(struct lista Lista);

Nota che ho deciso di non modificare l'oggetto lista all'interno della funzione ma di ritornare il nuovo oggetto lista. Pertanto queste funzioni non hanno alcun puntatore a struct lista. In altre parole, quando aggiungi un elemento all'inizio della lista, dovrai fare:

Codice:

Lista = aggiungi_in_testa(1, Lista);

invece di

Codice:

aggiungi_in_testa_v2(Lista, 1);

dove aggiungi_in_testa_v2 sarà definita come

Codice:

void aggiungi_in_testa_v2(struct lista * Lista, int Valore);

e fa la stessa cosa dell'altra funzione.

Supponi quindi di voler aggiungere 3 e 4 alla fine della lista, allora con la mia interfaccia scriverai

Codice:

struct nodo last = trova_ultimo_elemento( Lista );
last = aggiungi_dopo( last, 3 );
last = aggiungi_dopo( last, 4 );

invece di

Codice:

suf_insert(Lista->testa, 3);
suf_insert(Lista->testa, 4);

che però è equivalente a fare

Codice:

struct nodo last = trova_ultimo_elemento(Lista);
aggiungi_dopo(last, 3);
last = trova_ultimo_elemento(Lista);
aggiungi_dopo(last, 4);

Insomma stai facendo una operazione \(\displaystyle O(n) \) in più che però non hai bisogno di fare. Supponi per esempio di dover aggiungere \(\displaystyle 1000 \) elemento alla fine di una lista che ne contiene \(\displaystyle 2000 \). Ignorando la creazione degli elementi (che è piuttosto lenta e va fatta da entrambe le versioni), l'ordine delle operazioni della mia versione è circa \(\displaystyle 3000 \) (\(\displaystyle 2000 \) per trova_ultimo_elemento e \(\displaystyle 1000 \) per gli inserimenti), mentre se usi suf_insert fai \(\displaystyle 2000+2001+\dotsb+2999+1000 = 1000 + 1500\cdot 2999 - 1000 \cdot 1999 = 2500500 \) operazioni per fare esattamente la stessa cosa.

Detto questo sarebbe utile sapere qual'è il testo del tuo problema.

[Fenix797]

In generale, si usa un doppio puntatore come parametro di una funzione quando si vuole modificare il puntatore passato come argomento. Nel caso delle liste concatenate, la lista viene passata usando un doppio puntatore quando il nodo di testa potrebbe cambiare. Hai quindi bisogno di modificare il puntatore passato come argomento in modo che punti al nodo corretto.

C'è un punto poco chiaro nel tuo codice. Vuoi creare una nuova lista oppure modificare la lista passata come argomento? Il tipo della funzione sembra suggerire che stai cercando di modificare la lista inserendo i valori al suo interno, mentre il codice sembra cercare di creare una copia (il codice contiene numerosi errori). C'è in particolare un grosso errore all'inizio della funzione. Hai dichiarato la variabile tmp_ptr ma non l'hai inizializzata. Hai inoltre settato *ptr a NULL cancellando quindi l'unico puntatore alla tua lista.. Non comprendo il significato del commento nella prima riga, ma suppongo che volessi inizializzarla al valore di *ptr? Cosa fa la funzione suf_insert? Dall'utilizzo sembra essere un modo per inserire un elemento alla fine della lista? Si tratta dell'operazione più inefficiente che potresti in realtà fare su una lista.. Perché tratti separatamente il caso in cui il valore sia uguale a zero? Era nel testo dell'esercizio?

Premetto che mi sono fatta una risata perché questa è la soluzione del professore, che io sto cercando di decifrare allora, le inizializzazioni "esterne" alla funzione sicuramente non ci sono perché il programma è poi da completare a casa dopo il compito scritto in cui devo presentare solo la funzione, quindi questa è solo la funzione.
Il commento all'inizio scusa ho sbagliato, la parte init(&tmp_ptr); è della riga seguente quindi non del commento, quindi dovrebbe essere questa l'inizializzazione di cui parlavi.
L'esercizio sembra voler modificare la lista e non volerne creare un'altra con gli zeri aggiunti. Con un mio amico avevo dedotto che forse per aggiungere questi zeri (prima del valore se è pari, e dopo se il valore è dispari) invece di inserire lo zero nella posizione giusta della lista sembra reinserire tutto alla fine. Quindi esempio controlla il primo valore, è pari, lo zero serve prima, allora alla fine della lista faccio aggiungere (con suf_insert che mi viene sempre presentata negli appunti come una formulazione per aggiungere in coda) lo zero e il valore che avevo controllato, e così prosegue per ogni valore. Anche a me è sembrata un'operazione per "complicarsi la vita" però appunto, spero possa andar bene anche un semplice inserimento che devo capire come mettere in modo giusto.
Il caso zero non era nel testo dell'esercizio infatti la mia frase di risposta è stata "e io come avrei dovuto capirlo di inserire anche questo caso?", chi lo sa.

Per usare CODE non sapevo infatti come fare, basta scrivere [code] e [\code]?

Le parentesi degli if probabilmente una mia dimenticanza.

E chiamarli tutti ptr sì capisco, probabilmente capirei meglio anch'io le soluzioni del prof.

[Fenix797]

Detto questo sarebbe utile sapere qual'è il testo del tuo problema.

Il testo del problema è
Data una lista di valori interi scriver una funzione che:
1 inserisce il valore 0 in posizione antecedente agli elementi contenenti valori pari
2 inserisce il valore 0 in posizione successiva agli elementi contenenti valori dispari


Ho capito all'incirca la tua suddivisione nelle tre funzioni per semplificare le operazioni e diminuire i "passaggi". Però non ho capito la frase "Crea una nuova lista da un'altra lista aggiungendo un elemento in testa", cioè vuoi creare una lista nuova invece che modificarla, però la crei aggiungendo un elemento a...quale altra lista?

Il resto ho capito, anche come aggiungere l'elemento a questa lista che hai creato.

L'unico fatto è proprio che il prof chiede nell'esercizio una funzione, già una volta invece di una l'avevo divisa in due e nella soluzione era proprio evidenziato UNA. Quindi non so se lo potrebbe accettare.

[apatriarca]

Anche nel caso in cui il professore ti abbia chiesto di implementare una semplice funzione è comunque necessario averti fornito l'implementazione della lista e l'elenco di funzioni a cui hai accesso.. Ovviamente è possibile implementare tutto senza fare uso di alcuna funzione aggiuntiva come nella seguente soluzione:

Codice:

void pari_dispari_insert(struct list **lst)
{
    // Memorizzo sia il nodo corrente della iterazione sia quello precedente
    struct list *prev = NULL;
    struct list *current = *lst;

    while (current != NULL) {
        // Creo il nodo che andrà inserito prima o dopo il nodo corrente
        struct list *new_node = malloc(sizeof(struct list));
        new_node->value = 0;

        // Verifico se il valore è pari o dispari e agisco di conseguenza..
        if (current->value % 2 == 0) {
            new_node->next_ptr = current;

            // Se il nodo corrente è la testa della lista devo aggiornare lst
            if (prev == NULL) {
                *lst = new_node;
            }
        } else {
            // Inserisco il nuovo nodo dopo quello corrente
            new_node->next_ptr = current->next_ptr;
            current_next_ptr = new_node;

            // Aggiorno il nodo corrente al nuovo nodo in modo da saltarlo
            // nell'iterazione
            current = new_node;
        }

        // Aggiorno il nuovo precedente e corrente
        prev = current;
        current = current->next_ptr;
    }
}


Ho inserito qualche commento ma se hai dubbi chiedi pure.

P.S. Per inserire il codice è effettivamente sufficiente scriverlo tra quei due tag.

[Super Squirrel]

Dal momento che il puntatore passato come argomento alla funzione viene modificato o meno solo in base al valore assunto dal primo nodo della lista, il puntatore "prev" non è superfluo? Non basterebbe cambiare la condizione dell'if da
prev == NULL
a
current == *lst
?

[apatriarca]

Ovviamente no.. Ho dimenticato di inserire l'elemento tra quello precedente e quello corrente (vera ragione per l'esistenza di prev..):

Codice:

void pari_dispari_insert(struct list **lst)
{
    // Memorizzo sia il nodo corrente della iterazione sia quello precedente
    struct list *prev = NULL;
    struct list *current = *lst;

    while (current != NULL) {
        // Creo il nodo che andrà inserito prima o dopo il nodo corrente
        struct list *new_node = malloc(sizeof(struct list));
        new_node->value = 0;

        // Verifico se il valore è pari o dispari e agisco di conseguenza..
        if (current->value % 2 == 0) {
            new_node->next_ptr = current;

            // Se il nodo corrente è la testa della lista devo aggiornare lst
            if (prev == NULL) {
                *lst = new_node;
            } else { // Inserisco il nodo tra quello precedente e quello corrente
                prev->next_ptr = new_node;
            }
        } else {
            // Inserisco il nuovo nodo dopo quello corrente
            new_node->next_ptr = current->next_ptr;
            current_next_ptr = new_node;

            // Aggiorno il nodo corrente al nuovo nodo in modo da saltarlo
            // nell'iterazione
            current = new_node;
        }

        // Aggiorno il nuovo precedente e corrente
        prev = current;
        current = current->next_ptr;
    }
}


[Fenix797]

Ho scritto qualche commento per i due punti che non ho capito
Grazie mille

Codice:

void pari_dispari_insert(struct list **lst)
{
    // Memorizzo sia il nodo corrente della iterazione sia quello precedente
    struct list *prev = NULL;
    struct list *current = *lst;

    while (current != NULL) {
        // Creo il nodo che andrà inserito prima o dopo il nodo corrente
        struct list *new_node = malloc(sizeof(struct list));
        new_node->value = 0;

        // Verifico se il valore è pari o dispari e agisco di conseguenza..
        if (current->value % 2 == 0) {
            new_node->next_ptr = current;                                  //1)qui non ho capito
                                                                                                   perché dopo new node è current?

            // Se il nodo corrente è la testa della lista devo aggiornare lst
            if (prev == NULL) {
                *lst = new_node;
            } else { // Inserisco il nodo tra quello precedente e quello corrente
                prev->next_ptr = new_node;
            }
        } else {
            // Inserisco il nuovo nodo dopo quello corrente
            new_node->next_ptr = current->next_ptr;                  //2) qui non bastava
                                                                                                   current new_ptr =new_node ?
            current_next_ptr = new_node;

            // Aggiorno il nodo corrente al nuovo nodo in modo da saltarlo
            // nell'iterazione
            current = new_node;
        }

        // Aggiorno il nuovo precedente e corrente
        prev = current;
        current = current->next_ptr;
    }
}


Il resto ho capito .

[apatriarca]

La situazione iniziale della lista è

Codice:

.. -> PREV -> CURRENT -> NEXT -> ..

Se vuoi inserire un elemento prima di current devi settare il puntatore next_ptr del nodo precedente al nuovo nodo e quello del nodo nuovo a current in modo da avere la seguente situazione:

Codice:

.. -> PREV -> NEW_NODE -> CURRENT -> NEXT -> ..

Se invece lo devi inserire dopo devi settare il puntatore next_ptr del nuovo nodo a NEXT e quello del nodo corrente al nuovo nodo in modo da avere la seguente situazione:

Codice:

.. -> PREV -> CURRENT -> NEW_NODE -> NEXT -> ..

Spero sia chiaro. In un certo senso capito questo dovresti capire ogni esercizio sulle liste. Ogni esercizio consiste infatti come devono essere settati i puntatori successivi in modo che la lista ottenuta sia quella desiderata..