Lausnum skal skilað til viðkomandi dæmakennara (sjá lista yfir dæmatíma).
Reynið að skrifa stutt, skýr og hnitmiðuð forrit. Notið réttan inndrátt og gætið þess að forritin ykkar séu læsileg.
Skiladagur: þriðjudaginn 17. apríl fyrir kl 16:00
Bætið eftirfarandi runu af gildum í tóman skopplista: E A S Y Q U T I O N. Kastið krónu til að ákveða framgöngu. Teiknið mynd af skopplistanum eftir að öll gildin hafa verið sett í hann.
Skrifið fall sem tekur inn tilvísun á rótarhnút í tré og prentar út hnútana á hverri hæð í röð frá efstu hæð til neðstu með eina hæð per línu.
Dæmi: fyrir eftirfarandi tré myndi fallið prenta út
A
/ \
B C
/ \ /
D E F
Level 0: A Level 1: B C Level 2: D E F
Skrifið klasa sem uppfyllir eftirfarandi skil (interface) fyrir mengi strengja. Útfærið klasann þannig að hann geymi strengina í menginu í tengdum lista. Ef streng er bætt við sem er þegar í menginu þá á að gæta þess að hann sé ekki tvískráður í listann.
Með klasanum á að fylgja fastayrðing gagna sem lýsir þeirri gagnaskipan sem er notuð í útfærslunni. Tilgreinið einnig tímaflækju add og contains.
Skil (interface) fyrir mengi strengja:
public interface StringSet
{
// Notkun: set.add(s);
// Fyrir: Ekkert
// Eftir: Búið er að bæta strengnum s í mengið set.
void add(String s);
// Notkun: b = set.contains(s);
// Fyrir: Ekkert
// Eftir: b er satt þþaa. s er í set.
boolean contains(String s);
}
Beinagrind:
public class StringSetList implements StringSet
{
private static class Node
{
String s;
Node next;
}
// ??? Hér vantar tilviksbreytur og fastayrðingu gagna
// Notkun: set = new StringSetList();
// Fyrir: Ekkert
// Eftir: set er nýtt tómt mengi strengja
public StringSetList()
{
// ...
}
// Notkun: set.add(s);
// Fyrir: Ekkert
// Eftir: Búið er að bæta strengnum s í mengið set.
public void add(String s)
{
// ...
}
// Notkun: b = set.contains(s);
// Fyrir: Ekkert
// Eftir: b er satt þþaa. s er í set.
public boolean contains(String s)
{
// ...
}
}
Skrifið klasa sem uppfyllir skilin (interface) fyrir mengi strengja sem voru gefin upp í dæmi 3. Útfærið klasann þannig að hann geymi strengina í menginu í HashMap (útfærsla á fjölnota tætitöflu sem fylgir með Java).
Skrifið fastayrðingu gagna fyrir þá gagnaskipan sem er notuð í útfærslunni. Tilgreinið tímaflækju add og contains.
Þeir sem vilja mega alveg útfæra tætitöfluna sjálfir í staðinn fyrir að nota HashMap.
Gerum ráð fyrir að við séum með forrit sem þarf að byggja risastórt mengi af strengjum og það sé ekki pláss fyrir alla strengina í minni. Gerum ennfremur ráð fyrir því að við séum tilbúin að sætta okkur við eftirfarandi breytingu á contains í StringSet:
public interface StringSet
{
// Notkun: set.add(s);
// Fyrir: Ekkert
// Eftir: Búið er að bæta strengnum s í mengið set.
void add(String s);
// Notkun: b = set.contains(s);
// Fyrir: Ekkert
// Eftir: Ef b er satt þá er s kannski í set,
// en ef b er ósatt þá er s bókað ekki í set.
boolean contains(String s);
}
Við erum semsagt tilbúin að sætta okkur við ranglega jákvæð svör (tilfelli þar sem contains skilar true en s er í raun ekki í set), en ekki ranglega neikvæð svör (ef contains skilar false þá er s bókað ekki í menginu).
Skrifið klasa sem uppfyllir ofangreind skil. Útfærið klasann með því að nota tætingu og BitSet.
Útfærslan í þessu dæmi líkist einfaldri útgáfu af svokölluðum bloom filters. Áhugasamir nemendur geta lesið um þá á Wikipedia.