Diapositiva 1

Esercizi su liste circolari
1.
2.
3.
4.
5.
Scrivere una funzione per cercare un numero x in una
lista circolare di interi. La funzione deve restituire
NULL se il numero non esiste.
Scrivere una funzione che cancella un nodo da una lista
circolare contenente un valore x dato.
Scrivere una funzione per concatenare due liste
circolari. La funzione dovrà restituire una puntatore
all’ultimo nodo della nuova lista circolare.
Scrivere una funzione per fondere in unica lista
circolare ordinata due liste circolari ordinate.
Scrivere una funzione per invertire una lista circolare
NOTA: scrivere sempre pre e post condizione di ogni
funzione
Definizione di lista
(elementi interi)
struct list
{
int el;
struct list *next;
};
Esercizio 1
Scrivere una funzione per cercare un numero x
in una lista circolare di interi. La funzione deve
restituire NULL se il numero non esiste.
Pre condizioni:
la funzione prende in ingresso un numero x intero e
una lista L circolare a valori interi
Post condizioni:
se x  L, la funzione restituisce l’elemento di L che
codifica x
altrimenti restituisce NULL
Svolgimento
struct list *cerca(struct list *l, int x)
{
struct list *l2 = l;
/* se la lista è vuota, restituisce NULL */
if (l == NULL) return NULL;
/* per ogni elemento della lista */
do
{
if (l2->el == x) return l2;
/* elemento successivo */
l2 = l2->next;
} while(l2 != l);
}
return NULL;
Esercizio 2
Scrivere una funzione che cancella un nodo da
una lista circolare contenente un valore x dato.
Pre condizioni:
la funzione prende in ingresso un numero x intero e
una lista L circolare a valori interi
Post condizioni:
se x  L, la funzione restituisce un puntatore valido
alla lista L che codifica x
altrimenti restituisce L
Svolgimento
struct list *cancella(struct list *l, int x)
{
struct list *l2 = l, *prev = l;
/* se la lista è vuota, restituisce NULL */
if (l == NULL) return NULL;
/* per ogni elemento della lista */
do
{
/* elemento successivo */
l2 = l2->next;
/* se trova l’elemento */
if (l2->el == x)
{
/* ed è l’unico elemento */
if (prev == l2) { free(l2); return NULL; }
/* altrimenti “salta” l’elemento da cancellare */
prev->next = l2->next;
free(l2);
return prev;
}
prev = l2;
} while(l2 != l);
}
return l;
Esercizio 3
Scrivere una funzione per concatenare due liste
circolari. La funzione dovrà restituire una
puntatore all’ultimo nodo della nuova lista
circolare.
Pre condizioni:
la funzione prende in ingresso due liste circolari L1 e
L2
Post condizioni:
La funzione restituisce il puntatore all’ultimo nodo di
L2
Svolgimento
struct list *concatena(struct list *l1, struct list *l2)
{
struct list *h1;
/* se una delle due liste è vuota, restituisce l’altra
lista circolare */
if (l1 == NULL) return return l2;
if (l2 == NULL) return return l1;
h1 = l1->next;
l1->next = l2->next;
l2->next = h1;
}
return l2;
Esercizio 5
Scrivere una funzione per invertire una
lista circolare
Pre condizioni:
la funzione prende in ingresso una lista
circolare L
Post condizioni:
La funzione restituisce il puntatore all’ultimo
nodo della lista L invertita
Svolgimento
• Due possibili implementazioni:
– iterativa
– ricorsiva
Soluzione ricorsiva
•
•
Casi base:
1. lista vuota (si restituisce immediatamente
NULL)
2. ultimo elemento da invertire
Caso ricorsivo sul generico elemento l:
–
–
–
Memorizzare il puntatore all’elemento
successivo (n = l->next)
Richiedere l’inversione della parte
rimanente della lista (puntata da l->next)
Invertire l’elemento n->next = l