Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 7.Implementazioni di Liste puntate


Indice

  • Liste puntate semplici: Gli elementi sono organizzati in modo sequenziale e si possono scorrere in un unico verso. La lista ha un primo elemento (testa) e un ultimo elemento (coda)
  • Liste doppiamente puntate: Simili alle liste puntate semplici, ma permettono di scorrere gli elementi in entrambi i versi
  • Liste puntate semplici circolari: Sono liste puntate semplici senza testa ne coda.
  • Liste doppiamente puntate circolari: Liste doppiamente puntate senza testa ne coda.

Torniamo al linguaggio C

Per l’implementazione delle liste in linguaggio C, possiamo utilizzare due importanti costrutti:

  • STRUTTURE
  • ALLOCAZIONE DINAMICA DELLA MEMORIA

Strutture

Le strutture del C sono simili ai record del Pascal:

  • sostanzialmente permettono un’aggregazione di variabili, molto simile a quella degli array, ma a differenza di questi non ordinata e non omogenea (una struttura può contenere variabili di tipo diverso).

Per denotare una struttura si usa la parola chiave struct seguita dal nome identificativo della struttura, che è opzionale.

Nell’esempio in figura si definisce una struttura “libro” e si crea un’istanza di essa chiamata “biblio”.

Esempio: definizione di una struttura

Esempio: definizione di una struttura


Strutture

  • La variabile “biblio” può essere dichiarata anche mettendo il nome stesso dopo la parentesi graffa:
  • Inoltre, è possibile pre-inizializzare i valori, alla dichiarazione, mettendo i valori (giusti nel tipo) compresi tra parentesi graffe:
    • struct libro biblio = {“Guida al C”, “Fabrizio Ciacchi”, 2003, 45.2};
  • Per accedere alle variabili interne della struttura si usa l’operatore “.”
    • Esempio: Per assegnare alla variabile interna prezzo il valore 50 usiamo biblio.prezzo = 50;

Nuovi tipi di dato

  • Per definire nuovi tipi di dato si utilizza la funzione typedef.
  • Con typedef e l’uso di struct è possibile creare tipi di dato molto complessi, come mostrato nell’esempio in figura:
  • Per creare una variabile “guida” di tipo “t_libro”, usiamo:
    • t_libro guida={“Guida al C”, “Fabrizio Ciacchi”, 2003, 45.2};

Nuovi tipi di dato

  • Come per ogni altro tipo di dato, anche con “t_libro” si possono creare degli array:
    • t_libro raccolta[5000];
  • Nel caso di array, per accedere ad un variabile interna, si utilizza l’indice insieme all’operatore punto (.)
    • Esempio: Per assegnare il prezzo 50 al libro con indice 10 usiamo raccolta[10].prezzo = 50;

Puntatori e Strutture

Consideriamo il seguente esempio di uso congiunto di strutture e puntatori (vedi figura):

Abbiamo dunque creato una struttura di tipo PIPPO e di nome “elemento”, ed un puntatore ad una struttura di tipo PIPPO.

Per accedere ai membri interni della struttura “elemento” abbiamo usato l’operatore -> sul puntatore alla struttura.

  • In pratica, puntatore->x = 6 semplifica (*puntatore).x=6;
Costruzione di uno Stack
Puntatori e strutture
Funzione crea_lista()

Allocazione dinamica della memoria

A differenza di altri linguaggi, all’occorrenza il C permette di assegnare la giusta quantità di memoria alle variabili del programma.

Le funzioni utilizzate per gestire dinamicamente la memoria delle variabili sono principalmente:

  • malloc() e calloc(), adibite all’allocazione della memoria;
  • free() che serve per liberare la memoria allocata,
  • realloc(), che permette la modifica di uno spazio di memoria precedentemente allocato.

Infine, un comando particolarmente utile è sizeof, che restituisce la dimensione del tipo di dato da allocare.

Queste funzioni sono incluse nella libreria malloc.h,

Esempio di allocazione dinamica


Uso di realloc()

La sintassi della funzione realloc() ha due argomenti, il primo riguarda l’indirizzo di memoria, il secondo specifica la nuova dimensione del blocco;

Esempio di frammento di codice (vedi figura)

Esempio di frammento di codice

Esempio di frammento di codice


Rischi della gestione dinamica della memoria

Produzione di “garbage”:

  • quando la memoria allocata dinamicamente resta logicamente inaccessibile, perché si sono persi i riferimenti:
  • Esempio:
    • P=malloc(sizeof(TipoDato));
    • P=Q;

Riferimenti “dangling”(fluttuanti):

  • quando si creano riferimenti a zone di memoria logicamente inesistenti
  • Esempio:
    • P=Q; free(Q);
  • l’istruzione free libera l’area di memoria ma non provoca un assegnamento automatico di NULL al puntatore Q, per cui P e Q si riferiscono perciò a celle di memoria non più esistenti

Liste puntate

Una lista è una collezione di elementi omogenei

A differenza dell’array, la dimensione di una lista non è nota a priori e può variare nel tempo. Inoltre un elemento nella lista occupa una posizione qualsiasi, che tra l’altro può cambiare dinamicamente durante l’utilizzo della lista stessa.

Ogni elemento nella lista ha uno o più campi contenenti informazioni, e, necessariamente, deve contenere un puntatore per mezzo del quale è legato all’elemento successivo

Esempio (vedi figura)

Esempio

Esempio


Liste puntate

Una lista puntata (semplice) ha una gestione sequenziale, in cui è sempre possibile individuare la testa e la coda della lista.

Esempio (vedi figura)

Esempio

Esempio


Operazioni sulle liste

Le operazioni che agiscono su un a lista rappresentano gli operatori elementari che agiscono sulle variabili di tipo lista

Corrispondono a dei sottoprogrammi (funzioni)

Alcune operazioni modificano la lista

Operazioni tipiche:

  • Inizializzazione – modifica la lista
  • Inserimento in testa – modifica la lista
  • Inserimento in coda – modifica la lista
  • Inserimento all’interno – modifica la lista
  • Verifica lista vuota – non modifica la lista
  • Ricerca elemento – non modifica la lista
  • Stampa lista – non modifica la lista

Verifica Lista vuota

Data una lista L, per verificare se essa è vuota è sufficiente controllare se essa punta a NULL.

La seguente verifica se L è vuota


Inizializzazione

Consideriamo un semplice programma per l’inizializza-zione di una lista di interi.


Funzione crea_lista()

La funzione crea_lista() crea due puntatori ad elemento, uno di nome p (punta al primo elemento) e l’altro di nome punt (permette di scorrere la lista);

Funzione crea_lista()


Esempio di funzionamento di crea_lista

Assumiamo che si voglia creare una lista di 3 elementi (5,20,12); Alla prima iterazione abbiamo la seguente situazione:

Supponiamo adesso di aver inserito i primi due elementi e stiamo per inserire il terzo. La lista avrà la seguente forma:


Esempio di funzionamento di crea_lista

A questo punto inserendo il valore 12 per prima cosa viene creato un altro oggetto della lista, identificato con punt -> next,

poi “punt”, il puntatore ausiliario, viene fatto puntare, non più al secondo elemento, bensì al terzo, all’atto pratico “punt” diventa il puntatore dell’oggetto da lui puntato (cioè, punt = punt -> next;).

Quindi viene inserito il campo informazione dell’elemento tramite l’input da tastiera dell’utente; in questo caso viene inserito il valore 12;

Alla fine, punt punta al valore NULL che identifica la fine della lista.

Funzione visualizza_lista()

La seguente funzione iterativa permette di stampare tutti gli elementi interi presenti in una lista, nell’ordine in cui sono memorizzati


Ricorsione su liste

La ricorsione risulta particolarmente utile sulle liste collegate. Questo è dovuto al fatto che le liste si possono definire in modo ricorsivo:

Una lista è la lista vuota, oppure un elemento seguito da un’altra lista.

In altre parole, una variabile di tipo lista L può valere NULL (che rappresenta la lista vuota), oppure può essere un puntatore a una struttura che contiene un dato più un altro puntatore. Possiamo quindi dire che la struttura è composta da un elemento e da un puntatore, che rappresenta un’altra lista.

Ricorsione su liste

La lista si ottiene guardando la struttura puntata e poi seguendo i puntatori fino a NULL.

Sia L una lista definita da

struct lista {int val; struct lista *next;} L;

Una funzione ricorsiva su L avrà come argomento L, e al suo interno una chiamata ricorsiva a cui si passa L_next.

Queste funzioni normalmente operano su L_val (il primo elemento della lista), e poi agiscono sul resto della lista solo attraverso la chiamata ricorsiva.

Funzione visualizza_lista() ricorsiva

Se p rappresenta la lista vuota, non si stampa niente; si esce semplicemente dalla funzione senza fare nulla.

Al passo i-esimo, si stampa la testa della lista e si richiama la funzione visualizza_lista sulla lista meno la testa.


Esercizio

Sia L una lista definita da

struct lista {int val; struct lista *next;} L;

Scrivere in linguaggio C una funzione ricorsiva che preso in input L, raddoppi tutti gli elementi dispari della lista

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion