Liste semplici in Java

AlgoLab - Liste semplici

Liste semplici in Java

Laboratorio di Algoritmi 02/03

Prof. Ugo de’ Liguoro


Liste semplicemente concatenate

Sono strutture dati lineari per la rappresentazione di sequenze finite:

; 2 List(T)

i 2 T, l 2 List(T) ) [i j l] 2 List(T)

12 3 25

/

l

l = [12 | [3 | [25 | ;]]] = [12, 3, 25]


Primo approccio: contiamo gli oggetti

In prima approssimazione associamo un oggetto ad ogni elemento ed un oggetto contenitore ad ogni lista. Quindi ci saranno due classi:

T_Node: classe dei singoli elementi della lista, il cui valore (info) e’ di tipo T;

T_List: classe delle liste di elementi di tipo T.

Nota: non usando il polimorfismo, negli esempi T = int.


Realizzazione: IntNode

class IntNode {

public int info; // campo valore

public IntNode next; // campo prossimo el.

public IntNode(int i)

{this(i, null);}

// chiamata al secondo costruttore

public IntNode(int i, IntNode n)

{info = i; next = n;}

}

}


Realizzazione: IntSList

class IntSList {

private IntNode first;

// primo el. della lista

private int len; // lunghezza della lista

public IntSlist () {first = null, len = 0;}

public void cons(int el) {…} // aggiungi in testa

public boolean insert(int el, int index) {…}

public boolean delete(int index) {…}

public int retrieve(int index) {…}

public int length () {return len;}

}


Realizzazione: cons

public void cons(int el)

// inserisce el in testa alla lista

{ first = new IntNode(el,first);

len++;

}


Realizzazione: retrieve

public int retrieve(int index)

// pre: index in [0..len-1]

// post: ritorna il valore dell’index-esimo el.

{ int i; IntNode p;

for (i = 0, p = first; i < index; i++, p = p.next);

return p.info;

}


Realizzazione: insert

public boolean insert(int el, int index)

// se index in [0..len] ritorna true ed inserisce

// el in index-esima posizione; false altrimenti

{ if (index < 0 || index > len) return false;

if (index == 0) {cons(el); return true;}

int i; IntNode p;

for(i = 0, p = first; i < index-1; i++, p = p.next);

p.next = new IntNode(el,p.next); len++;

return true;

}

// per inserire come ultimo el. insert(el,length())


Esecuzione di insert

p

p.next = new IntNode(el,p.next);


Esecuzione di insert

p


Realizzazione: delete

public boolean delete(int index)

// se index in [0..len-1] ritorna true ed elimina

// l’index-esimo elemento; false altrimenti

{ if (index < 0 || index > len-1) return false;

if (index == 0)

{first = first.next; len--; return true;}

int i; IntNode p;

for(i = 0, p = first; i < index-1; i++, p = p.next);

// p punta all'el. precedente quello di indice index

p.next = p.next.next; len--;

return true;

}


Esecuzione di delete

p

p.next = p.next.next


Esecuzione di delete

p


Iteratore sulle liste

Iteratore: oggetto che enumera gli elementi di una collezione; implementa almeno i metodi:

1. NonAllaFine(): true se ci sono ancora elementi da scandire

2. ValoreCorrente(): ritorna il valore dell’el. corrente

3. Successivo(): passa al successivo (per lo più ritornando prima il valore corrente).

Lista

iteratore


Iteratore: realizzazione (1)

class IntListIt {

private IntNode current; // el. corrente della lista

public IntListIt(IntNode node) // costruttore

{ current = node;}

public boolean NotEnd() {return current != null;}

public int Succ()

// pre: current != null

// post: fornisce il corrente e avanza al successivo

{ int n = current.info; current = current.next;

return n;}

public int Val()

// pre: current != null, post: valore el. corrente

{ return current.info;}

}


Iteratore: realizzazione (2)

/********** aggiunta alla classe IntSlist ********/

class IntSList {

...

public IntListIt iterator()

// iteratore

{ return new IntListIt(first);

}

}

/**************** uso dell’iteratore *************/

IntSList list; IntListIt listitr; ...

listitr = list.iterator();

while (listitr.NotEnd())

dosomethingwith(listitr.Succ());


Ordinamento per fusione: Mergesort

MergeSort (pseudocodice)

MergeSort(List l): List

If lunghezza(l) > 1 then

(n, m) := prima e seconda meta’ di l rispettivamente;

// divisione distruttiva di l

n := MergeSort(n); // ordina ricorsivamente n

m := MergeSort(m); // ordina ricorsivamente m

return Merge(n,m); // fusione ordinata distruttiva

else return l

end.


MergeSort: realizzazione (1)

Si sceglie di aggiungere alla classe IntSList :1. Un metodo pubblico Sort(), riferito agli oggetti di

tipo lista ;2. Un metodo privato (più le sue subroutines):

IntNode MergeSort(IntNode)

che procede all’ordinamento (distruttivo) direttamente sulla catena dei nodi

Nota: questa tecnica consente di usare un’ implementazione C-like, ma piuttosto che essere un algoritmo che usa la struttura lista, è un suo servizio interno.



class IntSList {

...

public void Sort() {

first = MergeSort(first);

}

private IntNode MergeSort(IntNode n) {...}

private IntNode Split(IntNode n) {...}

private IntNode Merge(IntNode n1, IntNode n2)

{...}

}



private IntNode MergeSort(IntNode n) {

IntNode m;

if (n != null && n.next != null)

{

m = Split(n); // n divisa distruttivamente

m = MergeSort(m);

n = MergeSort(n);

return Merge(n,m);

}

else return n;

}



private IntNode Split(IntNode n) {

// pre: n != null && n.next != null

IntNode p, q;

for(p = n, q = n.next;

q.next != null && q.next.next != null;

p = p.next, q = q.next.next);

q = p.next;

p.next = null;

return q;

}



private IntNode Merge(IntNode n1, IntNode n2) {

if (n1 == null) return n2;

if (n2 == null) return n1;

if (n1.info < n2.info)

{n1.next = Merge(n1.next,n2); return n1;}

else {n2.next = Merge(n1,n2.next); return n2;}

}

Liste semplici in Java

Documents

Transcript of Liste semplici in Java