Le liste

Per cominciare, vediamo come andava risolta l'esercitazione non guidata della lezione scorsa.
Nell'esercitazione si dovevano prevedere le seguenti opzioni:
1) inserimento di un elemento in testa alla lista (e' piu' semplice);
2) cancellazione dell'ultimo elemento inserito;
3) stampa degli elementi correnti della lista;
piu' un 'ultima opzione per uscire dal programma. 


/* programma per la gestione di liste di punti */

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

typedef struct elemento
      {
        int ascissa;
        int ordinata;
        struct elemento *next;
       } punto;

punto* inserisci(punto *);

void stampa(punto *first);

punto *cancella(punto *first);   
  
int main(){
    int scelta;                
    punto *primo=NULL;   //Puntatore al primo elemento, inizializzato a NULL
    do
    {
 printf("Scegli la tua opzione\n");
 printf("1) Inserisci nuovo punto\n");
 printf("2) Cancella ultimo punto\n");
 printf("3) Stampa lista corrente dei punti\n");
 printf("4) Termina programma\n");
 scanf("%d",&scelta);
        switch(scelta){
   case 1: primo=inserisci(primo); break; //Ins. nuovo punto in testa
          case 2: primo=cancella(primo);break; //cancella ultimo punto inserito
          case 3: stampa(primo); break; //stampa gli elementi correnti della lista
   case 4: break;
   default: printf("Scelta scorretta; inserisci nuovamente\n\n");
          }
    } while (scelta!=4);
    printf("\nProgramma terminato correttamente\n");
    return EXIT_SUCCESS;
}

punto* inserisci(punto *first)
 {
  int asc,ord;
  punto *q;
  printf("\nInserisci le coordinate del nuovo punto\n");
  printf("Ascissa=");
  scanf("%d",&asc);
  printf("\nOrdinata=");
  scanf("%d",&ord);
  q=(punto *)malloc(sizeof(punto)); //allocazione dinamica memoria 
  if (q==NULL) { //verifico che l'allocazione abbia avuto successo
    printf("\nMemoria esaurita!\n");
    return(first);
     }
  q->ascissa=asc;
  q->ordinata=ord;
  q->next=first; //inserimento in testa
  printf("Punto (%d,%d) inserito con successo.\n",q->ascissa,q->ordinata);
  return q;
 }

punto *cancella(punto *first) 
 {
  punto *p;
  if (first==NULL) printf("\nNessun elemento nella lista.\n\n");
     else {
     p=first->next;
     free(first); //deallocazione della memoria
    }
  return p;
 }
  
void stampa(punto *first)
 {
  int cont=1;
  punto *q;
  if (first==NULL) printf("La lista Ë vuota.\n");
    else
      for(q = first; q != NULL; q = q-> next)
       {
        printf("%d -- (%d,%d)\n",cont,q->ascissa,q->ordinata);
        cont++;
       }



Gli alberi

Gli alberi sono una struttura dati molto utilizzata in informatica, ad esempio per rendere piu' efficienti le operazioni di ricerca di un elemento in un insieme ordinato. Gli alberi utilizzati per questo scopo sono detti alberi binari di ricerca, e possono essere definiti in C utilizzando le strutture nel modo seguente.

 
typedef struct elemento
      {
        int valore;
        struct elemento *sx;
        struct elemento *dx;
       } albero;


Come si puo' vedere, gli alberi binari si distinguono dalle liste per la presenza di due puntatori: il primo puntatore punto al sottoalbero sinistro, mentre il secondo al sottoalbero destro. Dunque, a differenza delle liste che possono essere viste come una struttura lineare, gli alberi hanno una strutturata ramificata (vedi figura).

Albero


In un albero, esiste un unico nodo radice, che permette l'accesso agli altri elementi dell'albero. Un generico nodo interno dell'albero ha un unico nodo padre, ed uno o piu' nodi figli. Nel caso degli alberi binari, un nodo puo' avere al piu' due figli. Un nodo senza figli e' detto nodo foglia.

L'albero della figura precedente e' un albero binario, ma non e' un albero binario di ricerca. Infatti, gli alberi binari di ricerca godono della seguente proprieta': dato un qualsiasi elemento E dell'albero il cui campo valore e' x, il valore di tutti gli elementi contenuti nel sottoalbero sinistro di E e' <=x, mentre il valore di tutti gli elementi contenuti nel sottoalbero destro di E e' > x. Ad esempio, l'albero seguente e' un albero binario di ricerca.
Albero di Ricerca

Gli alberi di ricerca permettono di velocizzare notevolmente le operazioni di ricerca di un elemento in un insieme ordinato, rispetto ad esempio
al caso in cui gli elementi siano memorizzati in una lista ordinata.

Molto spesso gli alberi si prestano ad una definizione ricorsiva delle funzioni che operano su di essi. Ad esempio, vediamo come scrivere una
funzione che, dato un albero binario di ricerca che non contiente valori duplicati ed un elemento intero x da ricercare nell'albero,
restituisce il puntatore all'elemento dell'albero di valore x, se esiste, e restituisce NULL altrimenti.





/* funzione verifica la presenza di un elemento
in un albero binario di ricerca */

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


typedef struct elemento{
 int valore;
 struct elemento *sx;
 struct elemento *dx;
} albero;


albero* verifica(albero *r,int x){
if r==NULL return NULL;
if (r->valore==x) return r;
  else 
    if (r->valore < x) return verifica(r->dx,x);
    else return verifica(r->sx,x);
}



Esercitazione non guidata


Risolvere il seguente esercizio. Non occorre spedirlo via e-mail.

Esercizio:

Scrivere una funzione che, dato un albero binario, ne stampa tutti gli elementi. Provare a fare l'esercizio sia scrivendo una funzione ricorsiva (piu' semplice)
che una funzione iterativa (piu' complicato).


Torna alla HomePage del corso