Coda su lista concatenata

Cosa studiare nel libro

• Capitolo 7: tutto tranne Argomenti avanzati 7.2 e 7.5

• Capitolo 8: solo 8.5, 8.6, 8.7, 8.8 e Argomenti avanzati 8.1

• Capitolo 9: tutto fino a 9.6 (escluso)

• Capitolo 10: tutto fino a 10.9 (escluso)

• Capitolo 11: tutto tranne 11.5

• Capitolo 12: tutto tranne 12.5

• Capitolo 13: tutto

• Capitolo 14: tutto

• Capitolo 15: 15.1, 15.3, 15.4

• No Capitolo 16

• Appendice H

Coda su lista concatenata

Coda su lista concatenata

• Analogamente a quanto fatto con la Pila, andiamo a realizzare la Coda tramite una lista concatenata.

• Utilizziamo due riferimenti: primo vede la testa della Coda e ultimo vede l’ultimo elemento della Coda.

• Si inserisce con ultimo e si estrae con primo.

• Gli assiomi da realizzare sono: verifica se è vuota, estrai, inserisci, guarda la testa.

Coda su lista concatenata

• verifica di Coda vuota:

primo == null

O(1) primo

• guarda la testa:

se non è vuota primo.info O(1)

primo

••••

Coda su lista concatenata

• estrai la testa:

se non è vuota:

primo = primo.next;

O(1)

primo

Coda su lista concatenata

• inserisci in coda; si deve costruire il nuovo elemento:

ElemIntero nuovo = new ElemIntero();

si assegnano i valori ai campi info e next:

nuovo.info = elem;

nuovo.next = null; //ultimo nodo si aggancia il nuovo elemento alla Coda (distinguendo due casi: la Coda è vuota oppure no) e tale elemento dovrà poi diventare l’ultimo:

ultimo = nuovo;

Coda su lista concatenata

• inserisci in coda I caso: Coda vuota

se primo == null primo = nuovo O(1)

primo primo

nuovo

ultimo

••••

••••

••••

Coda su lista concatenata

• inserisci in coda II caso: Coda non è vuota se primo ≠ null ultimo.next = nuovo O(1)

primo ultimo

nuovo

••••

••••

Coda su lista concatenata

• Nella Coda, diversamente dalla Pila, la gestione dell’inserimento del primo elemento è diversa:

1) se la Coda non è vuota ultimo.next = nuovo;

2) se la Coda è vuota primo = nuovo;

Coda su lista concatenata

public class CodaListaConc {/** Coda di interi realizzata con lista concatenata */

private ElemIntero primo = null;

private ElemIntero ultimo = null;

public boolean vuota() {//isEmpty:

if(primo == null) return true;

else return false;

}

Coda su lista concatenata

public void inserisci(int elem) { //enqueue

ElemIntero nuovo =

new ElemIntero();

nuovo.next = null;

nuovo.info = elem;

if (primo == null) primo = nuovo;

else ultimo.next = nuovo;

ultimo = nuovo;

}

Coda su lista concatenata

public void estrai(){//dequeue:

if ( !vuota() )

primo = primo.next;

else

throw new EmptyQueueException();

}

public int testa() {//front if ( !vuota() )

return primo.info;

else

throw new EmptyQueueException();

}

Coda su lista concatenata

/** Classe interna: la classe e' privata ma le sue variabili d'istanza sono visibili ai metodi

della classe CodaListaConc */

private class ElemIntero { int info;

ElemIntero next;

}

}//fine CodaListaConc

Interfaccia Queue

• Definizione dell’interfaccia Queue:

public interface Queue{

boolean isEmpty();

void enqueue(Object obj);

void dequeue();

Object front();

}

/* oppure Object dequeue()per restituire la testa */

Realizzazione dell’interfaccia Queue

• Costruzione della Queue:

public class QueueArray

implements Queue { //codice relativo ad una Queue con

//array }

public class QueueListC

implements Queue { //codice relativo ad una Queue con

//lista concatenata }

Realizzazione dell’interfaccia Queue

• In maniera analoga a quanto fatto con lo Stack, nella classe di prova avremo:

Queue queA = new QueueArray();

Queue queL = new QueueListC();

e costruiremo due Code ad esempio con stringhe:

. . .

while (line != null) { queA.enqueue(line);

queL.enqueue(line);

line = in.readLine();

}

Esercizio per casa

• Considerare la classe Stud della settimana 7, sovrascrivere toString per stampare nome cognome e matricola dello studente, costruire uno Stack e una Queue (realizzate con lista concatenata) per studenti del corso23 (il cui numero di matricola finisce per 2 o per 3).

• Stampare lo Stack e la Queue.

• Meditare sulle conversioni dei riferimenti.

Lista

Lista

• La Lista è un TDA che generalizza il concetto di sequenza: gli elementi hanno un ordine posizionale. Nella Lista tutti gli elementi sono accessibili.

• Come TDA la Lista è definita in una interfaccia e per poter accedere ad ogni elemento si utilizza l’interfaccia IteratoresuLista che rappresenta la possibilità di attraversare la Lista, aggiungere e togliere elementi in ogni posizione. Ne vedremo la realizzazione su lista concatenata.

GenericContainer

Interface GenericContainer

• Abbiamo visto che TDA è un contenitore di informazioni e che deve essere inizializzato vuoto. Possiamo pensare che l’essere un contenitore sia un proprietà e possiamo rappresentarla in una interfaccia:

public interface GenericContainer{

boolean isEmpty();

void makeEmpty();

}

//si può aggiungere int getSize();

Interface GenericContainer

• Pertanto possiamo scrivere:

public interface Stack extends GenericContainer{

//push, pop, top }

e la classe che implementa Stack dovrà realizzare anche i metodi dell’interfaccia GenericContainer.

• Anche le interfacce possono essere estese ed ereditano i metodi della superinterfaccia.

Archivio: esercizio tipico

Archivio: esercizio tipico

• L’archivio è un concetto noto della vita quotidiana; vogliamo catalogare delle informazioni vere:

• archivio musicale: memorizziamo il titolo della canzone, il nome del cantante, l’autore, …

• archivio studenti: nome, matricola, media, numero esami sostenuti, …

• anagrafe comunale: nome, codice fiscale, indirizzo, professione, stato civile, …

• biblioteca: titolo, autore, numero copie presenti, collocazione, …

Archivio: esercizio tipico

• archivio patenti: numero patente, nome intestatario, numero punti, …

• I dati veri saranno i nostri oggetti: costruiremo una classe avente per campi le informazioni da memorizzare, metodi di accesso ai campi, eventuali metodi di modifica dei campi.

• Quali operazioni facciamo su un archivio?

• Costruzione

• Stampa

• Aggiornamento: inserire, cancellare, modificare

Archivio: esercizio tipico

• Stampare l’archivio modificato

• Gestione di eventuali errori nei dati: al posto della media c’è un carattere invece di un numero reale;

non ci sono tutte le informazioni sulla riga, …

• Come realizziamo l’archivio?

• Su array ordinato oppure no (ricerca lineare e ricerca binaria; inserimento alla fine o in ordine)

• Su lista concatenata ordinata oppure no

• Su tavola hash

Archivio: esercizio tipico

• Altre richieste:

• stampare in ordine decrescente di media i nomi degli studenti la cui media è superiore ad un valore fissato;

• stampa ricorsiva dell’archivio;

• gestione di eventuale file non trovato

• Nella prima parte del corso abbiamo studiato:

tipi base, oggetti, algoritmi di ordinamento e ricerca su array; nella seconda parte: eccezioni, ereditarietà, interfacce, lista concatenata.

Archivio: esercizio tipico

• Per la gestione dell’archivio occorre: sovrascrivere toString, equals, realizzare compareTo, fare il cast nel passaggio dei riferimenti, …

• Altri esercizi riguardano la gestione di TDA: fusione di due Code ordinate, costruzione di un Lista ordinata di interi e successive modifiche, …

• L’archivio è un TDA?

• Esiste un TDA di nome dizionario che rappresenta l’archivio: (chiave, informazione).

Dizionario

Dizionario

• Il dizionario è un TDA dove si vogliono eseguire ricerche dove l’informazione è individuata da una chiave che è unica.

• La parola del TDA deriva proprio dal dizionario (vocabolario) nel quale:

• le parole sono le chiavi di accesso e sono tutte distinte

• la definizione che segue la parola (informazione associata alla parola, attributo) caratterizza la parola.

Dizionario

• Il dizionario è un contenitore di coppie:

Coppia = (chiave, attributo)

• la chiave è confrontabile

• intero

• tipo che realizza Comparable (String)

• la chiave è unica

• se si vuole inserire una chiave si deve verificare che non sia presente, in tale caso si esegue una sostituzione.

Dizionario

• Le operazioni del TDA Dizionario sono:

• verifica se è vuoto

• inserimento

• ricerca

• cancellazione

• Possiamo descriverlo in una interfaccia e implementarlo su una delle strutture dati.

Dizionario

public interface Dictionary{

boolean isEmpty();

void insert(Comparable chiave, Object attributo);

void remove(Comparable chiave);

Object find(Comparable chiave);

}

Dizionario

• L’informazione Coppia è un record perché contiene campi di tipo diverso; la rappresentiamo perciò con una classe del tipo:

class Coppia implements Comparable{

Object attributo;

. . .

public int compareTo(Object x){

. . . } }

Dizionario

• Dovremo perciò scegliere cosa significa che due Coppie sono confrontabili: stabilire un ordine.

• Non sempre è necessario che le Coppie siano ordinate: per il dizionario è sufficiente la ricerca e quindi è sufficiente sovrascrivere equals. Ad esempio:

class Coppia{

Object attributo; //String, int . . .

public boolean equals(Object x){

. . . } }

Dizionario

• Costruiamo un archivio di studenti realizzando un dizionario e facendo riferimento alla seguente classe:

public class Studente { private String nome;

private int matricola;

public Studente (int m, String n){

nome = n;

matricola = m; } public int matricola () {

return matricola; } public String nome () {

return nome; }

Dizionario

public String toString () {

return matricola + ":" + nome;

}

}//fine Studente

• L’archivio sarà una classe di nome ArchivioStudente e la matricola sarà sia chiave che campo dell’attributo.

Dizionario

• Costruiamo la Coppia come classe interna:

class Coppia implements Comparable{

int chiave;

Studente attributo;

Coppia (int codice, Studente att){

chiave = codice;

attributo = att;

}

Dizionario

public int compareTo(Object x){

Coppia c = (Coppia) x;

if(this.chiave < c.chiave) return -1;

if(chiave > c.chiave) return 1;

return 0;

}//fine compareTo }//fine Coppia

Dizionario

/**La classe costruisce un archivio di studenti utilizzando un array

ridimensionabile*/

import java.util.NoSuchElementException;

public class ArchivioStudente { private Coppia archivio[];

private int dim;

Dizionario

public ArchivioStudente(){

archivio = new Coppia[1];

dim = 0; }

public boolean vuoto(){

return dim == 0;

}

/**si aggiunge un nuovo studente, se necessario si ridimensiona*/

public void aggiungi(int codice, int matricola, String nome){

Dizionario

Studente stud =

new Studente(matricola, nome);

Coppia target =

new Coppia(codice,stud);

//gestione di coppia gia' presente int i=0;

boolean trovato = false;

while( i<dim && !trovato)

if(archivio[i].compareTo(target)==0){

archivio[i] = target;

trovato = true; }

Dizionario

else i++; //fine while if (!trovato) {

//eventuale ridimensionamento if (dim == archivio.length){

Coppia[] nuovoArc =

new Coppia[2 * archivio.length];

for (i = 0; i < archivio.length;i++) nuovoArc[i] = archivio[i];

archivio = nuovoArc;

}

Dizionario

archivio[dim] = target;

dim++;

}

}//fine aggiungi

public Studente ricerca(int codice) throws NoSuchElementException{

Studente stud =

new Studente(0, null);

Coppia target =

new Coppia(codice, stud);

Dizionario

//ricerca della coppia boolean trovato =false;

int i=0;

while( i<dim && !trovato){

if(archivio[i].compareTo(target)==0) trovato =true;

else i++;

}//fine while

Dizionario

if(!trovato)

throw new NoSuchElementException();

else return archivio[i].attributo;

}//fine ricerca

public void cancella (int codice) throws NoSuchElementException{

Studente stud =

new Studente(0, null);

Coppia target =

new Coppia(codice, stud);

Dizionario

//ricerca della coppia int i=0;

boolean trovato =false;

while( i<dim && !trovato){

if(archivio[i].compareTo(target)==0) trovato =true;

else i++;

}//fine while

Dizionario

if(!trovato)

throw new NoSuchElementException();

else {//trovato in posizione i:

//sostituzione con l'ultimo archivio[i]=archivio[dim-1];

dim--;

// oppure costruzione di una copia //del dizionario senza l’elemento

}//fine else }//fine cancella

Dizionario

public String toString () { String tmp = "";

for (int i = 0; i<dim; i++)

tmp = tmp + archivio[i].chiave +

" " + archivio[i].attributo +

"\n";

return tmp;

}//fine toString //. . . classe Coppia } //fine ArchivioStudente

Prestazioni di un Dizionario

• Un dizionario si può realizzare con array non ordinato, array ordinato e lista concatenata.

• Array non ordinato.

• inserimento: dovendo verificare che la chiave non sia presente si effettua una ricerca lineare, O(n) e poi l’inserimento all’ultimo posto, O(1) in media per il raddoppio;

• ricerca: ricerca lineare, O(n)

• cancellazione: si effettua una ricerca, O(n), si sostituisce l’ultimo al posto i-esimo, O(1), oppure si ricopiano gli elementi all’indietro, O(n).

Prestazioni di un Dizionario

• Array ordinato.

• inserimento: dovendo verificare che la chiave non sia presente si effettua una ricerca binaria, O(log₂n) e successivamente l’inserimento in ordine, O(n), spostamento di dati;

• ricerca: ricerca binaria O(log₂n);

• cancellazione: si effettua una ricerca, O(log₂n) e poi si spostano gli elementi all’indietro per mantenere l’ordine, O(n).

Prestazioni di un Dizionario

• Lista concatenata

• inserimento: dovendo verificare che la chiave non sia presente si effettua una ricerca lineare e quindi è O(n); altrimenti l’inserimento è in testa, O(1);

• ricerca: ricerca lineare O(n)

• cancellazione: si effettua una ricerca, O(n) e si esegue la cancellazione O(1).

Scelte di programmazione

• Come si fa nei linguaggi non a oggetti a realizzare un archivio?

• Si costruisce un file (classe di prova) entro cui si inserisce il main, il record che rappresenta l’informazione (classe con incapsulamento) e tutte le funzioni (metodi) per risolvere il problema: inserisci, cancella, ricerca, stampa, ecc. Non c’è scelta per l’accesso: è come se tutto fosse pubblico.

• Si può fare così anche in Java? Sì, naturalmente. Ma noi abbiamo fatto di più.

Scelte di programmazione

• Potevamo scegliere di scrivere tutto in un’unica classe, oppure in classi diverse, e tutto visibile e statico.

• Abbiamo scelto gli oggetti e i TDA:

• abbiamo voluto proteggere i dati

• abbiamo individuato in gruppi di metodi delle proprietà astratte da realizzare.

• In tale modo non solo abbiamo risolto problemi “per noi” ma abbiamo scritto codice generale e riusabile.

Gestione hash di un array di interi

Gestione hash di un array di interi

• Vogliamo inserire dei numeri interi in un array e pensiamo ad una memorizzazione efficiente con lo scopo di ottimizzare successivamente la ricerca del numero.

• Esempio.

• Pensiamo di memorizzare in un array i numeri di matricola di un corso di n=120 studenti; alla matricola si possono poi far corrispondere ulteriori informazioni riguardanti lo studente.

Gestione hash di un array di interi

• Oppure potremmo pensare di individuare lo studente tramite la sua postazione al PC del laboratorio: in questo caso avremo 120 numeri diversi per i 120 studenti. In questo secondo caso consideriamo un array di dimensione 120 e memorizziamo al posto i-esimo lo i-esimo studente: l’indice dell’array coincide con l’informazione che vogliamo memorizzare:

indice = informazione

Gestione hash di un array di interi

• Se andiamo ad eseguire una ricerca il costo sarà sempre O(1); l’accesso diretto alla posizione i- esima ci fornisce l’informazione cercata:

postazione[i] = i

• Potremmo pensare di risolvere in modo analogo il problema di memorizzare il numero di matricola, supponiamo compreso tra 575000 e 580000. Se avessimo a disposizione un array di 580000 componenti nuovamente troveremmo la matricola cercata in un tempo O(1)

matricola[575231] = 575231

Gestione hash di un array di interi

• Possiamo vedere la matricola e la postazione come delle chiavi di accesso all’informazione vera, costituita dai dati dello studente. Se l’insieme delle possibili chiavi coincide con il numero di elementi che vogliamo rappresentare, come nel caso della postazione, allora la scelta è buona.

• Nel caso della matricola avremmo un notevole spreco di memoria: un array di 580000 componenti per memorizzare 120 dati.

Gestione hash di un array di interi

• L’idea pertanto è la seguente:

• lo spazio in più può dare dei vantaggi

• per non sprecarlo cerchiamo una funzione che trasformi la matricola (chiave) in un valore di indice possibile per un array di dimensione dim, con dim un po’ più grande di n=120.

• Vogliamo determinare una funzione h tale che, per ogni valore della chiave (matricola) si abbia:

h(chiave) = posizione con 0 ≤ posizione ≤ dim-1

Gestione hash di un array di interi

• Una funzione di trasformazione può essere il calcolo del resto della divisione con dim:

posizione = h(k) = k mod dim

• Si può dimostrare che, con questa scelta della funzione, è bene che sia dim ≥ n del 10-20% e che dim sia un numero primo. Infatti una buona scelta di h comporta che i resti siano, nella maggior parte dei casi, diversi tra loro.

• Se fosse dim=100, tutti i numeri del tipo 575100, 575200, . . ., 576100, 576200, . . ., avrebbero lo stesso resto.

Gestione hash di un array di interi

• Non sempre le chiavi troveranno resti diversi: si parla allora di “collisione” dato che due chiavi dovrebbero andare nello stesso posto. Come risolvere il problema?

• Lo spazio nell’array c’è, visto che dim ≥ n , pertanto si effettua una scansione cercando un

“posto libero”, provando con il successivo modulo dim:

se posizione = k mod dim è occupata, allora si cerca in

posizione = (posizione+1) mod dim

Gestione hash di un array di interi

• Come abbiamo visto nella Coda, questa tecnica permette di “fare il giro” dell’array.

• Esempio. Consideriamo i seguenti n=9 valori:

1, 3, 4, 15, 18, 20, 22, 35, 48

e proviamo ad inserirli con la tecnica del resto in un array di dim=11 elementi.

• Calcoliamo i resti:

1%11 = 1; 3%11 = 3; 4%11 = 4;

15%11 = 4 ma la posizione 4 è occupata

Gestione hash di un array di interi

• Facciamo:

(4+1)%11 = 5%11= 5 che è libera continuiamo:

18%11= 7; 20%11= 9; 22%11= 0;

35%11= 2; 48%11= 4 che è occupata:

(4+1)%11 = 5%11= 5 che è occupata (5+1)%11 = 6%11= 6 che è libera I numeri nell’array sono memorizzati in ordine diverso da quello di inserimento (rimescolati):

Gestione hash di un array di interi

0 1 2 3 4 5 6 7 8 9 10

• Quanto costa inserire con questa tecnica?

• L’inserimento di un numero che trova subito il suo posto è O(1): calcolo del resto invece di +1; quando c’è una collisione si deve cercare il posto: se n=dim il caso peggiore è O(n), si fa tutto il giro; nel nostro caso abbiamo 12 confronti (per cercare il posto libero) per 9 elementi.

• Si può dimostrare che, se dim è “buona”, in media il costo è O(1).

22 1 35 3 4 15 48 18 20

Gestione hash di un array di interi

• Proviamo ora ad effettuare una ricerca di un valore nell’array. La tecnica per la ricerca sarà la stessa: calcolare il resto della divisione con dim:

valore%dim

fornisce l’indice in cui cercare il valore (chiave).

• Il costo della ricerca di un valore presente è lo stesso di quello dell’inserimento: in media O(1).

Per un valore non presente il costo è superiore:

può capitare di fare tutto il giro, O(n) nel caso peggiore.

Gestione hash di un array di interi

• Per costruire l’array dobbiamo dare un significato al posto “vuoto”. Possiamo inizializzare l’array con un valore non appartenente all’universo delle chiavi; ad esempio 0 per le matricole, -1 per le postazioni dei PC, ecc.

• Durante la costruzione dell’array il posto vuoto indica la posizione libera in cui poter inserire l’elemento.

• Durante la ricerca il posto vuoto indica

“elemento non presente”.

Gestione hash di un array di interi

• Nel caso della ricerca si effettua la stessa scansione facendo il giro dell’array. In caso di array pieno (n=dim) e di elemento non presente, si fa tutto il giro ritornando alla posizione iniziale senza trovarlo.

• Per gestire questa situazione, si salva il valore della chiave presente all’indice chiave%dim in una variabile temporanea, si copia in tale posizione l’elemento da cercare, si effettua la ricerca (che avrà esito positivo).

Gestione hash di un array di interi

• Se l’elemento viene trovato nella posizione iniziale (si è fatto tutto il giro) significa che non c’è, altrimenti lo si è trovato più avanti e ciò significa che c’era stata una collisione.

Infine si ripristina il valore salvato.

• Si può ottimizzare la ricerca del caso non trovato, inserendo le chiavi in ordine: se si trova un elemento più grande ciò significa che quello più piccolo non c’è.

Tavola: dizionario con chiave intera

Tavola: dizionario con chiave intera

• Vogliamo ora rappresentare un dizionario la cui chiave è un valore intero; le operazioni sono sempre:

ricerca, inserisci, cancella.

• Si dà il nome di Tavola ad un dizionario a chiave intera:

boolean isEmpty();

void insert(int chiave,

Object attributo);

void remove(int chiave);

Object find(int chiave);

Tavola Hash

Tavola Hash

• Dal momento che la chiave è intera possiamo pensare di utilizzare la tecnica vista prima per memorizzare la chiave.

• Però possiamo fare meglio.

• Il problema delle collisioni portava ad un sovradimensionamento della tavola; cerchiamo di risolverlo in altro modo: mantenere le stesse prestazioni e non sprecare spazio.

• L’array offre con l’accesso diretto O(1), la lista concatenata offre un inserimento O(1).

Tavola Hash

• Costruiamo un array di liste concatenate: la scelta dell’indice nell’array si effettua con chiave trasformata (ridotta) e la collisione si risolve con un inserimento in testa alla lista.

• Abbiamo quindi un Tavola realizzata tramite due strutture di dati che prende il nome di Tavola Hash con bucket (bucket è la lista concatenata).

• Le prestazioni della Tavola dipendono dalla funzione hash e dalle chiavi.

Tavola Hash

• La funzione h potrebbe fornire sempre lo stesso valore di chiave ridotta: caso peggiore, O(n)

•

•

•

•

••••

coppia coppia coppia

Tavola Hash

• Caso favorevole: tutte le liste hanno la stessa lunghezza, n/dim, O(n/dim); se n~dim si ha circa O(1)

coppia

coppia

coppia . . .

Tavola Hash

• Se le chiavi sono uniformemente distribuite, la funzione hash con il resto della divisione con dim è una buona scelta: anche le chiavi ridotte sono uniformemente distribuite.

• Dobbiamo usare solo i numeri o possiamo fare lo stesso anche con altri tipi Comparable?

• Proviamo con le stringhe.

• Dobbiamo associare ad una stringa un valore intero per poter poi calcolare il resto.

Tavola Hash

• Ricordiamo la notazione posizionale dei numeri:

257 = 2 ××××10²+ 5 ××× 10× ¹ + 7 ××× 10× ⁰

possiamo trasformare una stringa in un numero pensando alla base b=65536:

“ABC” = ‘A’ ×××× b²+ ‘B’ ××× b× ¹+ ‘C’ ×××× b⁰

• Sarebbe una buona idea, dato che in Java un char è anche un intero (short: numero d’ordine nel codice UNICODE), ma si avrebbe un numero troppo elevato e spesso overflow.

Tavola Hash

• La libreria standard usa per le stringhe il valore 31 (primo) come moltiplicatore, al posto di b:

“ABC” = ‘A’ ×××× 31²+ ‘B’ ×××× 31¹+ ‘C’ ××× 31× ⁰

• Possiamo quindi calcolare il valore hash per

“ABC”:

String s = “ABC”;

final int MOLTIPLICATORE = 31;

int h=0;

for(int i=0; i<s.length(); i++) h = MOLTIPLICATORE*h + s.charAt(i);

System.out.println(“codice hash = “ + h);

Tavola Hash

• Il ciclo for utilizza per il calcolo di h la formula di Horner per il calcolo del valore di un polinomio:

a₀xⁿ+ a₁x ^n-1+ …. + a_n-1x + a_n=

= (…((a₀x + a₁)x + a₂)x + ….+ a_n-1)x + a_n

il calcolo è più efficiente che non partire da a_n e sommare calcolando le potenze x^k= x k-1•x .

Tavola Hash

• Per gestire oggetti generici si può usare il metodo hasCode() della classe Object che restituisce un int a partire dall’indirizzo di memoria dell’oggetto. Si può pertanto fare:

int codicehash = oggetto.hasCode();

e quindi:

int posizione = codicehash%dim;

Tavola Hash

• Vogliamo costruire l’archivio degli studenti:

private static final int dimTabh = 7;

private Elemento archivio[];

private int dim;

public ArchivioTabh(){//costruttore archivio =

new Elemento[dimTabh];

dim = 0; //numero di elementi inseriti }

Tavola Hash

• Il nodo sarà una classe interna:

private class Elemento{

Coppia info;

Elemento next;

}

• La classe Coppia è la stessa dell’archivio su array.

• Il metodo aggiungi calcola la posizione nella tavola e poi verifica se la lista (bucket) è vuota o se c’è collisione.

Tavola Hash

• public void aggiungi(int codice, int matricola, String nome){

Studente stud =

new Studente(matricola, nome);

Coppia target = new Coppia(codice, stud);

int i = hash(codice);

if(archivio[i] == null){ //lista vuota archivio[i] = new Elemento();

archivio[i].info = target;

archivio[i].next = null;

dim++;

}

Tavola Hash

else{//collisione

//cerca se la coppia e' gia' presente Elemento tmp = archivio[i];

boolean trovato = false;

while( tmp!=null && !trovato)

if((tmp.info).compareTo(target)==0){

//se presente si riassegna tmp.info = target;

trovato =true;

}

else tmp=tmp.next;

//fine while

Tavola Hash

//se la coppia non c'e', inserimento in // testa alla lista

if (!trovato) {//push

Elemento nuovo = new Elemento();

nuovo.info = target;

nuovo.next = archivio[i];

archivio[i] = nuovo;

dim++;

}

}//else collisione }//fine aggiungi