Puntatore a puntatore nell'elenco collegato

Aug 18 2020

Qualcuno può spiegarmi perché questo codice mi dà come risultato l'elenco vuoto:

typedef struct str_node{
int data;
struct str_node *next;
}node;


void begin(node *head);
void display_list(node *head);


int main(){

node *head;
int i;

head = NULL;

for(i=0;i<5;i++) {
    begin(head);
}
display_list(head);




return 0;
}

void begin(node *head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = head;
head = new;
}

Ma se cambio la funzione begin () con il puntatore al puntatore, mi dà l'elenco giusto?

void begin(node **head){
node *new;
int value;
new = (node*) malloc(sizeof(node));
printf("Insert the element to add at the beginning of the list: ");
scanf("%d",&value);
new->data = value;
new->next = *head;
*head = new;
}

Puoi anche spiegarmi perché quando passo nel main il nodo head alla funzione begin devo passarlo come "&head"? e non più come "testa"

Risposte

2 VladfromMoscow Aug 18 2020 at 22:31

Nel primo programma in questo frammento di codice

head = NULL;

for(i=0;i<5;i++) {
    begin(head);
}

il puntatore headviene passato alla funzione beginper valore. Cioè viene creata una copia del valore del puntatore headdichiarato in main e viene assegnata al parametro con lo stesso nome della funzione begin

void begin(node *head);

Quindi all'interno della funzione è il parametro headche contiene inizialmente una copia del puntatore originale headche viene modificato. Il puntatore originale headil cui valore è stato assegnato al parametro non viene modificato.

Per cambiare l'intestazione del puntatore originale dichiarata in main bisogna passarla alla funzione per riferimento indirettamente tramite un puntatore all'intestazione del puntatore come si fa nel secondo programma.

Quindi la funzione dovrebbe essere dichiarata come

void begin(node **head);

E devi passare la testa del puntatore indirettamente attraverso un puntatore ad essa

begin( &head );

In questo caso dereferenziando il puntatore passato la funzione otterrà un accesso diretto alla testa del puntatore originale dichiarata in main e potrà cambiarla (non una copia del suo valore come avviene nella prima definizione della funzione)

new->next = *head;
*head = new;

Per renderlo più chiaro considera questo semplice programma dimostrativo.

#include <stdio.h>

typedef int T;

void f( T t )
{
    t = 10;
}

int main(void) 
{
    T t = 0;
    
    printf( "Before calling f t is equal to %d\n", t );
    
    f( t );
    
    printf( "After  calling f t is equal to %d\n", t );

    return 0;
}

La sua uscita è

Before calling f t is equal to 0
After  calling f t is equal to 0

Poiché la funzione f si occupa di una copia del valore dell'argomento passato, il valore della variabile tdichiarata in main non è stato modificato.

Quindi è necessario passare la variabile originale tper riferimento tramite un puntatore come

#include <stdio.h>

typedef int T;

void f( T *t )
{
    *t = 10;
}

int main(void) 
{
    T t = 0;
    
    printf( "Before calling f t is equal to %d\n", t );
    
    f( &t );
    
    printf( "After  calling f t is equal to %d\n", t );

    return 0;
}

Ora l'output del programma è

Before calling f t is equal to 0
After  calling f t is equal to 10

In questi programmi dimostrativi il nome Tè usato come alias per il tipo inte in main l'oggetto tha questo tipo.

Supponiamo ora che il nome T sia un alias per il tipo int *.

typedef int * T;

In questo caso una dichiarazione in main come ad esempio

T t = NULL;

significa che la variabile tha il tipo di puntatore int *. Cioè è equivalente a

int * t = NULL;

Quindi per passarlo a una funzione che deve cambiare la variabile originale t dobbiamo passarlo per riferimento like

f( &t );

ciò significa che la funzione corrispondente deve avere il tipo di parametro dichiarato come

void f( T *t );

ma come Tè un alias per int *quindi significa che la funzione ha un parametro del tipo int **.

void f( int * *t );
1 ScottHunter Aug 18 2020 at 21:13

Perché headè (effettivamente) una variabile locale, quindi cambiarla non ha alcun effetto al di fuori della funzione, mentre cambiare *headcambia ciò che headpunta a, e quindi lo fa.

Se si desidera che una funzione sia in grado di modificare il valore in una intvariabile (diciamo, x), le si passa un puntatore a x, che avrebbe il tipo int*e si otterrebbe il puntatore xutilizzando &x. Lo stesso vale indipendentemente dal tipo x.

1 arfneto Aug 19 2020 at 03:16

Un po' di confusione può derivare dalla dichiarazione

    node        *head;

invece di

    node*       head;

Stai dichiarando head. headè la variabile ed è un puntatore. Non è un nodo. Si noti inoltre che un nodo non è un elenco collegato: un elenco collegato è una raccolta di nodi e possibilmente qualcos'altro per avere un'implementazione utile. Ne parleremo più avanti alla fine.

Il fatto è che hai main()dichiarato head, solo un file node*. Il nodo stesso non esiste ancora. Hai dichiarato begin()come

    void begin(node *head);

e penso che lo vedrai più chiaramente come

    void begin(node*  parameter);

parameterè node*.

All'interno begin()si ottiene una copia del puntatore e la modifica del puntatore non cambierà il puntatore originale in main(). Nel tuo caso indicherà per main()sempre NULL.

Ciò che conta è che un puntatore è come qualsiasi variabile: un puntatore ha un indirizzo. E un contenuto. Quando passi per valore, proprio come hai fatto tu, il puntatore begin()inizia con NULL, il VALUE che proviene da main(). Ma il legame tra loro finisce nella chiamata: il valore iniziale.

Quando passi un puntatore a begin(), usando l'operatore 'indirizzo di' e scrivendo &headle cose cambiano: lo cambierai usando l'operatore nel '*'senso che cambierai l'indirizzo a cui punta, quindi cambierà in main(). Poiché headè node*un puntatore ad esso verrà dichiarato comenode**

Ma considera di cambiare la dichiarazione di begin()per un elenco collegato usando:

    node* begin(node* node);

La logica è che l'inserimento di un nodo può cambiare l'intestazione dell'elenco, quindi si restituisce il nuovo indirizzo, come in

node* _insert_begin(int value, node* pNode)
{
    node* new = (node*)malloc(sizeof(node));
    new->data = value;
    new->next = pNode;
    return new;
}

è un modo comune per scrivere questo. Un altro è usare node**.

Nel modo in cui sto descrivendo qui, qualsiasi operazione che può cambiare l'inizio dell'elenco deve

  • restituire la nuova testa
  • ricevere e aggiornare un puntatore al puntatore della testa

Si veda ancora questo codice che si inserisce all'inizio della lista:

node* _insert_begin(int value, node* pNode)
{   // insert 'value' at the start of the list
    node* new = (node*)malloc(sizeof(node));
    (*new).data = value;
    new->next = pNode;
    return new;
}

tornando newti headaggiorni. E puoi scrivercimain()

node* another = NULL;
display_list(another);

// inserts 5 to 0 at the beginning
for (int i = 5; i >= 0; i -= 1)
    another = _insert_begin(i, another);
printf("inserted 5..0 at the beginning\n");
display_list(another);

Nota la linea another = _insert_begin(i, another);e vedrai come main()viene aggiornato il puntatore.

Questa è l'uscita

empty list
inserted 5..0 at the beginning
       0        1        2        3        4
       5
list has 6 elements

Usando questa implementazione di display_list(), che stampa 5 valori per riga:

int display_list(node* p)
{
    if (p == NULL)
    {
        printf("empty list\n");
        return 0;
    };
    int count = 0;
    // not empty
    do
    {
        printf("%8d ", p->data);
        count++;
        if (count % 5 == 0) printf("\n");
        p = p->next;
    } while (p != NULL);
    if (count % 5 != 0) printf("\n");
    printf("list has %d elements\n", count);
    return count;
};

Un altro esempio: l'inserimento alla fine

si noti che l'inserimento alla fine può anche cambiare l'intestazione, nel caso in cui la lista sia vuota, quindi dobbiamo comunque restituire l'indirizzo di testa

node* _insert_end(int value, node* pNode)
{   // insert value at the end of the list
    node* new = (node*)malloc(sizeof(node));
    new->data = value;
    new->next = NULL;
    if (pNode == NULL) return new;
    node* p = pNode;
    while (p->next != NULL) p = p->next;
    p->next = new;
    return pNode;
}

Altro utilizzo: inserimento in ordine crescente

Certo, l'inserimento in ordine crescente può anche cambiare la testa, come in

node* _insert_ordered(int value, node* pNode)
{   // insert value at ascending order in the list
    node* new = (node*)malloc(sizeof(node));
    new->data = value;
    new->next = NULL;
    if (pNode == NULL) return new;

    node* p = pNode;
    node* prev = NULL; // previous node: list if forward only
    while (p->next != NULL)
    {
        if (new->data < p->data)
        {
            // insert before first greater than value
            if (prev == NULL)
            {
                // new head
                new->next = p;
                return new;
            };  // if()
            prev->next = new;
            new->next = p;
            return pNode; // no change in head
        };
        prev = p; p = p->next; // updates pointers
    };  // while()
    // we are at the end: new will be the last?
    if (new->data < p->data)
    {
        if (prev == NULL)
            pNode = new;
        else
            prev->next = new;
        new->next = p;
    }
    else
    {
        p->next = new;
    };
    return pNode;
}   // _insert_ordered()

Eliminazione di un elenco

Anche l'eliminazione di una lista dovrebbe restituire node*a per invalidare il puntatore head. È normale. Man mano che ti abitui al suo meccanismo, questo assicura che un puntatore non valido non rimanga in giro.

Si noti che questa logica è cooperativa: è necessario riassegnare il puntatore della testa a ogni chiamata che può cambiare la testa

node* delete_list(node* H)
{
    if (H == NULL) return NULL;
    if (H->next == NULL)
    {   // single node
        free(H);
        return NULL; 
    };
    // more than one node
    do
    {   node* p = H->next;
        free(H);
        H = p;
    } while (H != NULL);
    return NULL;
};

Un programma in esecuzione

Output del programma di esempio

empty list
inserted 5..0 at the beginning
       0        1        2        3        4
       5
list has 6 elements
inserted 6 to 10 at the end
       0        1        2        3        4
       5        6        7        8        9
      10
list has 11 elements
inserted 0 to 10, ordered
       0        0        1        1        2
       2        3        3        4        4
       5        5        6        6        7
       7        8        8        9        9
      10       10
list has 22 elements
inserted -1 to -10, ordered
     -10       -9       -8       -7       -6
      -5       -4       -3       -2       -1
       0        0        1        1        2
       2        3        3        4        4
       5        5        6        6        7
       7        8        8        9        9
      10       10
list has 32 elements
inserted 11 to 20, ordered
     -10       -9       -8       -7       -6
      -5       -4       -3       -2       -1
       0        0        1        1        2
       2        3        3        4        4
       5        5        6        6        7
       7        8        8        9        9
      10       10       11       12       13
      14       15       16       17       18
      19       20
list has 42 elements
about to delete list
empty list

Il programma di esempio in C

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

typedef struct str_node
{
    int             data;
    struct str_node* next;
}   node;

void    begin(node* pNode);
node*   delete_list(node*);
int     display_list(node*);
node*   _insert_begin(int, node*);
node*   _insert_end(int, node*);
node*   _insert_ordered(int, node*);

int main()
{
    node* another = NULL;
    display_list(another);

    // insert 5 to 0 at the beginning
    for (int i = 5; i >= 0; i -= 1)
        another = _insert_begin(i, another);
    printf("inserted 5..0 at the beginning\n");
    display_list(another);

    // insert 6 to 10 at the end
    for (int i = 6; i <= 10; i += 1)
        another = _insert_end(i, another);
    printf("inserted 6 to 10 at the end\n");
    display_list(another);

    // insert 0 to 10 ordered
    for (int i = 0; i <=10; i += 1)
        another = _insert_ordered(i, another);
    printf("inserted 0 to 10, ordered\n");
    display_list(another);

    // insert -1 to -10 ordered
    for (int i = -1; i >= -10; i -= 1)
        another = _insert_ordered(i, another);
    printf("inserted -1 to -10, ordered\n");
    display_list(another);

    // insert 11 to 20 ordered
    for (int i = 11; i <= 20; i += 1)
        another = _insert_ordered(i, another);
    printf("inserted 11 to 20, ordered\n");
    display_list(another);

    printf("about to delete list\n");
    another = delete_list(another);
    display_list(another);
    return 0;
}

node* delete_list(node* H)
{
    if (H == NULL) return NULL;
    if (H->next == NULL)
    {   // single node
        free(H);
        return NULL; 
    };
    // more than one node
    do
    {   node* p = H->next;
        free(H);
        H = p;
    } while (H != NULL);
    return NULL;
};

node* _insert_begin(int value, node* pNode)
{   // insert 'value' at the start of the list
    node* new = (node*)malloc(sizeof(node));
    (*new).data = value;
    new->next = pNode;
    return new;
}

node* _insert_end(int value, node* pNode)
{   // insert value at the end of the list
    node* new = (node*)malloc(sizeof(node));
    new->data = value;
    new->next = NULL;
    if (pNode == NULL) return new;
    node* p = pNode;
    while (p->next != NULL) p = p->next;
    p->next = new;
    return pNode;
}

node* _insert_ordered(int value, node* pNode)
{   // insert value at ascending order in the list
    node* new = (node*)malloc(sizeof(node));
    new->data = value;
    new->next = NULL;
    if (pNode == NULL) return new;

    node* p = pNode;
    node* prev = NULL; // previous node: list if forward only
    while (p->next != NULL)
    {
        if (new->data < p->data)
        {
            // insert before first greater than value
            if (prev == NULL)
            {
                // new head
                new->next = p;
                return new;
            };  // if()
            prev->next = new;
            new->next = p;
            return pNode; // no change in head
        };
        prev = p; p = p->next; // updates pointers
    };  // while()
    // we are at the end: new will be the last?
    if (new->data < p->data)
    {
        if (prev == NULL)
            pNode = new;
        else
            prev->next = new;
        new->next = p;
    }
    else
    {
        p->next = new;
    };
    return pNode;
}   // _insert_ordered()

int display_list(node* p)
{
    if (p == NULL)
    {
        printf("empty list\n");
        return 0;
    };
    int count = 0;
    // not empty
    do
    {
        printf("%8d ", p->data);
        count++;
        if (count % 5 == 0) printf("\n");
        p = p->next;
    } while (p != NULL);
    if (count % 5 != 0) printf("\n");
    printf("list has %d elements\n", count);
    return count;
};

Una struttura dell'elenco collegato probabilmente più utile

Considera quanto segue

struct no
{
    void*       item;
    struct no*  next;
    struct no*  prev;
};  // no
typedef struct no Node;

typedef struct
{   // example, more flexible
    char*       name;
    unsigned    size;
    unsigned    capacity;
    Node*       head;
    Node*       tail;
}   Linked_list;

In questo modo una lista collegata è definita come un contenitore di nodi.

  • Ha anche un optional name.
  • sizeè sempre disponibile e aggiornato
  • un limite di dimensione può essere implementato comecapacity
  • inserire alla fine e all'inizio non richiede di seguire tutti gli altri nodi, poiché l'elenco incapsula i puntatori sia alla testa che alla coda
  • un nodo ha puntatori ai nodi successivi E precedenti, quindi alcuni dati come playlist o raccolte del genere possono essere iterati più facilmente.
  • un programma può avere qualsiasi numero di elenchi poiché ognuno incapsula tutti questi metadati.
  • un elenco può contenere qualsiasi cosa poiché i dati sono un puntatore a void,void*
  • funzioni come empty() o size() possono essere implementate facilmente
  • tutte le funzioni usano un puntatore all'elenco
    Linked_list  ll_one;
    Linked_list  many_ll[20];
    Linked_list* pLL = &ll_one;
user3629249 Aug 19 2020 at 21:07

per quanto riguarda:

void begin(node *head){

La modifica cambia headsolo lo stack di chiamate 'head', ciò che è necessario è cambiare dove punta 'head' nella funzione del chiamante. PER fare ciò, il chiamante deve passare l'indirizzo di 'capo'. Il fatto che 'head' sia, di per sé, un puntatore non aiuta con la chiarezza di ciò che deve essere fatto,