Ukeoppgaver 9:  25. - 29. okt (INF1000 - H?st 2010)

M?l
Forst? forskjellene mellom arrayer og HashMaper, og anvendelsesomr?dene for disse datastrukturene, og forst? hvordan innstikksortering fungerer.

Oppgaver til teoritimen

1. HashMap: Hva skrives ut?  (Se oversikten p? side 188 i l?reboka)

   import java.util.*;
   class Personer {
       public static void main(String[] args) {
   	HashMap <String, Person> register = new HashMap <String, Person> ();
   
   	Person p1 = new Person("Ida", 19);
   	Person p2 = new Person("Lars", 21);
   
   	register.put(p1.navn, p1);
   	register.put(p2.navn, p2);
   
   // a)
   	Person p = register.get("Ida");
   	System.out.println(p.navn + p.alder);
   
   // b)
   	for (String s : register.keySet()) {
   	    System.out.println(s);
   	}
   // c)
   	p1.alder = 24;
   	for (Person p3 : register.values()) {
   	    System.out.println(p3.navn + ":" + p3.alder);
   	}
   // d)
   	if (register.containsValue(p2) && ! register.containsKey("Elin")) {
   	    System.out.println(true);
   	}
   // e)
   	register.remove("Lars");
   	System.out.println(register.size() + " - " + register.isEmpty());
   // f)
   	System.out.println(register.remove("Ida") == null);
   	System.out.println(register.remove("Ida") == null);
       }
   }
   
   class Person {
       String navn;
       int alder;
   
       Person(String navn, int alder) {
   	this.navn = navn;
   	this.alder = alder;
       }
   }
   

   
   
   
2. Bank.java: Array vs. HashMap
   (a) F?lgende program viser et enkelt banksystem med en array kontoer[], og metoder for ? finne en konto vha. navn til eieren og vha. kontonummer.  Skriv om programmet slik at det bruker en HashMap i stedet for arrayen kontoer[].  I f?rste omgang lager vi ¨¦n HashMap, med personnavn som n?kkel og et Konto-objekt som verdi, deklarert slik:
     HashMap<String, Konto> kontoFraNavn = new HashMap<String, Konto>();
   
   Hvilke fordeler og ulemper f?r vi av ? bruke HashMap her?  Hva kan variabelen antKontoer erstattes med i programmet?  (Anta forel?pig at personnavnene er unike og at hver person bare kan ha ¨¦n konto i banken.)

   class Konto {
       int nr; // kontonummer
       String navn; // eier
       int saldo;
   
       Konto(int nr, String navn, int saldo) {
   	this.nr = nr;
   	this.navn = navn;
   	this.saldo = saldo;
       }
   
       void settInn(int innskudd) {
   	saldo = saldo + innskudd;
       }
   }
   
   class Bank {
       Konto[] kontoer = new Konto[1000];
       int antKontoer = 0;
   
       public static void main(String[] args) {
   	Bank b = new Bank();
       }
   
       Bank() {
           ?pneNyttKonto(530010, "Nils", 4000);
           ?pneNyttKonto(720020, "Elin", 8000);
           ?pneNyttKonto(910030, "Tina", 9000);
   
           Konto k = finnKontoFraNavn("Elin");
           System.out.println("Elins kontonr: " + k.nr + ", saldo: " + k.saldo);
   
   	k = finnKontoFraNr(530010);
   	System.out.println("Kontonr. " + k.nr + " tilh?rer " + k.navn);
       }
   
       void ?pneNyttKonto(int nr, String navn, int saldo) {
   	Konto k = new Konto(nr, navn, saldo);
   	kontoer[antKontoer] = k;
   	antKontoer++;
       }
   
       Konto finnKontoFraNavn(String navn) {
   	for (int i = 0; i < antKontoer; i++) {
   	    if (kontoer[i].navn.equals(navn)) {
   		return kontoer[i];
   	    }
   	}
   	return null;
       }
   
       Konto finnKontoFraNr(int kontonr) {
   	for (int i = 0; i < antKontoer; i++) {
   	    if (kontoer[i].nr == kontonr) {
   		return kontoer[i];
   	    }
   	}
   	return null;
       }
   }
   
   KJ?REEKSEMPEL:
   Elins kontonr: 720020, saldo: 8000
   Kontonr. 530010 tilh?rer Nils
   

   
   (b) Lag en HashMap til, kalt kontoer, hvor du bruker som n?kkel kontonummeret konvertert til String, og fortsatt Konto-objektene som verdi.  Vis at metoden finnKontoFraNr() blir enklere n?.  Videre tenk deg at vi skal ha en metode for ? fjerne en konto.  F?lgende kode viser hvordan det kan gj?res med arrayer.  Hvor mange programsetninger trengs det n?r vi bruker ¨¦n HashMap i stedet?  Og med to?

       void avsluttKonto(Konto k) {
   	// Fjerner en konto ved ? finne indeksen til kontoen i arrayen
   	// kontoer[] og flytte alle kontoene med h?yere indeks en plass ned.
   	boolean funnet = false;
   	for (int i = 0; i < antKontoer && !funnet; i++) {
   	    if (kontoer[i] == k) {
   		funnet = true;
   		for (int j = i; j < antKontoer - 1; j++) {
   		    kontoer[j] = kontoer[j + 1];
   		}
   		antKontoer--;
   	    }
   	}
       }
   

   
   (c) Disse oppgavene har begrensningen at personnavnene m? v?re unike og at hver person bare kan ha ¨¦n konto i banken.  Hvordan ville man unng?tt disse begrensninger i et mer avansert system?  Hvilke fordeler og ulemper ser du av ? bruke HashMap-er i stedet for 2D-arryaer i Oblig 3? (foresl? mulige n?kkel/verdi-kombinasjoner).
   Hint: Se avsnitt 9.11 p? side 189 i l?reboka for forskjellene mellom arrayer og HashMap-er.
   
   
   

3. HashMap med akronymer:  kap. 9, oppg. 2 (side 193)
   (a) Et akronym er en bokstavkombinasjon som uttrykker noe mer fullstending for eksempel FN = Forente nasjoner.  Lag et program som leser inn en rekke akronymer og deres tolkning fra fil (du finner en fil med akronymer p? bokas hjemmeside: akronymer.txt).  Legg akronymene og tolkningene i en HashMap med akronymet som n?kkel.

   Brukeren skal oppgi et akronym til programmet og f? tilbake en eller flere tolkninger av akronymet.  Det kan maksimalt v?re 10 tolkninger til hvert akronym.  Denne brukerdialogen skal g? i l?kke til brukeren svarer.

   Tips: Lag en klasse der objekter har f?lgende attributter: akronymet og en String-array med tolkninger, samt antall tolkninger.  Pekere til objekter av denne klassen legges i HashMap med akronymet som n?kkel.  Det kan v?re lurt ? lage en metode i denne klassen som legger til en ny tolkning, og som holder orden p? hvor mange tolkninger det er i ?yeblikket.

   API 	Application Programming Interface
   AV 	Audio/Video
   AV 	Authenticity Verification
   BASH 	Bourne Again Shell [Unix]
   EU 	Europaunionen
   FN 	Forente nasjoner
   ...osv...
   

   
   

   (b) Utvid programmet slik at bruker f?r anledning til ? legge til en tolkning dersom den ikke finnes fra f?r.

   
   
   
4. Innstikksortering av kontoer:  (l?reboka side 93)
   Ta utgangspunkt i f?lgende program (som sorterer en heltalls-array og en String-array); og lag en metode som sorterer arrayen kontoer[] fra oppgave nr. 2 (a) ovenfor alfabetisk p? personnavn.  Etter et kall p? metoden skal f.eks. kontoer[0] v?re Elins konto, kontoer[1] Nils sin, osv.  Metoden skal ha to inn-parametre: Konto[] kontoer, og int antKontoer; og skal kunne sortere et vilk?rlig antall kontoer.  Utvid programmet i nr. 2 (a) med et kall p? metoden for ? sjekke at den fungerer.

   class Innstikksort {
   
       /** Sorterer en heltallsarray. */
       public static void sorter(int[] a) {
   	for (int k = 0 ; k < a.length - 1; k++) {
   
   	    if (a[k] > a[k + 1]) {
   		// a[k + 1] st?r p? feil plass, ta den ut:
   		int tmp = a[k + 1];
                   int i = k;
   
   		// Skyv a[i] mot h?yre ett hakk til vi finner
   		// riktig plass til tmp:
   		while (i >= 0 && a[i] > tmp) {
   		    a[i + 1] = a[i];
   		    i--;
   		}
   		// Sett tmp inn p? riktig plass:
   		a[i + 1] = tmp;
   	    }
   	}
       }
   
       /** Sorterer en String-array.  Dette er en redigert utgave av
       metoden ovenfor som jobber med String-array i stedet for int-array. */
       public static void sorter(String[] a) {
   	for (int k = 0 ; k < a.length - 1; k++) {
   	    if (a[k].compareTo(a[k + 1]) > 0 ) {
   		String tmp = a[k + 1];
   		int i = k;
   		while (i >= 0 && (a[i].compareTo(tmp) > 0)) {
   		    a[i + 1] = a[i];
   		    i--;
   		}
   		a[i + 1] = tmp;
   	    }
   	}
       }
   }
   
   /** Test av innstikksortering */
   class TestInnstikksort {
       public static void main(String[] args) {
   
   	int[] a = { 3, 12, 8, 1, 10 };
   	Innstikksort.sorter(a);
   	for (int i = 0; i < a.length; i++) {
   	    System.out.println("a[" + i + "] = " + a[i]);
   	}
   
   	String[] navn = { "Ola", "Kari", "Arne", "Eli" };
   	Innstikksort.sorter(navn);
   	for (int i = 0; i < navn.length; i++) {
   	    System.out.println("navn[" + i + "] = " + navn[i]);
   	}
       }
   }
   
   KJ?REEKSEMPEL:
   a[0] = 1
   a[1] = 3
   a[2] = 8
   a[3] = 10
   a[4] = 12
   navn[0] = Arne
   navn[1] = Eli
   navn[2] = Kari
   navn[3] = Ola
   

Oppgaver til terminaltimen

1. HashMap og innstikksortering:
   (Samme oppgaver som i nr. 1, 2, og 3 for teoritimen).
   
   
   
2. Begynn med Oblig 4:
   Viktigste tema i obligen er HashMap-er, s? det kan v?re lurt ? l?se en enklere oppgave med HashMap f?r du g?r l?s p? Oblig 4, f.eks. oppgave nr. 2 eller 3 for teoritimen.

> javadoc -package Programnavn.java
> firefox index.html &