Kirjoita ohjelma, joka tallentaa kokonaislukuja taulukkoon käyttäen hajautusta. Käytä avointa osoitteenmuodostusta ja esimerkiksi lineaarista etsintää.
Toteuta ainakin lisäys- ja poisto-operaatiot.
Osaisko joku auttaa ja naputella tämmösen ohjelman?
No kuten parissa aiemmassakin viestissä, niin ei naputella valmista ohjelmaa. Laita kuitenkin esille mitä olet tähän mennessä ohjelmoinut, niin katsotaan miten asiassa kannattaisi edetä.
Ohjeet ratkaisuun löytyvät varmasti kurssimateriaalista. Jos oma kurssimateriaali on hukassa, hakukoneella löytyy esim. Jyväskylän yliopiston Algoritmit 2 -kurssin luento 21.3.2019 juuri tästä aiheesta.
Juurikin kyseisen kurssin tehtävä. Tämmöistä saanut aikaiseksi. Poista-aliohjelma ja mainin tulostus on hakusessa. Pseudokoodista koittanut väkerrellä.
public class Binääripuu {
Puusolmu juuri;
class Puusolmu {
Puusolmu vasen;
Puusolmu oikea;
long avain;
}
/**
* lisää-metodi
* @param avain alkion avain
*/
public void lisaa(long avain) {
Puusolmu uusi = new Puusolmu();
uusi.avain = avain;
if (juuri == null) {
juuri = uusi;
return;
}
Puusolmu solmu = juuri;
while (true) {
if (avain == solmu.avain) {
return;
}
if (avain < solmu.avain) {
if (solmu.vasen == null) {
solmu.vasen = uusi;
return;
}
solmu = solmu.vasen;
} else {
if (solmu.oikea == null) {
solmu.oikea = uusi;
} else {
solmu = solmu.oikea;
}
}
}
}
/**
* poista-metodi
*
*/
public void poista() {
//
}
/**
* haku-metodi
* @param avain alkion avain
* @return false
*/
public boolean haku(long avain) {
Puusolmu solmu = juuri;
while (true) {
if (solmu == null) {
return false;
}
if (avain == solmu.avain) {
return true;
}
if (avain < solmu.avain) {
solmu = solmu.vasen;
} else {
solmu = solmu.oikea;
}
}
}
/**
* Pääohjelma
* @param args ei käytössä
*/
public static void main(String[] args) {
int[] a = { 5, 1, 9, 62, 31, 80 };
System.out.println(Arrays.toString(a));
/*haku();
System.out.println(Arrays.toString(a));
lisaa();
System.out.println(Arrays.toString(a));
poista();
System.out.println(Arrays.toString(a));*/
}
}Tehtävässä kuitenkin pyydettiin hajautustaulua eikä binääripuuta, eli olet tehnyt täysin väärää asiaa.
Lineaarisella haulla toteutettuun hajautustauluun tarvitset taulukon, jossa on olioita. Oliolla on avain ja arvo ja jokin merkintätapa sille, onko kyseinen kohta hajautustaulusta poistettu. Avaimesta lasketaan taulukon indeksi (esimerkiksi avain % taulukko.length), joka on ensimmäinen mahdollinen kohta kyseiselle avaimelle. Arvon lisäyksessä edetään tuosta silmukalla eteenpäin, kunnes löytyy vapaa paikka (tyhjä tai poistettu). Arvon etsinnässä edetään, kunnes tulee oikea alkio tai tyhjä kohta (ei osumaa). Arvon poisto toimii kuten etsintä, mutta löytyneeseen alkioon lisätään poistomerkintä. Kohtaa ei voi poistettaessa merkitä tyhjäksi, koska silloin tämän kohdan jälkeen päätyneet alkiot eivät enää haulla löytyisi.
Tämä teksti oli sisällöltään lähes suoraan luentomateriaalista.
Jos taulukko tulee täyteen (tai hakuketju tulee liian pitkäksi), yleensä kannattaa kasvattaa taulukkoa. Kasvatuksen yhteydessä pitää luoda uusi taulukko ja siirtää kaikki arvot vanhasta uuteen edellä kuvatulla lisäysalgoritmilla, jotta ne päätyvät oikeisiin kohtiin.
Aihe on jo aika vanha, joten et voi enää vastata siihen.