Post on 29-Nov-2018
transcript
Politecnico di Milano - Prof. Sara Comai 1
LEZIONE 12: Liste
• Modulo 1: ADT lista e implementazione basata su array
• Modulo 2: Lista concatenata
Informatica 3
Politecnico di Milano - Prof. Sara Comai 2
Lezione 12 - Modulo 1
ADT lista e implementazione basata su array
Informatica 3
Politecnico di Milano - Prof. Sara Comai 3
Introduzione
• Scopo: confrontare implementazioni diverse
• Definizione di lista – Sequenza ordinata e finita di dati o elementi
• ogni elemento della lista è caratterizzato da una posizione
– Notazione: <a0, a1, …, an-1>
posizione
Politecnico di Milano - Prof. Sara Comai 4
Posizione corrente
• Considereremo liste caratterizzate dal concetto di posizione corrente– La posizione corrente definisce la partizione sinistra e
la partizione destra di una lista – La posizione corrente funziona da separatore e la
indicheremo con il simbolo |
– Esempio: <20, 23 | 12, 15>
posizione corrente
partizionesinistra
partizionedestra
Politecnico di Milano - Prof. Sara Comai 5
ADT lista
template <class Elem> class List {public:virtual void clear() = 0;virtual bool insert(const Elem&) = 0;virtual bool append(const Elem&) = 0;virtual bool remove(Elem&) = 0;virtual void setStart() = 0;virtual void setEnd() = 0;virtual void prev() = 0;virtual void next() = 0;virtual int leftLength() const = 0;virtual int rightLength() const = 0;virtual bool setPos(int pos) = 0;virtual bool getValue(Elem&) const = 0;virtual void print() const = 0;
};
Politecnico di Milano - Prof. Sara Comai 6
Esempio
Lista: <12 | 32, 15>lista.insert(99);
Lista risultante: <12 | 99, 32, 15>
Esempio di uso di funzioni per iterare sulla lista:
for (lista.setStart(); lista.getValue(elemento);lista.next()){
// operazioni su elemento...
}
Politecnico di Milano - Prof. Sara Comai 7
Implementazione della lista
• Due approcci standard: – Lista basata su array
– Lista concatenata con puntatori
Politecnico di Milano - Prof. Sara Comai 8
Implementazione lista basata su arrayOperazione di inserimento:• in testa
• in codaInserisci 25
25
Inserisci 23
Politecnico di Milano - Prof. Sara Comai 9
Implementazione lista basata su arrayOperazione di cancellazione:
– Es. Cancella 12
posizione corrente
Politecnico di Milano - Prof. Sara Comai 10
Classe lista basata su array (1)
template <class Elem> // Array-based listclass AList : public List<Elem> {
private:int maxSize; // Maximum size of listint listSize; // Actual elem countint fence; // Current position (fence)Elem* listArray; // Array holding list
public:AList(int size=DefaultListSize) { //Constructor
maxSize = size;listSize = fence = 0;listArray = new Elem[maxSize];
} operazione costosa
> Θ(1)
Politecnico di Milano - Prof. Sara Comai 11
Classe lista basata su array (2)
...
void prev() { if (fence != 0) fence--; }
bool setPos(int pos) {if ((pos >= 0) && (pos <= listSize))
fence = pos;return (pos >= 0) && (pos <= listSize);
}
Θ(1)
Θ(1)
Politecnico di Milano - Prof. Sara Comai 12
Inserimento in testa
// Insert at front of right partitiontemplate <class Elem>bool AList<Elem>::insert(const Elem& item) {
if (listSize == maxSize) return false;
for(int i=listSize; i>fence; i--){// Shift Elems up to make roomlistArray[i] = listArray[i-1];
}listArray[fence] = item;listSize++; // Increment list sizereturn true;
}
Θ(n)
Politecnico di Milano - Prof. Sara Comai 13
Inserimento in coda
// Append Elem to end of the listtemplate <class Elem>bool AList<Elem>::append(const Elem& item) {
if (listSize == maxSize) return false;listArray[listSize++] = item;return true;
}
Θ(1)
Politecnico di Milano - Prof. Sara Comai 14
Cancellazione
// Remove and return first Elem in right// partitiontemplate <class Elem> bool AList<Elem>::remove
(Elem& it) {if (rightLength() == 0) return false;it = listArray[fence]; // Copy Elemfor(int i=fence; i<listSize-1; i++)
// Shift them downlistArray[i] = listArray[i+1];
listSize--; // Decrement sizereturn true;
}
Θ(n)nel caso medio
Politecnico di Milano - Prof. Sara Comai 15
Lezione 12 - Modulo 2
Lista concatenata
Informatica 3
Politecnico di Milano - Prof. Sara Comai 16
Implementazione lista basata su puntatori
• Implementazione basata su puntatori: – lista concatenata (linked list)
– Alloca la memoria dinamicamente• alloca solamente la memoria necessaria
– La lista concatenata è composta da una serie di oggetti, detti nodi della lista
• classe nodo separata (riusabile)
Politecnico di Milano - Prof. Sara Comai 17
Nodo della lista: classe Link
// Singly-linked list nodetemplate <class Elem> class Link {
public:Elem element; // Value for this nodeLink *next; // Pointer to next node
//constructor with initial valueLink(const Elem& elemval, Link* nextval = NULL)
{ element = elemval; next = nextval; }
//constructor without initial valueLink(Link* nextval = NULL)
{ next = nextval; }};
Politecnico di Milano - Prof. Sara Comai 18
Inserimento (1)• Operazione di inserimento
• Problema: lista vuota, partizione di sinistra vuota– gestione di casi particolari
testa
testa
coda
coda
posizione corrente
posizione corrente
Politecnico di Milano - Prof. Sara Comai 19
Inserimento (2)• Operazione di inserimento con nodo testa
testa codaposizione corrente
testa codaposizione corrente
Politecnico di Milano - Prof. Sara Comai 20
Inserimento (3)
• Inserimento di un nuovo nodo: 1. creazione del nuovo nodo2. impostazione del puntatore
next del nuovo nodo al primo nodo della partizione di destra
3. impostazione del puntatore next dell’ultimo nodo della partizione di sinistra al nuovo nodo
posizione corrente
posizione corrente
Es: inserisci 10
Politecnico di Milano - Prof. Sara Comai 21
Cancellazione
• Cancellazione di un nodo: posizione corrente
posizione corrente
elemento da cancellare
Politecnico di Milano - Prof. Sara Comai 22
Classe lista concatenata (1)
/ Linked list implementationtemplate <class Elem> class LList:
public List<Elem> {
private:
Link<Elem>* head; // Point to list headerLink<Elem>* tail; // Pointer to last ElemLink<Elem>* fence;// Last element on leftint leftcnt; // Size of leftint rightcnt; // Size of right
void init() { // Intialization routinefence = tail = head = new Link<Elem>;leftcnt = rightcnt = 0;
}
Politecnico di Milano - Prof. Sara Comai 23
Classe lista concatenata (2)
void removeall() { //Return link nodes to free storewhile(head != NULL) {
fence = head;head = head->next;delete fence;
}}
public:
LList(int size=DefaultListSize){ init(); }
~LList() { removeall(); } // Destructor
...
Politecnico di Milano - Prof. Sara Comai 24
Inserimento
// Insert at front of right partitiontemplate <class Elem>bool LList<Elem>::insert(const Elem& item) {
fence->next = new Link<Elem>(item, fence->next); if (tail == fence)
tail = fence->next; rightcnt++;return true;
}// Append Elem to end of the listtemplate <class Elem>bool LList<Elem>::append(const Elem& item) {
tail = tail->next = new Link<Elem>(item, NULL);rightcnt++;return true;
}
Θ(1)
Θ(1)
Politecnico di Milano - Prof. Sara Comai 25
Cancellazione
// Remove and return first Elem in right partitiontemplate <class Elem> bool LList<Elem>::remove(Elem& it){
if (fence->next == NULL) return false;
it = fence->next->element; // Remember valLink<Elem>* ltemp = fence->next; // Remember link nodefence->next = ltemp->next; // Removeif (tail == ltemp) // Reset tail
tail = fence;delete ltemp; // Reclaim spacerightcnt--;return true;
}
Θ(1)(assumendo l’operazione di delete costante)
Politecnico di Milano - Prof. Sara Comai 26
Elemento precedente
// Move fence one step left;// no change if left is emptytemplate <class Elem> void LList<Elem>::prev() {
Link<Elem>* temp = head;if (fence == head)
return; // No prev Elemwhile (temp->next!=fence)
temp=temp->next;fence = temp;leftcnt--;rightcnt++;
}
Θ(n)
Politecnico di Milano - Prof. Sara Comai 27
Setpos
// Set the size of left partition to postemplate <class Elem>bool LList<Elem>::setPos(int pos) {
if ((pos < 0) || (pos > rightcnt+leftcnt)) return false;
fence = head;for(int i=0; i<pos; i++)
fence = fence->next;return true;
}
Θ(i)
Politecnico di Milano - Prof. Sara Comai 28
Confronto tra le implementazioni
Operazione Lista basata su array Lista concatenata
Inserimento e cancellazione Θ(n) Θ(1)Accesso diretto e elemento Θ(1) Θ(n)precedenteSpazio occupato Allocazione a priori Allocazione
dinamicaOverhead Nessuno se le posizioni Per ogni
sono piene elemento
Politecnico di Milano - Prof. Sara Comai 29
Confronto di spazio
Punto di pareggio:
E: Spazio per memorizzare il valore dell’elementoP: Spazio per il puntatoreD: Numero di elementi dell’arrayn: numero di elementi della lista
DE = n(P + E);
n = DE Se P==E allora n=D/2P + E