G. Amodeo,
C. Gaibisso
Programmazione di Calcolatori
Lezione XXI
Le liste di variabili strutturate
Programmazione di Calcolatori: le liste di variabili strutturate
1
G. Amodeo,
C. Gaibisso
Liste di record
• Definizione:
- insieme omogeneo di record
collegati tra loro tramite
puntatori in modo tale che, dato
un record, è sempre possibile
accedere al suo successore nella
lista stessa
- un puntatore permette l’accesso
al primo elemento della lista
Programmazione di Calcolatori: le liste di variabili strutturate
2
G. Amodeo,
C. Gaibisso
Liste di record
• Graficamente:
struct item {
…….
struct item *next;
};
struct item *lista
…
…
…
…
…
NULL
Programmazione di Calcolatori: le liste di variabili strutturate
3
G. Amodeo,
C. Gaibisso
Lista di interi: definizione dei tipi
// definizione del tipo strutturato di un elemento
// della lista di interi
struct ldi_item {
// valore dell'elemento
int valore;
// riferimento al prossimo elemento
struct ldi_item *successivo;
};
// definizione del tipo di una lista di interi
typedef struct ldi_item * ldi;
Programmazione di Calcolatori: le liste di variabili strutturate
4
G. Amodeo,
C. Gaibisso
Generazione di un nuovo elemento
struct ldi_item *new_item
• La logica:
VALORE
• La funzione:
NULL
// Alloca memoria e inizializza un nuovo elemento della lista
struct ldi_item *itemIni(int valore)
{
// definisce un puntatore per il nuovo elemento della lista
struct ldi_item *new_item;
// alloca memoria per il nuovo elemento
new_item = (struct ldi_item *) malloc(sizeof(struct ldi_item));
if (new_item != NULL)
// se l’operazione ha esito positivo
{
// inizializza opportunamente i campi valore e successivo
new_item -> valore = valore;
new_item -> successivo= NULL;
};
// restituisce il riferimento al nuovo elemento, se allocato con successo,
// NULL altrimenti
return(new_item);
};
Programmazione di Calcolatori: le liste di variabili strutturate
5
G. Amodeo,
C. Gaibisso
Inizializzazione di una lista
• La logica:
ldi lista
NULL
• La funzione:
// Inizializza una lista di interi a lista vuota
void ldiIni (ldi *lista)
{
// inizializza la lista a lista vuota
*lista = NULL;
};
Programmazione di Calcolatori: le liste di variabili strutturate
6
G. Amodeo,
C. Gaibisso
Scansione di una lista
• La logica:
struct ldi_item *ptr
…
…
…
ldi lista
• Il codice:
…
NULL
// tipo delle variabili coinvolte
ldi lista;
struct ldi_item *ptr;
…
ptr = lista;
// scansione
while (ptr != NULL)
{
…
ptr = ptr -> successivo;
};
Programmazione di Calcolatori: le liste di variabili strutturate
7
G. Amodeo,
C. Gaibisso
Inserimento di un nuovo elemento
• La logica:
ldi lista
X
…
…
…
NULL
(1)
(2)
…
NULL
struct ldi_item *new_item
Programmazione di Calcolatori: le liste di variabili strutturate
8
G. Amodeo,
C. Gaibisso
Inserimento di un elemento
• La funzione:
// Costanti simboliche per gli esiti di una operazione
#define NEG_RESULT
0
#define POS_RESULT
1
…
// Aggiunge un nuovo elemento in testa alla lista
int ldiIns(ldi *lista, int valore)
{
// definisce un puntatore al nuovo elemento
struct ldi_item *item;
// inizializza il nuovo elemento
item = itemIni(valore);
// se la generazione del nuovo elemento fallisce termina con esito
// negativo
if (item == NULL)
return(NEG_RESULT);
// altrimenti inserisce il nuovo elemento in testa alla lista
item -> successivo = *lista;
*lista = item;
// termina con esito positivo
return(POS_RESULT);
};
Programmazione di Calcolatori: le liste di variabili strutturate
9
G. Amodeo,
C. Gaibisso
Cancellazione di un elemento
• La logica:
 primo della lista:
(2)
ldi lista
X
(1)
X
…
(3)
…
…
NULL
struct ldi_item *temp
Programmazione di Calcolatori: le liste di variabili strutturate
10
G. Amodeo,
C. Gaibisso
Cancellazione di un elemento
 altrimenti:
struct ldi_item *del
elemento interessato
dalla cancellazione
(2)
lista
…
(1)
X
X
…
(3)
…
…
NULL
struct ldi_item *item
riferimento all’elemento precedente a
quello oggetto della cancellazione
Programmazione di Calcolatori: le liste di variabili strutturate
11
G. Amodeo,
C. Gaibisso
Cancellazione di un elemento
• Le funzioni:
Continua …
// Individua, se esiste, l'elemento che memorizza il valore, se e' il primo
// della lista; l'elemento a questo precedente, altrimenti.
struct ldi_item *ldiCercaCanc (ldi lista, int valore)
{
// se la lista e' vuota restituisce NULL
if (ldiEmpty(lista))
return(NULL);
// se l'elemento cercato è il primo della lista ne restituisce il riferimento
if (lista -> valore == valore)
return(lista);
// altrimenti scandisce la lista alla ricerca dell’elemento precedente
// a quello che memorizza il valore cercato
while (lista -> successivo != NULL)
// restituisce il riferimento all'elemento corrente, se l'elemento
// a questo successivo memorizza il valore cercato
if (lista -> successivo -> valore == valore)
return(lista);
else
// altrimenti considera l'elemento successivo a quello corrente
lista = lista -> successivo;
// restituisce NULL se la lista non memorizza il valore
return(NULL);
};
Programmazione di Calcolatori: le liste di variabili strutturate
12
G. Amodeo,
C. Gaibisso
Cancellazione di un elemento
• Le funzioni:
// cancella dalla lista il primo elemento che memorizza il valore
int ldiCancItem(ldi *lista, int valore)
{
// definisce una variabile per il riferimento all'elemento da cancellare,
// se e' il primo della lista; al suo predecessore altrimenti
struct ldi_item *item;
// definisce una variabile di appoggio per il riferimento all'elemento
// da cancellare
struct ldi_item *del;
// individua tale riferimento
item = ldiCercaCanc (*lista, valore);
// se il valore in input non compare nella lista termina con esito
// negativo
if (item == NULL)
return(NEG_RESULT);
Continua …
Programmazione di Calcolatori: le liste di variabili strutturate
13
G. Amodeo,
C. Gaibisso
Cancellazione di un elemento
• Le funzioni:
// gestisce il caso in cui l'elemento da cancellare è il primo della lista
if (item -> valore == valore)
{
// salva il riferimento all'elemento da cancellare
del = item;
// elimina l'elemento dalla lista
*lista = (*lista) -> successivo;
}
else
{
// altrimenti salva il riferimento all'elemento da cancellare
del = item -> successivo;
// elimina l'elemento dalla lista
item -> successivo = item -> successivo -> successivo;
};
// recupera la memoria allocata per l'elemento eliminato dalla lista
free(del);
// termina con esito positivo
return(POS_RESULT);
};
Programmazione di Calcolatori: le liste di variabili strutturate
14
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi
• Specifiche:
implementare una soluzione per la gestione di
una lista di interi che preveda le seguenti
funzionalità:
1. inserimento nella lista di un valore intero
2. cancellazione dalla lista della prima
occorrenza di un valore intero
3. verifica della presenza di un valore intero
all’interno della lista
4. calcolo della lunghezza della lista
5. test di lista vuota
Programmazione di Calcolatori: le liste di variabili strutturate
15
G. Amodeo,
C. Gaibisso
Organizzazione del codice: file e contenuto
• Definizione dei tipi:
– ldi_tipi.h:
definizioni dei tipi, strutturati e non, per la
gestione della lista di interi
• Codice sorgente:
– ldi_main.c: codice per l’attivazione delle funzionalità di
gestione della lista di interi
– ldi_ges.c: definizione delle funzioni fondamentali per
la gestione della lista di interi
– ldi_uti.c:
definizione delle utilities di supporto alle
funzioni per la gestione della lista di interi
• Dichiarazioni extern
– ldi_ges.h:
– ldi_uti.h:
dichiarazioni extern delle funzioni
fondamentali per la gestione della lista di
interi
dichiarazioni extern delle utilities di supporto
alle funzioni per la gestione della lista di interi
Programmazione di Calcolatori: le liste di variabili strutturate
16
G. Amodeo,
C. Gaibisso
Organizzazione del codice: file e contenuto
• Pseudodichiarazioni:
– ldi_const.h: pseudodichiarazioni per le costanti
simboliche utilizzate nella gestione della
lista di interi
– ldi_msg.h: pseudodichiarazioni per i messaggi
restituiti nella gestione della lista di interi
Programmazione di Calcolatori: le liste di variabili strutturate
17
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_tipi.h
// Nome e posizione del file:
//
Lezione_XXI/ldi_tipi.h
// Descrizione del contenuto del file:
//
contiene le definizioni dei tipi, strutturati e non,
//
per la gestione di una lista di interi
// definizione del tipo strutturato elemento di una lista di interi
struct ldi_item {
// valore dell'elemento
int valore;
// riferimento al prossimo elemento
struct ldi_item *successivo;
};
// definizione del tipo lista di interi
typedef struct ldi_item * ldi;
Programmazione di Calcolatori: le liste di variabili strutturate
18
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_ges.c
Continua …
// Nome e posizione del file:
//
Lezione_XXI/ldi_ges.c
// Descrizione del contenuto del file:
//
definizione delle funzioni per la gestione di una lista di interi
// PSEUDODICHIARAZIONI
// pseudodichiarazioni per i messaggi restituiti nella gestione di una
// lista di interi
#include "./ldi_msg.h"
// pseudodichiarazioni per le costanti simboliche
// utilizzate nella gestione di una lista di interi
#include "./ldi_const.h"
// DEFINIZIONI DI TIPO
// definizioni dei tipi, strutturati e non, per la gestione di una lista di interi
#include "./ldi_tipi.h"
// DICHIARAZIONI EXTERN
// inclusione del file di intestazione della libreria standard che contiene
// definizioni di macro, costanti e dichiarazioni di funzioni e tipi funzionali
// alle varie operazioni di I/O
#include <stdio.h>
// dichiarazioni extern delle utilities di supporto alle funzioni per la gestione di
// una lista di interi
#include "./ldi_uti.h"
Programmazione di Calcolatori: le liste di variabili strutturate
19
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_ges.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
// Nome della funzione:
//
ldiEmpty()
// Tipo, nome e significato dei parametri della funzione:
//
ldi lista: riferimento al primo elemento della lista di
//
interi
// Descrizione della funzionalita' implementata:
//
implementa il test di lista vuota
// Tipo e significato del valore restituito:
//
int:
TRUE se la lista è vuota;
//
FALSE altrimenti
int ldiEmpty(ldi lista)
{
// restituisce TRUE se la lista è vuota, FALSE altrimenti
if (lista == NULL)
return(TRUE);
else
return(FALSE);
};
20
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_ges.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
// Nome della funzione:
//
ldiIns()
// Tipo, nome e significato dei parametri della funzione:
//
ldi *lista: riferimento al puntatore di accesso alla lista di interi
//
int valore: valore da inserire
// Descrizione della funzionalita' implementata:
//
aggiunge un nuovo elemento in testa alla lista
// Tipo e significato del valore restituito:
//
int:
POS_RESULT se l'operazione ha avuto esito positivo;
//
NEG_RESULT altrimenti
int ldiIns(ldi *lista, int valore)
{
// definisce un puntatore al nuovo elemento
struct ldi_item *item;
// inizializza il nuovo elemento
item = itemIni(valore);
// se la generazione del nuovo elemento fallisce termina con esito
// negativo
if (item == NULL)
return(NEG_RESULT);
// altrimenti inserisce il nuovo elemento in testa alla lista
item -> successivo = *lista;
*lista = item;
// termina con esito positivo
return(POS_RESULT);
};
21
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_ges.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
// Nome della funzione:
//
ldiVis()
// Tipo, nome e significato dei parametri della funzione:
//
ldi lista:
riferimento al primo elemento della lista di interi
// Descrizione della funzionalita' implementata:
//
visualizza gli interi memorizzati dalla lista
// Tipo e significato del valore restituito:
//
alcuno
void ldiVis (ldi lista)
{
// se la lista è vuota memorizza un opportuno messaggio
if (ldiEmpty(lista))
printf(EMPTY_LOI);
// altrimenti
else
{
printf(LIST);
// scandisce la lista
while (lista != NULL)
{
// visualizza il contenuto dell'elemento corrente
printf("->%d", lista -> valore);
// considera l'elemento successivo a quello corrente
lista = lista -> successivo;
};
};
};
22
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_ges.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
// Nome della funzione:
//
ldiCancItem()
// Tipo, nome e significato dei parametri della funzione:
//
ldi *lista: riferimento al puntatore di accesso alla lista di interi
//
int valore: valore da eliminare
// Descrizione della funzionalita' implementata:
//
cancella dalla lista il primo elemento che memorizza il valore
// Tipo e significato del valore restituito:
//
int: l'esito dell'operazione: POS_RESULT se il valore e' presente
//
NEG_RESULT altrimenti
int ldiCancItem(ldi *lista, int valore)
{
// definisce una variabile per il riferimento all'elemento
// oggetto della cancellazione, se e' il primo della lista;
// al suo predecessore altrimenti
struct ldi_item *item;
// definisce una variabile per il riferimento all'elemento oggetto
// della cancellazione
struct ldi_item *del;
// individua tale riferimento e lo memorizza
item = ldiCercaCanc (*lista, valore);
// se il valore in input non compare nella lista termina con esito
// negativo
if (item == NULL)
return(NEG_RESULT);
23
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_ges.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
// gestisce il caso in cui l'elemento da cancellare è il primo della lista
if (item -> valore == valore)
{
// salva il riferimento all'elemento da cancellare
del = item;
// elimina l'elemento dalla lista
*lista = (*lista) -> successivo;
}
else
{
// altrimenti salva il riferimento all'elemento da cancellare
del = item -> successivo;
// elimina l'elemento dalla lista
item -> successivo = item -> successivo -> successivo;
};
// recupera la memoria allocata per l'elemento eliminato dalla lista
free(del);
// termina con esito positivo
return(POS_RESULT);
};
24
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_ges.c
Continua …
// Nome della funzione:
//
ldiCercaItem()
// Tipo, nome e significato dei parametri della funzione:
//
ldi lista:
riferimento al primo elemento della lista di interi
//
int valore: valore oggetto della ricerca
// Descrizione della funzionalita' implementata:
//
verifica la presenza del valore nella lista di interi
// Tipo e significato del valore restituito:
//
int: TRUE se esiste almeno un elemento che memorizza il valore;
//
FALSE altrimenti
int ldiCercaItem (ldi lista, int valore)
{
// se la lista e' vuota restituisce FALSE
if (ldiEmpty(lista))
return(FALSE);
// altrimenti scandisce la lista
while (lista != NULL)
// se l'elemento corrente memorizza il valore cercato, restituisce TRUE
if (lista -> valore == valore)
return(TRUE);
else
// altrimenti considera l'elemento successivo a quello corrente
lista = lista -> successivo;
// se non individua il valore oggetto della ricerca restituisce FALSE
return(FALSE);
};
Programmazione di Calcolatori: le liste di variabili strutturate
25
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_ges.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
// Nome della funzione:
//
ldiLung()
// Tipo, nome e significato dei parametri della funzione:
//
ldi lista:
riferimento al primo elemento della lista di interi
// Descrizione della funzionalita' implementata:
//
calcola la lunghezza della lista
// Tipo e significato del valore restituito:
//
int: la lunghezza della lista di interi
int ldiLung (ldi lista)
{
// definisce e inizializza la variabile per la lunghezza della lista
int lunghezza = 0;
// scandisce la lista aggiornando la lunghezza della lista
// ad ogni elemento incontrato
while (lista != NULL)
{
// aggiunge 1 alla lunghezza della lista
lunghezza ++;
// considera l'elemento successivo a quello corrente
lista = lista -> successivo;
};
// restituisce la lunghezza della lista
return(lunghezza);
};
26
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_ges.c
// Nome della funzione:
//
ldiReset()
// Tipo, nome e significato dei parametri della funzione:
//
ldi *lista: riferimento al puntatore di accesso alla lista di interi
// Descrizione della funzionalita' implementata:
//
azzera la lista recuperando tutta la memoria allocata per i
//
suoi elementi
// Tipo e significato del valore restituito:
//
alcuno
void ldiReset (ldi *lista)
{
// definisce un puntatore ad un elemento della lista
struct ldi_item *item = *lista;
// scandisce la lista
while (item != NULL)
{
// stacca l'elemento corrente dalla testa della lista
*lista = item -> successivo;
// libera la memoria allocata per tale elemento
free(item);
// considera l’elemento successivo a quello corrente
item = *lista;
};
};
Programmazione di Calcolatori: le liste di variabili strutturate
27
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_ges.h
// Nome e posizione del file:
//
Lezione_XXI/ldi_ges.h
// Descrizione del contenuto del file:
//
contiene le dichiarazioni extern delle funzioni fondamentali
//
per la gestione di una lista di interi
extern int ldiEmpty(ldi);
extern int ldiIns(ldi *, int);
extern void ldiVis(ldi);
extern int ldiCancItem(ldi *, int);
extern int ldiCercaItem (ldi, int);
extern int ldiLung (ldi);
extern void ldiReset (ldi *);
Programmazione di Calcolatori: le liste di variabili strutturate
28
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_uti.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
// Nome e posizione del file:
//
Lezione_XXI/ldi_uti.c
// Descrizione del contenuto del file:
//
definizione delle utilities di supporto alle funzioni
//
per la gestione di una lista di interi
// DEFINIZIONI DI TIPO
// definizioni dei tipi, strutturati e non, per la gestione di una
// lista di interi
#include "./ldi_tipi.h"
// DICHIARAZIONI EXTERN
// inclusione del file di intestazione della libreria
// standard che contiene definizioni di macro,
// costanti e dichiarazioni di funzioni e tipi funzionali
// alle varie operazioni di I/O
#include <stdio.h>
// inclusione del file di intestazione della libreria che contiene
// definizioni di macro, costanti e dichiarazioni di funzioni e tipi
// di interesse generale
#include <stdlib.h>
// dichiarazioni extern delle funzioni fondamentali
// per la gestione di una lista di interi
#include "ldi_ges.h"
29
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_uti.c
// Nome della funzione:
//
ldiIni()
// Tipo, nome e significato dei parametri della funzione:
//
ldi *lista: riferimento al puntatore di accesso alla lista di
//
interi
// Descrizione della funzionalita' implementata:
//
inizializza la lista di interi a lista vuota
// Tipo e significato del valore restituito:
//
alcuno
void ldiIni (ldi *lista)
{
// inizializza la lista a lista vuota
*lista = NULL;
};
Continua …
Programmazione di Calcolatori: le liste di variabili strutturate
30
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_uti.c
Continua …
// Nome della funzione:
//
itemIni()
// Tipo, nome e significato dei parametri della funzione:
//
int valore: intero memorizzato dal nuovo elemento
// Descrizione della funzionalita' implementata:
//
alloca memoria e inizializza un nuovo elemento della lista
// Tipo e significato del valore restituito:
//
struct ldi_item *: riferimento al nuovo elemento di una
//
lista di interi, se allocato con successo;
//
NULL altrimenti
struct ldi_item *itemIni(int valore)
{
// definisce un puntatore per il nuovo elemento della lista
struct ldi_item *item;
// alloca memoria per il nuovo elemento
item = (struct ldi_item *) malloc(sizeof(struct ldi_item));
if (item != NULL) // se l’operazione ha esito positivo
{
// inizializza opportunamente i campi valore e successivo
item -> valore = valore;
item -> successivo = NULL;
};
// restituisce il riferimento al nuovo elemento, se allocato con successo,
// NULL altrimenti
return(item);
};
Programmazione di Calcolatori: le liste di variabili strutturate
31
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_uti.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
// Nome della funzione:
//
ldiCercaCanc()
// Tipo, nome e significato dei parametri della funzione:
//
ldi lista:
riferimento al primo elemento di una lista di interi
//
int valore: intero oggetto della cancellazione
// Descrizione della funzionalita' implementata:
//
individua, se esiste, l'elemento che memorizza il valore specificato,
//
se e‘ il primo della lista;
//
l'elemento a questo precedente, altrimenti.
// Tipo e significato del valore restituito:
//
struct ldi_item *: il riferimento a tale elemento, se esiste;
//
NULL altrimenti
struct ldi_item *ldiCercaCanc (ldi lista, int valore)
{
// se la lista e' vuota restituisce NULL
if (ldiEmpty(lista))
return(NULL);
// se l'elemento da cancellare è il primo della lista restituisce il
// riferimento all'elemento stesso
if (lista -> valore == valore)
return(lista);
32
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_uti.c
// altrimenti scandisce la lista
while (lista -> successivo != NULL)
// restituisce il riferimento all'elemento corrente, se l'elemento
// a questo successivo memorizza il valore cercato
if (lista -> successivo -> valore == valore)
return(lista);
else
// altrimenti passa a considerare l'elemento successivo a quello
// corrente
lista = lista -> successivo;
// restituisce NULL se non esiste alcun elemento all'interno
// della lista che memorizza il valore cercato
return(NULL);
};
Programmazione di Calcolatori: le liste di variabili strutturate
33
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_uti.h
// Nome e posizione del file:
//
Lezione_XXI/ldi_uti.h
// Descrizione del contenuto del file:
//
contiene le dichiarazioni extern delle utilities di supporto
//
alle funzioni per la gestione di una lista di interi
extern void ldiIni(ldi *);
extern struct ldi_item *itemIni(int);
extern struct ldi_item *ldiCercaCanc (ldi, int);
Programmazione di Calcolatori: le liste di variabili strutturate
34
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_main.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
// Nome e posizione del file:
//
Lezione_XXI/ldi_main.c
// Descrizione del contenuto del file:
//
chiamante per la gestione di una lista di interi
// PSEUDODICHIARAZIONI
// pseudodichiarazioni per i messaggi restituiti nella gestione di una
// lista di interi
#include "./ldi_msg.h"
// pseudodichiarazioni per le costanti simboliche
// utilizzate nella gestione di una lista di interi
#include "./ldi_const.h"
// DEFINIZIONI DI TIPO
// definizioni dei tipi, strutturati e non, per la gestione di una lista di interi
#include "./ldi_tipi.h"
// DICHIARAZIONI EXTERN
// inclusione del file di intestazione della libreria
// standard che contiene definizioni di macro,
// costanti e dichiarazioni di funzioni e tipi funzionali
// alle varie operazioni di I/O
#include <stdio.h>
// dichiarazioni extern delle utilities di supporto
// alle funzioni per la gestione di una lista di interi
#include "./ldi_uti.h"
// dichiarazioni extern delle funzioni per la gestione di una lista di interi
#include "./ldi_ges.h"
35
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_main.c
Continua …
// Nome della funzione:
//
LdiMenu()
// Tipo, nome e significato dei parametri della funzione:
//
ldi *lista: riferimento al puntatore di accesso alla lista di interi
// Descrizione della funzionalita' implementata:
//
implementa il menu di scelta delle funzionalita' di gestione
//
di una lista di interi
// Tipo e significato del valore restituito:
//
alcuno
void ldiMenu(ldi *lista)
{
// definisce e inizializza la variabile
// che permette l'uscita dal programma
int quit = 0;
// definisce la variabile per il valore oggetto delle
// operazioni di inserimento, cancellazione e ricerca
int valore;
Programmazione di Calcolatori: le liste di variabili strutturate
36
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_main.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
// rimane nel ciclo finche' la variabile quit rimane uguale a 0
while(!quit)
{
// definisce la variabile che memorizza la selezione
int selezione;
// visualizza le possibili scelte
printf(SELECT_FUN_LOI);
printf(ADD_ITEM_LOI);
printf(DEL_ITEM_LOI);
printf(SEARCH_ITEM_LOI);
printf(LENGTH_OF_LOI);
printf(RESET_LOI);
printf(DISPLAY_LOI);
printf(EMPTY_LOI_TEST);
printf(LEAVE_MAN_LOI);
printf(SELECT_OP_LOI);
// acquisisce la scelta
scanf("%d", &selezione);
37
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_main.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
// discrimina tra le diverse scelte
switch (selezione)
{
case 1:
// inserimento di un nuovo elemento
// acquisisce il valore oggetto dell'inserimento
printf(ITEM_VALUE_REQ);
scanf("%d", &valore);
// chiama la funzione per l’inserimento di un nuovo
// elemento nella lista, testa l'esito dell'operazione e
// lo visualizza
if (ldiIns(lista, valore) == POS_RESULT)
printf(POS_RES_MSG);
else
{
printf(NEG_RES_MSG);
printf(ITEM_GEN_FAILED);
};
break;
38
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_main.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
case 2:
// cancellazione di un elemento
// acquisisce il valore oggetto della cancellazione
printf(ITEM_VALUE_REQ);
scanf("%d", &valore);
// chiama la funzione per la cancellazione del primo
// elemento della lista che memorizza il valore, testa
// l'esito dell'operazione e lo visualizza
if (ldiCancItem(lista, valore) == POS_RESULT)
printf(POS_RES_MSG);
else
{
printf(NEG_RES_MSG);
printf(ITEM_DEL_FAILED);
};
break;
39
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_main.c
Continua …
case 3:
// ricerca di un elemento
// acquisisce il valore oggetto della ricerca
printf(ITEM_VALUE_REQ);
scanf("%d", &valore);
// chiama la funzione per la ricerca del valore nella lista,
// testa l'esito dell'operazione e lo visualizza
if (ldiCercaItem(*lista, valore))
printf(ITEM_SEARCH_SUCC);
else
printf(ITEM_SEARCH_FAIL);
break;
case 4:
// lunghezza della lista
// chiama la funzione per il calcolo della lunghezza della
// lista e la visualizza
printf(LOI_LENGTH);
printf("%d", ldiLung(*lista));
break;
case 5:
// reset della lista
// chiama la funziona che azzera la lista
ldiReset(lista);
break;
Programmazione di Calcolatori: le liste di variabili strutturate
40
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_main.c
Programmazione di Calcolatori: le liste di variabili strutturate
Continua …
};
};
case 6:
// visualizzazione della lista
// chiama la funzione per la visualizzazione della lista
ldiVis(*lista);
break;
case 7:
// test di lista vuota
// chiama la funzione per il test di lista vuota e
// visualizza il risultato
if (ldiEmpty(*lista))
printf(EMPTY_LOI);
else
printf(NOT_EMPTY_LOI);
break;
case 8:
// uscita
// forza l’uscita dal sistema
quit = 1;
break;
default:
// selezione errata
// segnala un errore di selezione delle funzionalità
printf(WRONG_SELECTION);
};
41
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_main.c
// Nome della funzione:
//
main()
// Tipo, nome e significato dei parametri della funzione:
//
alcuno
// Descrizione della funzionalita' implementata:
//
chiamante
// Tipo e significato del valore restituito:
//
alcuno
int main()
{
// definisce il puntatore di accesso alla lista di interi;
ldi lista;
// inizializza la lista
ldiIni(&lista);
// chiama la funzione che implementa il menu di scelta
// delle funzionalita' di gestione della lista di interi
ldiMenu(&lista);
// recupera la memoria allocata per la lista
ldiReset(&lista);
return(0);
};
Programmazione di Calcolatori: le liste di variabili strutturate
42
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_const.h
// Nome e posizione del file:
//
Lezione_XXI/ldi_const.h
// Descrizione del contenuto del file:
//
contiene le pseudodichiarazioni per le costanti simboliche
//
utilizzate nella gestione di una lista di interi
// definizione delle costanti simboliche per gli esiti di una operazione
#define NEG_RESULT
0
#define POS_RESULT
1
// definizione delle costanti mnemoniche per gli esiti di un test
#define TRUE
1
#define FALSE
0
Programmazione di Calcolatori: le liste di variabili strutturate
43
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_msg.h
// Nome e posizione del file:
//
Lezione_XXI/ldi_msg.h
// Descrizione del contenuto del file:
//
contiene le pseudodichiarazioni per i messaggi
//
restituiti nella gestione di una lista di interi
// definizione delle costanti simboliche per i messaggi utilizzati per il menu
#define SELECT_FUN_LOI
"\nSelezionare Funzionalita'\n"
#define ADD_ITEM_LOI
"\n1: Aggiungi un intero"
#define DEL_ITEM_LOI
"\n2: Cancella un intero"
#define SEARCH_ITEM_LOI
"\n3: Ricerca un intero"
#define LENGTH_OF_LOI
"\n4: Lunghezza della lista"
#define RESET_LOI
"\n5: Azzera la lista"
#define DISPLAY_LOI
"\n6: Visualizza la lista"
#define EMPTY_LOI_TEST
"\n7: Test di lista vuota"
#define LEAVE_MAN_LOI
"\n8: Interrompi"
#define SELECT_OP_LOI
"\n\nSelezione: "
#define WRONG_SELECTION "\nSelezionare 1, 2, 3, 4, 5, 6, 7 o 8"
Continua …
Programmazione di Calcolatori: le liste di variabili strutturate
44
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi: file ldi_msg.h
// definizione delle costanti simboliche per i messaggi di descrizione per l'esito
// delle operazioni
#define ITEM_GEN_FAILED
"\nGenerazione del nuovo elemento fallita"
#define ITEM_DEL_FAILED
"\nCancellazione dell'elemento fallita:
elemento non presente"
#define ITEM_SEARCH_SUCC "\nEsito della ricerca positivo\n"
#define ITEM_SEARCH_FAIL
"\nEsito della ricerca negativo\n"
#define LOI_LENGTH
"\nLunghezza della lista: "
// definizione delle costanti simboliche per i messaggi descrittivi della lista
#define EMPTY_LOI
"\nLista vuota\n"
#define NOT_EMPTY_LOI
"\nLista non vuota\n"
#define LIST
"\nLista: "
// definizione delle costanti simboliche per messaggi per l'esito delle operazioni
#define NEG_RES_MSG
"\nOperazione fallita\n"
#define POS_RES_MSG
"\nOperazione terminata con successo\n“
// definizione delle costanti simboliche per i messaggi di acquisizione di dati
#define ITEM_VALUE_REQ
"\nValore elemento? "
Programmazione di Calcolatori: le liste di variabili strutturate
45
G. Amodeo,
C. Gaibisso
Grafo delle chiamate
• Obiettivo:
descrivere (graficamente) l’interazione
reciproca tra le funzioni
• Cos’è:
• un grafo nel quale ogni nodo identifica una
funzione e il file che la contiene
• esiste un arco orientato dal nodo per la
funzione f(.) a quello per la funzione g(.) se
e solo se f(.) chiama g(.)
Programmazione di Calcolatori: i tipi di dato astratto
46
G. Amodeo,
C. Gaibisso
Gestione di una lista di interi
• Grafo delle chiamate:
ldiIni()
./ldi_uti.c
ldiCancItem()
./ldi_ges.c
main()
./ldi_main.c
ldiReset()
./ldi_ges.c
ldiCercaCanc()
./ldi_uti.c
ldiMenu()
./ldi_main.c
ldiEmpty()
./ldi_ges.c
ldiLung()
./ldi_ges.c
ldiCercaItem()
./ldi_ges.c
ldiVis()
./ldi_ges.c
ldiIns()
./ldi_ges.c
itemIni()
./ldi_uti.c
Programmazione di Calcolatori: i tipi di dato astratto
47