Tölvunarfræði 2 - Vor 2012
Verkefni 13 - Sýnislausn
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
Dæmi 1 (2 stig) - Innsetning í skopplista
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.
Lausn:
Dæmi 2 (2 stig) - Hnútar á tiltekinni hæð í tré
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
Lausn:
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree
{
private String val;
private BinaryTree left, right;
private int level;
public BinaryTree(BinaryTree left, BinaryTree right, String val, int level)
{
this.left = left;
this.right = right;
this.val = val;
this.level = level;
}
public static void levelPrint(BinaryTree root)
{
if (root == null)
return;
Queue<BinaryTree> q = new LinkedList<BinaryTree>();
q.offer(root);
int lastLevel = -1;
while (!q.isEmpty())
{
BinaryTree x = q.remove();
if (lastLevel < 0)
System.out.printf("Level %d: %s ", x.level, x.val);
else if (lastLevel != x.level)
System.out.printf("\nLevel %d: %s ", x.level, x.val);
else
System.out.print(x.val + " ");
if (x.left != null)
q.offer(x.left);
if (x.right != null)
q.offer(x.right);
lastLevel = x.level;
}
System.out.println();
}
public static void main(String[] args)
{
BinaryTree D = new BinaryTree(null, null, "D", 2);
BinaryTree E = new BinaryTree(null, null, "E", 2);
BinaryTree B = new BinaryTree(D, E, "B", 1);
BinaryTree F = new BinaryTree(null, null, "F", 2);
BinaryTree C = new BinaryTree(F, null, "C", 1);
BinaryTree A = new BinaryTree(B, C, "A", 0);
BinaryTree.levelPrint(A);
}
}
Dæmi 3 (2 stig) - Mengi strengja útfært með tengdum lista
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);
}
Lausn sem notar lista í engri sérstakri röð:
public class StringSetList implements StringSet
{
private static class Node
{
String s;
Node next;
}
private Node head;
// Öll gildi í menginu eru í keðjunni head í engri
// sérstakri röð.
// Notkun: set = new StringSetList();
// Fyrir: Ekkert
// Eftir: set er nýtt tómt mengi strengja
public StringSetList()
{
head = null;
}
// Notkun: set.add(s);
// Fyrir: Ekkert
// Eftir: Búið er að bæta strengnum s í mengið set.
public void add(String s)
{
if (contains(s))
return;
Node p = new Node();
p.s = s;
p.next = head;
head = p;
}
// Notkun: b = set.contains(s);
// Fyrir: Ekkert
// Eftir: b er satt þþaa. s er í set.
public boolean contains(String s)
{
Node p = head;
while (p != null)
{
if (s.equals(p.s))
return true;
p = p.next;
}
return false;
}
public static void main(String[] args)
{
StringSetList set = new StringSetList();
set.add("A");
set.add("B");
set.add("C");
set.add("D");
System.out.println("A: " + set.contains("A"));
System.out.println("B: " + set.contains("B"));
System.out.println("C: " + set.contains("C"));
System.out.println("D: " + set.contains("D"));
System.out.println("E: " + set.contains("E"));
System.out.println("F: " + set.contains("F"));
}
}
Lausn sem notar lista í röð:
public class StringSetList implements StringSet
{
private static class Node
{
String str;
Node next;
}
private Node head;
// Strengirnir í menginu eru í keðjunni head í vaxandi
// stafrófsröð.
public void add(String str)
{
if (head == null || head.str.compareTo(str) > 0)
{
Node n = new Node();
n.str = str;
n.next = head;
head = n;
return;
}
if (head.str.compareTo(str) == 0)
return;
Node p = head;
while (p.next != null)
{
// p er keðja sem er aftari hluti keðjunnar head.
// Hlekkurinn p og fremri hlekkir innihalda strengi
// sem eru framar en str í stafrófsröð.
int cmp = p.next.str.compareTo(str);
if (cmp == 0)
return;
else if (cmp > 0)
break;
p = p.next;
}
Node n = new Node();
n.str = str;
n.next = p.next;
p.next = n;
}
public boolean contains(String str)
{
Node p = head;
while (p != null)
{
// p bendir á aftari hluta keðjunnar head (má vera tóm keðja).
// Sá hluti keðjunnar sem er fyrir framan p inniheldur ekki str.
int cmp = p.str.compareTo(str);
if (cmp == 0)
return true;
else if (cmp > 0)
return false;
p = p.next;
}
return false;
}
public static void main(String[] args) throws Exception
{
StringSetList set = new StringSetList();
set.add("A");
set.add("B");
set.add("C");
set.add("D");
System.out.println("A: " + set.contains("A"));
System.out.println("B: " + set.contains("B"));
System.out.println("C: " + set.contains("C"));
System.out.println("D: " + set.contains("D"));
System.out.println("E: " + set.contains("E"));
System.out.println("F: " + set.contains("F"));
}
}
Dæmi 4 (2 stig) - Mengi strengja útfært með HashMap tætitöflu
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.
Lausn:
import java.util.LinkedList;
public class StringSetMap
{
private LinkedList<String>[] st;
private int N;
private int M;
// Öll gildi í menginu eru í listunum st[0..M-1]
// N er heildarfjöldi gilda í menginu
// st[h] inniheldur öll gildi í menginu sem hafa tætigildi h
// (þ.e. öll gildi x þar sem hash(x) = i)
@SuppressWarnings({"unchecked"})
public StringSetMap(int M)
{
this.st = (LinkedList<String>[]) new LinkedList[M];
this.M = M;
this.N = 0;
}
private void resize(int chains)
{
StringSetMap temp = new StringSetMap(chains);
for (int i = 0; i < M; i++)
{
for (String key : st[i])
{
temp.add(key);
}
}
this.M = temp.M;
this.N = temp.N;
this.st = temp.st;
}
private int hash(String key)
{
return (key.hashCode() & 0x7fffffff) % M;
}
public boolean contains(String key)
{
int i = hash(key);
if (st[i] == null)
return false;
return st[i].contains(key);
}
public void add(String key)
{
if (N >= 10*M)
resize(2*M);
int i = hash(key);
if (st[i] == null)
st[i] = new LinkedList<String>();
else if (st[i].contains(key))
return;
st[i].add(key);
N++;
}
public static void main(String[] args)
{
StringSetMap set = new StringSetMap(1000);
set.add("A");
set.add("B");
set.add("C");
set.add("D");
System.out.println("A: " + set.contains("A"));
System.out.println("B: " + set.contains("B"));
System.out.println("C: " + set.contains("C"));
System.out.println("D: " + set.contains("D"));
System.out.println("E: " + set.contains("E"));
System.out.println("F: " + set.contains("F"));
}
}
Dæmi 5 (2 stig) - Mengi strengja útfært með tætingu og bitset
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.
Lausn:
public class StringSetBitSet
{
private BitSet bs;
private int n;
public StringSetBitSet(int n)
{
bs = new BitSet(n);
this.n = n;
}
public boolean contains(String s)
{
int h = (s.hashCode() & 0x7fffffff) % n;
return bs.get(h);
}
public void add(String s)
{
int h = (s.hashCode() & 0x7fffffff) % n;
bs.set(h);
}
public static void main(String[] args)
{
StringSetBitSet set = new StringSetBitSet(1000);
set.add("A");
set.add("B");
set.add("C");
set.add("D");
System.out.println("A: " + set.contains("A"));
System.out.println("B: " + set.contains("B"));
System.out.println("C: " + set.contains("C"));
System.out.println("D: " + set.contains("D"));
System.out.println("E: " + set.contains("E"));
System.out.println("F: " + set.contains("F"));
}
}