Le liste








#include <stdio.h>     // per printf()
#include <string.h>    // per le funzioni di gestione delle stringhe
#include <stdlib.h>    // per malloc()

struct temp{char titolo[100];
                 char *autore;
                 int collocazione;};


typedef struct temp libro;

int main()
{
  ... // istruzioni

  libro elenco[30];

  ... // istruzioni

}













L'istruzione con cui viene dichiarato un array formato da 30 elementi di tipo libro produce l'allocazione di una quantità di memoria tale da contenere 30 oggetti di tipo libro. Tali oggetti vengono posizionati, all'interno della memoria, uno di seguito all'altro (ovvero le aree di memoria relative a quei 30 elementi sono contigue)






                                                           












Durante l'esecuzione del programma (ovvero, durante l'inserimento dei dati da parte del bibliotecario) si possono presentare le seguenti situazioni:

(1) devo eliminare un elemento già inserito
(2) ho bisogno di qualche elemento in più (per inserire dati relativi a più di 30 libri)



Un oggetto come un vettore non permette di gestire agilmente situazioni di questo tipo (non posso disfarmi improvvisamente di un elemento dell'array né posso, con semplicità, aggiungerne di nuovi). La scarsa flessibilità dell'array deriva dal fatto che esso deve essere costituito da oggetti tutti uguali disposti uno dopo l'altro.








Visto che a noi fa comodo avere degli oggetti tutti uguali (per memorizzare dei dati relativi ai libri presenti in biblioteca), facciamo in modo di non disporli uno dopo l'altro (in questo modo NON POTREMO PIU' USARE L'ARITMETICA DEI PUNTATORI !).























Ora, l'unico elemento che abbiamo a disposizione per individuare i vari elementi all'interno della memoria è il loro indirizzo. Ogni elemento, quindi, dovrà contenere l'indirizzo del successivo e l'unico elemento che ci permette di trovare tutti gli altri è il primo, ovvero la testa della lista.























In questo modo diventa più semplice aggiungere un nuovo elemento in coda,




















... eliminarne uno dalla lista




















... inserirne uno nella lista.























Il prototipo della struttura che deve servire per la costruzione della lista è quindi:





struct ntemp{char titolo[100];
                   char *autore;
                   int collocazione;
                   struct ntemp *next ;};

typedef struct ntemp nlibro;












Comparendo esplicitamente in ciascuna solo L'INDIRIZZO della successiva, la gestione di tutta la lista viene spontaneamente effettuata solo mediante puntatori.



FONDAMENTALE
: se sappiamo dove inizia una lista, dobbiamo poter determinare anche dove la lista termina. Per convenzione, assegnamo al puntatore next dell'ultimo elemento della lista il valore NULL
























(1) creiamo il primo elemento (la testa della lista)

nlibro *testa;   // puntatore non inizializzato

// alloco memoria per UNA struttura di tipo nlibro
testa = (nlibro *) malloc (sizeof(nlibro));

/* ora che ho allocato memoria, ovvero che ho creato la struttura, posso accedere agli elementi della struttura */
testa -> next = NULL;


A questo punto testa è il primo (ed anche l'ultimo) elemento della lista.



Per questioni di comodità la creazione di un elemento può essere demandata ad una funzione (così siamo sicuri che essa SICURAMENTE inizializza a NULL il puntatore next).



nlibro *nuovo (void);


nlibro *nuovo (void)
{nlibro * temp;
  temp = (nlibro *) malloc (sizeof(nlibro));
  temp -> next = NULL;
  return temp;
 }














La stessa funzione può essere anche utilizzata per l'esecuzione di eventuali istruzioni di inizializzazione della struttura appena creata.


nlibro *nuovo (void);


nlibro *nuovo (void)
{nlibro * temp;
  temp = (nlibro *) malloc (sizeof(nlibro));
  temp -> next = NULL;

  temp -> collocazione = 0 ;   // inizializzo un altro membro della struttura
  temp -> autore = (char *) malloc ( 51 * sizeof(char));

  return temp;
 }



















(2) Inserimento di un nuovo elemento in coda alla lista. Per svolgere questa operazione utilizziamo una funzione. Se la lista contiene elementi, allora la funzione deve inserire il nuovo in coda alla lista; altrimenti il nuovo elemento diventa la testa della lista. La funzione deve restituire il puntatore al primo elemento della lista che contiene il nuovo elemento.


 nlibro *aggancia ( nlibro *,  nlibro *);

/*
si suppone che nuovo_el sia un puntatore ad una struttura già creata in precedenza
*/

 nlibro *
aggancia ( nlibro * primo_el,  nlibro * nuovo_el)
{nlibro * temp;
  temp = primo_el;

/*
Prima di agganciare in coda alla lista, devo determinare se la lista è vuota o piena. Se è piena, l'ultimo elemento è quello che ha il puntatore next pari a NULL; fino a quando il puntatore next è diverso da NULL so che dopo l'elemento che sto considerando ce n'è uno nuovo.
*/

 if(primo_el == NULL)
   {temp = nuovo_el;
     return temp;}
 else
   {while(primo_el -> next != NULL)
      primo_el = primo_el -> next ;

     primo_el - > next = nuovo_el;
     return temp;} // il primo elemento della lista
 }























(3) supponiamo ora di voler assegnare dei valori agli elementi delle strutture



void assegna( nlibro *);

/* si suppone che la lista abbia per lo meno un elemento */
void assegna( nlibro * testa)
{
      printf("Inserisci il titolo del libro (max 99 char)");
      gets (testa -> titolo);

/* testa -> autore era stato inizializzato in fase di creazione della struttura */
      printf("Inserisci il nome dell'autore (max 50 char) ");
      gets (testa -> autore);
  
      printf("Inserisci la collocazione del volume");
      scanf("%d", & ( testa -> collocazione ) );
}


















Unendo queste tre funzioni è possibile costruire una lista ed inizializzarne gli elementi. Il numero di elementi presenti nella lista sarà ESATTAMENTE quello richiesto dall'utente per memorizzare i dati relativi ai libri.




// inizio codice

#include <stdlib.h>
#include <stdio.h>
#include "myfun.h"
   // in questo file posso dichiarare il prototipo di struttura


int main()
{// inizializzo SUBITO i puntatori !!
   nlibro * testa = NULL;
   nlibro * da_inserire = NULL;
   char temp[4];

  while(1)
   {printf("vuoi inserire i dati relativi ad un libro ? (s/n)");
     scanf("%s",temp);
     if(temp[0] == 'n') break;
     
     da_inserire = nuovo();
     assegna(da_inserire);
     testa=aggancia(testa,da_inserire);
    }

 return 0;}
// fine codice