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)

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

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))

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).

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)

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

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

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)

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 /

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)}

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)

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

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!.

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.

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.

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)}

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 /

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 /

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 /

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

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)

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

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; } }

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

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 (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 (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 (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 (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 (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 (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

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

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

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

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

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

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

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, …)

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 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

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

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

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

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

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)

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)

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)

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)

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)

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)

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)

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)

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.

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.

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.

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; }

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

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

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

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;}

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

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]*/

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)

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)

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)

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=

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

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

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)

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)

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.

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

/

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

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

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;}

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

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

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

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

/

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

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

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

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

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])

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.

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

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

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

CODE mediante ARRAYCODE mediante ARRAY

Inserire 6

Cancellare

1=front5

2=rear2

1=front5

3=rear

2

6

2=front

3=rear

2

6

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)

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*+

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

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

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

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

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) }

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 } }

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

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

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/

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

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, …

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

…

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 )

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)

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 )

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 )