[C] Definizione liste

[Fenix797]

Ciao, ho cercato molte volte su internet una spiegazione punto per punto su come dichiarare, inizializzare, utilizzare una lista in linguaggio C, ma niente da fare, solo esempi o spiegazioni confusionarie.

Senza andare nei particolari di un esercizio che mi richiede una media dei valori, una stampa o altro, qualcuno riesce a spiegarmi cosa devo fare per rispondere a un esercizio qualsiasi che mi richiede una lista collegata con puntatori?
Cioè cosa devo scrivere prima del main, dopo per aggiungere valori..so che ci possono essere più alternative forse, ma quella che vi sembra più immediata e semplice va bene. Grazie!

[iggy]

Ti lascio il codice con cui il mio prof ci ha spiegato le liste in classe:

Codice:

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

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

struct node *create(int);
void destroy(struct node *);
int length(struct node *);
struct node *find(struct node *, int);
struct node *last(struct node *);
struct node *append(struct node *, struct node *);
void printlist(struct node *);

struct node *create(int data) {
  struct node *ptr = malloc(sizeof(struct node));
  ptr->data = data;
  ptr->next = NULL;

  return ptr;
}

int length(struct node *head) {
  int len = 0;
  for(struct node *n = head; n; n = n->next) {
    ++len;
  }

  return len;
}

struct node *find(struct node *head, int data) {
  for(struct node *n = head; n; n = n->next) {
    if(n->data == data)
      return n;
  }
  return NULL;
}

struct node *last(struct node *head) {
  for(struct node *n = head; n; n = n->next) {
    if(n->next == NULL)
      return n;
  }
  return NULL;
}

struct node *append(struct node *head1, struct node *head2) {
  struct node *last1 = last(head1);
  last1->next = head2;

  return head1;
}

void printlist(struct node *head) {
  for(struct node *n = head; n; n = n->next) {
    printf("%d ", n->data);
  }
  putchar('\n');
}

void destroy(struct node *head) {
  struct node *next = head;

  while(next) {
    struct node *n = next;
    next = n->next;
    free(n);
  }
}

int main() {
  struct node *list =
    append(create(3), append(create(42), append(create(2), create(4))));

  printf("Elementi della lista: ");
  printlist(list);

  printf("Lunghezza della lista: %d\n", length(list));

  printf("Lista a partire da 'find(list, 42)': ");
  printlist(find(list, 42));

  destroy(list);

  return 0;
}

Se hai dubbi sul funzionamento di una procedura prova a chiedermi.

Una funzione che ritorni la media potrebbe essere una cosa del genere:

Codice:

float media(struct node *head) {
  int sommaElementi = 0;
  int lunghezza = length(head);
  for(struct node *n = head; n; n = n->next) {
    sommaElementi = sommaElementi + n->data;
   
  }
  return (float)sommaElementi/lunghezza;
}

o se non hai implementata la funzione length():

Codice:

float media(struct node *head) {
  int sommaElementi = 0;
  int i = 0;
  for(struct node *n = head; n; n = n->next) {
    sommaElementi = sommaElementi + n->data;
    i++;
   
  }
  return (float)sommaElementi/i;
}

[Fenix797]

Intanto grazie mille davvero!
Suddividendo quindi le cose essenziali, dimmi se scrivo commenti sbagliati:
struct node { //node è il nome che voglio dare alla lista
int data; //data è in pratica un campo come se fosse il campo del titolo di un libro o il numero di pagine
struct node *next; //qui sorge il problema, è un puntatore di cui next è il "nome qualsiasi" e sarebbe l'inizializzazione?
};

struct node *create(int); //questo non capisco cosa crea
void destroy(struct node *);
int length(struct node *);
struct node *find(struct node *, int);
struct node *last(struct node *);
struct node *append(struct node *, struct node *); //queste righe help
void printlist(struct node *); //questo immagino stampi la lista

non ti voglio richiedere tutto il programma
però ad esempio ptr->data= data sta richiamando l'elemento a cui punta ptr e gli sta attribuendo valore data?

L'ho detto ci vorrebbero proprio le cose base, nel senso che senza di quelle la lista con puntatori proprio non esiste, ad esempio un puntatore come si inizializza, come cambio il valore a cui punto, come creo la lista cose così. Probabilmente è più difficile questo passo per passo che scrivere un programma intero una volta capito.

[iggy]

con struct node *next; io sto dichiarando che la lista non è formata solo dal campo int specificato sopra, ma anche da un puntatore chiamato "next" e questo puntatore è di tipo struct node quindi punterà a un altro elemento di tipo node che abbiamo appena definito, in questo modo si crea il legame fra un nodo e l'altro. Puoi vederla come una sorta di chiamata ricorsiva.

create() crea un nuovo nodo. La funziona malloc ha il compito di allocare una certa dimensione nella memoria e il parametro che si passa specifica che abbiamo bisogno di tanta memoria quanta serve per allocare un nodo.
Quindi grazie a malloc (che ritorna un puntatore alla memoria appena allocata) abbiamo creato un nodo "ptr" e nelle righe successive definiamo che data è inizialmente NULL e che questo nodo punta a nessun altro elemento. Le frecce "->" si utilizzano per specificare che voglio accedere a ptr ma più in particolare all'elemento data o next di ptr.

append() permette di "collegare" un nodo ad una lista. Nei parametri specifichiamo i due nodi interessati. Con la chiamata last() accediamo all'ultimo elemento della lista specificata nel primo parametro (solitamente si vuole inserire il nodo alla fine di una lista) e vogliamo assegnare il nodo head2 all'elemento next ( tramite last1->next=head2).
----

ptr->data= data // accedo alla variabile data di prt e a questa variabile assegno il valore di data (non confondere il primo data con il secondo: il primo da parte della struttura del nodo ptr, mentre il secondo, che poteva essere chiamato anche "pippo", è un intero passato alla funzione.

Un puntatoreèuna variabile che contiene l'indirizzo di un'altra variabile.
La dichiarazione di un puntatore avviene in modo simile a quella di un’altra variabile:
int *p = valore iniziale;
Il tipo int * indica un puntatore a variabili di tipo int.
Il puntatore va inizializzato con l’indirizzo di una variabile di tipo int, oppure con il valore speciale NULL.
Facciamo un esempio:

Codice:

int numero = 10;
int *puntatore = &numero//ora puntatore punta a x
printf("%d",*puntatore);//attraverso l'asterisco si specifica che si vuole accedere al contenuto del puntatore quindi questa istruzione stampa il contenuto di puntatore, ma il contenuto è numero che vale 10; quindi stampa 10.


Ricordati che il C non è come Java che si possono passare le variabili a funzioni esterne senza troppi problemi. In C l'unico modo di modificare una variabile da una funzione è utilizzando i puntatori.

[vict85]

A mio avviso una implementazione di una lista NON dovrebbe contenere le funzioni length e append (a meno che la lista in questione non sia stata ottimizzata per questo tipo di operazioni, ma non è questo il caso). Infatti queste operazioni richiedono una complessità lineare. Trovo più corretto sostituire append con una funzione per inserire un elemento all'inizio della lista e un'altra per inserire un elemento subito dopo il nodo presentato. Queste ultime hanno infatti complessità costante.

Detto questo, nel codice della media suggerirei di calcolare la lunghezza direttamente del ciclo invece di chiamare la funzione length per evitare di dover caricare la memoria di un elemento due volte.

Per capire perché sconsiglio la funzione append, basta calcolare la complessità delle seguenti funzioni:

Codice:

struct node * create_big_append( unsigned int n )
{
    if( n <= 0 )
        return NULL;
    struct node * list = create( 0 );
    for(int i = 1; i < n; i++)
    {
        struct node * el = create( i );
        list = append( list, el);
    }
    return list;
}

struct node * create_big( unsigned int n )
{
    if( n <= 0 )
        return NULL;
    struct node * list = create( 0 );
    struct node * last = first;
    for(int i = 1; i < n; i++)
    {
        struct node * el = create( i );
        last->next = el;
        last = el;
    }
    return list;
}

La seconda versione può anche essere implementata usando una funzione per inserire un nodo dopo un altro (ma fa qualche operazione in più). Si può anche fare con la funzione che inserisce sempre all'inizio della lista (qui inserisco direttamente all'inizio senza definire la funzione per farlo):

Codice:

struct node * create_big_v2( unsigned int n )
{
    struct node * list = NULL;
    for(int i = n; i > 0; i--)
    {
        struct node * el = create( i );
        el->next = list;
        list = el;
    }
    return list;
}

Ho tra l'altro notato che la funzione append non è robusta. Se infatti si chiama append(NULL, el) il programma crasha.

P.S.: Ho scritto le funzioni velocemente e non le ho ne compilate ne testate. Quindi testale prima di usarle da qualche parte.

[Fenix797]

Grazie a tutti dell'aiuto anche se siete scesi un po' nel particolare, sono riuscita a capire le cose "base" per usare liste e soprattutto puntatori. [quote="iggy"][/quote] Grazie delle spiegazioni dettagliate, utilissime!

Devo fare una domanda sempre sull'argomento ma penso di dover fare una nuova discussione perché è su un esercizio.

[apatriarca]

Lo scopo principale di insegnare le liste concatenate è quella di far prendere dimestichezza con puntatori e allocazione dinamica della memoria. Quasi tutte le operazioni consistono infatti nel seguire i puntatori e modificarli in modo che il risultato sia ancora una lista. Esistono infiniti modi in cui si possa richiedere di agire su una lista ed è quindi difficile fornire una ricetta che sia utilizzabile per ogni esercizio che un professore potrebbe richiedere. Oltretutto molti di queste implementazioni, anche quelle fornite dai professori, sono effettivamente complicate da usare nella pratica*. L'unico modo per riuscire a rispondere a questi problemi senza problemi è effettivamente acquisire questa conoscenza più approfondita sul funzionamento di puntatori, allocazione di memoria e sulle liste concatenate.

* Si consideri ad esempio cosa succederebbe se due liste avessero un nodo in comune e si cercasse di deallocare una delle due. E' semplice creare una lista circolare e in alcune situazioni potrebbe essere desiderata. Ma cosa succede quando una lista circolare viene passata ad una funzione come quella che calcola la media? Cosa succede se si cerca di deallocare tale lista? Si può decidere di ignorare tali problemi, creare una implementazione più complicata per tenere traccia di questi casi particolari oppure nascondere la lista dietro ad una nuova struttura che impedisce all'utente di accedere direttamente ai nodi.