Liste con sentinellaUniversità degli Studi di Milano

Marco Frasca

Un’ulteriore semplificazione delle operazioni sulle liste si ottiene utilizzando un elemento sentinella (dummy) che non contiene informazione, ma serve a segnalare la fine e l’inizio di una lista.

Questa soluzione va contemplata quando le lunghezze stimate dalle liste usate sono significativamente maggiori delle dimensioni di un elemento.

Bisogna in primo luogo allocare la sentinella al momento della creazione della lista.intlist *createlist(void){ intlist *q = malloc(sizeof(intlist)); if(!q) { fprintf(stderr, "Errore di allocazione nella creazione della lista\n");

exit(-1); } q->next = q->prev = q; return q;}

Liste con sentinellaUniversità degli Studi di Milano

Marco Frasca

Dopo il comando : root = createlist();

root:

Liste con sentinellaUniversità degli Studi di Milano

Marco Frasca

Dopo aver inserito in testa gli elementi 1, . . . , k:

root:

Liste con sentinellaUniversità degli Studi di Milano

Marco Frasca

Con l’introduzione della sentinella, inserimento e cancellazione diventano:void insert(intlist *p, int elem) { intlist *q = malloc(sizeof(intlist)); if(!q) { fprintf(stderr,"Errore nell’allocazione del nuovo elemento\n"); exit(-1); } q->dato = elem; q->next = p->next; p->next->prev = q; p->next = q; q->prev = p;}

void delete(intlist q) { /*Nota: la delete ha più la root come argomento*/ q->prev->next = q->next; q->next->prev = q->prev; free(q);}

Liste con sentinellaUniversità degli Studi di Milano

Marco Frasca

Anche altre funzioni sono state modificate:void listcat(intlist *p, intlist *q){ if(q != q->next) { /* lista q non vuota*/ if(p == p->next) { /* p contiene solo nodo il dummy */ p->next = q->next; q->next->prev = p; } else { p->prev->next = q->next; /* il predecessore di p è l'ultimo nodo */ q->next->prev = p->prev; } p->prev = q->prev;/* ricollega la sentinella all'ultimo nodo della lista q*/ q->prev->next = p; } free(q); /*libera il nodo dummy della lista q*/}

La funzione listcat non attua più la scansione per raggiungere la fine della prima lista, ma lavora in tempo costante.

Liste con sentinellaUniversità degli Studi di Milano

Marco Frasca

L’inserimento in coda alla lista risulta facile come l’inserimento in testa:

/* inserisce un elemento in coda alla lista */void insertatend(intlist *p, int elem) { intlist *q = malloc(sizeof(intlist)); if(!q) { fprintf(stderr,"Errore nell’allocazione del nuovo elemento\n"); exit(-1); } q->dato = elem; q->prev = p->prev; /*Il predecessore è l'ultimo nodo della lista*/ p->prev->next = q; /*q diventa il successore del'ultimo elemento della lista*/ p->prev = q; /*Collegamenti del nodo dummy*/ q->next = p;}

NOTA: le funzioni traverse, geteleminlist e countlist devono essere modificate per gestire la circolaritàSi inserisca questa implementazione nel file intlistdummy.c

Liste : altri miglioramenti Università degli Studi di Milano

Marco Frasca

Vi sono ancora funzioni che scandiscono la lista inutilmente, come countlist

In questo caso, per rimediare possiamo memorizzare l’informazione sul numero di elementi in un tipo struct che contiene anche il puntatore al primo elemento:

struct intlistheader {intlist *root;int count;

};

Un esercizio della lezione scorsa chiedeva di modificare le funzioni di manipolazione di liste per implementare questa versione. Ricordate di modificare anche la funzione countlistInserite questa implementazione nel file intlistdummycount.c

Struttura dati pila (Stack) Università degli Studi di Milano

Marco Frasca

Una pila può essere vista come una lista in cui le operazioni di inserimento, cancellazione e ricerca sono applicabili solo al primo elemento della lista

Una pila è quindi insieme di elementi gestiti secondo una politica LIFO (Last In First Out): l’ultimo elemento (temporalmente) inserito è ad essere primo estratto

Dati: un insieme finito S di elementi organizzati sequenzialmente

Operazioni:

1. is_empty() : restituisce true se S è vuoto, false altrimenti 2. push(elem u) : aggiunge u come elemento di testa di S 3. pop() : elimina da S l'elemento di testa e lo restituisce 4. top() : restituisce l’elemento di testa di S, senza eliminarlo

Pila : implementazione Università degli Studi di Milano

Marco Frasca

Poiché le pile sono collezioni di dati per i quali l’accesso può avvenire solo attraverso la politica LIFO, è facile implementare una pila attraverso le liste concatenate:struct intstack {

intlist *top;int count;

};

typedef struct intstack intstack;

intstack *createstack(void) { intstack *st = malloc(sizeof(intstack)); if(!st) { fprintf(stderr,"Errore allocazione creazione dello stack\n"); exit(-1); } st->top = createlist(); st->count = 0; return st;}

Pila : implementazione Università degli Studi di Milano

Marco Frasca

Usiamo l’implementazione di intlist con sentinella che è contenuta in intlistdummy.cint pop(intstack *st) {

int e;if(!st->count){ /* Oppure if(!is_empty(st)) */ fprintf(stderr,"Errore: pop su stack vuoto\n");

exit(-2);}e = head(st->top); /* legge il primo elemento della lista */deletehead(st->top); /* cancella il primo elemento della lista */st->count--;return e;

}

void push(intstack *st, int elem){insert(st->top, elem);st->count++;

}

char is_empty(intstack *st){return !st->count;

}

int top(intstack *st){int e = head(st->top);return e;

}

Pila : implementazione Università degli Studi di Milano

Marco Frasca

st = createstack();

st

Scriviamo questa implementazione in intstack.c

Università degli Studi di Milano

Marco Frasca

Una coda è usa struttura data sui cui elementi (un insieme finito S) sono possibili le seguenti operazioni:

1. is_empty() : restituisce true se S è vuoto, false altrimenti 2. enqeue(elem u) : inserisce u nella coda 3. front() : legge l'elemento che da più tempo è nella coda 4. dequeue() : elimina da S l'elemento inserito per prima e lo restituisce

Una coda quindi è una struttura dati simile alla pila, ma che però segue la politica FIFO: First In First Out; ossia, si estrae sempre il primo elemento (temporalmente) inserito tra quelli in S

Struttura dati coda (queue)

Università degli Studi di Milano

Marco Frasca

L’implementazione di intqueue è quasi identica a quella di intstack:solo l’inserimento di dati in intqueue differisce:

Si confrontino push ed enqueue:void push(intstack *st, int elem){

insert(st->top, elem);st->count++;

}

void enqueue(intqueue *q, int elem){insertatend(q->head, elem);q->count++;

}

Implementiamo intqueue nel file intqueue.c

Coda: implementazione

Ordinamento. InsertionSort: pseudo-

codiceInsertionSort (Array A)

1. for i = 2 to length(A) do

2. v ← A[i]

3. j ← i-1

4. while j>=1 and A[j]>v do

5. A[j + 1] ← A[j]

6. j ← j-1

7. end while

8. A[j + 1] ← v

9. end for

10.return A

Università degli Studi di Milano

Marco Frasca

i=25 | 2 | 1 | 8 | 7 | 3 |

j = 1

Linea 5j = 0

2 | 5 | 1 | 8 | 7 | 3 |

i=3

v = 2

Linea 6

v Linea 8

2 | 5 | 1 | 8 | 7 | 3 |

j = 2

Linea 5j = 1

2 | 5 | 5 | 8 | 7 | 3 |

v = 1

Linea 6

Linea 8

A[j] > v

i=4

j = 1

2 | 2 | 5 | 8 | 7 | 3 |v = 1

v Linea 8 Linea 5

Linea 5

1 | 2 | 5 | 8 | 7 | 3 | j< 1

Insertion Sort: quante operazioni Università degli Studi di Milano

Marco Frasca

n = length(A)

Costo Ripetizioni

1 n-11 n-11 2*m ?1 m1 m

1 n-1--------------------------------T(n,m) = 3*(n-1) + 4*m

- Quanto vale m ?

InsertionSort(Array A)1.  for i = 2 to length(A) do2.    v   A← [i]3.    j    ← i ­ 14.    while j >= 1 and A[j] > v do5. A[j + 1] ← A[j]6. j ← j ­ 17.    end while8.    A[j + 1] ← v9.   end for10.return A

Insertion Sort

Caso peggiore: quanto vale m ? ● m = 1 quando i = 2, m = 2 quando i = 3, ...., m = n - 1 quando i = n

● Il ciclo while viene eseguito volte.

●

E nel caso migliore?

● Qual è la classe di complessità di T(n)?

Università degli Studi di Milano

Marco Frasca

∑i=1

n−1

i=n (n−1)/2=n2

2−

n2

T n=3n−14 n2

2−

n2=2n2

n−3

EserciziUniversità degli Studi di Milano

Marco Frasca

1. Implementare in C l'algoritmo la funzione void InsertionSort(int* v, char o) per ordinare il vettore di interi v in modo crescente, se o == 'c', in modo decrescente se o == 'd' mediante l'algoritmo InsertionSort. Scrivere poi la funzione il cui prototipo è void InsertionSortS(char **s, char o),che modifichi la funzione precedente per ordinare l'array di stringhe s in modo lessicografico. 2. Riprendere le funzioni leggiparola e leggitesto della lezione precedente e scrivere un programma C che legga le parole di un testo e le ordini lessicograficamente usando InsertionSortS. Scrivere sia la versione che legge da tastiera (stdin) e scriva il risultato a Video, sia quella che legge il tasto da un file testo.txt e scriva il risultato nel file testoOrdinato.txt.

EserciziUniversità degli Studi di Milano

Marco Frasca

3. Scrivere un programma C che fornisca all'utente un menu a scelta per ciascuna delle seguenti operazioni su una lista concatenata con nodo dummy

(a) Create: Creare una lista vuota(b) Inserimento in testa: il programma deve chiedere all'utente di inserire un

intero ed inserirlo in testa ad una lista concatenata(c)Inserimento in fondo: Idem, ma inserirlo in fondo alla lista(d) Visualizza: stampare tutti gli elementi della lista(e) Ricerca: l'utente deve inserire un intero a e il programma deve restituire

'presente' se a è presente nella lista, 'assente' altrimenti(f) Cancellazione: elimina dalla lista l'intero inserito dall'utente(g) Conta: restituisce il numero di elementi nella lista(h) Cancella lista: liberare lo spazio occupato da tutta la lista(i) Esci: per terminare il programma

Produrre anche il makefile per compilare il programma

EserciziUniversità degli Studi di Milano

Marco Frasca

4. Ripetere l'esercizio 3 utilizzando un lista con nodo dummy e contatore del numero di elementi.

5. Scrivere un programma C che fornisca all'utente un menu a scelta per ciascuna delle seguenti operazioni su una coda

(a) Create: Creare una coda vuota (b) Inserisci elemento: il programma deve chiedere all'utente di inserire un intero

ed inserirlo in una coda(c) Visualizza elemento: il programma deve visualizzare l'elemento che è da più

tempo in coda, senza cencellarlo(d) Cancellazione: elimina l'elemento inserito per primo dalla coda(e) Conta: restituisce il numero di elementi nella coda(f) Controllo coda vuota(g) Cancella coda: liberare lo spazio occupato dall coda(h) Esci: per terminare il programma

6. Implementare e testare la struttura dati Pila