Ripartiamo dal prototipo di struttura utilizzato ieri:


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

typedef struct ntemp nlibro;




L'obiettivo è quello di preparare una lista di strutture utilizzando strutture aventi il prototipo indicato qui sopra.

Per preparare una lista devo:

(1) saper creare un nuovo elemento
(2) saperlo inizializzare
(3) saperlo agganciare alla lista (o crearne una nuova, nel caso essa sia vuota)


(1) e (2) agiscono sulla SINGOLA STRUTTURA e quindi tali operazioni possono essere effettuate come se stessimo agendo su una struttura qualsiasi mediante il puntatore alla struttura stessa.

Attenzione: gli elementi di una lista vengono gestiti mediante puntatori, quindi vengono sempre passati alle funzioni per riferimento !

(1) creazione di un nuovo elemento

nlibro *nuovo (void);

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




















(2) inizializzazione di un nuovo elemento

void assegna( nlibro *);

void assegna( nlibro * elemento)
{
      printf("Inserisci il titolo del libro (max 99 char)");
      gets (elemento -> titolo);

      elemento -> autore = (char *) malloc (51 * sizeof(char));
      printf("Inserisci il nome dell'autore (max 50 char) ");
      gets (elemento -> autore);
  
      printf("Inserisci la collocazione del volume");
      scanf("%d", & ( elemento -> collocazione ) );
}
























(3) l'operazione di "agganciare" un elemento suppone che ci sappiamo muovere all'interno di una lista.


Facciamo il paragone con i vettori; cerchiamo di raggiungere l'ultimo elemento di un vettore usando un indice per scorrere il vettore stesso. Il numero di elementi contenuti nel vettore è pari a 40.



int *vettore;
vettore = (int *) malloc (40 * sizeof(int));
int indice = 0;

while(1)
  {if(indice==39)
     {printf("questo è l'indirizzo dell'ultimo elemento %p", vettore + indice);
       break;}
    indice ++;
  }


L'operazione che svolgo è la seguente: sposto in avanti l'indice che mi permette di scorrere l'intero vettore; quando trovo la condizione che mi indica che sono arrivato alla fine mi fermo.


Eseguiamo quindi la stessa cosa con una lista.





Nel caso della lista bisogna ridefinire:

chi sia l'indice
come lo incremento
quale sia la condizione che mi indica quando sono arrivato in fondo alla lista




indice per scorrere la lista:
tutti gli elementi di una lista sono gestibili mediante il corrispondente indirizzo, quindi un buon indice è rappresentato da una variabile di tipo puntatore a struttura


metodo di incremento:
l'unico modo che abbiamo a disposizione per passare da un elemento all'altro è quello di utilizzare il valore del puntatore next dell'elemento cui fa riferimento l'indice


condizione di raggiungimento del fondo della lista:
                      trovo un elemento il cui membro next valga NULL







Supponiamo di avere una lista di 4 elementi: come individuo il quarto ?


nlibro *testa; // puntatore al primo elemento

testa->next;      // puntatore al secondo elemento

(testa->next) -> next;      // puntatore al terzo elemento

((testa -> next) -> next) -> next;      // puntatore al quarto elemento






















Un po' scomodo ... usiamo l'indice !

nlibro *testa; // puntatore al primo elemento
nlibro *indice;

indice = testa;    // dico all'indice di far riferimento al primo elemento

indice -> next;    // puntatore al secondo elemento

indice = indice -> next;     // ora indice diventa il puntatore al secondo elemento

indice = indice -> next;    // ora indice diventa il puntatore al terzo elemento

indice = indice -> next;    // ora indice diventa il puntatore al quarto elemento



Il metodo di incremento, quindi, consiste nell'assegnare all'indice l'indirizzo contenuto nel membro next della struttura.















Cerchiamo ora di individuare, usando questo metodo, chi sia il puntatore all'ultima struttura della lista.




nlibro *testa;
nlibro *indice;

... // istruzioni per la creazione della lista (v. dopo)

indice = testa;    // ora indice fa riferimento al primo elemento della lista

while( 1 )
  {if(indice-> next == NULL)     // ecco la condizione di raggiungimento del fondo della lista
     {
       printf(" questo è l'indirizzo dell'ultimo elemento della lista %p", indice );
       break;
      }
    indice = indice -> next;   // metodo di incremento
  }


















Sapere quale sia l'ultimo elemento di una lista è utile nel caso in cui intendiamo agganciare alla lista un eventuale nuovo elemento.

Immaginando che la variabile indice contenga l'indirizzo dell'ultimo elemento come ci aggancio un nuovo elemento ?





nlibro *aggiungi;
aggiungi = nuovo();

.. // istruzioni

indice -> next = aggiungi;

/* aggiungi -> next è stato inizializzato a NULL da nuovo(), quindi aggiungi è un buon ultimo elemento */


















A questo punto possiamo implementare la funzione che aggancia un nuovo elemento alla lista e che crea la lista nel caso in cui essa sia vuota.


Compiti che la funzione deve svolgere:

(1) se la lista è vuota, crearla (ovvero inserire un elemento)
(2) se la lista non è vuota agganciare un nuovo elemento in coda
(3) restituire il puntatore al primo elemento della lista



















/* testa rappresenta il puntatore al primo elemento della lista; se la lista è vuota testa vale NULL */


nlibro *aggancia(nlibro * testa,nlibro * nuovo_elemento)
{nlibro * indice;

    if(testa == NULL)     // lista vuota
     {return nuovo_elemento;}  // il nuovo elemento diventa il primo (e unico) della lista
    else
     {indice = testa;
       while( indice -> next != NULL )
         {indice = indice -> next;}

       // ora indice fa riferimento all'ultimo elemento
       indice -> next = nuovo_elemento;
       return testa; // puntatore al primo elemento della lista
     }
 }



















A questo punto abbiamo tutti i mezzi per poter 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)");
     gets(temp);
     if(temp[0] == 'n') break;
     
     da_inserire = nuovo();
     assegna(da_inserire);
     testa=aggancia(testa,da_inserire);
    }

 return 0;}
// fine codice












Supponiamo ora di voler effettuare una ricerca all'interno della lista: vogliamo cercare se sono stati inseriti dei libri scritti da un autore in particolare.




Compito della funzione (da svolgere in ogni elemento della lista)

(1) controllare se nella stringa cui fa riferimento il membro autore di ciascuna struttura sono contenuti i caratteri inseriti dall'utente
(2) stampare un messaggio nel caso la ricerca abbia esito positivo
(3) passare alla struttura successiva all'interno della lista
(4) la funzione si deve fermare dopo aver controllato anche l'ultimo elemento


Quindi non userò come condizione di terminazione

indice -> next != NULL

altrimenti mi fermo prima di leggere dentro l'ultimo. Userò perciò

indice != NULL

ovvero mi fermo perché l'indice NON fa riferimento ad un elemento valido (questa condizione, tra l'altro, previene accessi illegali alla memoria nel caso in cui la lista sia vuota (v. dopo))




















#include <string.h>


void ricerca (nlibro * );

void ricerca ( nlibro * testa )
{nlibro * indice;
  char temp[100];

  printf("\n Modulo di ricerca per nome dell'autore \n");
  printf("Inserisci il nome dell'autore (max 100 car)");
  gets(temp);

  /* inizia la ricerca */
  indice = testa;



  while( indice != NULL )
    {
      /* effettuo il confronto */

     if( strcmp(temp, indice -> autore ) == 0 )
      {printf("il titolo del libro scritto da %s e' : %s", indice-> autore, indice -> titolo);
        printf("\n la collocazione del testo e' : %d", indice-> collocazione ); }
      
       indice = indice -> next ;   /* passo alla struttura successiva */

     }
 }













Supponiamo ora di voler visualizzare l'elenco delle collocazioni di tutti i libri

void stampa(nlibro * );

void stampa(nlibro * testa)
{
  while(testa != NULL)
    {printf("La collocazione del libro %s e' %d", testa-> titolo,testa-> collocazione);
      testa = testa -> next;}
}

























La funzione, fino a quando non è giunta in fondo alla lista, continua a svolgere sempre il medesimo compito in modo iterativo. Tale funzione è un buon prototipo di funzione da implementare in modalità ricorsiva.



void stampa(nlibro * );

void stampa(nlibro * testa)
{
  if(testa != NULL)
    {printf("La collocazione del libro %s e' %d", testa-> titolo,testa-> collocazione);
      stampa(testa -> next);}
}


















Domanda

Studiando le strutture abbiamo visto che, all'atto della definizione di una struttura, è possibile inserire come membro della struttura un puntatore ad una struttura dello stesso tipo di quella che stiamo definendo.
Domanda: pensando un po' al perché questo sia possibile vi viene in mente come mai si possa implementare una funzione in modo ricorsivo ?