Salve a tutti,
premetto che non so se questa è la sezione adatta al post in questione, quindi se mi trovo in quella sbagliata, chiedo scusa in anticipo
sto preparando l'esame di algoritmi e strutture dati e sto facendo passo passo i vari esercizi che mi capitano davanti.
L'esercizio che ho ora sotto gli occhi è il seguente :
Dato l'insieme di chiavi K = 5,11,18,13,14,6,4 e sia m=7 inserire le chiavi in una tabella hash inizialmente vuota di dimensione m usando la funzione hash h(k)=k mod m e gestendo le collisioni con le liste di trabocco. Ripetere l'esercizio usando l'indirizzamento aperto con scansione lineare data da h(k,i) = (h(k)+i) mod m. Mostrare il contenuto della tabella alla fine dell'inserimento :
Allora, per la prima parte dell'esercizio credo di non avere problemi, ma per sicurezza vi mostro il ragionamento che sto adottando :
h0 = 5mod 7 = 5
h1 = 11 mod 7 = 4
h2 = 18 mod 7 = 4
h3 = 13 mod 7 = 6
h4 = 14 mod 7 = 0
h5 = 6 mod 7 = 6
h6 = 4mod 7 = 4
Quindi alla fine la mia tabella dovrebbe essere in questo modo :
Posizioni | Valori
0 h4
1 /
2 /
3 /
4 h1 -> h2 -> h6
5 h0
6 h5
Non so se è giusto il ragionamento, in caso sbaglio qualcosa, mi potete dire dov'è l'errore ?
Per quanto riguarda il secondo esercizio io so, a livello teorico che l'idea è quella di memorizzare tutte le chiavi in una stessa tabella dove ogni slot contiene una chiave o il valore NIL e nell'ispezione lineare la formula è :
H (k,i) = (H(k)+h⋅i) mod m
Nel mio esercizio ho : h(k,i) = (h(k)+i) mod m, quindi vorrei sapere da voi, come dovrei procedere :
dovrei fare per esempio
h(5,0) = (h(5)+0) mod 7
h(11,1) = (h(11)+1) mod 7 e cosi via ???
ma in questi casi, come li metto nella tabella ?
Rispondi quotando
