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