Modello dati LISTA
LISTA: sequenza finita di 0 o più elementi
LISTA di tipo T: lista in cui tutti gli elementi sono dello
stesso tipo T.
es. lista di int, di real, di struct,…
Lista che contiene elementi a1,…,an  (a1,…,an)
Es. lista dei numeri primi <20 in ordine crescente
 (1,2,3,5,7,11,13,17)
Modello dati LISTA
LISTA: sequenza finita di 0 o più elementi
LISTA di tipo T: lista in cui tutti gli elementi sono dello
stesso tipo T.
es. lista di int, di real, di struct,…
Lista che contiene elementi a1,…,an  (a1,…,an)
Es. lista dei numeri primi <20 in ordine crescente
 (1,2,3,5,7,11,13,17)
Lunghezza di una lista = numero di elementi nella lista
Es. lunghezza di (1,2,3,5,7,11,13,17) è 8
Lista vuota = e = lista con zero elementi
Modello dati LISTA
Data la lista (a1,…,an)
Head= primo elemento della lista = a1
Tail= lista senza head = (a2,…,an)
Modello dati LISTA
Data la lista (a1,…,an)
Head= primo elemento della lista = a1
Tail= lista senza head = (a2,…,an)
Sottolista : ogni lista (ai,ai+1,…, aj)
1<i<j<n
Sottosequenza: elimina alcuni elementi dalla lista
lascandi gli altri in ordine
Es. Data (1,2,3)
sottoliste: e, (1), (2), (3), (1,2), (2,3), (1,2,3)
sottosequenze: tutte le sottoliste e (1,3).
Modello dati LISTA
Data la lista (a1,…,an)
Prefisso= sottolista che inizia con a1
Suffisso= sottolista che finisce con an
La lista vuota è prefisso e suffisso di ogni lista
Es. Data (1,2,3,4)
prefissi: e, (1), (1,2), (1,2,3), (1,2,3,4)
suffissi: e, (4), (3,4), (2,3,4), (1,2,3,4)
Modello dati LISTA
Data la lista (a1,…,an)
Elemento in posizione i= ai
Predecessore di ai = ai-1
Successore di ai= ai+1
Occorrenza di x = una posizione i tale che ai=x
Es. Data (a,b,c,b,b)
elemento in posizione 1 = a
elemento in posizione 4 = b
occorrenza di a = 1
occorrenze di b = 2,4,5
occorrenza di c = 3
Operazioni su liste
Sorting: data la lista (a1,…an) restituisce la lista ordinata
(b1,…,bn) contenente gli stessi elementi
Merging: date due liste ordinate restituisce una lista
ordinata contenente tutti gli elementi delle liste input
Dizionario: insieme di elementi su cui si vogliono fare le
operazioni di inserzione, ricerca e cancellazione
Operazioni su liste
Push: insert nuovo elemento come head della lista
es. L=(1,2,3,2), push(L,1)  L’=(1,1,2,3,2)
Pop: cancella head della lista
es. L=(1,2,3,2), pop(L)  L’=(2,3,2)
Concatenazione di 2 liste:
L=(a1,…,an), M=(b1,…bm)  (a1,…,an,b1,…bm)
Liste a puntatori (struttura dati)
typedef struct CELL *LIST
struct CELL{
int element; /*per semplicità assumiamo elementi interi*/
LIST next}
lista: (modello)
(sruttura)
L=(a1,…,an)
a1
a2
an /
Liste a puntatori (struttura dati)
Dizionario su lista a puntatori (insert, delete, lookup)
Nota: dizionario contiene ogni elemento al più una volta
ordine non ha importanza, (1,3,5) equiv. (3,1,5)
Lookup: è x in D?
Metodo: Scorre celle della lista L che rappresenta D
finchè trova x oppure L finisce
Boolean lookup(int x, LIST L)
{if (L==NULL) return false
else if(L->element==x) return true
else return lookup(x, list ->next)}
Liste a puntatori (struttura dati)
Boolean lookup(int x, LIST L)
{if (L==NULL) return false
else if(L->element==x) return true
else return lookup(x, list ->next)}
R.T. T(0)=c
T(n)=b+T(n-1)  T(n)=O(n)
Liste a puntatori (struttura dati)
Boolean lookup(int x, LIST L)
{if (L==NULL) return false
else if(L->element==x) return true
else return lookup(x, list ->next)}
Correttezza. Mostriamo per induzione
S(n): lookup(.) su una lista di n elementi restituisce
true se e solo se x in L
Liste a puntatori (struttura dati)
Boolean lookup(int x, LIST L)
{if (L==NULL) return false
else if(L->element==x) return true
else return lookup(list ->next)}
Correttezza. Mostriamo per induzione
S(n): lookup(.) su una lista di n elementi restituisce
true se e solo se x in L
Base: n=0. n=0  L=NULL; risultato false; ok.
Passo: Sia S(n-1) vera. Consideriamo lista di n elementi.
Lookup(L) restituisce vero se x è il primo elemento
di L, ok!,
altrimenti restituisce vero sse (per i.i.) x è in tail
di L; ok!.
Liste a puntatori (struttura dati)
Cancellazione di x da lista L:
Elimina la cella contenente x
Si usa il puntatore pL
(chiamata per referenza)
invece di L per poter
modificare L.
Void delete(int x, LIST *pL)
{if (*pL!=NULL)
if(*pL->element==x) *pL=*pL ->next
else delete(x, *pL->next)}
x

x
Liste a puntatori (struttura dati)
Cancellazione di x da lista L:
Elimina la cella contenente x
Si usa il puntatore pL
(chiamata per referenza)
invece di L per poter
modificare L.
Void delete(int x, LIST *pL)
{if (*pL!=NULL)
if(*pL->element==x) *pL=*pL ->next
else delete(x, *pL->next)}
x

x
R.T. T(n)=O(n)
Correttezza. Mostrare per induzione
S(n): delete(L) su una lista di n elementi restituisce
L se x non in L, elimina x da L altrimenti.
Liste a puntatori (struttura dati)
Inserzione di x nella lista L:
Inserisce, se x non in L, una cella contenente x
Void insert(int x, LIST *pL)
{if (*pL==NULL)
{/*inserisci x */
(*pl)=(LIST)malloc(sizeof(struct CELL));
(*pL)->element=x;
(*pl)->next=NULL;}
else if((*pL)->element!=x) insert(x,(*pL) ->next)}
Liste a puntatori (struttura dati)
Inserzione di x nella lista L:
Inserisce, se x non in L, una cella contenente x
Void insert(int x, LIST *pL)
{if (*pL==NULL)
{/*inserisci x */
(*pl)=(LIST)malloc(sizeof(struct CELL));
(*pL)->element=x;
(*pl)->next=NULL;}
else if((*pL)->element!=x) insert(x,(*pL) ->next)}
Se la lista è vuota crea cella contenente x
L
X
/
Liste a puntatori (struttura dati)
Inserzione di x nella lista L:
Inserisce, se x non in L, una cella contenente x
Void insert(int x, LIST *pL)
{if (*pL==NULL)
{/*inserisci x */
(*pl)=(LIST)malloc(sizeof(struct CELL));
(*pL)->element=x;
(*pl)->next=NULL;}
else if((*pL)->element!=x) insert(x,(*pL) ->next)}
Se la lista è vuota crea cella contenente x
Altrimenti arriva a fine lista:
L
NULL

X
/
X
/
Liste a doppi puntatori
L
/ a1
a2
an /
type def struct CELL *LIST
Struct CELL
{LIST previous;
int element;
LIST next}
Es. Cancella la cella puntata dal puntatore p:
delete(LIST p, LIST *pL)
Liste a doppi puntatori
Es. Cancella la cella puntata dal puntatore p
Void delete(LIST p, LIST *pL)
{if (p->next != NULL) p->next->previous=p->previous;
if (p->previous==NULL) (*pL)=p->next;
else p->previous->next=p->next;}
p
Sorting: MERGESORT
Vogliamo ordinare lista (a1,…,an).
1. Dividi lista in 2 sottoliste aventi (quasi) la stessa
dimensione: (a1,a3,a5,…) e (a2,a4,…), (SPLIT)
2. Ordina le due liste separatamente (MERGESORT)
3. Fondi le due liste ottenute (ordinate) in una
unica lista ordinata (MERGE)
MERGE (di due liste ordinate L1,L2  M)
Algoritmo dipende dalla rappresentazione delle liste
Usiamo LISTE A PUNTATORI:
ogni elemento della lista è una struttura
typedef struct CELL *LIST
struct CELL{
int element
/* elemento della lista*/
LIST next
/* puntatore alla successiva
struttura (elemento)*/
}
(a1,a2,…,an) 
a1
a2
…
an
MERGE (di due liste ordinate L1,L2  M)
-Trova il minimo tra il primo elemento di L1 e di L2,
rimuovilo dalla lista di appartenenza ed aggiungilo ad M.
- Ripeti
LIST merge (LIST list1, LIST list2)
{ if (list1==NULL) return list2
else if (list2==NULL) return list1
}
else
if (list1->element <= list2 -> element)
/* entrambe le liste non vuote ed il primo
elemento di list1 è minore del primo di list2*/
{ list1->next=merge(list1->next, list2);
return list1;
}
else /*entrambe le liste non vuote ed il primo
elemento di list2 è minore del primo di list1*/
{ list2->next=merge(list1, list2->next);
return list2;
}
MERGE (di due liste ordinate L1,L2  M)
LIST merge (LIST list1, LIST list2) {
if (list1==NULL) return list2
else if (list2==NULL) return list1
else if ( list1->element <= list2->element )
{/* entrambe le liste non vuote ed il primo elemento
di list1 è minore del primo di list2*/
list1->next=merge(list1->next, list2);
return list1;}
else
…}
list1
a1
a2
list2
b1
b2
list1
a1
merge
an
…
…
a2
b1
bn
…
…
an
bn
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
list1 merge(list1, list2)  merge (2-4-7, 3-5-6-9)
9 p
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a=merge(a, list2)  merge(4-7,3-5-6-9)
9 p
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a=merge(a, list2)  merge(4-7,3-5-6-9)
b=merge(a, b)
 merge(4-7, 5-6-9)
9 p
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a=merge(a, list2)  merge(4-7,3-5-6-9)
b=merge(a, b)
g=merge(g, b)
 merge(4-7, 5-6-9)

merge(7, 5-6-9)
9 p
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a=merge(a, list2)  merge(4-7,3-5-6-9)
b=merge(a, b)
 merge(4-7, 5-6-9)
g=merge(g, b)

merge(7, 5-6-9)
d=merge(g, d)

merge(7, 6-9)
9 p
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
merge(a, list2)  merge(4-7,3-5-6-9)
merge(a, b)
 merge(4-7, 5-6-9)
g= merge(g, b)

merge(7, 5-6-9)
d= merge(g, d)

merge(7, 6-9)
e= merge(g, e)

merge(7, 9)
9 p
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
9 p
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b)
 merge(4-7, 5-6-9)
g= merge(g, b)

merge(7, 5-6-9)
d= merge(g, d)

merge(7, 6-9)
e= merge(g, e)
t= merge(NULL, e)=e

merge(7, 9)

merge( , 9)
e
9
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
9 p
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b)
 merge(4-7, 5-6-9)
g= merge(g, b)

merge(7, 5-6-9)
d= merge(g, d)

merge(7, 6-9)
e= merge(g, e) =g

merge(7, 9)
g
7
t
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
9 p
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b)
g= merge(g, b)
d= merge(g, d)=d
 merge(4-7, 5-6-9)

merge(7, 5-6-9)

merge(7, 6-9)
d
6
e
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
9 p
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b)
g= merge(g, b) = b
 merge(4-7, 5-6-9)
 merge(7, 5-6-9)
b
5
d
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
9 p
Merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)  merge(4-7,3-5-6-9)
b= merge(a, b) = a

merge(4-7, 5-6-9)
a
4
g
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
9 p
list1=merge(list1, list2)  merge (2-4-7, 3-5-6-9)
a= merge(a, list2)=list2  merge(4-7,3-5-6-9) list2
3
b
MERGE (di due liste ordinate L1,L2  M)
list1
2
list2
3 b
a
4
5
g
7 t
d
6 e
list1=merge(list1, list2)  merge (2-4-7, 3-5-6-9) list1
9 p
2
a
SPLIT (di L in due liste ordinate L1,L2)
L=(a1,a2, a3, a4, …, an)  L1 =(a1, a3, …) , L2 =(a2, a4, …)
LIST Split (LIST list)
{
List pSecondcell;
if (list==NULL) return NULL
else if (list->next==NULL) return NULL
else
{/* list contiene almeno 2 elementi*/
pScondcell=list->next;
list->next = pSecondcell->next;
pSecondcell->next=split(pSecondcell->next);
return pSecondcell;
}
}
SPLIT (di L in due liste ordinate L1,L2)
LIST Split (LIST list)
{ List pSecondcell;
if (list==NULL) return NULL
else if (list->Next==NULL) return NULL
else {/* list contiene almeno 2 elementi*/
pScondcell=list->next;
list->next = pSecondcell->next;
pSecondcell->next=split(pSecondcell->next);
return pSecondcell;}}
list
a1
a2
a3
…
an
SPLIT (di L in due liste ordinate L1,L2)
LIST Split (LIST list)
{ List pSecondcell;
if (list==NULL) return NULL
else if (list->Next==NULL) return NULL
else {/* list contiene almeno 2 elementi*/
pScondcell=list->next;
list->next = pSecondcell->next;
pSecondcell->next=split(pSecondcell->next);
return pSecondcell;}}
list
pSecondcell
a1
a2
a3
…
an
SPLIT (di L in due liste ordinate L1,L2)
LIST Split (LIST list)
{ List pSecondcell;
if (list==NULL) return NULL
else if (list->Next==NULL) return NULL
else {/* list contiene almeno 2 elementi*/
pScondcell=list->next;
list->next = pSecondcell->next;
pSecondcell->next=split(pSecondcell->next);
return pSecondcell;}}
list
pSecondcell
a1
a2
a3
…
an
SPLIT (di L in due liste ordinate L1,L2)
LIST Split (LIST list)
{ List pSecondcell;
if (list==NULL) return NULL
else if (list->Next==NULL) return NULL
else {/* list contiene almeno 2 elementi*/
pScondcell=list->next;
list->next = pSecondcell->next;
pSecondcell->next=split(pSecondcell->next);
return pSecondcell;}}
list
a1
a2
a3
Split di
pSecondcell
…
an
MERGESORT
BASE: Se la lista contiene 0 o 1 elemento, stop
Ind.: Split di (a1,a2,…) in (a1,a3,…) e (a2,a4,…)
Mergesort delle due liste separatamente
Merge delle 2 liste ordinate
MERGESORT
BASE: Se la lista contiene 0 o 1 elemento, stop
Ind.: Split di (a1,a2,…) in (a1,a3,…) e (a2,a4,…)
Mergesort delle due liste separatamente
Merge delle 2 liste ordinate
LIST Mergesort (LIST list)
{
List SecondList;
if (list==NULL) return NULL
else if (list->next==NULL) return list
else
{/* list contiene almeno 2 elementi (da ordinare)*/
SecondList=split(list);
return merge(mergesort(list),mergesort(ScondList));
}
}
R.T. della funzione SPLIT
LIST Split (LIST list)
{ List pSecondcell;
if (list==NULL) return NULL
else if (list->Next==NULL) return NULL
else {/* list contiene almeno 2 elementi*/
pScondcell=list->next;
list->next = pSecondcell->next;
pSecondcell->next=split(pSecondcell->next);
return pSecondcell;}}
Sia n=|list|. Si ha la relazione di ricorrenza
T(0)=T(1)=O(1)
T(n)=c+T(n-2), per n>1
Quindi T(n)=O(n)
R.T. del MERGE
LIST merge (LIST list1, LIST list2)
{ if (list1==NULL) return list2
else if (list2==NULL) return list1
}
else
if (list1->element <= list2 -> element)
{ list1->next=merge(list1->next, list2);
return list1; }
else
{ list2->next=merge(list1, list2->next);
return list2;}
Siano n1=|list1|, n2=|list2|, n=n1+n2.
Si ha la relazione di ricorrenza
T(0)=T(1)=O(1) (almeno 1 lista vuota)
T(n)=c+T(n-1), per n>1
Quindi T(n)=O(n)
R.T. MERGESORT
LIST Mergesort (LIST list)
{List SecondList;
if (list==NULL) return NULL
else if (list->next==NULL) return list
else /* list contiene almeno 2 elementi (da ordinare)*/
{SecondList=split(list);
return merge(mergesort(list),mergesort(ScondList));}
}
Sia n=|list|. Si ha la relazione di ricorrenza
T(0)=T(1)=O(1) (list contiene 0 o 1 elemento)
T(n)=O(n) + O(n) +T(n/2) +T(n/2)
=O(n) + 2 T(n/2), per n>1
Quindi T(n)=O(n log n)
R.T. MERGESORT
T(0)=T(1)=O(1)
T(n)=c n + 2 T(n/2), per n>1
Si assuma per semplicità che n=2m (cioè m=log n)
R.T. MERGESORT
T(0)=T(1)=O(1)
T(n)=c n + 2 T(n/2), per n>1
Si assuma per semplicità che n=2m (cioè m=log n)
T(2m)=c 2m + 2 T(2m-1)
=c 2m + 2 (c 2m-1 + 2 T(2m-2))= c 2m + c 2m +4 T(2m-2)
= 2c 2m + 4 T(2m-2)
R.T. MERGESORT
T(0)=T(1)=O(1)
T(n)=c n + 2 T(n/2), per n>1
Si assuma per semplicità che n=2m (cioè m=log n)
T(2m)=c 2m +
=c 2m +
= 2c 2m
= 2c 2m
= 3c 2m
2 T(2m-1)
2 (c 2m-1 + 2 T(2m-2))= c 2m + c 2m +4 T(2m-2)
+ 4 T(2m-2)
+4 (c 2m-2 + 2 T(2m-3))=2c 2m + c 2m+8T(2m-3)
+ 8 T(2m-3)
R.T. MERGESORT
T(0)=T(1)=O(1)
T(n)=c n + 2 T(n/2), per n>1
Si assuma per semplicità che n=2m (cioè m=log n)
T(2m)=c 2m + 2 T(2m-1)
=c 2m + 2 (c 2m-1 + 2 T(2m-2))= c 2m + c 2m +4 T(2m-2)
= 2c 2m + 4 T(2m-2)
= 2c 2m +4 (c 2m-2 + 2 T(2m-3))=2c 2m + c 2m+8T(2m-3)
= 3c 2m + 8 T(2m-3)
……
= i c 2m + 2i T(2m-i)
R.T. MERGESORT
T(0)=T(1)=O(1)
T(n)=c n + 2 T(n/2), per n>1
Si assuma per semplicità che n=2m (cioè m=log n)
T(2m)=c 2m + 2 T(2m-1)
=c 2m + 2 (c 2m-1 + 2 T(2m-2))= c 2m + c 2m +4 T(2m-2)
= 2c 2m + 4 T(2m-2)
= 2c 2m +4 (c 2m-2 + 2 T(2m-3))=2c 2m + c 2m+8T(2m-3)
= 3c 2m + 8 T(2m-3)
……
= i c 2m + 2i T(2m-i)
Scegliendo i=m=log n si ha
T(n)= T(2m) = m c 2m + 2m T(20)= m c n + n a=
= c n log n + a n = O(n log n)
Correttezza MERGESORT
LIST Mergesort (LIST list)
{List SecondList;
if (list==NULL) return NULL
else if (list->next==NULL) return list
else /* list contiene almeno 2 elementi (da ordinare)*/
{SecondList=split(list);
return merge(mergesort(list),mergesort(ScondList));}
}
Assumiamo correttezza delle funz. split e merge (esercizio)
Per induzione completa su n=|list|.
Base. Se n=0 o n=1, restituisce lista inalterata, ok.
Correttezza MERGESORT
LIST Mergesort (LIST list)
{List SecondList;
if (list==NULL) return NULL
else if (list->next==NULL) return list
else /* list contiene almeno 2 elementi (da ordinare)*/
{SecondList=split(list);
return merge(mergesort(list),mergesort(ScondList));}
}
Assumiamo correttezza delle funz.split e merge (esercizio)
Per induzione completa su n=|list|.
Base. Se n=0 o n=1, restituisce lista inalterata, ok.
Passo (n>1). Assumiamo per i.i. mergesort(list),
mergesort(ScondList) restituiscono liste input ordinate.
Correttezza MERGESORT
LIST Mergesort (LIST list)
{List SecondList;
if (list==NULL) return NULL
else if (list->next==NULL) return list
else /* list contiene almeno 2 elementi (da ordinare)*/
{SecondList=split(list);
return merge(mergesort(list),mergesort(ScondList));}
}
Assumiamo correttezza delle funz.split e merge (esercizio)
Per induzione completa su n=|list|.
Base. Se n=0 o n=1, restituisce lista inalterata, ok.
Passo (n>1). Assumiamo per i.i. mergesort(list),
mergesort(ScondList) restituiscono liste input ordinate.
Quindi
Split divide n elementi lista input tra list e Secondlist;
mergesort(list),mergesort(ScondList) ordina le liste;
Merge fonde le liste restituendo in output una lista ordinata
contenete gli stessi n elementi della lista input.
Liste mediante array
Struttura dati: array per contenere elementi
variabile length per contare # elementi
Array A[0..MAX-1] (lista può contenere al più MAX el.)
Lista (a0,…,an-1) usa prime n locazioni di A, length=n
0
1
a0
…
n-1 an-1
…
MAX
Typedef struct LIST /*lista  struttura con
2 campi: array e length*/
{
int A[MAX];
int length;
}
Liste mediante array
0
1
a0
…
n-1 an-1
…
Typedef struct LIST /*lista  struttura con
2 campi: array e length*/
{
int A[MAX];
int length;
}
MAX
pL: puntatore a struct LIST L
pL->A[i] = elemento i-mo della lista
pL->length = lunghezza lista
Liste mediante array
pL: puntatore a struct LIST
pL->A[i]= elemento i-mo della lista
pL->length=lunghezza lista
LOOKUP
Ricerca lineare
Boolean lookup(int x, LIST *pL)
{int i
for (i=0, i<*pL->length,i++)
if (x==*pL->A[i]) return TRUE;
return FALSE;}
R.T O(n), n=lunghezza lista
Liste mediante array
Ricerca lineare con sentinella
Boolean lookup(int x, LIST *pL)
{int i;
pL->A[pl->length]=x; /*sentinella*/
i=0;
while (x!=pL->A[i]) i++;
return (i<pL->length);}
R.T O(n), n=lunghezza lista
Liste mediante array
Ricerca lineare con sentinella
Boolean lookup(int x, LIST *pL)
{int i;
*pL->A[*pL->length]=x; /*sentinella*/
i=0;
while (x!=*pL->A[i]) i++;
return (i<*pL->length);}
R.T O(n), n=lunghezza lista
NOTA:
numero di operazioni minore rispetto alla ricerca lineare.
Boolean lookup(int x, LIST *pL)
{int i
for (i=0, i<*pL->length,i++) if (x==*pL->A[i]) return TRUE;
return false;}
LOOKUP con RICERCA BINARIA su lista ORDINATA
Sia a0,a1,…,an-1 una lista ordinata (a0 < a1 < …< an-1)
rappresentata mediante un array A[0..n-1].
Cerchiamo x.
a0
Se x<A[mid] continua la
ricerca di x in A[0.. mid-1]
amid mid=[(n-1)/2]
Se x=A[mid], trovato x, STOP
an-1
Se x>A[mid] continua la ricerca
di x in A[mid+1.. n-1]
LOOKUP con RICERCA BINARIA su lista ORDINATA
alow
amid
ahigh
Boolean BinSesarch(int x, int A[],int low, int high)
{int mid;
if (low > high) return FALSE; /*low>high array vuoto*/
else {
mid=(low+high)/2;
if(x<A[mid]) return BinSearch(x,A,low,mid-1);
else if (x>A[mid]) return BinSearch(x,A,mid+1,high);
else return TRUE /*x=A[mid]*/
LOOKUP con RICERCA BINARIA su lista ORDINATA
alow
amid
ahigh
Boolean BinSesarch(int x, int A[],int low, int high)
{int mid;
if (low > high) return FALSE;
else {
mid=(low+high)/2;
if(x<A[mid]) return BinSearch(x,A,low,mid-1);
else if (x>A[mid]) return BinSearch(x,A,mid+1,high);
else return TRUE /*x=A[mid]*/
CORRETTEZZA: restituisce true sse x in A[low..high]
Per induzione completa su m=high-low+1 (ampiezza array)
Base. m=0 (high<low), array vuoto, restituisce False, ok
Passo. (esercizio)
LOOKUP con RICERCA BINARIA su lista ORDINATA
alow
amid
ahigh
Sia P(k)=max numero elementi su cui si può fare la
ricerca con k confronti (chiamate ricorsive)
P(1)=1
P(2)=3
(mid, P(1)=1 elementi minori di mid,
P(1)=1 elementi maggiori di mid)
LOOKUP con RICERCA BINARIA su lista ORDINATA
alow
amid
Sia P(k)=max numero elementi su cui si può fare la
ricerca con k confronti (chiamare ricorsive)
P(1)=1
P(2)=3
(mid, P(1)=1 elementi minori di mid,
P(1)=1 elementi maggiori di mid)
P(k)=2 P(k-1)+1 (mid, P(k-1)=1 elementi minori di mid,
P(k-1)=1 elementi maggiori di mid)
ahigh
LOOKUP con RICERCA BINARIA su lista ORDINATA
alow
amid
Sia P(k)=max numero elementi su cui si può fare la
ricerca con k confronti (chiamate ricorsive)
P(1)=1
P(2)=3
(mid, P(1)=1 elementi minori di mid,
P(1)=1 elementi maggiori di mid)
P(k)=2 P(k-1)+1 (mid, P(k-1)=1 elementi minori di mid,
P(k-1)=1 elementi maggiori di mid)
ahigh
P(k)=2 P(k-1)+1= 2( 2 P(k-2)+1)+1= 4 P(k-2)+2+1=
LOOKUP con RICERCA BINARIA su lista ORDINATA
alow
amid
Sia P(k)=max numero elementi su cui si può fare la
ricerca con k confronti (chiamate ricorsive)
P(1)=1
P(2)=3
(mid, P(1)=1 elementi minori di mid,
P(1)=1 elementi maggiori di mid)
P(k)=2 P(k-1)+1 (mid, P(k-1)=1 elementi minori di mid,
P(k-1)=1 elementi maggiori di mid)
ahigh
P(k)=2 P(k-1)+1= 2( 2 P(k-2)+1)+1= 4 P(k-2)+2+1=
…
= 2i P(k-i) +2i-1+… + 2 + 1
LOOKUP con RICERCA BINARIA su lista ORDINATA
alow
amid
Sia P(k)=max numero elementi su cui si può fare la
ricerca con k confronti (chiamate ricorsive)
P(1)=1
P(2)=3
(mid, P(1)=1 elementi minori di mid,
P(1)=1 elementi maggiori di mid)
P(k)=2 P(k-1)+1 (mid, P(k-1)=1 elementi minori di mid,
P(k-1)=1 elementi maggiori di mid)
ahigh
P(k)=2 P(k-1)+1= 2( 2 P(k-2)+1)+1= 4 P(k-2)+2+1=
…
= 2i P(k-i) +2i-1+… + 2 + 1
= 2i P(k-i) + 2i -1
= 2k-1 P(1) + 2k-1 -1
= 2k -1
LOOKUP con RICERCA BINARIA su lista ORDINATA
alow
amid
Sia P(k)=max numero elementi su cui si può fare la
ricerca con k confronti (chiamate ricorsive)
P(1)=1
P(2)=3
(mid, P(1)=1 elementi minori di mid,
P(1)=1 elementi maggiori di mid)
P(k)=2 P(k-1)+1 (mid, P(k-1)=1 elementi minori di mid,
P(k-1)=1 elementi maggiori di mid)
ahigh
P(k)=2 P(k-1)+1= 2( 2 P(k-2)+1)+1= 4 P(k-2)+2+1=
…
= 2i P(k-i) +2i-1+… + 2 + 1
= 2i P(k-i) + 2i -1
= 2k-1 P(1) + 2k-1 -1
= 2k -1k
Quindi ponendo n= P(k) si ha
n=2k -1  k= log (n+1)  numero confronti=R.T=O(log n)
CODE
CODA: struttura basata sulle liste, ma con restrizioni
sulle operazioni di inserzione e cancellazione
Inserzione: sempre da un estremo detto rear
Cancellazione: sempre da altro estremo, detto front
FIFO: First In First Out
(a0, a1, …, an-1)
front
rear
Es. C=(a,b,c)
insert d in C  C’=(a,b,c,d)
delete
 C’’=(b,c,d)
OPERAZIONI su CODA Q
•clear(Q): rendi Q vuota
•dequeue(Q,x): se Q è vuota return FALSE, altrimenti
- poni x=elemento alfront di Q
- elimina elemento al front di Q
- return TRUE
•enqueue(Q,x): se Q è piena return FALSE, altrimenti
- inserisci x al rear di Q
- return TRUE
•isempty(Q): restituisci TRUE se Q è vuota, FALSE alt.
•isfull(Q): restituisci TRUE se Q è piena, FALSE alt.
CODE mediante Liste a Puntatori
Coda  lista con due puntatori: front e rear
typedef struct{
LIST front, rear
} QUEUE
front
/
rear
Coda piena mai, isfull(Q) restituisce sempre FALSE
Coda vuota  front=NULL
BOOLEAN isEmpty(QUEUE *pQ)
{return (pQ->front=NULL);}
void clear(QUEUE *pQ)
{*pQ->front=NULL;}
CODE mediante Liste a Puntatori
BOOLEAN dequeue(QUEUE *pQ, int *px)
{if (isempty(pQ) return FALSE;
else {(*px)=pQ->front->element;
pQ->front=pQ->front->next;
return TRUE;}
front
a
/
rear
CODE mediante Liste a Puntatori
BOOLEAN dequeue(QUEUE *pQ, int *px)
{if (isempty(pQ) return FALSE;
else {(*px)=pQ->front->element;
pQ->front=pQ->front->next;
return TRUE;}
front
a
/
rear
x vale a
CODE mediante Liste a Puntatori
BOOLEAN enqueue(QUEUE *pQ, int x)
{if (isempty(pQ)
{pQ->front=(LIST)malloc(sizeof(struct CELL));
pQ->rear= pQ->front;}
else {pQ->rear->next= =(LIST)malloc(sizeof(struct CELL));
pQ->rear=pQ->rear->next;}
pQ->rear->element=x;
pQ->rear->next=NULL;
return TRUE;}
CODE mediante Liste a Puntatori
BOOLEAN enqueue(QUEUE *pQ, int x)
{if (isempty(pQ)
{pQ->front=(LIST)malloc(sizeof(struct CELL));
pQ->rear= pQ->front;}
else {pQ->rear->next= =(LIST)malloc(sizeof(struct CELL));
pQ->rear=pQ->rear->next;}
pQ->rear->element=x;
pQ->rear->next=NULL;
return TRUE;}
front
CODE mediante Liste a Puntatori
BOOLEAN enqueue(QUEUE *pQ, int x)
{if (isempty(pQ)
{pQ->front=(LIST)malloc(sizeof(struct CELL));
pQ->rear= pQ->front;}
else {pQ->rear->next= =(LIST)malloc(sizeof(struct CELL));
pQ->rear=pQ->rear->next;}
pQ->rear->element=x;
pQ->rear->next=NULL;
return TRUE;}
front
rear
CODE mediante Liste a Puntatori
BOOLEAN enqueue(QUEUE *pQ, int x)
{if (isempty(pQ)
{pQ->front=(LIST)malloc(sizeof(struct CELL));
pQ->rear= pQ->front;}
else {pQ->rear->next= =(LIST)malloc(sizeof(struct CELL));
pQ->rear=pQ->rear->next;}
pQ->rear->element=x;
pQ->rear->next=NULL;
return TRUE;}
front
x
/
rear
CODE mediante Liste a Puntatori
BOOLEAN enqueue(QUEUE *pQ, int x)
{if (isempty(pQ)
{pQ->front=(LIST)malloc(sizeof(struct CELL));
pQ->rear= pQ->front;}
else {pQ->rear->next= =(LIST)malloc(sizeof(struct CELL));
pQ->rear=pQ->rear->next;}
pQ->rear->element=x;
pQ->rear->next=NULL;
return TRUE;}
front
/
rear
CODE mediante Liste a Puntatori
BOOLEAN enqueue(QUEUE *pQ, int x)
{if (isempty(pQ)
{pQ->front=(LIST)malloc(sizeof(struct CELL));
pQ->rear= pQ->front;}
else {pQ->rear->next= =(LIST)malloc(sizeof(struct CELL));
pQ->rear=pQ->rear->next;}
pQ->rear->element=x;
pQ->rear->next=NULL;
return TRUE;}
front
rear
CODE mediante Liste a Puntatori
BOOLEAN enqueue(QUEUE *pQ, int x)
{if (isempty(pQ)
{pQ->front=(LIST)malloc(sizeof(struct CELL));
pQ->rear= pQ->front;}
else {pQ->rear->next= =(LIST)malloc(sizeof(struct CELL));
pQ->rear=pQ->rear->next;}
pQ->rear->element=x;
pQ->rear->next=NULL;
return TRUE;}
front
rear
CODE mediante Liste a Puntatori
BOOLEAN enqueue(QUEUE *pQ, int x)
{if (isempty(pQ)
{pQ->front=(LIST)malloc(sizeof(struct CELL));
pQ->rear= pQ->front;}
else {pQ->rear->next= =(LIST)malloc(sizeof(struct CELL));
pQ->rear=pQ->rear->next;}
pQ->rear->element=x;
pQ->rear->next=NULL;
return TRUE;}
front
X
rear
Nota. Il R.T. è O(1) per tutte le operazioni
/
CODE mediante ARRAY
Array circolare: immaginato come se dopo la posizione
n-1 venga nuovamente la posizione 0
0
A= …
Visto come
n-1
n-1 0
…
1
2
In senso
orario
Front, rear: le posizioni occupate dalla coda vanno
da front a rear, front precede rear in senso orario
Typedef struct{
int A[n];
int front, rear} QUEUE
CODE mediante ARRAY
Front, rear: le posizioni occupate dalla coda vanno
da front a rear, front precede rear in senso orario
7
6
5
8 0
4
1
2
3
Front=2, rear=5  coda=(A[2],A[3],A[4],A[5])
Front=5, rear=2  coda=(A[5],…,A[8],A[0],A[1],A[2])
CODE mediante ARRAY
Front, rear: le posizioni occupate dalla coda vanno
da front a rear, front precede rear in senso orario
Coda vuota: front in posizione immediatamente
successiva al rear
es. front=3, rear=2.
CODE mediante ARRAY
Front, rear: le posizioni occupate dalla coda vanno
da front a rear, front precede rear in senso orario
Coda vuota: front in posizione immediatamente successiva
al rear
es. front=3, rear=2.
Coda piena: contiene n-1 elementi
front a 2 posizioni successive al rear
es. front=3, rear=1  coda=(A[3],…,A[n-1],A[0],A[1])
Nota: se coda contenesse n elementi allora front in
posizione immediatamente successiva al rear,
es. front=3, rear=2 
coda=(A[3],…,A[n-1], A[0], A[1], A[2]),
si confonderebbe con coda vuota
CODE mediante ARRAY
Operazioni modulo n:
x+y mod n=resto divisine di (x+y) per n
es. x+1 mod n= x+1 se x<n-1, 0 se x=n-1.
Clear: poni front=1, rear=0 (quindi front=rear+1 mod n)
isEmpty: controlla se front=rear+1 mod n
isFull: risultato del confronto (front==rear +2 % n)
Enqueue(Q,x): se coda è piena restituisce FALSE,
altrimenti rear=(rear +1)%n; Q[rear]=x; return TRUE
Dequeue(Q,x): se coda vuota restituisce FALSE,
altrimenti x=Q[front]; front=(front+1)%n; return TRUE
CODE mediante ARRAY
8
In una coda circolare con
n=9, inizialmente vuota:
5
1=front=rear
Inserire 5
Inserire 2
5
0=rear
1=front
1=front
2 2=rear
CODE mediante ARRAY
5
1=front
2 2=rear
5
Inserire 6
2
6
Cancellare
1=front
3=rear
2 2=front
6
3=rear
STACK (o Pile)
Stack. lista (a1,…,an) su cui vogliamo fare 2 operazioni
principali: PUSH, POP.
Tutte le operazioni principali sono fatte ad uni stesso
estremo detto TOP
Se stack=S= (a1,…,an), assumiamo top=ultimo elemento=an
PUSH(x,S): inserisce x al top  (a1,…,an,x)
POP(S): elimina elemento al top  (a1,…,an-1)
Stack=Struttura LIFO (Last In First Out)
STACK (o Pile)
Es. Compilatore usa espressioni aritmetiche tradotte da
notazione infissa a postfissa (operandi precedono
operatore)
(3+4)*2  34+2*
3*5+2*7  35*27*+
STACK (o Pile)
Es. Compilatore usa espressioni aritmetiche tradotte da
notazione infissa a postfissa (operandi precedono
operatore)
(3+4)*2  34+2*
Espressioni postfisse valutate mediante stack
Simbolo
3
4
+
2
*
Azione
Stack
e
push 3
3
push 4
3,4
pop, pop
e
push 7
7
push 2
7,2
pop, pop
e
push 14
14
STACK (o Pile)
3*5+2*7  35*27*+
Simbolo
3
5
*
2
7
*
+
Azione
Stack
e
push 3
3
push 5
3,5
pop, pop
e
push 15
15
push 2
15,2
push 7
15,2,7
pop, pop
15
push 14
15,14
pop, pop
e
push 28
28
Operazioni su STACK
Clear(S): rende stack S vuoto
IsEmpty(S): TRUE se S vuoto, FALSE altrimenti
IsFull(S):
TRUE se S pieno, FALSE altrimenti
Pop(S,x): se S è vuoto, restituisce FALSE
altrimenti pone x=elemento al top di S e
restituisce TRUE
Push(S,x): se S è pieno, restituisce FALSE
altrimenti inserisce x al top di S e
restituisce TRUE
stack mediante array
0
1
a0
…
n-1 an-1
…
Top
Typedef struct LIST /*lista  struttura con
2 campi: array e top*/
{
int A[MAX];
int top;
} STACK
MAX-1
Stack (a0,…,an-1) usa prime n locazioni di A, length=n
Primo elemento inserito è a0
Ultimo elemento inserito è an-1
top=n-1
Stack vuoto  top=-1
stack mediante array
Passiamo stack “per referenza”, altrimenti si copia
intero array
Void clear(STACK *pS)
{ ps->top=-1}
Boolean isEmpty(STACK *pS)
{ return (ps->top<0) }
Boolean isFull(STACK *pS)
{ return (ps->top<= MAX-1) }
stack mediante array
Boolean Pop(STACK *pS, int *px)
{ if isempty(pS)) return FALSE
else { (*px)=ps->A[(ps->top)--];
return TRUE }
}
Boolean Push(STACK *pS, int x)
{ if isFull(pS)) return FALSE
else { ps->A[++(ps->top)]=x;
return TRUE }
}
Stack mediante Liste a Puntatori
Stack  lista a puntatori con top al front
typedef struct CELL *STACK
struct CELL {
int element;
STACK next}
S
/
top
Stack mediante Liste a Puntatori
S
/
top
Stack pieno mai, isFull restituisce sempre FALSE
BOOLEAN isFull(STACK *pS)
{return FALSE}
Stack vuoto  lista vuota
BOOLEAN isEmpty(QUEUE *pS)
{return (*pS)==NULL);}
void clear(QUEUE *pQ)
{(*pS)=NULL;}
Stack mediante Liste a Puntatori
BOOLEAN pop(STACK *pS, int *px)
{if ((*pS)==NULL) return FALSE;
else { (*px)=(*ps)->element;
(*ps)=(*ps)->next;
return TRUE }
}
S
/
top
top
S
/
Stack mediante Liste a Puntatori
BOOLEAN push(STACK *pS, int *px)
{STACK newcell;
newcell=(STACK)malloc(sizeof(struct CELL));
newcell->element=x;
newcell->next=(*pS);
(*pS)=newcell;
return TRUE }
}
/
S
top
top
S
x
/
Implementazione di Chiamate di funzioni mediante
Stack
Quando funzione F chiama P: l’ esecuzione di F è sospesa e
le variabili di F sono memorizzate
Per funzioni ricorsive si hanno piu’ chiamate attive allo
Stesso tempo della stessa funzione
int fact(int n)
{if (n<=1) return 1
else return n*fact(n-1)}
fact(10)  fact(9)  fact(8)  … fact(2)
sono tutte attive (e sospese) fino al completamento di fact(1).
Ogni chiamata attiva ha diversi valori di: input, variabili, …
Implementazione di Chiamate di funzioni mediante
Stack
Esecuzione di funzione è chiamata attivazione
Record di attivazione: tutti i dati relativi all’esecuzione;
es: variabili locali, da dove riprendere esecuzione,…
STACK = record di attivazione di tutte le attivazioni non
terminate
Top
A1
A1 in esecuzione
A2
A2 ha chiamato A1, riprende al termine di A1
A3
…
Ak
A3 ha chiamato A2, riprende al termine di A2
…
Implementazione di Chiamate di funzioni mediante
Stack
Es. Record di attivazione per fact
(n,fact)  (valore input, valore output (riempito alla fine))
chiama
fact(4)
crea
stack
fact(3)

stack
(4, fact)
(3, fact )
(4, fact )
(2, fact )
Chiama fact(2)

stack
(3, fact )
(4, fact )
Implementazione di Chiamate di funzioni mediante
Stack
(2, fact )
Chiama fact(2)

stack
(3, fact )
(4, fact )
(1, fact)
(2, fact )
Chiama fact(1)

stack
(3, fact )
(4, fact )
Implementazione di Chiamate di funzioni mediante
Stack
Fact(1) termina 
Fact(2) termina 
(1, fact=1)
(2, fact )

(2, fact )
(3, fact )
(3, fact )
(4, fact )
(4, fact )
(2, fact =2)
(3, fact )
(4, fact )

(3, fact )
(4, fact )
Implementazione di Chiamate di funzioni mediante
Stack
(2, fact =2)
Fact(2) termina 
(3, fact )

(4, fact )
Fact(3) termina 
Fact(4) termina 
(3, fact =6)
(4, fact )
(4, fact=24 )
(3, fact )
(4, fact )

(4, fact )