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 27. mars fyrir kl 16:00
Leysið dæmi 3.3.1 í bókinni.
Draw the 2-3 tree that results when you insert the keys E A S Y Q U T I O N in that order into an initially empty tree.
Leysið dæmi 3.3.9 í bókinni.
Which of the following are red-black BSTs?
Lausn: (iii) og (iv) eru rauð-svört tré, en (i) og (ii) eru það ekki. (i) er ekki í jafnvægi og (ii) er ekki tvíleitartré.
Leysið dæmi 3.3.10 í bókinni.
Draw the red-black BST that results when you insert items with the keys E A S Y Q U T I O N in that order into an initially empty tree
Skrifið forrit sem les orð af aðalinntaki og prentar út á aðalúttak hversu oft hvert orð kemur fyrir í inntakinu.
Notið rautt-svart tré (RedBlackBST) til að halda utan um talninguna.
import java.util.Scanner; public class wc { public static void main(String[] args) { RedBlackLiteBST<String, Integer> count = new RedBlackLiteBST<String, Integer>(); Scanner scan = new Scanner(System.in); while (scan.hasNext()) { String word = scan.next(); if (count.contains(word)) count.put(word, count.get(word) + 1); else count.put(word, 1); } for (String s : count.keys()) { System.out.printf("%s: %d\n", s, count.get(s)); } } }
Skrifið forrit í C eða Java sem tekur inn lista af skrám sem viðföng í skipanalínu og býr til flýtivísi þ.a. það sé hægt að fletta hratt upp öllum skránum sem innihalda gefið orð.
Forritið á að lesa orð af aðalinntaki og prenta út lista yfir allar skrár (af þeim sem voru gefnar upp á skipanalínu sem viðföng) sem innihalda viðkomandi orð.
Notið rautt-svart tré til að geyma flýtivísinn. Lyklarnir í trénu eiga að vera orð og gildin eiga að vera listi af skrám sem innihalda viðkomandi orð.
Þið megið nota java.util.TreeSet tilvik sem gildi í trénu.
import java.io.File; import java.util.Scanner; import java.util.TreeSet; public class FileIndex { public static void main(String[] args) throws Exception { RedBlackLiteBST<String, TreeSet<File>> st = new RedBlackLiteBST<String, TreeSet<File>>(); System.out.println("Indexing files"); for (String filename : args) { System.out.println(" " + filename); File file = new File(filename); Scanner scan = new Scanner(file); while (scan.hasNext()) { String word = scan.next(); if (!st.contains(word)) st.put(word, new TreeSet()); TreeSet set = st.get(word); set.add(file); } } Scanner stdin = new Scanner(System.in); while (stdin.hasNext()) { String query = stdin.next(); if (!st.contains(query)) continue; TreeSet<File> set = st.get(query); for (File file : set) System.out.println(" " + file.getName()); } } }