Università degli Studi di Bergamo Esercitazioni di ... · a.a. 2018-2019 Codice corso: 21012 ....

Università degli Studi di Bergamo Esercitazioni di Informatica Facoltà di Ingegneria (modulo di programmazione - 6 CFU) a.a. 2018-2019 Codice corso: 21012

Pagina 1 di 19

LISTE DINAMICHE Liste semplicemente concatenate: La definizione del tipo di dato astratto lista è intrinsecamente ricorsiva, infatti una lista può essere: • la lista vuota; • oppure contiene un valore (di un certo tipo di dato) seguito da una lista Per poter definire in C un tipo di dato astratto "lista", si utilizza un puntatore a una struttura che contiene un campo di informazioni e un campo che è invece il puntatore alla struttura successiva. typedef struct Node { int data; struct Node *next; } node; typedef node* list;

Oss: mentre gli "array" sono "tipi di dato" ad accesso casuale, cioè è possibile accedere in maniera diretta a ogni singolo elemento(con [ ]); una lista è un "tipo di dato" ad accesso sequenziale, cioè bisogna scorrere necessariamente tutti gli elementi che precedono l’elemento d’interesse prima di potervi accedere. Inoltre una lista semplice è sempre identificata con il puntatore al primo nodo e termina sempre con un puntatore a NULL. Nota: in C++ la definizione precedente del tipo di dato astratto "lista" si può ri-scrivere anche come: struct node { int data; node *next; }; typedef node* list;


Pagina 2 di 19

ESERCIZIO 1 Questi esercizi presentano (in gran parte) esempi d'uso delle liste dinamiche già presentati a lezione. In quanto segue non è utilizzato il passaggio parametri per reference. Come esercizio supplementare è possibile provare a ri-scrivere i sottoprogrammi seguenti applicando tale modalità di passaggio parametri, laddove lo si ritenga utile. Scrivere i sottoprogrammi di manipolazione delle liste concatenate semplici (di interi), indicate di seguito, utilizzando un procedimento ricorsivo e uno iterativo per ognuna di esse:

- Creazione di un nuovo nodo: nodo *createNode(int d);

- Inserimento in testa di un nuovo nodo con prototipo seguente: list insertHead(list h, node *el);

- Inserimento in coda di un nuovo nodo con prototipo seguente: list insertTail(list h, node *el);

- Stampa di una lista : void printList(list h);

- Calcolo della lunghezza di una lista: int lenLista(list h);

- Ricerca elemento in una lista: list searchList(list h, int x);

- Copia di una lista: list copyList(list h);

- Concatenazione di due liste: void appendLista(list& h1, lista& h2);

- Inserimento in una lista ordinata: list insertSorted(list h, int x);

- Cancellazione di una lista: void wipeList(list& h);

- Cancellazione 1ma occorrenza di un elemento da una lista: void deleteList(list& h, int x);

- Cancellazione di tutte le occorrenze di un elemento in lista: void deleteListAll(list& h, int x);


Pagina 3 di 19

#include <iostream.h> #define N 5 int main () { list head = NULL; // supponiamo di creare una lista con N numeri interi int i, numero; node *t; for (i = 0; i < 5; ++i) { cout << “\n Inserisci numero: “; cin >> numero; t = createNode(numero); head = insertTail(head, t); } cout << “\n I numeri inseriti sono: \n”; printList(head); // copio la lista node *headListaCopiata = NULL; headListaCopiata = copyList(head); cout << “\n I numeri della lista copiata sono: \n”; printList(headListaCopiata); // concateno la seconda lista alla prima appendList(head, headListCopia); cout << “\n I numeri nella lista dopo la concatenazione, sono: \n”; printList(head); // dealloco tutti i nodi creati wipeList(head); return 0; }


Pagina 4 di 19

// Definizione dei sottoprogrammi:

node *createNode(int d) { node *p; p = new node; /* Creazione nuovo nodo */ p->data = d; p->next = NULL; return p; } list insertHead(list h, node *el) { if (h == NULL) return el; if (el == NULL) return h; el->next = h; return el; } list insertTail(list h, node *el) { node *aux; if (h == NULL) return el; if (el == NULL) return h; aux = h; while (aux->next != NULL) aux = aux->next; aux->next = el; return h; } void printList(list h) { /* stampa ricorsiva */ if (h!=NULL) { cout << " -> " << h->data; printList(h->next); } }


Pagina 5 di 19

int lenList(list h) { if (h == NULL) return 0; else return( 1 + lenList(h->next)); } list searchList(list h, int x) { /* ricerca ricorsiva, ritorna il puntatore al nodo che */ /* contiene la prima occorrenza di x. */ if (h == NULL) return NULL; if ( h->data == x ) return h; /* caso base */ else return searchList(h->next, x); } list copyList(list h) { list ch = NULL, aux; while (h != NULL) { aux = (node*) new node; aux->data = ch->data; aux->next = NULL; ch = insertTail(ch, aux); h = h->next; } return ch; } void appendList(list& h1, list& h2) { // restituisce h1 = h1 concatenato h2 if ( h1 == NULL ) h1 = h2 ; // caso base else if ( h1->next == NULL ) // caso base h1->next = h2; else appendList(h1->next,h2); }


Pagina 6 di 19

list insertSorted(list h, int x) { node *prev = NULL, *curr = h; if (curr == NULL) { // se nella lista non ci sono nodi curr = createNode(x); return curr; } while ( curr != NULL && curr->data < x ) { prev = curr; curr = curr->next; } if (prev == NULL) { prev = createNode(x); prev->next = curr; return prev; } else { prev->next = createNode(x); prev->next->next = curr; return h; } } void wipeList(list& h) { node *aux; if ( h != NULL ) { aux = h->next; /* salva punt. al nodo successivo */ delete h; /* cancella il primo elemento */ h = NULL; wipeLista(aux); /* cancella il resto della lista */ } }


Pagina 7 di 19

void deleteList(list& h, int x) { // soluzione ricorsiva // per esercizio scriverne una versione iterativa node *aux; if ( h == NULL ) return; if ( h->data == x ) { aux = h; h = h->next; delete aux; return ; } deleteLista(h->next,x); } void deleteListAll(list& h, int x) { // soluzione ricorsiva // per esercizio scriverne una versione iterativa node *aux; if ( h == NULL ) return; if ( h->data == x ) { aux = h; h = h->next; delete aux; deleteListAll(h,x); } else deleteListAll(h->next,x); }


Pagina 8 di 19

ESERCIZIO 2 Scrivere una funzione in linguaggio C che elimini tutti i nodi di posto pari in una lista semplicemente concatenata di interi. Es: 1 5 7 9 3 diventa 1 7 3 #include <iostream> #include <cstdlib> struct node { int data; node *next; }; typedef node* list; list DeleteEven(list h); int main( ) { int info; list h = NULL;/* Dichiarazione e inizializzazione lista */ /* (lista vuota) */ ... h = DeleteEven(h); ... return 0; } list DeleteEven(list h) { node *curr, *prev; int count; if (h == NULL || h->next == NULL) return h; prev = h; curr = h->next; count = 2; while (curr != NULL) { if (count % 2 == 0) { prev->next = curr->next; delete curr; curr = prev->next; } else { prev = curr; curr = curr->next; } count++; } // end while return h; } // end DeleteEven


Pagina 9 di 19

ESERCIZIO 3 Scrivere una funzione in linguaggio C che elimini tutti i nodi di posto dispari in una lista semplicemente concatenata di interi. Es: 1 5 7 9 3 diventa 5 9 #include <iostream> #include <cstdlib> struct node { int data; node *next; }; typedef node* list; list DeleteOdd(list h); int main( ) { int info; list h = NULL;/* Dichiarazione e inizializzazione lista */ /* (lista vuota) */ ... return 0; } list DeleteOdd(list h) { node *aux, *curr, *prev; int count; if (h == NULL) return h; aux = h; h = h->next; delete aux; prev = NULL; curr = h; count = 2; while (curr != NULL) { if (count % 2 == 1) { prev->next = curr->next; delete curr; curr = prev->next; } else { prev = curr; curr = curr->next; } count++; } // end while return h; } // end DeleteOdd


Pagina 10 di 19

ESERCIZIO 4 (TE Appello del 10 Luglio 2009) Si consideri un programma che gestisce gli orari dei treni di un servizio ferroviario. In particolare, si definisca una lista dinamica che rappresenta le singole fermate di ciascun treno: ogni nodo della lista descrive un numero di treno, il numero progressivo della fermata (la stazione di partenza corrisponde alla fermata numero 1), il nome della stazione, l’ora e i minuti (si usino due campi separati di tipo intero). Nella stessa lista possiamo perciò trovare le fermate di treni diversi. Dopo aver definito la struttura dati, si scriva in C/C++ la funzione TreniAlternativi, che riceve come parametro la lista delle fermate, e un numero di treno; la funzione restituisce il numero dei treni che collegano i due capolinea del treno fornito come parametro (se il treno indicato come parametro parte dalla stazione A e arriva alla stazione B, vogliamo sapere quanti sono i treni che collegano A con B, anche se A e B non sono capolinea). La funzione restituisce -1 se il treno indicato come parametro non esiste.


Pagina 11 di 19

#include <cstring> #define STRLEN 30 struct Nodo { int numTreno; int numFermata; char nomeStazione[STRLEN+1]; int hh; int mm; Nodo *next; }; int TreniAlternativi(Nodo* F, int numT) { Nodo* Fi, Fj; char stazioneA[STRLEN+1] ={'\0'};//nome del Capolinea A del treno numT char stazioneB[STRLEN+1] ={'\0'};//nome del Capolinea B del treno numT int contaFermate; // per trovare l’ultima stazione del treno numT int contTreni; contaFermate = 1; Fi = F; while (Fi != NULL) { if (Fi->numTreno == numT) { if (Fi->numFermata == 1) { strcpy(stazioneA,Fi->nomeStazione);} else if (Fi->numFermata > contaFermate) { contaFermate = Fi->numFermata; strcpy(stazioneB,Fi->nomeStazione); } } Fi = Fi->next; } if (strlen(stazioneA) == 0) return -1; contTreni = 0; // N.B. la lista non è ordinata in nessun modo for (Fi = F; Fi != NULL; Fi = Fi->next) { if (strcmp(stazioneA, Fi->nomeStazione) == 0) { for (Fj = F; Fj != NULL; Fj = Fj->next) { if ( Fi->numTreno == Fj->numTreno && strcmp(stazioneB, Fj->nomeStazione) == 0 && Fj->numFermata >= Fi->numFermata ) { /* NOTA: >=, per includere il caso limite in cui stazioneA coincide con stazioneB */ contTreni++; } // end if } // end for Fj } // end if } // end for Fi return contTreni; } // end TreniAlternativi


Pagina 12 di 19

ESERCIZIO 5 - Algoritmica di base e memoria dinamica La funzione …toro(…) riceve come parametro un vettore di interi e la specifica della sua dimensione, e alloca e restituisce una lista dinamica "circolare" di interi che contiene solo i valori del vettore positivi e divisibili per 11. Ovviamente la lista può essere circolare solo se non è vuota, quindi si suggerisce di renderla circolare solo alla fine dell'analisi del vettore [N.B. una lista è circolare se l'ultimo elemento invece di avere un puntatore a NULL ha un puntatore alla testa]. (a) Si definiscano la struttura della lista e il prototipo della funzione toro. struct Nodo { int numero; Nodo *next; }; typedef Nodo* ListaC; ListaC toro( int v[], int len ); (b) Si codifichi la funzione (unitamente alle eventuali funzioni di supporto).

ListaC toro( int v[], int len ) { int i = 0; ListaC ptr, testa ; testa = ptr = NULL; while (i < len) { if (v[i] > 0 && v[i] % 11 == 0) { if (testa == NULL) { testa = creaNodo(v[i]); ptr = testa; } else { ptr->next = creaNodo(v[i]); ptr = ptr->next; } } ptr->next = testa; return testa; } Nodo* creaNodo(int a) { ListaC ptr = (Nodo*) new Nodo; ptr->numero = a; ptr->next = NULL; } (c) Si disegni, la lista ottenuta con la funzione passando come parametro il vettore

[111, 0, 11, -8, 73, -29, 121, 49, 16, 33, -110, 101, 44, 21]


Pagina 13 di 19

ESERCIZIO 6 - Sintesi di codice – Liste e Vettori

struct Nodo { char c; Nodo * next; }; typedef Nodo * Lista;

Si considerino una lista L di almeno N nodi e un vettore v di esattamente N puntatori a Nodo, tutti diversi da NULL e diversi tra loro, che puntano a un sottoinsieme dei nodi di L. Diciamo che L è compatibile con v se i nodi puntati da v compaiono in L in un ordine compatibile con l'ordine in cui i puntatori sono contenuti in v (cioè non succede mai che un nodo n1 puntato dal puntatore v[i] preceda in L il nodo n2 puntato dal puntatore v[j] che però si trovi "più avanti" in v).

a) Si codifichi la funzione …compatibili(…) che controlla che una lista e un vettore

siano compatibili secondo la precedente definizione. La soluzione più semplice si ha notando che la lista che inizia da ogni elemento v[i] deve avere più nodi di ogni lista che inizia da ogni elemento v[j] con j>i. Si noti che a rigore non è necessario passare L alla funzione. int contanodi( Lista x ) { if( x == NULL ) return 0; return 1 + contanodi( x->next ); } int compatibili( Lista v[] ) {

int i = 0; for ( i=1; i<N; i++ ) if ( contanodi(v[i-1]) < contanodi(v[i]) ) return 0; return 1;

}


Pagina 14 di 19

Esiste anche una soluzione di complessità lineare (la precedente è quadratica) che scandisce la lista e il vettore, sempre "in avanti" – se termina prima il vettore sono compatibili, se termina prima la lista, no: int compatibili( Lista v[], Lista L ) {

int i = 0; while( L != NULL && i<N ) {

if( L == v[i] ) i++; L = L->next;

} return i == N;

}

b) Si codifichi la funzione …vprintf(…) che stampa su stdout la parola ottenuta seguendo nell'ordine i puntatori di v e accedendo ai caratteri contenuti nella lista, se L e v sono compatibili, e nulla se sono incompatibili (stamperebbe "ciao" nel caso dell'esempio soprastante).

void vprintf( Lista v[] ) { int i; if ( compatibili(v) ) for ( i=0; i<N; i++ ) cout << v[i]->c; }


Pagina 15 di 19

ESERCIZIO 7 - Memoria Dinamica e strutture dati Si consideri la seguente definizione: struct Nodo { char * parola;

Nodo * next; }; typedef Nodo * Lista;

(a) Si disegni la struttura allocata dalle istruzioni del blocco di codice a lato, si indichino i valori di ogni variabile (sia statica sia dinamica: per i puntatori si usino le frecce, per i valori ignoti i punti interrogativi), e se ne calcoli la dimensione totale in byte. MMMMMMMMM sizeof(char) = 1, sizeof(void *) = 4)

Dimensione: 2 puntatori, 3 array da 8 char, 3 nodi formati da 2 puntatori = 8 ptr + 24 char = 56 byte

? ? ? ? ? ? ? ?

s

p

n

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

= 1 byte

Nodo n, *p; char * s; s = (char *) new char[strlen("fischio")+1]; p = (Lista) new Nodo; n.next = (Lista) new Nodo; p->parola =(char*) new char[strlen("maschio")+1]; n.next->next = NULL; n.parola = s; p->next = n.next; s = (char *) new char[strlen("rischio")+1]; p->next->parola = s;


Pagina 16 di 19

(b) Due parole si dicono simili se hanno al più due caratteri diversi. Una catena di parole si dice

compatibile col telefono senza fili (cctsf) se ogni parola è simile alle adiacenti.

La funzione int simili (char *s1, char *s2); restituisce 1 se s1 e s2 sono simili, 0 altrimenti. Usando la funzione simili(…) (senza codificarla), si codifichi una funzione f(…), opzionalmente anche ricorsiva, che riceve come parametro una lista dinamica di parole (secondo la definizione soprastante) e restituisce 1 se la lista rappresenta una catena cctsf, 0 altrimenti. int f( Lista a ) { /* Versione ricorsiva */ if ( a == NULL || a->next == NULL ) return 1; if ( !simili(a->parola, a->next->parola) ) return 0; else return f( a->next ); } int f( Lista a ) { /* Versione iterativa */ while ( a != NULL && a->next != NULL ) { if ( !simili(a->parola, a->next->parola) ) return 0; a = a->next; } return 1; }

(c) Si codifichi la funzione int simili (char *s1, char *s2 ); int simili (char *s1, char *s2) { int i; int cont = strlen(s1) - strlen(s2); if (cont > 2 || cont < -2) return 0; cont = i = 0; while (i < strlen(s1) && i < strlen(s2)) { cont += (s1[i] != s2[i]); i++; } // end while return cont < 3; }


Pagina 17 di 19

(d) Si consideri poi la definizione di una lista di catene di parole (da ogni NodoTesta inizia una Lista).

struct NodoTesta { Lista catena; NodoTesta * next; }; typedef NodoTesta *ListaDiListe;

Si codifichi una funzione che riceve una lista di liste così definita e dealloca interamente dalla lista di liste le sequenze di parole che non sono cctsf. Attenzione: si ipotizzi che nelle catene non ci siano parole allocate staticamente, e si badi a deallocare tutta la memoria dinamica. void deallocaCatena( Lista a ) { if ( a != NULL ) { deallocaCatena( a->next ); delete [] a->parola;/* deallocazione del vettore dinamico */ delete a ; } } ListaDiListe sfrondaListaDiListe( ListaDiListe b ) { if ( b != NULL ) { ListaDiListe tmp = sfrondaListaDiListe( b->next ); if ( !f( b->catena ) ) { deallocaCatena( b->catena ); delete b ; return tmp; } else b->next = tmp; } return b; }


Pagina 18 di 19

ESERCIZIO 8 - Liste e matrici Si consideri la definizione struct Nodo { int numero; Nodo* next; }; typedef Nodo * Lista; Si codifichi la funzione …spargidivisori(…), che riceve come parametri una lista di interi, una matrice NxN di interi, tutti strettamente positivi (come matrice dinamica), e la lunghezza N. La funzione deve cercare di copiare ogni valore v della lista nella matrice, inserendolo al posto di un valore che sia multiplo di v. Se ci riesce, restituisce 1, e la matrice deve contenere tutti i valori modificati, se non ci riesce, però, oltre a restituire 0, deve lasciare inalterata la matrice. Attenzione: i valori v devono sempre essere confrontati con la versione iniziale della matrice, non con le "versioni intermedie" derivanti dalla sostituzione di alcuni valori, se ci sono più multipli di v, se ne può sostituire uno a piacere (il primo che si incontra), si badi a definire chiaramente e/o dichiarare eventuali opportune strutture dati di appoggio o funzioni ausiliarie.


Pagina 19 di 19

int spargidivisori(Lista L, int** mat, int N) { int auxmat = (int**) new (int*)[N]; for (i=0; i<N; i++) { auxmat[i] = (int*) new int[N]; for (j=0; j<N; j++) auxmat[i][j] = 0; }

int i, j, flag; int contL = 0, contFlag = 0; while (L != NULL) { contL++; flag = 0; for (i=0;i<N && !flag; i++) for (j=0;j<N && !flag; j++) if (L->numero % mat[i][j] == 0) { flag = 1; auxmat[i][j] = L->numero; contFlag++;

} L = L->next; } if (contL != contFlag) flag = 0; else { flag = 1; for (i=0; i<N; i++) for (j=0; j<N; j++) if (auxmat[i][j] != 0) mat[i][j] = auxmat[i][j]; } for (i=0; i<N; i++) delete[] auxmat[i]; delete[] auxmat; return flag; } }

Università degli Studi di Bergamo Esercitazioni di ... · a.a. 2018-2019 Codice corso: 21012 ....

Documents

Transcript of Università degli Studi di Bergamo Esercitazioni di ... · a.a. 2018-2019 Codice corso: 21012 ....