modello dati lista lista: lista: sequenza finita di 0 o più elementi lista di tipo t: lista in cui...
TRANSCRIPT
![Page 1: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/1.jpg)
Modello dati LISTAModello dati LISTA
LISTA: LISTA: sequenza finita di 0 o più elementi
LISTA di tipo T: LISTA di tipo T: lista in cui tutti gli elementi lista in cui tutti gli elementi sono dello sono dello stesso tipo T.stesso tipo T.
es. lista di es. lista di intint, di , di realreal, di , di structstruct,…,… Lista che contiene elementi aLista che contiene elementi a11,…,a,…,ann (a (a11,…,a,…,ann))
Es. lista dei numeri primi <20 in ordine crescente Es. lista dei numeri primi <20 in ordine crescente (1,2,3,5,7,11,13,17)(1,2,3,5,7,11,13,17)
![Page 2: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/2.jpg)
Modello dati LISTAModello dati LISTA
LISTA: LISTA: sequenza finita di 0 o più elementi
LISTA di tipo T: LISTA di tipo T: lista in cui tutti gli elementi lista in cui tutti gli elementi sono dello sono dello stesso tipo T.stesso tipo T.
es. lista di es. lista di intint, di , di realreal, di , di structstruct,…,… Lista che contiene elementi aLista che contiene elementi a11,…,a,…,ann (a (a11,…,a,…,ann))
Es. lista dei numeri primi <20 in ordine crescente Es. lista dei numeri primi <20 in ordine crescente (1,2,3,5,7,11,13,17)(1,2,3,5,7,11,13,17)
Lunghezza di una listaLunghezza di una lista = numero di elementi = numero di elementi nella listanella lista
Es. lunghezza di (1,2,3,5,7,11,13,17) è 8Es. lunghezza di (1,2,3,5,7,11,13,17) è 8
Lista vuota = Lista vuota = = lista con zero elementi= lista con zero elementi
![Page 3: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/3.jpg)
Modello dati LISTAModello dati LISTA
Data la lista (aData la lista (a11,…,a,…,ann))
HeadHead= primo = primo elementoelemento della lista = a della lista = a11
TailTail= = listalista senza head = (a senza head = (a22,…,a,…,ann))
![Page 4: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/4.jpg)
Modello dati LISTAModello dati LISTA
Data la lista (aData la lista (a11,…,a,…,ann))
HeadHead= primo = primo elementoelemento della lista = a della lista = a11
TailTail= = listalista senza head = (a senza head = (a22,…,a,…,ann))
SottolistaSottolista : : ogni lista (ai,ai+1,…, aj) 1ogni lista (ai,ai+1,…, aj) 1<<ii<<jj<<nn
Sottosequenza: Sottosequenza: elimina alcuni elementi dalla elimina alcuni elementi dalla listalista
lascandi gli altri in ordinelascandi gli altri in ordine
Es. Data (1,2,3)Es. Data (1,2,3) sottoliste: sottoliste: , (1), (2), (3), (1,2), (2,3), (1,2,3), (1), (2), (3), (1,2), (2,3), (1,2,3) sottosequenze: tutte le sottoliste e (1,3).sottosequenze: tutte le sottoliste e (1,3).
![Page 5: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/5.jpg)
Modello dati LISTAModello dati LISTA
Data la lista (aData la lista (a11,…,a,…,ann))
PrefissoPrefisso= sottolista che inizia con a= sottolista che inizia con a11
SuffissoSuffisso= sottolista che finisce con an= sottolista che finisce con an
La lista vuota è prefisso e suffisso di ogni listaLa lista vuota è prefisso e suffisso di ogni lista
Es. Data (1,2,3,4)Es. Data (1,2,3,4) prefissi: prefissi: (1), (1,2), (1,2,3), (1,2,3,4) (1), (1,2), (1,2,3), (1,2,3,4) suffissi: suffissi: (4), (3,4), (2,3,4), (1,2,3,4)(4), (3,4), (2,3,4), (1,2,3,4)
![Page 6: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/6.jpg)
Modello dati LISTAModello dati LISTA
Data la lista (aData la lista (a11,…,a,…,ann))
Elemento in posizione i= aiElemento in posizione i= ai
Predecessore di ai = ai-1Predecessore di ai = ai-1Successore di ai= ai+1Successore di ai= ai+1
Occorrenza di x = una posizione i tale che ai=xOccorrenza di x = una posizione i tale che ai=x
Es. Data (a,b,c,b,b)Es. Data (a,b,c,b,b) elemento in posizione 1 = aelemento in posizione 1 = a elemento in posizione 4 = belemento in posizione 4 = b
occorrenza di a = 1occorrenza di a = 1 occorrenze di b = 2,4,5occorrenze di b = 2,4,5 occorrenza di c = 3occorrenza di c = 3
![Page 7: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/7.jpg)
Operazioni su listeOperazioni su liste
Sorting: Sorting: data la lista (adata la lista (a11,…a,…ann) restituisce la lista ) restituisce la lista ordinata (bordinata (b11,…,b,…,bnn) contenente gli stessi elementi) contenente gli stessi elementi
Merging: Merging: date due liste ordinate restituisce una date due liste ordinate restituisce una lista ordinata contenente tutti gli elementi delle lista ordinata contenente tutti gli elementi delle liste inputliste input
Dizionario: Dizionario: insieme di elementi su cui si vogliono insieme di elementi su cui si vogliono fare le operazioni di fare le operazioni di inserzione, ricerca e inserzione, ricerca e cancellazionecancellazione
![Page 8: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/8.jpg)
Operazioni su listeOperazioni su liste
PushPush: : insert nuovo elemento come head della insert nuovo elemento come head della listalista
es. L=(1,2,3,2), push(L,1) es. L=(1,2,3,2), push(L,1) L’=(1,1,2,3,2) L’=(1,1,2,3,2)
PopPop: : cancella head della listacancella head della lista es. L=(1,2,3,2), pop(L) es. L=(1,2,3,2), pop(L) L’=(2,3,2) L’=(2,3,2)
Concatenazione di 2 liste:Concatenazione di 2 liste: L=(a1,…,an), M=(b1,…bm) L=(a1,…,an), M=(b1,…bm) (a1,…,an,b1, (a1,…,an,b1,
…bm)…bm)
![Page 9: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/9.jpg)
Liste a puntatori (struttura dati)Liste a puntatori (struttura dati)
typedef struct CELL *LISTtypedef struct CELL *LIST struct CELL{struct CELL{ int element; int element; /*per semplicità assumiamo elementi /*per semplicità assumiamo elementi
interi*/interi*/
LIST next}LIST next}
lista: (modello) L=(a1,…,an)lista: (modello) L=(a1,…,an)
(sruttura) a1 a2 an / (sruttura) a1 a2 an /
![Page 10: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/10.jpg)
Liste a puntatori (struttura dati)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)}
![Page 11: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/11.jpg)
Liste a puntatori (struttura dati)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)
![Page 12: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/12.jpg)
Liste a puntatori (struttura dati)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
![Page 13: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/13.jpg)
Liste a puntatori (struttura dati)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!.
![Page 14: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/14.jpg)
Liste a puntatori (struttura dati)Liste a puntatori (struttura dati)
Cancellazione di x da lista L:Elimina la cella contenente x
Void delete(int x, LIST *pL){if (*pL!=NULL) if(*pL->element==x) *pL=*pL ->next else delete(x, *pL->next)}
x x
Si usa il puntatore pL (chiamata per referenza) invece di L per poter modificare L.
![Page 15: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/15.jpg)
Liste a puntatori (struttura dati)Liste a puntatori (struttura dati)
Cancellazione di x da lista L:Elimina la cella contenente x
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.
Si usa il puntatore pL (chiamata per referenza) invece di L per poter modificare L.
![Page 16: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/16.jpg)
Liste a puntatori (struttura dati)Liste a puntatori (struttura dati)
Inserzione di x nella lista L:Inserisce, se x non in L, una cella contenente xVoid 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)}
![Page 17: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/17.jpg)
Liste a puntatori (struttura dati)Liste a puntatori (struttura dati)
Inserzione di x nella lista L:Inserisce, se x non in L, una cella contenente xVoid 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 /
![Page 18: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/18.jpg)
Liste a puntatori (struttura dati)Liste a puntatori (struttura dati)
Inserzione di x nella lista L:Inserisce, se x non in L, una cella contenente xVoid 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 Altrimenti arriva a fine lista:
NULL
X /
X /
![Page 19: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/19.jpg)
Liste a doppi puntatori Liste a doppi puntatori
type def struct CELL *LISTStruct CELL{LIST previous; int element; LIST next}
Es. Cancella la cella puntata dal puntatore p:
delete(LIST p, LIST *pL)
L / a1 a2 an /
![Page 20: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/20.jpg)
Liste a doppi puntatori 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
![Page 21: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/21.jpg)
Sorting: MERGESORTSorting: 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)
![Page 22: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/22.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
Algoritmo dipende dalla rappresentazione delle liste
Usiamo LISTE A PUNTATORI:
ogni elemento della lista è una struttura typedef struct CELL *LISTstruct CELL{ int element /* elemento della lista*/ LIST next /* puntatore alla successiva
struttura (elemento)*/
}
(a1,a2,…,an) a1 a2 … an
![Page 23: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/23.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) 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; } }
![Page 24: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/24.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
LIST merge (LIST list1, LIST list2) {if (list1==NULL) return list2else 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 … an
list2 b1 b2 … bn
a2 … an list1 a1 merge
b1 … bn
![Page 25: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/25.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7
list2 3 5 6 9
list1 merge(list1, list2) merge (2-4-7, 3-5-6-9)
![Page 26: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/26.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7
list2 3 5 6 9
Merge(list1, list2) merge (2-4-7, 3-5-6-9)
merge(list2) merge(4-7,3-5-6-9)
![Page 27: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/27.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7
list2 3 5 6 9
Merge(list1, list2) merge (2-4-7, 3-5-6-9)
merge(list2) merge(4-7,3-5-6-9)
merge(, ) merge(4-7, 5-6-9)
![Page 28: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/28.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7
list2 3 5 6 9
Merge(list1, list2) merge (2-4-7, 3-5-6-9)
merge(list2) merge(4-7,3-5-6-9)
merge(, ) merge(4-7, 5-6-9)
merge(, ) merge(7, 5-6-9)
![Page 29: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/29.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7
list2 3 5 6 9
Merge(list1, list2) merge (2-4-7, 3-5-6-9)
merge(list2) merge(4-7,3-5-6-9)
merge(, ) merge(4-7, 5-6-9)
merge(, ) merge(7, 5-6-9)
merge(, ) merge(7, 6-9)
![Page 30: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/30.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7
list2 3 5 6 9
Merge(list1, list2) merge (2-4-7, 3-5-6-9)
merge(list2) merge(4-7,3-5-6-9)
merge(, ) merge(4-7, 5-6-9)
= merge(, ) merge(7, 5-6-9)
= merge(, ) merge(7, 6-9)
= merge(, ) merge(7, 9)
![Page 31: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/31.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7
list2 3 5 6 9
Merge(list1, list2) merge (2-4-7, 3-5-6-9)
merge(list2) merge(4-7,3-5-6-9)
= merge(, ) merge(4-7, 5-6-9)
= merge(, ) merge(7, 5-6-9)
= merge(, ) merge(7, 6-9)
= merge(, ) merge(7, 9)
= merge(NULL, )= merge( , 9) 9
![Page 32: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/32.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7 list2 3 5 6 9
Merge(list1, list2) merge (2-4-7, 3-5-6-9)
merge(list2) merge(4-7,3-5-6-9)
= merge(, ) merge(4-7, 5-6-9)
= merge(, ) merge(7, 5-6-9)
= merge(, ) merge(7, 6-9)
= merge(, ) = merge(7, 9) 7
![Page 33: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/33.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7 list2 3 5 6 9
Merge(list1, list2) merge (2-4-7, 3-5-6-9)
merge(list2) merge(4-7,3-5-6-9)
= merge(, ) merge(4-7, 5-6-9)
= merge(, ) merge(7, 5-6-9)
= merge(, )= merge(7, 6-9) 6
![Page 34: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/34.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7 list2 3 5 6 9
Merge(list1, list2) merge (2-4-7, 3-5-6-9)
merge(list2) merge(4-7,3-5-6-9)
= merge(, ) merge(4-7, 5-6-9)
= merge(, ) = merge(7, 5-6-9) 5
![Page 35: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/35.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7 list2 3 5 6 9
Merge(list1, list2) merge (2-4-7, 3-5-6-9)
merge(list2) merge(4-7,3-5-6-9)
= merge(, ) = merge(4-7, 5-6-9) 4
![Page 36: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/36.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7 list2 3 5 6 9
list1=merge(list1, list2) merge (2-4-7, 3-5-6-9)
merge(list2)=list2 merge(4-7,3-5-6-9) list2 3
![Page 37: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/37.jpg)
MERGE (di due liste ordinate LMERGE (di due liste ordinate L11,L,L22 M) M)
list1 2 4 7 list2 3 5 6 9
list1=merge(list1, list2) merge (2-4-7, 3-5-6-9) list1 2
![Page 38: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/38.jpg)
SPLIT (di L in due liste ordinate LSPLIT (di L in due liste ordinate L11,L,L22))
LIST Split (LIST list){ List pSecondcell;if (list==NULL) return NULLelse 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; }}
L=(a1,a2, a3, a4, …, an) L1 =(a1, a3, …) , L2 =(a2, a4, …)
![Page 39: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/39.jpg)
SPLIT (di L in due liste ordinate L1,L2)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
![Page 40: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/40.jpg)
SPLIT (di L in due liste ordinate L1,L2)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
pSecondcell
![Page 41: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/41.jpg)
SPLIT (di L in due liste ordinate L1,L2)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
pSecondcell
![Page 42: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/42.jpg)
SPLIT (di L in due liste ordinate L1,L2)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
pSecondcell
![Page 43: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/43.jpg)
MERGESORTMERGESORT
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
![Page 44: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/44.jpg)
MERGESORTMERGESORT
LIST Mergesort (LIST list){ List SecondList;if (list==NULL) return NULLelse if (list->next==NULL) return list else {/* list contiene almeno 2 elementi (da ordinare)*/ SecondList=split(list); return merge(mergesort(list),mergesort(ScondList)); }}
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
![Page 45: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/45.jpg)
R.T. della funzione SPLITR.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)
![Page 46: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/46.jpg)
R.T. del MERGER.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)
![Page 47: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/47.jpg)
R.T. MERGESORTR.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)
![Page 48: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/48.jpg)
R.T. MERGESORTR.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)
![Page 49: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/49.jpg)
R.T. MERGESORTR.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)
![Page 50: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/50.jpg)
R.T. MERGESORTR.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)
![Page 51: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/51.jpg)
R.T. MERGESORTR.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)
![Page 52: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/52.jpg)
R.T. MERGESORTR.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)
![Page 53: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/53.jpg)
Correttezza MERGESORTCorrettezza MERGESORTLIST 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.
![Page 54: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/54.jpg)
Correttezza MERGESORTCorrettezza MERGESORTLIST 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.
![Page 55: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/55.jpg)
Correttezza MERGESORTCorrettezza MERGESORTLIST 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.
![Page 56: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/56.jpg)
Liste mediante array 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
01
n-1
MAX
a0
an-1
…
…
Typedef struct LIST /*lista struttura con 2 campi: array e length*/ { int A[MAX]; int length; }
![Page 57: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/57.jpg)
Liste mediante array Liste mediante array
01
n-1
MAX
a0
an-1
…
…
Typedef struct LIST /*lista struttura con 2 campi: array e length*/ { int A[MAX]; int length; }
pL: puntatore a struct LIST LpL->A[i] = elemento i-mo della listapL->length = lunghezza lista
![Page 58: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/58.jpg)
Liste mediante array Liste mediante array
pL: puntatore a struct LISTpL->A[i]= elemento i-mo della listapL->length=lunghezza lista
LOOKUP
Ricerca lineareBoolean 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
![Page 59: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/59.jpg)
Liste mediante array Liste mediante array
Ricerca lineare con sentinellaBoolean 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
![Page 60: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/60.jpg)
Liste mediante array Liste mediante array
Ricerca lineare con sentinellaBoolean 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;}
![Page 61: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/61.jpg)
LOOKUP con RICERCA BINARIA su lista LOOKUP con RICERCA BINARIA su lista ORDINATAORDINATA
Sia a0,a1,…,an-1 una lista ordinata (a0 < a1 < …< an-1) rappresentata mediante un array A[0..n-1].Cerchiamo x.
a0
an-1
amid mid=[(n-1)/2]
Se x<A[mid] continua la ricerca di x in A[0.. mid-1]
Se x>A[mid] continua la ricerca di x in A[mid+1.. n-1]
Se x=A[mid], trovato x, STOP
![Page 62: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/62.jpg)
LOOKUP con RICERCA BINARIA su lista LOOKUP con RICERCA BINARIA su lista ORDINATAORDINATA
alow
ahigh
amid
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]*/
![Page 63: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/63.jpg)
LOOKUP con RICERCA BINARIA su lista LOOKUP con RICERCA BINARIA su lista ORDINATAORDINATA
alow
ahigh
amid
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)
![Page 64: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/64.jpg)
LOOKUP con RICERCA BINARIA su lista LOOKUP con RICERCA BINARIA su lista ORDINATAORDINATAalow
ahigh
amid
Sia P(k)=max numero elementi su cui si può fare la ricerca con k confronti (chiamate ricorsive)
P(1)=1P(2)=3 (mid, P(1)=1 elementi minori di mid, P(1)=1 elementi maggiori di mid)
![Page 65: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/65.jpg)
LOOKUP con RICERCA BINARIA su lista LOOKUP con RICERCA BINARIA su lista ORDINATAORDINATAalow
ahigh
amid
Sia P(k)=max numero elementi su cui si può fare la ricerca con k confronti (chiamare ricorsive)
P(1)=1P(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)
![Page 66: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/66.jpg)
LOOKUP con RICERCA BINARIA su lista LOOKUP con RICERCA BINARIA su lista ORDINATAORDINATAalow
ahigh
amid
Sia P(k)=max numero elementi su cui si può fare la ricerca con k confronti (chiamate ricorsive)
P(1)=1P(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)
P(k)=2 P(k-1)+1= 2( 2 P(k-2)+1)+1= 4 P(k-2)+2+1=
![Page 67: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/67.jpg)
LOOKUP con RICERCA BINARIA su lista LOOKUP con RICERCA BINARIA su lista ORDINATAORDINATAalow
ahigh
amid
Sia P(k)=max numero elementi su cui si può fare la ricerca con k confronti (chiamate ricorsive)
P(1)=1P(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)
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
![Page 68: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/68.jpg)
LOOKUP con RICERCA BINARIA su lista LOOKUP con RICERCA BINARIA su lista ORDINATAORDINATAalow
ahigh
amid
Sia P(k)=max numero elementi su cui si può fare la ricerca con k confronti (chiamate ricorsive)
P(1)=1P(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)
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
![Page 69: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/69.jpg)
LOOKUP con RICERCA BINARIA su lista LOOKUP con RICERCA BINARIA su lista ORDINATAORDINATAalow
ahigh
amid
Sia P(k)=max numero elementi su cui si può fare la ricerca con k confronti (chiamate ricorsive)
P(1)=1P(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)
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)
![Page 70: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/70.jpg)
CODECODE
CODA: struttura basata sulle liste, ma con restrizioni sulle operazioni di inserzione e cancellazione
Inserzione: sempre da un estremo detto rearCancellazione: 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)
![Page 71: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/71.jpg)
OPERAZIONI su CODA QOPERAZIONI 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.
![Page 72: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/72.jpg)
CODE mediante Liste a PuntatoriCODE mediante Liste a Puntatori
Coda lista con due puntatori: front e rear typedef struct{ LIST front, rear } QUEUE
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;}
frontrear
/
![Page 73: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/73.jpg)
CODE mediante Liste a PuntatoriCODE 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;}
frontrear
/a
![Page 74: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/74.jpg)
CODE mediante Liste a PuntatoriCODE 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;}
frontrear
/a
x vale a
![Page 75: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/75.jpg)
CODE mediante Liste a PuntatoriCODE 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;}
![Page 76: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/76.jpg)
CODE mediante Liste a PuntatoriCODE 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
![Page 77: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/77.jpg)
CODE mediante Liste a PuntatoriCODE 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;}
frontrear
![Page 78: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/78.jpg)
CODE mediante Liste a PuntatoriCODE 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;}
frontrear
/x
![Page 79: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/79.jpg)
CODE mediante Liste a PuntatoriCODE 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;}
frontrear
/
![Page 80: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/80.jpg)
CODE mediante Liste a PuntatoriCODE 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;}
frontrear
![Page 81: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/81.jpg)
CODE mediante Liste a PuntatoriCODE 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;}
frontrear
![Page 82: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/82.jpg)
CODE mediante Liste a PuntatoriCODE 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;}
frontrear
X /
Nota. Il R.T. è O(1) per tutte le operazioni
![Page 83: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/83.jpg)
CODE mediante ARRAYCODE mediante ARRAY
Array circolare: immaginato come se dopo la posizione n-1 venga nuovamente la posizione 0
A= …
0
n-1
Visto come In senso orario
n-1 0 1 2
…
Typedef struct{ int A[n]; int front, rear} QUEUE
Front, rear: le posizioni occupate dalla coda vanno da front a rear, front precede rear in senso orario
![Page 84: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/84.jpg)
CODE mediante ARRAYCODE mediante ARRAY
Front, rear: le posizioni occupate dalla coda vanno da front a rear, front precede rear in senso orario
8 0 1 2
4 3 5 6 7
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])
![Page 85: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/85.jpg)
CODE mediante ARRAYCODE 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.
![Page 86: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/86.jpg)
CODE mediante ARRAYCODE 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
![Page 87: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/87.jpg)
CODE mediante ARRAYCODE mediante ARRAY
Operazioni modulo n: x+y mod n=resto divisine di (x+y) per nes. 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
![Page 88: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/88.jpg)
CODE mediante ARRAYCODE mediante ARRAY8 0=rear
1=frontIn una coda circolare con n=9, inizialmente vuota:
Inserire 5
Inserire 2
1=front=rear5
1=front5
2=rear2
![Page 89: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/89.jpg)
CODE mediante ARRAYCODE mediante ARRAY
Inserire 6
Cancellare
1=front5
2=rear2
1=front5
3=rear
2
6
2=front
3=rear
2
6
![Page 90: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/90.jpg)
STACK (o Pile)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)
![Page 91: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/91.jpg)
STACK (o Pile)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*+
![Page 92: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/92.jpg)
STACK (o Pile)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 Azione Stack 3 push 3 3 4 push 4 3,4 + pop, pop push 7 7 2 push 2 7,2 * pop, pop push 14 14
![Page 93: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/93.jpg)
STACK (o Pile)STACK (o Pile)
3*5+2*7 35*27*+
Simbolo Azione Stack 3 push 3 3 5 push 5 3,5 * pop, pop push 15 15 2 push 2 15,2 7 push 7 15,2,7 * pop, pop 15 push 14 15,14 + pop, pop push 28 28
![Page 94: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/94.jpg)
Operazioni su STACKOperazioni 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
![Page 95: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/95.jpg)
stack mediante array stack mediante array
Primo elemento inserito è a0
Ultimo elemento inserito è an-1
top=n-1
Stack vuoto top=-1
01
n-1
MAX-1
a0
an-1
…
…
Typedef struct LIST /*lista struttura con 2 campi: array e top*/ { int A[MAX]; int top; } STACK
Top
Stack (a0,…,an-1) usa prime n locazioni di A, length=n
![Page 96: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/96.jpg)
stack mediante array 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) }
![Page 97: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/97.jpg)
stack mediante array 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 } }
![Page 98: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/98.jpg)
Stack mediante Liste a PuntatoriStack mediante Liste a Puntatori
Stack lista a puntatori con top al front
typedef struct CELL *STACK struct CELL { int element; STACK next}
S/
top
![Page 99: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/99.jpg)
Stack mediante Liste a PuntatoriStack mediante Liste a Puntatori
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;}
S/
top
![Page 100: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/100.jpg)
Stack mediante Liste a PuntatoriStack mediante Liste a Puntatori
BOOLEAN pop(STACK *pS, int *px) {if ((*pS)==NULL) return FALSE; else { (*px)=(*ps)->element; (*ps)=(*ps)->next; return TRUE } }
topS
/
top
S/
![Page 101: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/101.jpg)
Stack mediante Liste a PuntatoriStack 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 } }
topS
/
top
S/x
![Page 102: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/102.jpg)
Implementazione di Chiamate di funzioni Implementazione di Chiamate di funzioni mediante Stackmediante 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 alloStesso 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, …
![Page 103: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/103.jpg)
Implementazione di Chiamate di funzioni Implementazione di Chiamate di funzioni mediante Stackmediante 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 terminateA1
…
Top
A2
A3
Ak
A1 in esecuzione
A2 ha chiamato A1, riprende al termine di
A1
A3 ha chiamato A2, riprende al termine di
A2
…
![Page 104: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/104.jpg)
Implementazione di Chiamate di funzioni Implementazione di Chiamate di funzioni mediante Stackmediante Stack
Es. Record di attivazione per fact (n,fact) (valore input, valore output (riempito alla fine))
fact(4) crea stack (4, fact)
chiama fact(3) stack
Chiama fact(2) stack
(3, fact )
(4, fact )
(3, fact )
(4, fact )
(2, fact )
![Page 105: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/105.jpg)
Implementazione di Chiamate di funzioni Implementazione di Chiamate di funzioni mediante Stackmediante Stack
Chiama fact(2) stack
Chiama fact(1) stack
(3, fact )
(4, fact )
(2, fact )
(3, fact )
(4, fact )
(2, fact )
(1, fact)
![Page 106: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/106.jpg)
Implementazione di Chiamate di funzioni Implementazione di Chiamate di funzioni mediante Stackmediante Stack
Fact(1) termina
Fact(2) termina
(3, fact )
(4, fact )
(2, fact )
(1, fact=1)
(3, fact )
(4, fact )
(2, fact )
(3, fact )
(4, fact )
(2, fact =2)
(3, fact )
(4, fact )
![Page 107: Modello dati LISTA 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](https://reader033.vdocumenti.com/reader033/viewer/2022061609/5542eb4b497959361e8b8867/html5/thumbnails/107.jpg)
Implementazione di Chiamate di funzioni Implementazione di Chiamate di funzioni mediante Stackmediante Stack
Fact(2) termina
Fact(3) termina
Fact(4) termina
(3, fact )
(4, fact )
(2, fact =2)
(3, fact )
(4, fact )
(3, fact =6)
(4, fact )
(4, fact )
(4, fact=24 )