Tutorato di Programmazione A.A. 2016-2017

Liste

Antonino Furnari http://www.dmi.unict.it/~furnari/ - furnari@dmi.unict.it

Convenzioni

Lo scopo di questa esercitazione è guidare il lettore attraverso la comprensione di concetti chiave e la loro implementazione pratica. Per facilitare la comprensione degli argomenti proposti, durante l'esercitazione, viene richiesto al lettore di rispondere ad alcune domande e risolvere alcuni esercizi pratici. Tali richieste sono indicate dai seguenti simboli:

Questo simbolo è presente laddove viene richiesto al lettore di rispondere a una domanda.
Questo simbolo è presente laddove viene richiesto di inserire la risposta a una domanda.
Questo simbolo è presente laddove viene richiesto a lettore di svolgere un esercizio. Per ogni esercizio sviluppato, creare un nuovo file sorgente `cpp`. Nel caso in cui un esercizio ne estenda uno precedente, si parta dal codice dell'esercizio precedente e lo si modifichi come necessario.

1 Liste concatenate (linked lists)

In programmazione, si rende spesso necessario gestire collezioni sequenziali (ovvero, gli elementi vengono memorizzati in un ordine preciso) e omogenee (ovvero, gli elementi memorizzati sono dello stesso tipo) di dati. Il modo più semplice per organizzare queste collezioni, consiste nel creare un array.

Il principale limite degli array, tuttavia, è che essi sono strutture dati statiche, ovvero, non è possibile cambiare la dimensione di un array durante l'esecuzione del programma. Inoltre, alcune operazioni quali la rimozione e l'inserimento di un elemento da una posizione arbitraria dell'array risultano di difficile e poco efficiente implementazione.

Domanda 1.1

Si consideri l'array di interi definito come segue:

int array[100];
int count=1;
for (int i=0; i<100; i++) {
    array[i]=count;
    count+=2;
}
  • Qual è il contenuto dell'array?
  • Si supponga di voler inserire altri 100 elementi nell'array (in coda). Come si dovrebbe procedere?
  • Si supponga di voler inserire il numero 112 nella diciottesima posizione, spostando in avanti di una posizione tutti i valori consecutivi. Come si dovrebbe procedere?

Risposta 1.1






1.1 Definizione di lista concatenata (linked list)

Una lista concatenata è una collezione di elementi accessibili sequenzialmente. Ogni elemento contiene dei dati (ad esempio degli interi o delle stringhe) e un collegamento all'elemento successivo della lista. Tale collegamento è spesso chiamato next (o succ). Il primo elemento della lista è il suo punto di accesso ed è generalmente denominato head (o testa) della lista. L'ultimo elemento della lista è generalmente denominato tail (o coda) della lista. Il collegamento next dell'elemento tail non punta a nulla.

Domanda 1.2 Si consideri la sequente rappresentazione di una lista concatenata:

  1. Evidenziare nel diagramma tutti elementi della lista;
  2. Evidenziare nel diagramma tutti i collegamenti next;
  3. Evidenziare nel diagramma l'elemento head;
  4. Evidenziare nel diagramma l'elemento tail;

  5. Di che tipo sono i valori contenuti negli elementi della lista?
  6. Qual è la lunghezza della lista?

Risposta 1.2






Domanda 1.3

I componenti fondamentali di una lista concatenata sono elementi e collegamenti next. Come possono essere implementati tali componenti in C++?

Risposta 1.3






Domanda 1.4

Quali sono i vantaggi delle liste concatenate rispetto agli array e, viceversa, degli array rispetto alle liste? In particolare, quale delle due strutture dati è più oppurtuna nei seguenti scenari?

  1. Gestione di una collezione di $100$ interi;
  2. Gestione di una collezione di un numero indeterminato di interi;
  3. Accesso casuale ad elementi di una collezione;
  4. Inserimento di un nuovo elemento in una posizione intermedia della collezione;
  5. Gestione di una collezione di $n$ interi, dove $n$ è noto solo a run time.

Risposta 1.4






1.2 Implementazione funzioni di base

Vediamo adesso una semplice implementazione di una lista di interi mediante strutture. Iniziamo definendo la struct Element:

In [1]:
#include<iostream>
using namespace std;

struct Element {
    int value;
    struct Element* next;
}
Out[1]:

Domanda 1.5

Perché abbiamo implementato Element mediante una struct e non mediante un tipo primitivo?

Risposta 1.5






Definiamo dunque la struttura Lista:

In [2]:
struct List {
    struct Element* head;
}
Out[2]:

Domanda 1.6

Perché la struttura Lista contiene solo un puntatore a struct Element e non contiene un valore?

Risposta 1.6






Definiamo dunque una lista vuota:

In [3]:
struct List l; //dichiariamo la lista
l.head = 0; //la lista è vuota, quindi la sua testa "non punta a nulla"
Out[3]:
(struct Element *) nullptr

Domanda 1.7

Disegnare un diagramma della lista l in maniera simile a quanto visto nella Domanda 1.2.

Risposta 1.7






Inseriamo $5$ nella lista:

In [4]:
struct Element* el = new struct Element; //definiamo e inizializziamo un puntatore a Elemento
el->value = 5; //inseriamo 5 come valore del nuovo elemento
el->next = 0; //l'elemento sarà il primo e ultimo della lista, quindi non ha successivo

l.head = el; //impostiamo l'elemento come nuova testa della lista
Out[4]:
(struct Element *) 0x18f43a0

Domanda 1.8

Disegnare un diagramma della lista l in maniera simile a quanto visto nella Domanda 1.2.

Risposta 1.8






Inseriamo $16$ in testa:

In [5]:
struct Element* el2 = new struct Element;

el2->value = 16; //inseriamo 16 come valore dell'elemento
el2->next = l.head; //la vecchia testa della lista sarà il successivo del nuovo elemento

l.head = el2; //il nuovo elemento è la nuova testa della lista
Out[5]:
(struct Element *) 0x2cf02f0

Domanda 1.9

Disegnare un diagramma della lista l in maniera simile a quanto visto nella Domanda 1.2.

Risposta 1.9






Adesso inseriamo 23 in coda. Per effettuare questo inserimento, dobbiamo prima scorrere la lista fino a trovare il riferimento dell'ultimo nodo (coda) della lista. Per farlo, usiamo un ciclo while:

In [6]:
struct Element* elementoCorrente = l.head; //iniziamo a ispezionare la testa della lista
struct Element* elementoCoda; //dichiariamo un puntatore che conterrà l'elemento coda

while(elementoCorrente!=0) {//eseguiamo il ciclo finché non troviamo un null
    //alla prima iterazione elementoCorrente sarà il nodo testa
    
    elementoCoda = elementoCorrente; //salviamo il riferimento dell'elemento corrente
    elementoCorrente = elementoCorrente->next; //scorriamo la lista
}
Out[6]:

Alla fine del ciclo while:

  • elementoCorrente sarà pari a null;
  • elementoCoda conterrà il puntatore all'ultimo nodo non null (la coda della lista).
In [7]:
cout << elementoCorrente << endl; //null
cout << elementoCoda << endl; //indirizzo valido
cout << elementoCoda->next <<endl; //il successivo è null. Si tratta del nodo coda
cout << elementoCoda->value; //valore dell'ultimo nodo
0
0x18f43a0
0
5
Out[7]:
(std::basic_ostream<char, std::char_traits<char> >::__ostream_type &) @0x7fe4dc59c700

Creiamo dunque l'elemento e facciamo puntare il collegamento dell'elemento coda ad esso:

In [8]:
struct Element* el3 = new struct Element;

el3->value = 23; //valore del nuovo elemento
el3->next = 0; //stiamo inserendo l'elemento in coda, dunque il suo successivo è null

//inseriamo dunque l'elemento in coda come segue:
elementoCoda->next=el3;
Out[8]:
(struct Element *) 0x186a7b0

Domanda 1.10

Disegnare un diagramma della lista l in maniera simile a quanto visto nella Domanda 1.2.

Risposta 1.10






Stampiamo adesso tutti gli elementi della lista, nell'ordine in cui essi si trovano. Per scorrere tutta la lista, utilizzeremo un ciclo while:

In [9]:
elementoCorrente = l.head; //iniziamo a scorrere la lista dalla testa

while(elementoCorrente != 0) { //eseguiamo il ciclo finché l'elemento corrente non è null
    cout << elementoCorrente->value << " -> ";
    elementoCorrente = elementoCorrente->next; //scorriamo la lista
}

cout << "X"; //la coda punta a "X"
16 -> 5 -> 23 -> X
Out[9]:
(std::basic_ostream<char, std::char_traits<char> > &) @0x7fe4dc59c700

Eliminare l'elemento in testa è semplice. Basta far puntare la testa al suo successivo:

In [10]:
struct Element *tmp; //creo un puntatore di supporto
tmp = l.head; //conservo il riferimento del nodo da eliminare

l.head=l.head->next; //faccio puntare la testa al suo successivo

delete tmp; //elimino il nodo vecchio per liberare memoria
Out[10]:
(void) @0x7ffc4fc88900

Domanda 1.11

Disegnare un diagramma della lista l in maniera simile a quanto visto nella Domanda 1.2.

Risposta 1.11






L'eliminazione dell'elemento di coda è un po' più complessa: prima dobbiamo trovare il penultimo nodo, poi dobbiamo far puntare il successivo di questo a null. Inoltre, bisogna considerare due casi speciali:

  • testa è nulla (la lista è vuota);
  • la lista ha un solo elemento (in questo caso basta mettere testa a null).
In [11]:
elementoCorrente = l.head; //iniziamo dalla testa
struct Element* penultimoElemento = 0; //inizializziamo il penultimo elemento a null

if (elementoCorrente!=0) {//assicuriamoci che la testa non sia null
    //in tal caso la lista è vuota e non possiamo effettuare la rimozione
    
    if (elementoCorrente->next==0) {//se la lista contiene un solo elemento
        l.head=0; //la rimozione viene effettuata ponendo la testa a null
    } else {
        while(elementoCorrente->next->next!=0) { //finché elementoCorrente
            //non è il penultimo elemento, scorri la lista
            elementoCorrente=elementoCorrente->next;
        }
        //alla fine del while, elementoCorrente è il penultimo elemento
        //effettuiamo la rimozione in coda facendo puntare il suo successivo a null
        tmp = elementoCorrente->next;
        elementoCorrente->next=0;
        delete tmp;
    }
}
Out[11]:

Domanda 1.12

Disegnare un diagramma della lista l in maniera simile a quanto visto nella Domanda 1.2.

Risposta 1.12






Esercizio 1.1

Abbiamo visto come implementare le liste concatenate e alcune operazioni base mediante strutture. Per rendere queste operazioni più agevoli e facilmente ripetibili, implementare:

  1. la funzione creaLista che non prende nessun valore in input e restituisce una lista vuota sotto forma di struct Lista;
  2. la funzione void inserisciInTesta che prende in input una lista e un intero e inserisce un nuovo elemento contenente il valore specificato in testa alla lista;
  3. la funzione void inserisciInCoda che prende in input una lista e un intero e inserisce un nuovo elemento contenente il valore specificato in coda alla lista;
  4. la funzione void rimuoviInTesta che prende in input una lista e ne rimuove il primo elemento;
  5. la funzione void rimuoviInCoda che prende in input una lista e ne rimuove l'ultimo elemento;
  6. la funzione void stampaLista che prende in input una lista e ne stampa a schermo gli elementi (nell'ordine in cui essi si trovano);
  7. la funzione lunghezzaLista che prende in input una lista e ne restituisce il numero di elementi.

Effettuare dunque le seguenti operazioni:

  1. creare una lista vuota l;
  2. inserire 18 in coda;
  3. inserire 30 in testa;
  4. inserire 28 in testa;
  5. stampare a schermo il numero di elementi contenuti nella lista;
  6. stampare il contenuto della lista;
  7. inserire 15 in testa;
  8. rimuovere il valore in coda;
  9. rimuovere il valore in testa;
  10. stampare il contenuto della lista.

1.3 Implementazione di operazioni più complesse

Abbiamo visto come implementare le operazioni di base. Adesso vediamo come implementare operazioni più complesse. Iniziamo costruendo una semplice lista con alcuni valori:

In [12]:
struct List lista;

struct Element* elem1; //inserisci elemento 1
elem1 = new struct Element;
elem1->value=18;

lista.head=elem1;

struct Element* elem2; //inserisci elemento 2 in coda
elem2 = new struct Element;
elem2->value=27;
elem1->next=elem2;

struct Element* elem3; //inserisci elemento 3 in coda
elem3 = new struct Element;
elem3->value=14;
elem2->next=elem3;

struct Element* elem4; //inserisci elemento 4 in coda
elem4 = new struct Element;
elem4->value=32;
elem3->next=elem4;

struct Element* elem5; //inserisci elemento 5 in coda
elem5 = new struct Element;
elem5->value=29;
elem5->next=0; //ultimo elemento della lista
elem4->next=elem5;
Out[12]:
(struct Element *) 0x35d6f10

Domanda 1.13

Disegnare un diagramma della lista l in maniera simile a quanto visto nella Domanda 1.2.

Qual è il valore dell'elemento di indice 3?

Risposta 1.13






Adesso proviamo a leggere il valore contenuto nell'elemento di indice $3$. Per fare ciò dobbiamo scorrere la lista e tenere traccia del numero di elemento che stiamo analizzando:

In [13]:
struct Element* elcorr = lista.head; //iniziamo dalla testa

for (int i=0; elcorr!=0; i++, elcorr=elcorr->next) {
    if (i==3) {
        cout << elcorr->value;
    }
}
32
Out[13]:

Troviamo ora l'indice dell'elemento che contiene il valore $14$:

In [14]:
elcorr=lista.head;

for (int i=0; elcorr!=0; i++, elcorr=elcorr->next) {
    if (elcorr->value==14) {
        cout << i;
    }
}
2
Out[14]:

Esercizio 1.2

Definire:

  1. una funzione readValueAt che prende in input una lista e un intero i e restituisce il valore contenuto nell'elemento di indice i. Gestire i casi speciali. Es. cosa succede se la lista è vuota? Cosa succede se si cerca di leggere il valore di un nodo inesistente?
  2. una funzione indexAtValue che prende in input una lista e un intero val e restituisce l'indice del primo elemento della lista contenente il valore val. Gestire i casi speciali. Es cosa succede se il valore non esiste nella lista?

Rimozione di elementi

Vediamo come rimuovere elementi contenuti nelle posizioni interne di una lista. Supponiamo di voler rimuovere un elemento in posizione $i$. Per effettuare la rimozione dovremo:

  • Trovare l'elemento precedente e1;
  • Trovare l'elemento successivo e2;
  • Far puntare e1.succ a e2.

L'operazione può essere schematizzata come segue:

Supponiamo che $i=3$. In questo caso, l'elemento precedente e1 avrà indice 2, mentre il successivo e2 avrà indice 4. Dato che le liste non permettono accesso casuale ai dati, dovremo scorrere tutti gli elementi fino a trovare quelli interessati:

In [15]:
int ind_prec = 2;
int ind_succ = 4;

struct Element* elprec = 0; //inizializziamo due puntatori a elemento precedente e successivo
struct Element* elsucc = 0;

bool done = 0; //indica se la ricerca è finita
//inizialmente impostata a zero (false)

elcorr=lista.head;
for (int i=0; elcorr!=0 && !done; i++, elcorr=elcorr->next) {
    if(i==ind_prec) { //se l'indice è quello dell'elemento precedente
        elprec=elcorr; //salva il riferimento dell'elemento corrente
    } else if (i==ind_succ) { //se l'indice è quello dell'elemento successivo
        elsucc=elcorr; //salva il riferimento dell'elemento successivo
    }
    
    if (elprec!=0 && elsucc!=0) { //se ho trovato entrambi i riferimenti
        tmp = elprec->next;
        elprec->next=elsucc; //faccio puntare il successivo del precedente
        //al successivo dell'elemento da eliminare
        delete tmp;
        done=1; //serve a uscire prima dal for
    }
}
Out[15]:

Esercizio 1.3

Definire:

  1. una funzione void rimuoviPosizione che prende in input una lista e un intero i e rimuove dalla lista l'elemento contenuto alla posizione i. Gestire i casi speciali. Es cosa succede se l'elemento specificato non esiste?
  2. una funzione rimuoviValore che prende in input una lista e un intero val e rimuove dalla lista il primo elemento contenente il valore val. Gestire i casi speciali. Es cosa succede se il valore non esiste nella lista?

Inserimento di valori

Adesso supponiamo di voler inserire un elemento in una data posizione. Per effettuare l'inserimento dovremo:

  • trovare l'elemento $s1$ dopo il quale effettuare l'inserimento;
  • trovare l'elemento $s2$ prima del quale effettuare l'inserimento;
  • creare un nuovo elemento $s3$;
  • far puntare next di $s1$ a $s3$ e next di $s3$ a $s2$.

L'operazione può essere illustrata come segue:

In particolare, supponiamo di voler inserire l'elemento $8$ alla posizione $2$:

In [16]:
int idx_prec = 1; //indice dopo il quale effettuare l'inserimento
int idx_succ = 2; //indice al quale effettuare l'inserimento

struct Element* elprev = 0; //inizializziamo due puntatori a elemento precedente e successivo
struct Element* elnext = 0;

bool found = 0; //indica se la ricerca è finita
//inizialmente impostata a zero (false)

elcorr=lista.head;
for (int i=0; elcorr!=0 && !found; i++, elcorr=elcorr->next) {
    if(i==idx_prec) { //se l'indice è quello dell'elemento precedente
        elprev=elcorr; //salva il riferimento dell'elemento corrente
    } else if (i==idx_succ) { //se l'indice è quello dell'elemento successivo
        elnext=elcorr; //salva il riferimento dell'elemento successivo
    }
    
    if (elprev!=0 && elnext!=0) { //se ho trovato entrambi i riferimenti
        struct Element* newel = new Element; //nuovo elemento
        newel->value=8; //con valore 8
        
        //il nuovo elemento punta al successivo
        newel->next=elnext;
        //il precedente punta al nuovo elemento
        elprev->next=newel;
        
        found=1; //serve a uscire prima dal for
    }
}
Out[16]:

1.3 Implementazione a oggetti

Fino ad ora abbiamo visto come implementare una lista e le sue operazioni utilizzando strutture e funzioni. Questo tipo di implementazione è tuttavia poco naturale e scomoda da utilizzare. Vediamo dunque come implementare una lista concatenata a oggetti. Iniziamo dalla definizione di una classe Elemento:

class Element {
    private:
        int val; //valore dell'elemento
        Element* next; //puntatore all'elemento successivo

    public:
        //costruttore, prende in input un valore e, opzionalmente
        //un puntatore all'elemento successivo
        Element(int v, Element* n = 0): val(v), next(n) {}

        //getter e setter per valore
        int getValue() {return val;}
        void setValue(int v) {val = v;}

        //getter e setter per succ
        Element* getNext() {return next;}
        void setNext(Element* n) {next=n;}
};

Definiamo l'oggetto ListaConcatenata:

class LinkedList {
    private:
        Element* head; //elemento head
    public:
        //costruttore, prende in input, opzionalmente
        //un puntatore al primo nodo
        LinkedList(Element *h = 0) : head(h) {} 

        //getter e setter per head
        Element* getHead() {return head;}
        void setHead(Element *h) {head=h;}
};

Possiamo dunque creare liste come segue:

LinkedList l1 = LinkedList; //nuova lista vuota
LinkedList l2 = LinkedList(new Element(15)); //lista contenente un elemento: 15 -> X
LinkedList l3 = LinkedList(new Element(15,new Element(32))); //lista contenente due elementi: 15 -> 32 -> X

Esercizio 1.4

Inserire come nuovi metodi della classe LinkedList, le funzioni sviluppate per le struct negli esercizi precedenti. In particolare, sviluppare i metodi con le seguenti signatures:

int LinkedList::getLength() //ottieni la lunghezza (numero di elementi) della lista
int LinkedList::readHead() //ottieni il valore del primo elemento della lista
int LinkedList::readTail() //ottieni il valore dell'ultimo elemento della lista
int LinkedList::readAt(int i) //restituisce il valore contenuto nell'elemento di indice i
int LinkedList::getIndexOf(int val) //restituisce l'indice del primo elemento di valore pari a val
void LinkedList::print() //stampa a schermo gli elementi contenuti nella lista

Gestire tutti i casi limite, ad esempio, liste vuote, valori non esistenti, indici non esistenti. Testare il corretto funzionalmento della classe con il seguente codice:

LinkedList l = LinkedList;

cout << l.getLength() << endl; //0
cout << l.readHead() << endl; //errore
cout << l.readTail() << endl; //errore
cout << l.readAt(18) << endl; //errore
cout << l.getIndexOf(7) << endl; //errore
l.print() // X
LinkedList l2 = LinkedList(new Element(15, new Element(32, new Element(77)));

cout << l2.getLength() << endl; //3
cout << l2.readHead() << endl; //15
cout << l2.readTail() << endl; //77
cout << l2.readAt(1) << endl; //32
cout << l2.getIndexOf(77) << endl; //2
l2.print() // 15 -> 32 -> 77 -> X

Esercizio 1.5

Implementare in LinkedList i metodi di inserimento e rimozione di nodi:

void LinkedList::insertHead(int val) //inserisce in testa un elemento con valore val
void LinkedList::insertTail(int val) //inserisce in coda un elemento con valore val
void LinkedList::insertValueAt(int val, int i) //inserisce il valore val alla posizione i

void LinkedList::removeHead() //effettua rimozione in testa
void LinkedList::removeTail() //effettua rimozione in coda
void LinkedList::removeValue(int val) //rimuove il primo elemento con valore val
void LinkedList::removeValueAt(int i) //rimuove l'elemento di indice i

Gestire tutti i casi limite, ad esempio, liste vuote, valori o posizioni non esistenti. Testare il corretto funzionamento della classe con il seguente codice:

LinkedList l = LinkedList;

l.insertHead(22);
l.insertTail(19);
l.insertHead(28);
l.insertValueAt(77,1);
l.print(); //28 -> 77 -> 22 -> 19 -> X

l.removeHead();
l.print(); //77 -> 22 -> 19 -> X
l.removeValueAt(1);
l.print(); //77 -> 19 -> X
l.removeValue(19);
l.print(); //77 -> X

Esercizio 1.6

Si modifichi il costruttore di LinkedList in modo che esso accetti array di interi come input. La signature del metodo deve essere la seguente:

LinkedList::LinkedList(int array[]=0,int n=0)

dove n è il numero di elementi di array.

Se il parametro array viene passato al costruttore, la lista dovrà essere inizializzata con i valori contenuti dentro array. Ad esempio:

int array[] = {1,5,7,3};

LinkedList l = LinkedList(array,4);
l.print(); //1 -> 5 -> 7 -> 3 -> X

LinkedList l2 = LinkedList();
l2.print(); //X

Per una corretta gestione della memoria, è buona norma inserire un metodo distruttore che liberi la memoria occupata dai vari nodi della lista:

LinkedList::~LinkedList() {
    Element* aux = this->head;

    while(aux!=0) {
        Nodo* temp= aux->succ; 
        delete aux; 
        aux=temp; 
    }
}

Domanda 1.14

Abbiamo visto due implementazioni per le liste concatenate: mediante strutture e mediante oggetti. Quali delle due implementazioni permette di scrivere codice di più facile lettura? Quali sono i vantaggi di una implemntazione sull'altra?

Risposta 1.14






1.4 Implementazione a oggetti con template

Finora abbiamo costruito liste di interi. Il codice sviluppato in questo contesto non è durettamente utilizzabile nel caso in cui avessimo bisgno ad esempio di liste di double. Riadattare il codice per questo secondo utilizzo richiederebbe la ridefinizione della classe e di tutti i metodi (si pensi ai tipi di input e output), mentre gli algoritmi resterebbero immutati. Per rendere la definizione del codice indipendente dal tipo, possiamo implementare le liste utilizzando i template. In particolare, vedremo una implementazione a oggetti mediante template.

Iniziamo definendo nuovamente l'oggetto Element:

template <class T> class Element {
    private:
        T val;
        Element<T>* next;
    public:
        Element<T>(T v, Element<T>* n=0) : val(v), next(n) {}

        T getValue() {return val;}
        void setValue(T v) {val=v;}

        Element<T>* getNext() {return next;}
        void setNext(Element<T>* n) {next=n;}
};

L'oggetto Element può adesso essere utilizzato con diversi tipi di dato:

Element<int> e1 = Element<int>(15);
cout << e1.getValue() << endl; //15

Element<double> e2 = Element<double>(3.14);
cout << e2.getValue() << endl; //3.14

Esercizio 1.7

Si riscriva la classe LinkedList utilizzando i template. Si verifichi il corretto funzionamento della classe mediante il seguente codice:

double array[] = {1.2, 3.4, 0.33, 5.5};

LinkedList<double> l = LinkedList<double>(array,4);
l.print(); //1.2 -> 3.4 -> 0.33 -> 5.5 -> X

l.removeHead();
l.print(); //3.4 -> 0.33 -> 5.5 -> X

l.inserValueAt(0.01,2);
l.print(); //3.4 -> 0.33 -> 0.01 -> 5.5 -> X

l.removeValue(0.33);
l.print(); //3.4 -> 0.01 -> 5.5 -> X

Esercizio 1.8

Inserire un nuovo metodo substitute all'interno della classe LinkedList. Il metodo deve prendere in input due valori v1 e v2, cercare il primo elemento della lista contenente v1 e sostituire tale valore con v2. Esempio:

float arr[] = {1.2,2.3,4.5};

LikedList<float> l =LinkedList<float>(arr,3);
l.substitute(2.3,0);
l.print(); //1.2 -> 0 -> 4.5

Esercizio 1.9 Si implementi una lista concatenata ordinata, ovvero una lista in cui tutte le operazioni di inserimento vengono effettuate in maniera ordinata. Si consideri la seguente definizione:

struct Element {
    int value;
    struct Element* next;
}

class SortedList {
    private:
        struct Element* head;
    public:
        void print(); //stampa gli elementi contenuti nella lista
        void insert(int); //inserisce un elemento in maniera ordinata
        void remove(int);  //rimuove un determinato valore
}

Si proceda con l'implementazione.

2 Liste doppiamente concatenate (doubly linked list)

Le liste concatenate semplici viste finora rendono alcune operazioni particolarmente complicate. Si pensi ad esempio alla semplice operazione di stampare gli elementi di una lista in ordine inverso. Per effettuare questa operazione si dovrebbe accedere in sequenza all'ultimo, penultimo, terzultimo, ecc.. nodo scorrendo la lista più volte.

Abbiamo inoltre visto che molte operazioni sulle liste concatenate richiedono di memorizzare un puntatore al penultimo elemento visitato (si pensi all'eliminazione o inserimento di un elemento in una posizione interna della lista). Da questa constatazione nasce l'idea di costruire delle liste doppiamente concatenate. Queste liste sono simili alle liste concatenate semplici, ma ogni elemento contiene due collegamenti: un collegamento all'elemento successivo (next) e un collegamento all'elemento precedente (prev).

Il collegamento prev del nodo head "non punterà a nulla" così come il collegamento next del nodo tail.

Domanda 2.1

Si consideri la rappresentazione di una lista doppiamente concatenata riportata di seguito:



Indicare:

  • collegamenti prev;
  • collegamenti next.

Risposta 2.1






Domanda 2.2

L'implementazione di una lista doppiamente concatenata richiede più memoria rispetto a quella di una lista concatenata semplice? Perché? In quali casi utilizzare una lista concatenata semplice è comunque più vantaggioso di utilizzare una lista doppiamente concatenata?

Risposta 2.2






La definizione della classe Element in questo caso è simile a quanto visto in precedenza:

template <class T> class Element {
    private:
        T val;
        Element<T>* prev;
        Element<T>* next;
    public:
        Element<T>(T v, Element<T>* p=0, Element<T>* n=0) : val(v), prev(n), next(n) {}

        T getValue() {return val;}
        void setValue(T v) {val=v;}

        Element<T>* getPrev() {return prev;}
        void setPrev(Element<T>* p) {prev=p;}

        Element<T>* getNext() {return next;}
        void setNext(Element<T>* n) {next=n;}
};

La dichiarazione di una lista doppiamente linkata è praticamente invariata:

template <class T> class DoublyLinkedList {
    private: 
        Element<T>* head;
    public: 
        DoublyLinkedList<T>(Element<T> *h=0) : head(h) {}
        ~DoublyLinkedList();

        T getLength(); //ottieni la lunghezza (numero di elementi) della lista
        T readHead(); //ottieni il valore del primo elemento della lista
        T readTail(); //ottieni il valore dell'ultimo elemento della lista
        T readAt(int i); //restituisce il valore contenuto nell'elemento di indice i
        T getIndexOf(T val); //restituisce l'indice del primo elemento di valore pari a val
        void print(); //stampa a schermo gli elementi contenuti nella lista

        void insertHead(T val); //inserisce in testa un elemento con valore val
        void insertTail(T val); //inserisce in coda un elemento con valore val
        void insertValueAt(T val, int i); //inserisce il valore val alla posizione i

        void removeHead(); //effettua rimozione in testa
        void removeTail(); //effettua rimozione in coda
        void removeValue(T val); //rimuove il primo elemento con valore val
        void removeValueAt(int i); //rimuove l'elemento di indice i
};

L'implementazione dei metodi invece cambia. In alcuni casi si complica un po', mentre in altri si semplifica notevolemente. Vediamo ad esempio l'implementazione del metodo insertHead:

DoublyLinkedList<T>::insertHead(T val) {
    //creiamo un nuovo elemento con valore val
    Element<T>* e = new Element<T>(val)
    e->setPrev(0); //pred punta a null (è il primo elemento della lista)
    e->setNext(this->head); //next punta alla vecchia head (sarà il secondo valore)

    //ora dobbiamo aggiornare il prev di head
    //che dovrà puntare al nuovo nodo (la nuova head)
    if (this->head!=0) { 
        //possiamo fare l'aggiornamento
        //solo se head non è null
        this->head->setPrev(e);
    } 

    //adesso aggiorniamo il valore di head:
    this->head = e;
}

L'implementazione di inserHead si è un po' complicata per via della necessità di tenere traccia di due collegamenti: pred e next. Vediamo cosa succede invece nel caso della rimozione di un elemento interno alla lista:

void DoublyLinkedList<T>::removeValueAt(int i) {
    //creiamo un puntatore ausiliario e inizializziamolo con head
    Element<T>* current = this->head;

    //scorri la lista fino alla fine
    //tenendo traccia dell'indice corrente
    for (int idx=0; current!=0; idx++) {
        if(idx==i) {//se siamo in presenza dell'indice corrente

            //teniamo traccia dell'elemento precedente
            //e di quello successivo al corrente (aux)
            Element<T> *prev = current->getPrev();
            Element<T> *next = current->getNext();

            //collega il successivo del nodo precedente
            //direttamente al nodo successivo (saltando quindi current)
            prev->setNext(next);

            //collega il precedente del nodo successivo a current
            //direttamente al nodo precedente (saltando current anche in questo caso)
            next->setPrev(prev);

            //salva vecchio riferimento a current
            Element<T>* tmp=current;

            //scorre lista
            current = current->getNext();

            //libera memoria
            delete tmp;
        }
    }
}

Domanda 2.3

L'implementazione della rimozione di un elemento interno alla lista si è semplificata o complicata? Perché?

Risposta 2.3






Esercizio 2.1

Implementare i seguenti metodi della classe DoublyLinkedList:

T getLength(); //ottieni la lunghezza (numero di elementi) della lista
T readHead(); //ottieni il valore del primo elemento della lista
T readTail(); //ottieni il valore dell'ultimo elemento della lista
T readAt(int i); //restituisce il valore contenuto nell'elemento di indice i
T getIndexOf(T val); //restituisce l'indice del primo elemento di valore pari a val
void print(); //stampa a schermo gli elementi contenuti nella lista

Gestire tutti i casi limite, ad esempio, liste vuote, valori non esistenti, indici non esistenti. Testare il corretto funzionalmento della classe con il seguente codice:

DoublyLinkedList<int> l = DoublyLinkedList<int>(new Element<int>(15, new Element<int>(32, new Element<int>(77)));

cout << l2.getLength() << endl; //3
cout << l2.readHead() << endl; //15
cout << l2.readTail() << endl; //77
cout << l2.readAt(1) << endl; //32
cout << l2.getIndexOf(77) << endl; //2
l2.print() // 15 -> 32 -> 77 -> X

Esercizio 2.2

Implementare in DoublyLinkedList i seguenti metodi:

void insertHead(T val); //inserisce in testa un elemento con valore val
void insertTail(T val); //inserisce in coda un elemento con valore val
void insertValueAt(T val, int i); //inserisce il valore val alla posizione i

void removeHead(); //effettua rimozione in testa
void removeTail(); //effettua rimozione in coda
void removeValue(T val); //rimuove il primo elemento con valore val
void removeValueAt(int i); //rimuove l'elemento di indice i

Gestire tutti i casi limite, ad esempio, liste vuote, valori o posizioni non esistenti. Testare il corretto funzionamento della classe con il seguente codice:

DoubleLinkedList<int> l = LinkedList<int>;

l.insertHead(22);
l.insertTail(19);
l.insertHead(28);
l.insertValueAt(77,1);
l.print(); //28 -> 77 -> 22 -> 19 -> X

l.removeHead();
l.print(); //77 -> 22 -> 19 -> X
l.removeValueAt(1);
l.print(); //77 -> 19 -> X
l.removeValue(19);
l.print(); //77 -> X

Esercizio 2.3

Implementare in DoublyLinkedList il metodo:

void DoublyLinkedList::printReverse();

Il metodo deve stampare a schermo i valori di tutti gli elementi della lista in ordine inverso (ovvero, cominciando dalla coda). Questa implementazione è più o meno semplice rispetto a quella necessaria nel caso di una lista concatenata semplice?

Esercizio 2.4

Si implementi nuovamente la classe dell'Esercizio 1.9 utilizzando stavolta le liste doppiamente concatenate.

3 Liste circolari

Una ulteriore variante delle liste concatenate è quella delle liste concatenate circolari. Queste sono definite allo stesso modo delle liste concatenate con la differenza il nodo tail punta al nodo head invece di puntare a null. Di seguito una rappresentazione grafica di lista concatenata circolare.

Queste liste sono utili nei casi in cui i dati considerati sono inerentemente circolari. Alcuni esempi in cui è naturale utilizzare liste circolari sono i seguenti:

  • Scheduling di processi in un sistema operativo. Il sistema deve concedere l'uso della cpu ad ogni processo per un determinato tempo. I processi sono inseriti in una lista circolare. In questo modo, dopo lo scheduling dell'ultimo processo (tail della coda), tocca nuovamente al primo (head);
  • Gestione di un gioco multigiocatore. Il sistema deve permettere di giocare a un giocatore alla volta. Una volta che l'ultimo giocatore (tail della coda) ha terminato il proprio turno, tocca nuovamente al primo (head);

Domanda 3.1

Una lista concatenata circolare occupa più spazio di una normale lista concatenata? Perché?

Risposta 3.1






Domanda 3.2

Nella definizione di una lista concatenata circolare, l'implementazione di alcuni metodi cambia. Quali? Si considerino in particolare i seguenti metodi:

T getLength(); 
T readHead(); 
T readTail(); 
T readAt(int i); 
T getIndexOf(T val); 
void print(); 

void insertHead(T val); 
void insertTail(T val); 
void insertValueAt(T val, int i); 

void removeHead(); 
void removeTail(); 
void removeValue(T val); 
void removeValueAt(int i);

Risposta 3.2






Vediamo come cambia l'implementazione del metodo insertHead nel caso di una lista circolare:

CircularLinkedList<T>::insertHead(T val) {
    //creiamo un nuovo elemento con valore val
    Element<T>* e = new Element<T>(val)
    e->setNext(this->head); //next punta alla vecchia head (sarà il secondo valore)

    //adesso aggiorniamo il valore di head:
    Element<T>* oldHead=this->head; //salviamo il riferimento alla vecchia head
    this->head = e;

    //non abbiamo finito...dobbiamo aggiornare il next dell'elemento tail!
    Element<T>* aux = this->head; //nodo ausiliario impostato inizialmente a head

    //scorriamo la lista finché non troviamo un
    //elemento che punta alla vecchia head.
    //Quello sarà l'ultimo elemento
    while(aux->get->next()!=oldHead) {
        aux=axu->getNext();
    }

    //aggiorniamo il next dell'elemento con la nuova head
    aux->setNext(this->head);
}

Esercizio 3.1

Implementare la classe CircularLinkedList (usare i template) che contenga i metodi:

T getLength(); 
T readHead(); 
T readTail(); 
T readAt(int i); 
T getIndexOf(T val); 
void print(); 

void insertHead(T val); 
void insertTail(T val); 
void insertValueAt(T val, int i); 

void removeHead(); 
void removeTail(); 
void removeValue(T val); 
void removeValueAt(int i);

Si riutilizzi il codice scritto negli esercizi precedenti.

Esercizio 3.2

Il vantaggio delle liste circolari è quello di permettere la scansione degli elementi in modo cicliclo e indeterminato. Si modifichi la classe CircularLinkedList come segue:

  • aggiungere un campo privato currentElement di tipo puntatore a Elemento<T>;
  • il campo currentElement deve essere inizializzato a null dal costruttore;


  • inserire un metodo T readNext() che agisca come segue:
    • se currentElement è null, restituisce il valore contenuto in head e imposta currentElement uguale all'elemento head;
    • altrimenti, restituisce il valore contenuto nel nodo puntato da currentElement e imposta currentElement uguale al proprio successivo;

Creare una lista circolare di interi contenenti i valori $1, 2, 6, 7$ e invocare il metodo readNext() $6$ volte. Quali sono i valori restituiti dalle invocazioni?

Domanda 3.3

Si consideri il metodo definito nell'esercizio 3.2. E' possibile implementarlo in una lista concatenata semplice? Se sì, come?

Risposta 3.3






3.1 Liste doppiamente concatenate circolari

E' possibile implementare anche le liste doppiamente concatenate mediante liste circolari. Le liste doppiamente concatenate circolari sono definite in maniera simile alle liste doppiamente concateante con la differenza che:

  • Il prev dell'elemento head punta all'elemento tail invece di puntare a null;
  • Il next dell'elemento tail punta all'elemento head invece di puntare a null.

Anche in questo caso, le liste doppiamente concatenate circoli sono particolarmente utili quando i dati sono inerentemente circolari. Inoltre, alcune operazioni (ad esempio inserimento di un elemento in coda) risultano semplificate.

Domanda 3.4

Una lista doppiamente concatenate circolare occupa più spazio in memoria rispetto ad una normale (non circolare) lista doppiamente concatenata? Perché?

Risposta 3.4






Vediamo l'implementazione del metodo insertTail:

CircularDoublyLinkedList<T>::insertTail(T val) {
    //ottenere l'elemento tail è molto semplice
    //basta guardare nel prev di head
    Element<T>* oldTail = this->head->getPrev();

    //definiamo un nuovo elemento coda
    Element<T> tail = new Element<T>(val);

    //inseriamo un nuovo elemento in coda
    //modificando il next dell'elemento tail
    oldTail->setNext(tail);

    //Aggiorniamo il prev di head:
    //deve puntare alla nuova coda
    head->setPrev(tail);
}

Domanda 3.5

Nella definizione di una lista doppiamente concatenata circolare, l'implementazione di alcuni metodi cambia. Quali? Si considerino in particolare i seguenti metodi:

T getLength(); 
T readHead(); 
T readTail(); 
T readAt(int i); 
T getIndexOf(T val); 
void print(); 

void insertHead(T val); 
void insertTail(T val); 
void insertValueAt(T val, int i); 

void removeHead(); 
void removeTail(); 
void removeValue(T val); 
void removeValueAt(int i);

Risposta 3.5






Esercizio 3.3

Implementare la classe CircularDoublyLinkedList (usare i template) che contenga i metodi:

T getLength(); 
T readHead(); 
T readTail(); 
T readAt(int i); 
T getIndexOf(T val); 
void print(); 

void insertHead(T val); 
void insertTail(T val); 
void insertValueAt(T val, int i); 

void removeHead(); 
void removeTail(); 
void removeValue(T val); 
void removeValueAt(int i);

Si riutilizzi il codice scritto negli esercizi precedenti.

Esercizio 3.4

Si consideri il metodo readNext implementato nell'Esercizio 3.2. Si implementi un analogo metodo readPrev all'interno della classe CircularDoublyLinkedList. Il metodo deve permettere di accedere ai valori degli elementi della lista in maniera sequenziale e inversa, ovvero, iniziando dall'elemento tail e procedendo verso l'elemento head.