Ukeoppgaver 9:  17. - 23. okt (INF1000 - Høst 2012)

Hashmap, sortering, oppramstyper og litt om Javadoc  (kap. 9 i "Rett på Java" 3. utg.)

Mål
Mer om HashMap, litt om sortering, oppramstyper og Javadoc.

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. 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.

   
   

2. Mer om HashMap: (som oppgave 4 i kap. 9, side 197)
   Finn fram en oppgave du har l?st vha. arrayer, og bytt ut noen av arrayene med HashMap-er. Hvilke deler av programmet blir enklere n?, evt. vanskeligere? Bruk gjerne din egen Oblig 2 eller 3.

   
   

3. Innstikksortering av kontoer: (l?reboka side 95)
   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
   

   
   

4. 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 &
   

   
   

5. 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.
   




* STJERNEOPPGAVER




6. * Innstikksortering
   a) Skriv en metode for ? sorterte tall med innstikksortering. Innstikksortering kan du lese om i Rett p? Java s. 95 (3.utgave). Test programmet ditt p? en heltallsarray av passende st?rrelse.

   b) Hvilke endringer m? gj?res i metoden over for ? kunne sortere strenger? Gj?r disse endringene og test programmet ditt p? ordene fra filen names.txt (hentet fra inf1010, v12, ob4).

   Hint: String har en metode int compareTo(). Sl? opp i API-et og les om denne.

   c) Hvilke endringer m? til for at du skal kunne sortere (andre) objekter? Skriv en klasse Person som skal kunne sammenlignes og sorter en array av Person-objekter.

   Hint: skriv en compareTo() - metode i klassen Person.

   
   

7. * Dobbel-sortert utskrift av HashMap (veldig vanskelig!)
   NB! Denne oppgaven er litt kunstig, vanligvis bruker man ikke HashMap som eneste datastruktur for ? lagre data som skal sorteres. Lag en metode "void skrivSortert(HashMap register)" som skriver ut innholdet i HashMap-en fra oppgave nr. 1 (h11) ovenfor sortert p? alder. Utskriften skal vise alder og navn for personene, og hvis det er flere med samme alder skal disse skrives ut sortert p? navn. For ? teste metoden lager du et objekt av klassen Personer og kaller metoden din via dette objektet, etter ? ha lagt inn 5 personer i HashMap-en: Ida 19, Lars 21, Elin 21, Nils 19, og Anna 19.

   
   

---

Tibakemelding om dette oppgavesettet kan du skrive i bloggen eller sende på mail til siriamj[a] ifi.uio.no