Corso di Algoritmi e Strutture Dati
APPUNTI SUL LINGUAGGIO C
Esercizi su Liste
Liste concatenate
Operazioni fondamentali:
Inserimento di un nuovo nodo
Cancellazione di un nodo esistente
Ricerca di un nodo esistente
Lista come parametro di una funzione
Un elemento x di una lista è un oggetto con almeno due
campi
info[x] campo chiave
next[x] puntatore al successore dell’oggetto nella lista
Una lista L è un oggetto con un campo:
head[L]
NIL
head[L] puntatore al primo elemento x della lista
Lista vuota: head[L] = NIL
Lista come parametro di una funzione
Passare una lista come parametro significa passare il
puntatore al primo nodo.
l
Nel caso di inserimento e cancellazione, vogliamo ottenere
un side effect sulla lista dopo la chiamata della funzione
Lista come parametro di una funzione
Ricordiamo che i parametri di una funzione in C vengono
catturati per valore
<tipo> funzione(plist l)
l
l’
La funzione ritorna un puntatore come risultato
plist funzione(plist l)
l
l’
// nel codice principale
…
l = funzione(l);
Passiamo per riferimento il puntatore
void funzione(plist* l)
l’
l
// nel codice principale
…
funzione(l);
Liste concatenate in C
// definizione della struttura nodo
typedef struct elem{
int info; // <tipo> <valore del nodo>;
struct elem* next;
} elist;
// definizione del puntatore ai nodi della
lista
typedef elist* plist;
Inserimento di un nuovo nodo: in Testa
void funzione(plist* l, elemento el)
l’
l
temp
el
INS-Testa(L,x)
next[x] <- head[L]
head[L] <- x
Inserimento di un nuovo nodo: in Testa
// funzione per inserire in testa ad una
lista un nuovo nodo
void inserisciInTesta(plist* l, int n){
plist temp = (plist)malloc(sizeof(elist));
temp->info = n;
temp->next = *l;
*l = temp;
}
Inserimento di un nuovo nodo: in Coda
void funzione(plist* l, elemento el)
l’
l
temp
el
Inserimento di un nuovo nodo: in Coda
NULL(L)
return (head[L] = NIL)
INS-Coda(L,x)
if NULL(L) then head(L) <- x
else
y <- head(L)
while next(y) ≠ NIL
do y <- next(y)
next(y) <- x
next(x) <- NIL
Inserimento di un nuovo nodo: in Coda
//funzione per inserire in coda ad una lista un nuovo
nodo
void inserisciInCoda(plist* l, int n){
plist temp = (plist)malloc(sizeof(elist));
temp->info = n;
temp->next = NULL;
if (*l == NULL) *l = temp;
else {
plist temp2 = *l;
while (temp2->next != NULL)
temp2 = temp2->next;
temp2->next=temp;
}
}
Inserimento di un nuovo nodo: in una posizione precisa
void funzione(plist* l, elemento el, int pos)
prev
l’
cur
l
temp
el
Inserimento di un nuovo nodo: in una posizione precisa
LUNG(L)
x <- head(L)
cont <- 0
while x ≠
NIL
do x = next(x)
cont <- cont + 1
return cont
Inserimento di un nuovo nodo: in una posizione precisa
// funzione per calcolare il numero di nodi di una
lista
int lungLista(plist l){
int cont = 0;
while (l != NULL) {
cont++;
l = l->next;
}
return cont;
}
Inserimento di un nuovo nodo: in una posizione precisa
INS-Pos(L,x,pos)
if LUNG(L) < pos then INS-Coda(L,x)
else
switch (pos) {
case 0: error “posizione non valida"
case 1: INS-Testa(L,x)
default:
prev <- head(L)
cur <- next(prev)
while pos > 2 do prev <- cur;
cur <- next(cur)
pos = pos - 1
next(prev) <- x
next(x) <- cur
Inserimento di un nuovo nodo: in una posizione precisa
// funzione per inserire in un data posizione della lista un
nuovo nodo
void inserisciInPos(plist *l, int n, int pos) {
plist prev,cur;
plist temp = (plist)malloc(sizeof(elist));
temp->info = n;
temp->next = NULL;
int ln = lungLista(*l);
if (ln<pos) inserisciInCoda(l,n);
else
Inserimento di un nuovo nodo: in una posizione precisa
switch (pos) {
case 0: printf("bisogna indicare una posizione
positiva maggiore di zero\n"); break;
case 1: inserisciInTesta(l,n); break;
default:
prev = *l; cur = prev->next;
while (pos>2) {
prev = cur;
cur = cur->next;
pos--;
}
prev->next = temp;
temp->next = cur;
}
}
Cancellazione di un nodo: in Testa
void funzione(plist* l)
l’
l
temp
CANC-Testa(L)
if not NULL(L) then head(L) <- next(head(L))
else error “la lista è vuota”
Cancellazione di un nodo: in Testa
// funzione per cancellare in una lista il
nodo in testa
void cancellaInTesta(plist* l){
if (*l != NULL) {
plist temp = *l;
*l = temp->next;
free(temp);
}
else printf("La lista e' vuota\n");
}
Cancellazione di un nodo: in Coda
void funzione(plist* l)
l’
l
Cancellazione di un nodo: in Coda
CANC-Coda(L)
switch LUNG(L)
case 0: error “la lista è vuota”
case 1: head(L) <- NIL
default:
prev <- head(L)
cur <- next(prev)
while next(cur) ≠ NIL
do prev <- cur
cur <- next(cur)
next(prev) <- NIL
Cancellazione di un nodo: in Coda
// funzione per cancellare in una lista il nodo in coda
void cancellaInCoda(plist* l){
plist prev,cur;
switch(lungLista(*l)) {
case 0: printf("La lista e' vuota\n"); break;
case 1: free(*l); break;
default:
prev = *l;
cur=prev->next;
while (cur->next != NULL){
prev = cur;
cur = cur->next;
}
free(cur);
prev->next=NULL;
}
}
Cancellazione di un nodo: in una posizione precisa
void funzione(plist* l, int pos)
prev
l’
l
cur
Cancellazione di un nodo: in una posizione precisa
CANC-Pos(L,pos)
ln = LUNG(L)
if ln < pos error “posizione non valida”
else switch pos
case 0: error “posizione non valida”
case 1: CANC-Testa(L)
default:
prev <- head(L)
cur <- next(prev)
while pos > 2 do prev <- cur
cur <- next(cur)
pos = pos - 1
next(prev) <- next(cur)
Cancellazione di un nodo: in una posizione precisa
// funzione per cancellare inun alista un nodo in una data posizione
void cancellaInPos(plist* l, int pos){
plist prev,cur;
int ln = lungLista(*l);
if (ln<pos) printf("La lunghezza della lista e' minore della posizione fornita\n");
else
switch(pos) {
case 0: printf("Hai fornito una posizione non valida\n"); break;
case 1: cancellaInTesta(l); break;
default:
prev = *l;
cur=prev->next;
while (pos>2){
prev = cur;
cur = cur->next;
pos--;
}
prev->next=cur->next;
free(cur);
}
}
Ricerca di un nodo in una lista
void funzione(plist l, valore x)
l
x
SEARCH(L,k)
if NULL(L) then return NIL
else x <- head(L)
while x ≠ NIL and info(x) ≠ k
do x <- NEXT(x)
return x
Ricerca di un nodo in una lista
// funzione per cercare in una lista un nodo
int cerca(plist l, int n){
int test = 0;
while ((l!=NULL)&&(!test))
if (l->info == n) test = 1;
else l = l->next;
return test;
}
Esercizio
Data una lista L i cui nodi contengono valori interi, scrivere le
seguenti procedure (pseudo-codice e implementazione in C):
– CANC-Val(L,x) che cancella nella lista L il nodo con valore x
– CONT-Val(L,x) che conta in L quanti nodi hanno valore x
– INS-Val(L,x,y) che inserisce in L un nodo con valore x dopo il
nodo esistente in L con valore y (se il nodo con valore y non
esiste allora sarà fatto un inserimento in coda)
Corso di Algoritmi e strutture Dati
APPUNTI SUL LINGUAGGIO C
Esercizi su Liste
FINE