Informatica 3 LEZIONE 12: Liste - Intranet DEIBhome.deib.polimi.it/comai/info3/File/Lezione 12 -...

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


Lezione 12 - Modulo 1

ADT lista e implementazione basata su array

Informatica 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


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


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;

};


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

}


Implementazione della lista

• Due approcci standard: – Lista basata su array

– Lista concatenata con puntatori


Implementazione lista basata su arrayOperazione di inserimento:• in testa

• in codaInserisci 25

25

Inserisci 23


Implementazione lista basata su arrayOperazione di cancellazione:

– Es. Cancella 12

posizione corrente


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)


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)


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)


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)


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


Lezione 12 - Modulo 2

Lista concatenata

Informatica 3


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)


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


Inserimento (1)• Operazione di inserimento

• Problema: lista vuota, partizione di sinistra vuota– gestione di casi particolari

testa

testa

coda

coda

posizione corrente

posizione corrente


Inserimento (2)• Operazione di inserimento con nodo testa

testa codaposizione corrente

testa codaposizione corrente


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


Cancellazione

• Cancellazione di un nodo: posizione corrente

posizione corrente

elemento da cancellare


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;

}


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

...


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)


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)


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)


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)


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


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

Date post:	29-Nov-2018
Category:	Documents
Upload:	nguyenkhuong
View:	223 times
Download:	1 times

Informatica 3 LEZIONE 12: Liste - Intranet DEIBhome.deib.polimi.it/comai/info3/File/Lezione 12 -...

Documents