INF1000 - H?st 2008
Du er her: UiO > 澳门葡京手机版app下载 > Emner > Matematikk og naturvitenskap > Informatikk > INF1000 > h08 > ukeoppgaver >

Ukeoppgaver 8:  13. - 16. okt (INF1000 - H?st 2008)

HashMap (kap. 9.1 - 9.11), oppramstyper (kap. 8.16), innstikksortering (kap. 5.6), og litt om javadoc.

M?l
Forst? forskjellene mellom arrayer og HashMap; og f? litt ?velse i bruk av enum, innstikksortering, og javadoc-kommentarer.

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 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. Oppramstyper: "enum"  (side 158)
    Lag en oppramstype for m?neder (jan, feb,..) og et program som ber bruker taste inn m?nedsnummer (1, 2,..) og gir m?nedsnavnet som svar.  Hint: Se f?lgende eksempel fra side 158 i l?reboka (ogs? gitt p? side 2 i lysarkene uke 8): 
    enum Farge {
    r?d, gr?nn, bl?, gul;
}

class EnumEks {
    public static void main(String[] args) {
	Farge f = Farge.r?d;
	System.out.println("Farge f er:" + f);

	for (Farge ff: Farge.values()) {
	    System.out.println("ff:" + ff + ", nummer:" + ff.ordinal());
	}
    }
} // end class EnumEks

KJ?REEKSEMPEL:
Farge f er:r?d
ff:r?d, nummer:0
ff:gr?nn, nummer:1
ff:bl?, nummer:2
ff:gul, nummer:3


  4. Innstikksortering av kontoer:  (l?reboka side 93; lysark uke 8 s. 36)
    Ta utgangspunkt i programmet fra side 25 og 36 i lysarkene uke 8 (gjengitt under) som sorterer en heltalls-array og en String-array, og lag en metode som sorterer arrayen kontoer[] fra punkt 2 (a) alfabetisk p? navn.  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 punkt 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 */
    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, 1, 7, 14, 2, 156, 77 };
	Innstikksort.sorter(a);
	for (int i = 0; i < a.length; i++) {
	    System.out.println("a[" + i + "] = " + a[i]);
	}

	String[] navn = { "Ola", "Kari", "Arne", "Jo" };
	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] = 2
a[2] = 3
a[3] = 7
a[4] = 14
a[5] = 77
a[6] = 156
navn[0] = Arne
navn[1] = Jo
navn[2] = Kari
navn[3] = Ola

Oppgaver til terminaltimen

  1. HashMap, enum, og innstikksortering:
    (Samme oppgaver som i punkt 2 - 4 for teoritimen).


  2. Fortsett ? jobbe med din Oblig 3.  Se tipsene fra seminaret og Marits objekter.pdf.


  3. Mer om HashMap-er:  (som oppgave 4 i kap. 9, side 195)
    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.


  4. Javadoc:  (lysark uke 8, side 39 - 44)
    Se eksemplene p? javadoc-kommentarer her eller p? side 39 i lysarkene uke 8 og skriv lignende kommentarer i din Oblig 3.  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 som vist p? side 40 i lysarkene: 
    > javadoc -package Programnavn.java
> opera index.html &
    ?pne til slutt den genererte index.html-filen i en browser for ? se p? resultatet.  (NB! Javadoc er ikke et krav i Oblig 3, men du kan godt begynne ? eksperimentere med det allerede n?!). 


  5. Ukens n?tt: Dobbel-sortert utskrift av HashMap  (veldig vanskelig!)
    Lag en metode "void skrivSortert(HashMap <String, Person> register)" som skriver ut innholdet i HashMap-en fra punkt 1 for teoritimen 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.

L?sningsforslag
L?sningsforslagene viser én av mange mulige m?ter ? l?se disse oppgavene p?.