Ukeoppgaver 10: 24. okt - 30. okt (INF1000 - Høst 2013)

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

Oppgave merket med nøkkelsymbol er plukket ut som spesielt representativ for de viktigste temaene fra ukens forelesning, og alle bør ha som minimumsmål å løse denne selvstendig.

Oppgaver

1. HashMap: Hva skrives ut?  (Se oversikten på side 190 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 191 i læreboka for forskjellene mellom arrayer og HashMap-er.
   
   

   • Javadoc
     Du kan finne offisielle eksempler på javadoc-kommentarer her og her. Se på noen av disse eksemplene, og skriv lignende kommentarer i din Oblig 3 eller 4. Javadoc-kommentarer startes med /** og avsluttes med */, og plasseres i linjen(e) rett før klassen, metoden, eller objektvariabelen man ønsker å kommentere. Kjør deretter javadoc-kommandoen, og åpne til slutt den genererte index.html-filen i en browser for å se på resultatet:

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

   • Kort og Kortstokk
     Programmer enum Type, som kan være Hjerter, Ruter, Spar eller Kløver. Programmer også public enum Kort, som inneholder en Type og et tall mellom 1-13, og en klasse Kortstokk. Kortstokken skal ta vare på 52 Kort i en beholder (f.eks et array). Programmer en "dealer" som har en kortstokk og skal ha metoder for å kontrollere at alle spillekortene er i Kortstokken og denne skal returnere true hvis kortstokken kan brukes og false hvis kort mangler. Videre skal Dealeren ha metoder for å stokke kortstokken - dette skal da bytte om på rekkefølgen i Kortstokkens beholder (tips bruk Random.nextInt(52) for å finne ut hvilken plass) og for å dele ut kortene. Dette skal i første omgang bare skrive ut rekkefølgen av kortene til skjerm. Lag en metode i Kortstokk som oppretter sine kort og en metode bruk. Bruk random for å finne ut om noen kort blei tapt (og evt hvilke) under bruk. I såfall må du sette dette kortets plass i beholderen tom.

Tibakemelding om dette oppgavesettet kan du sende på mail til ingridgg [a] ifi.uio.no