Anno accademico 2010-2011 1 Le strutture e le unioni in C.
-
Upload
marcello-colli -
Category
Documents
-
view
215 -
download
3
Transcript of Anno accademico 2010-2011 1 Le strutture e le unioni in C.
Anno accademico 2010-2011Anno accademico 2010-2011
11
Le strutture e le unioni in CLe strutture e le unioni in C
Anno accademico 2010-2011Anno accademico 2010-2011
22
SommarioSommario
• Le strutture e le unioniLe strutture e le unioni• Le liste concatenateLe liste concatenate
Allocazione dinamicaAllocazione dinamica Creazione ed aggiunta di un nuovo elemento alla Creazione ed aggiunta di un nuovo elemento alla
listalista Inserimento e cancellazione di elementiInserimento e cancellazione di elementi La ricerca di un elementoLa ricerca di un elemento
Anno accademico 2010-2011Anno accademico 2010-2011
33
Le strutture e le unioniLe strutture e le unioni
Anno accademico 2010-2011Anno accademico 2010-2011
• Gli array sono uno strumento adeguato per il trattamento di insiemi di variabili di uno stesso tipo
• Quando i tipi di dati, che devono essere logicamente aggregati, sono disomogenei, è necessario usare il tipo strutturastruttura (o recordrecord)
• L’ulteriore tipo composto unioneunione consente di interpretare il contenuto delle stesse locazioni di memoria con modalità diverse (è la realizzazione del concetto di record a lunghezza variabilerecord a lunghezza variabile)
44
IntroduzioneIntroduzione
Anno accademico 2010-2011Anno accademico 2010-2011
• Esempio:Esempio: Supponiamo di voler memorizzare, relativamente a ciascun abitante di un dato comune, nome e cognome, data di nascita e codice fiscale:
Nome e cognome costituiscono un array di caratteri
La data è composta da tre numeri interi, che descrivono giorno, mese ed anno
Il codice fiscale è un array di 16 caratteri (15 per il codice ed uno per il carattere nullo di terminazione)
Le informazioni non possono essere collezionate Le informazioni non possono essere collezionate in un unico array di caratteri, perché sono in un unico array di caratteri, perché sono disomogeneedisomogenee
55
Le strutture Le strutture 1 1
Anno accademico 2010-2011Anno accademico 2010-2011
• Possibile soluzione:Possibile soluzione: memorizzare le informazioni in variabili distinte
• Un’organizzazione più naturale consiste nella definizione di una variabile che contenga tutti i dati relativi ad una persona: utilizzando un tipo strutturastruttura
• Una struttura è simile ad un array, ma è costituita da campicampi (piuttosto che da elementi) che sono identificati da nominomi (piuttosto che da indici) e possono contenere informazione di tipo diverso
Le informazioni relative ad una persona sono sparse per la memoria
char name[20], fiscode[16];char name[20], fiscode[16];
short day, month, year;short day, month, year;
66
Le strutture Le strutture 2 2
Anno accademico 2010-2011Anno accademico 2010-2011
• Vi sono due dichiarazioni: la prima contiene lo schemaschema della struttura vitalstatvitalstat, la seconda dichiara una variabile vsvs di tipo struct struct vitalstatvitalstat
• Nota:Nota: includere un prefisso nei nomi dei campi, per distinguerli da campi di strutture diverse
struct vitalstat
{
char vs_name[20],vs_fiscode[16];
short vs_day,vs_month,vs_year;
};
struct vitalstat vs;
• L’allocazione della struttura vsvs sulla macchina di riferimento presuppone che i campi siano memorizzati consecutivamente, nell’ordine in cui sono dichiarati, ma non necessariamente in maniera contigua
EsempioEsempio
vs_fiscode[]
vs_year[]
vs_name[]
vs_day[] vs_month[]
77
Le strutture Le strutture 3 3
Anno accademico 2010-2011Anno accademico 2010-2011
• Il nome vitalstatvitalstat è un’etichettaetichetta (o tagtag) e struct struct vitalstatvitalstat rappresenta un nuovo tipo di dati definito dall’utente, per il quale non viene riservata memoria
• L’etichetta può essere utilizzata ogni volta che è necessario creare ulteriori variabili che contengono gli stessi campi
• La sintassi della dichiarazione di una struttura può assumere diverse forme:
Dichiarazione dell’etichetta e uso dell’etichetta Dichiarazione dell’etichetta e uso dell’etichetta (insieme alla parola chiave structstruct) per definire le variabili per definire le variabili
Uso di Uso di typedeftypedef per definire un particolare tipo struttura per definire un particolare tipo struttura
struct vitalstat vsa[1000], *pvs;
pvs &vsa[10];
88
Le strutture Le strutture 4 4
Anno accademico 2010-2011Anno accademico 2010-2011
• Il nome di tipo è scritto maiuscolo, per distinguerlo dai nomi di etichette e variabili
• Un’etichetta o un typedeftypedef consentono di definire una sola volta lo schema di una struttura, per dichiarare variabili del tipo struttura quando necessario
• Le dichiarazioni di struttura sono normalmente raggruppate in file headerfile header, così da poter essere accedute da più file sorgente
• Il tipo VITALSTATVITALSTAT rappresenta l’intera struttura, compresa la parola chiave structstruct
typedef
struct
{
char vs_name[20],vs_fiscode[16];
short vs_day, vs_month, vs_year;
}
VITALSTAT;
99
Le strutture Le strutture 5 5
Anno accademico 2010-2011Anno accademico 2010-2011
• Una struttura può essere inizializzata facendo seguire al nome della variabile di tipo struttura il simbolo di uguale e la lista dei valori iniziali racchiusi tra parentesi graffe
• Ogni valore iniziale deve essere dello stesso tipo del corrispondente campo della struttura
VITALSTAT vs {“Marco Rossi”, “MRCRSS91C23D612K”, 23, 3, 1991};
1010
L’inizializzazione di strutture L’inizializzazione di strutture 1 1
Anno accademico 2010-2011Anno accademico 2010-2011
• Un valore iniziale non può essere incluso in una dichiarazione che contiene solo un’etichetta o un typedeftypedef, poiché tali dichiarazioni definiscono lo schema della struttura, ma non riservano memoria
typedef struct
{
int a;
float b;
} s {1, 1.0}; /* non ammesso */
1111
L’inizializzazione di strutture L’inizializzazione di strutture 2 2
Anno accademico 2010-2011Anno accademico 2010-2011
1212
L’accesso ai campi della L’accesso ai campi della strutturastruttura
• Esistono due modalità diverse di accesso ai campi di una struttura, dipendenti dalla modalità di accesso alla struttura, diretta o mediante puntatore Nel caso di accesso diretto alla struttura, si usano il nome
della struttura ed il nome del campo, separati dall’operatore punto “..”
Nel caso di accesso tramite puntatore alla struttura, si usa l’operatore freccia destra “>>”, formato dalla concatenazione del segno meno e del simbolo maggiore
• L’operatore >> è una forma abbreviata per accedere all’indirizzo contenuto nel puntatore e quindi applicare l’operatore punto
VITALSTAT *pvs;… … …pvs>vs_day 23; pvs>vs_month 3; pvs>vs_year 1991;
pvs>vs_day è equivalente a (*pvs).vs_day
vs.vs_day 23; vs.vs_month 3; vs.vs_year 1991;
Anno accademico 2010-2011Anno accademico 2010-2011
include “v_stat.h” /* file header che contiene la dichiarazione * typedef VITALSTAT */
int agecount(vsa,size,low_age,high_age,current_year)VITALSTAT vsa[];int size, low_age, high_age, current_year;{ int age, count0; VITALSTAT *pvsa, *p_last&vsa[size];
for (; p<p_last; p) { agecurrent_year p>vs_year; if ((age > low_age) && (age < high_age)) count; } return count;}
Esempio:Esempio: Funzione che calcola il numero di persone con età compresa in un intervallo specificato
Le variabili locali pp e p_lastp_last sono state introdot-te per mantenere invariato il valore del parametro formale vsavsa (che altrimenti potrebbe essere usato direttamente nel ciclo)
• Gli array di strutture vengono dichiarati facendo precedere al nome dell’array il nome typedeftypedef della struttura
1313
Gli array di struttureGli array di strutture
Anno accademico 2010-2011Anno accademico 2010-2011
• Una struttura innestatastruttura innestata è una struttura in cui almeno uno dei campi è, a sua volta, una struttura
• Le strutture innestate sono comuni in C perché consentono di creare gerarchie di dati
typedef struct
{
char day;
char month;
short year;
} DATE;
typedef struct
{
char vs_name[20], vs_fiscode[16];
DATE vs_birth_date;
} VITALSTAT;
typedef struct{ char vs_name[20], vs_fiscode[16]; struct vs_birth_date { short vs_day; short vs_month; short vs_year; };} VITALSTAT;
Per identificare l’anno di nascita in una struttura vsvs dichiarata VITALSTATVITALSTAT, si deve scrivere
vs.vs_birth_date.vs_year 1414
Le strutture innestate Le strutture innestate 1 1
Anno accademico 2010-2011Anno accademico 2010-2011
• Una struttura innestata viene inizializzata racchiudendo i valori iniziali fra parentesi graffe
• Non esistono limiti al numero di livelli di nestingnesting delle strutture, anche se i riferimenti agli elementi diventano sempre più difficili da leggere perché contengono i nomi di tutte le strutture intermedie
typedef struct
{
DATE d;
char event[20];
} CALENDAR;
CALENDAR holiday {{25, 12, 2010}, “Natale”};
1515
Le strutture innestate Le strutture innestate 2 2
Anno accademico 2010-2011Anno accademico 2010-2011
• Le strutture e le unioni non possono contenere istanze di sé stesse, ma possono contenere puntatori a sé stesse
• Il compilatore consente di dichiarare un puntatore ad una struttura prima che sia stata dichiarata la struttura
struct s {
int a, b;
float c;
struct s *pointer_to_s;
};
1616
Le strutture contenenti Le strutture contenenti puntatori a sé stesse puntatori a sé stesse 1 1
Anno accademico 2010-2011Anno accademico 2010-2011
1717
Le strutture contenenti Le strutture contenenti puntatori a sé stesse puntatori a sé stesse 2 2
• Il riferimento in avantiriferimento in avanti a strutture (e unioni) è uno dei pochi casi nel linguaggio C in cui un identificatore può essere utilizzato prima di essere dichiarato
• Il riferimento in avanti non è ammesso con la definizione di tipo (typedeftypedef)
typedef struct neg {
int a;
FOO *p; /* errato perché FOO non
* è ancora stato dichiarato
*/
} FOO;
Anno accademico 2010-2011Anno accademico 2010-2011
1818
L’allineamento dei campi L’allineamento dei campi delle strutture delle strutture 1 1
• Alcune architetture (come i processori Motorola) richiedono che ogni oggetto di dimensioni superiori ad un charchar venga memorizzato in locazioni di memoria con indirizzo pari
• I problemi di allineamento non sono normalmente visibili al programmatore, ma possono creare spazi spazi vuoti vuoti all’interno delle strutturestruct align_examp
{
char mem1;
short mem2;
char mem3;
} s1;
mem1
mem2
mem3
mem1
mem2
mem3
spazio spazio vuotovuoto
spazio spazio vuotovuoto
Allocazione con restrizioni di allineamento
Allocazione senza restrizioni di allineamento
1000 1001
1003
1002
1000 1001
1004 1005
Anno accademico 2010-2011Anno accademico 2010-2011
1919
L’allineamento dei campi L’allineamento dei campi delle strutture delle strutture 2 2
• Gli spazi vuoti vengono eliminati da una redistribuzione delle dichiarazioni degli elementi
• Poiché le strutture possono essere memorizzate in modi diversi sui diversi calcolatori, è necessario accedervi con modalità portabili
• L’allineamento naturale allineamento naturale (tutti gli oggetti di 2 byte iniziano da indirizzi pari, gli oggetti di 4 byte a indirizzi divisibili per quattro, etc.) è il requisito più stringente imposto dai calcolatori
Se la struttura è allineata in modo naturale è portabile
struct align_examp { char mem1, mem3; short mem2;} s1;
Anno accademico 2010-2011Anno accademico 2010-2011
2020
Il passaggio di strutture come Il passaggio di strutture come parametri di funzione parametri di funzione 1 1
• Esistono due modalità per passare strutture come argomenti di funzione: Passaggio della struttura vera e propria, per valoreper valore Passaggio di un puntatore alla struttura, per indirizzoper indirizzo
• Il passaggio per indirizzo è più efficiente perché solo il puntatore viene copiato nell’area di memoria degli argomenti, mentre il passaggio per valore richiede la copia dell’intera struttura
VITALSTAT vs; … … …func1(vs); /* Passaggio per valore */… … …func2(&vs); /* Passaggio per indirizzo */
Anno accademico 2010-2011Anno accademico 2010-2011
2121
Il passaggio di strutture come Il passaggio di strutture come parametri di funzione parametri di funzione 2 2
• Le strutture dovrebbero essere passate per valore solo se… …la struttura è molto piccola (di dimensione
paragonabile al puntatore) …è necessario garantire che la funzione chiamata non
ne alteri il contenuto originale
• In dipendenza della modalità di passaggio prescelta, occorre dichiarare il parametro all’interno della funzione come struttura o come puntatore a struttura
void func2(pvs)
VITALSTAT *pvs; /* l’argomento è un puntatore a struttura */
void func1(vs)VITALSTAT vs; /* l’argomento è una struttura */
Anno accademico 2010-2011Anno accademico 2010-2011
2222
Il passaggio di strutture come Il passaggio di strutture come parametri di funzione parametri di funzione 3 3
• La scelta della modalità di passaggio dei parametri struttura definisce gli operatori da impiegare all’interno della funzione chiamata: il punto se la struttura è passata per valore la freccia destra se è passata per indirizzo
Anno accademico 2010-2011Anno accademico 2010-2011
2323
Il passaggio di strutture ed array Il passaggio di strutture ed array come parametri di funzione come parametri di funzione 1 1
• Le modalità per il passaggio di strutture e di array come parametri di funzione non sono omogenee Per passare un array, si specifica il solo nome dell’array
senza indici: il compilatore interpreta il nome come un puntatore al primo elemento dell’array, che viene passato per indirizzo
Non è possibile passare un array per valore, se non includendolo in una struttura passata per valore
Per le strutture, il nome viene interpretato come l’intera struttura
Applicando la stessa sintassi si ottiene una semantica diversa
int ar[100];struct tag st;… … …funcv(ar); /* viene passato un puntatore al primo elemento di ar[] */… … …funcs(st); /* viene passata l’intera struttura */
Anno accademico 2010-2011Anno accademico 2010-2011
2424
Il passaggio di strutture ed array Il passaggio di strutture ed array come parametri di funzione come parametri di funzione 2 2
• La stessa inconsistenza si riproduce anche all’interno delle funzioni Le due versioni basate su array sono equivalenti:
Le due versioni basate su strutture non lo sono:
void funcs(st)struct tag st; /* st è una struttura completa */
void funcs1(st); struct tag *st; /* st è un puntatore a struttura */
void funcv(ar)int ar[]; /* ar viene convertito in puntatore ad intero */
void funcv(ar); int *ar; /* ar è un puntatore ad intero */
Anno accademico 2010-2011Anno accademico 2010-2011
2525
Strutture restituite da funzioni Strutture restituite da funzioni 11
• Le funzioni possono restituire strutture o puntatori a strutture
• La dichiarazione del tipo di dato restituito da una funzione deve essere concorde con il valore effettivamente restituito
• Generalmente, è preferibile restituire puntatori a strutture per motivi di efficienza
• Se si restituisce un puntatore a struttura, la struttura deve avere durata fissa, perché altrimenti non sarebbe più accessibile al termine della funzione
• La restituzione di strutture è particolarmente utile quando si voglia comunicare all’esterno più di un valore
Anno accademico 2010-2011Anno accademico 2010-2011
2626
Strutture restituite da funzioni Strutture restituite da funzioni 22
include <stdio.h>include <math.h>define TOO_LARGE 100 /* dipendente dalla macchina */define NULL (void *) 0typedef struct{ double sine, cosine, tangent;} TRIG;
TRIG *get_trigvals(radian_val)double radian_val;{ static TRIG result;/* se radian_val è troppo grande, i valori sin, cos, tan non sono significativi */ if (radian_val > TOO_LARGE) { printf(“Valore di ingresso troppo grande”); return NULL; } result.sine sin(radian_val); result.cosine cos(radian_val); result.tangent tan(radian_val); return (&result);}
Anno accademico 2010-2011Anno accademico 2010-2011
2727
L’assegnamento di struttureL’assegnamento di strutture
• Lo standard ANSI consente di assegnare una struttura ad una variabile struttura dello stesso tipo
struct { int a; float b; } s1, s2, sf(), *ps;… … …s1 s2;s2 sf();ps &s1;s2 *ps;… … …
Anno accademico 2010-2011Anno accademico 2010-2011
2828
Le unioni Le unioni 1 1• Le unioni consentono agli elementi di sovrapporsi l’uno
sull’altro per condividere la stessa area di memoria• Esempio:Esempio:
• Il compilatore riserva sempre una quantità di memoria sufficiente all’elemento più grande e tutti gli elementi iniziano allo stesso indirizzo
typedef uniontypedef union{{ structstruct {{ char c1, c2;char c1, c2; } s;} s; long j;long j; float x;float x;} U;} U;
x
j
c1 c2
1000 1001 10041002
Anno accademico 2010-2011Anno accademico 2010-2011
2929
Esempio sulle unioni Esempio sulle unioni 1 1
• I dati viaggiano sulla linea un byte alla volta; le unioni consentono di raggruppare i byte in modo tale che i dati possano essere ricostruiti nella loro forma originale
• Sia get_byte() get_byte() una funzione che restituisce un singolo byte prelevato da un dispositivo di comunicazione
• Un valore doubledouble a otto byte può essere estratto dal dispositivo mediante otto chiamate successive alla funzione get_byte()get_byte()
Anno accademico 2010-2011Anno accademico 2010-2011
3030
Esempio sulle unioni Esempio sulle unioni 2 2
union doub
{
char c[8];
double val;
};
double get_double()
{
extern char get_byte();
int j;
union doub d;
for (j0; j<8; j) d.c[j] get_byte(); return d.val;
}
• I caratteri ricevuti vengono memo-rizzati in elementi successivi di c[]c[]: il valore del numero doubledouble si ottiene accedendo al campo valval dell’unione
• L’accesso ai campi di un’unione non ha impatto alcuno sui bit contenuti in memoria (non si effettuano conversioni di tipo): il compilatore interpreta in modo diverso gli stessi bit
Anno accademico 2010-2011Anno accademico 2010-2011
3131
Le liste concatenateLe liste concatenate
Anno accademico 2010-2011Anno accademico 2010-2011
3232
Allocazione dinamica Allocazione dinamica 1 1
• Finora, per gestire insiemi di dati, sono stati utilizzati array (di strutture) Tale approccio è valido se si conosce a priori il
numero di elementi che si devono gestire Viceversa, l’utilizzo di array può essere
estremamente oneroso, perché rende necessaria l’allocazione di una quantità di memoria sufficiente a memorizzare il caso peggiore:
Parte della memoria può andare sprecata (perché inutilizzabile per scopi diversi)Non è possibile accedere ad una quantità di memoria maggiore di quella allocata inizialmente
Anno accademico 2010-2011Anno accademico 2010-2011
3333
Allocazione dinamica Allocazione dinamica 2 2
• La soluzione consiste nell’allocare memoria in modo dinamico, con malloc() malloc() o calloc() calloc() che, tuttavia, non garantiscono la contiguità fisica per elementi logicamente contigui e nell’utilizzare liste concatenate
• Il modo più comune per garantire la contiguità logica di strutture allocate dinamicamente è infatti l’uso delle liste liste semplicemente/doppiamentesemplicemente/doppiamente concatenate concatenate
Anno accademico 2010-2011Anno accademico 2010-2011
3434
Le liste concatenate Le liste concatenate 1 1
• In una lista concatenata, ogni struttura contiene un elemento aggiuntivo (un puntatore) che punta alla struttura successiva
• Esistono liste semplici liste semplici e liste doppiamente concatenateliste doppiamente concatenate, in cui ogni struttura possiede due puntatori, rispettivamente all’elemento precedente ed al successivo
typedef struct vitalstat
{
char vs_name[20], vs_fiscode[16];
unsigned int vs_day,
vs_month,
vs_year;
struct vitalstat *next;
} VITALSTAT;
Dati Dati
Dati Dati
Lista concatenata sempliceLista concatenata semplice
Anno accademico 2010-2011Anno accademico 2010-2011
3535
Le liste concatenate Le liste concatenate 2 2• Le operazioni che si effettuano sulle liste sono:
Creazione di un elementoCreazione di un elemento
Aggiunta di un elemento alla fine della listaAggiunta di un elemento alla fine della lista
Inserimento di un elemento in una listaInserimento di un elemento in una lista
Cancellazione di un elemento da una listaCancellazione di un elemento da una lista
Ricerca di un elemento in una listaRicerca di un elemento in una lista
• Tutte le operazioni, tranne la ricerca, sono indipen-denti dal contenuto informativo delle strutture (dai campi dati) e possono essere formulate in modo generale
Anno accademico 2010-2011Anno accademico 2010-2011
3636
La creazione di un elemento La creazione di un elemento 1 1
• Per creare un elemento di una lista, è sufficiente riservare memoria per la struttura e restituire un puntatore all’area allocata
include “v_stat.h”include <stdlib.h>
ELEMENT *create_list_element(){ ELEMENT *p;
p (ELEMENT *)malloc(sizeof(ELEMENT)); if (p NULL) { printf(“create_list_element: malloc non riuscita.\n”); exit(1); } p > next NULL; return p;}
Alloca la memoria ad un elemento della lista, ma non lo collega alla lista stessa
Anno accademico 2010-2011Anno accademico 2010-2011
3737
La creazione di un elemento La creazione di un elemento 2 2
• Note:Note: Il nome ELEMENTELEMENT rende la funzione indipendente dal
tipo di dati effettivamente gestiti Per utilizzare la funzione create_list_element()create_list_element() in
relazione alla struttura vitalstatvitalstat, è necessario includere nel file v_stat.hv_stat.h (che contiene la definizione del tipo struttura) le ulteriori dichiarazioni:
ELEMENTELEMENT diviene un sinonimo di struct vitalstatstruct vitalstat Per dichiarare il puntatore occorre usare un’etichetta
invece di un typedeftypedef: è la sola modalità con cui una struttura può fare riferimento a sé stessa, dato che il nome di typedeftypedef non è definito fino al termine della dichiarazione
define NULL (void *) 0typedef struct vitalstat ELEMENT;
Anno accademico 2010-2011Anno accademico 2010-2011
3838
L’aggiunta di un nuovo elemento L’aggiunta di un nuovo elemento 1 1
include “v_stat.h”static ELEMENT *head;
void add_element(e)
ELEMENT *e;
{
ELEMENT *p;
/* se il primo elemento non esiste,
* viene creato */
if (head NULL) {
head e; return;
}
/* altrimenti, trova l’ultimo elemento */
for (phead; p>next ! NULL; pp>next) ; /* istruzione vuota */
p > next e;}
• La variabile headhead è un puntatore all’inizio della lista ed è dichiarata con ambito di visibilità a li-vello di file, per renderla disponibile a più funzioni
• Nel ciclo forfor, la scan-sione della lista è basata sul controllo del valore di p-p->next>next: se è diver-so da NULLNULL, esiste un elemento successivo, al-trimenti è stata rag-giunta la fine della lista
Anno accademico 2010-2011Anno accademico 2010-2011
3939
L’aggiunta di un nuovo elemento L’aggiunta di un nuovo elemento 2 2
• L’assegnamento pp>next >next e; e;
aggiunge una nuova struttura alla fine della lista• L’argomento ee della funzione è un puntatore alla
struttura che è stata allocata dalla funzione chiamante
• Esempio:Esempio: Creare una lista concatenata di dieci strutture vitalstatvitalstatinclude “v_stat.h”
static ELEMENT *head;
main() { for (j0; j<10; j) add_element(create_list_element());}
Anno accademico 2010-2011Anno accademico 2010-2011
4040
L’inserimento di un elementoL’inserimento di un elemento
• Per inserire un elemento in una lista concatenata, deve essere specificata la posizione in cui deve avvenire l’inserimento
q>next>nextdopodopoq
p
primaprimaq q>next
include “v_stat.h”
void insert_after(p,q) /* inserimento di p dopo q */ELEMENT *p, *q; {/* controllo di validità degli argomenti */ if((pNULL)) || (q NULL) || (p q)|| (q>next p)) { printf(“insert_after: argomenti errati.\n”); return; } p > next q > next; q > next p;}
Anno accademico 2010-2011Anno accademico 2010-2011
4141
La cancellazione di un elemento La cancellazione di un elemento 1 1
• Per la cancellazione di un elemento da una lista concatenata, occorre individuare l’elemento che precede quello da eliminare per riallacciare i puntatori della lista dopo l’eliminazione
• Inoltre, è necessario utilizzare la funzione free()free() per rilasciare la memoria dell’elemento eliminato
dopodopo
p p>next
primaprima
p p>next>nextgoner
Anno accademico 2010-2011Anno accademico 2010-2011
4242
La cancellazione di un elemento La cancellazione di un elemento 2 2
include “v_stat.h”static ELEMENT *head;
void delete_element(goner)
ELEMENT *goner;
{
ELEMENT *p;
if (goner head) head goner>next; else
{
for (phead;(p!NULL) && (p>next!goner);pp>next) ; /* istruzione vuota */
if (p NULL) {
printf(“delete_element: elemento non contenuto nella lista.\n”);
return;
}
p>next p>next>next ; }
free(goner);
}
L’operatore freccia destra ha associatività sinistra e pertanto l’espressione
p>next>next
viene valutata come
(p>next)>next
Anno accademico 2010-2011Anno accademico 2010-2011
4343
La ricerca di un elemento La ricerca di un elemento 1 1
• La funzione di ricerca di un elemento della lista viene fatta in base al contenuto di uno o più campi della struttura
• Esempio: Esempio: Funzione che ricerca, fra strutture di tipo vitalstatvitalstat, un elemento per cui il valore del campo namename coincida con l’argomento della funzione
Anno accademico 2010-2011Anno accademico 2010-2011
4444
La ricerca di un elemento La ricerca di un elemento 2 2
include “v_stat.h”include <string.h>static ELEMENT *head;
ELEMENT *find(aname)
char *aname;
{
ELEMENT *p;
for (p head; p ! NULL; p p>next) if (strcmp(p>vs_name, aname)0) return p;
return NULL;
}
Anno accademico 2010-2011Anno accademico 2010-2011
4545
Costruzione di una lista ordinata Costruzione di una lista ordinata 1 1
/* ** Letta in input una sequenza di numeri interi la** memorizza in una lista in ordine crescente. ** */
#include <stdlib.h>#include <stdio.h>
/* ** struttura per la rappresentazione dei nodi della ** lista */ struct nodo { int info; struct nodo *next; };
/* * Funzione principale. */ main(void) { struct nodo *primo;
primoleggi_lista_ordinata(); stampa_lista(primo); exit(0); }
Anno accademico 2010-2011Anno accademico 2010-2011
4646
Costruzione di una lista ordinata Costruzione di una lista ordinata 2 2
/*
* Legge una sequenza di numeri interi e li memorizza in
* una lista ordinata (in ordine crescente).
* Restituisce il puntatore al primo elemento della lista.
*/
struct nodo *leggi_lista_ordinata(void)
{
struct nodo *p, *p1, *primo, *prec;
int i, n, num;
primo = NULL;
printf(“Inserire numero di elementi: ”);
scanf(“%d”, &n);
for (i0; i<n; i) {
scanf(“%d”, &num);
p malloc(sizeof(struct nodo)); p->info num; p1 primo; prec NULL;
while((p1!NULL)&&(p1->info<p->info)) {
prec p1; p1 p1->next; }
if (prec ! NULL) prec->next p; else
primo p; p->next p1; }
return(primo);
}
Anno accademico 2010-2011Anno accademico 2010-2011
4747
Costruzione di una lista ordinata Costruzione di una lista ordinata 3 3
/*
* Stampa la lista, a partire dall’elemento puntato dal
* puntatore p, ricevuto come parametro.
*/
void stampa_lista(p)
struct nodo *p;
{
while (p ! NULL) {
printf(“%d ---> ”, p->info);
p p->next; }
printf(“NULL\n”);
return;
}