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