Poglavje 8
Delo s podatki

Za učinkovito shranjevanje podatkov v pomnilniku programer uporabi primerno zbirko podatkov. Najosnovnejšo zbirko, tabelo, že poznamo. Zbirke se med seboj razlikujejo predvsem po tem, na kakšen način so podatki v njih shranjeni (katero podatkovno strukturo uporabljajo). Za različne namene se uporabljajo različne podatkovne strukture, na primer,

Posamezno podatkovno strukturo lahko izvedemo (implementiramo) na različne načine: z linearnim seznamom, z drevesom, z zgoščeno tabelo, in podobno. Od izvedbe podatkovne strukture je odvisno, kako hitro bodo posamezne operacije delovale.

Poleg tabele, ki je osnovna zbirka za shranjevanje podatkov, Java ponuja tudi nekatere druge zbirke. Glavni slabosti tabele sta: fiksna velikost ter počasno dodajanje podatkov na začetek. Te slabosti lahko z drugimi zbirkami odpravimo.

Java ponuja dva vmesnika za delo z zbirkami: java.util.Collections in java.util.Map. Prvi je namenjen hranjenju podatkov, po katerih se sklicujemo s celoštevilskim indeksom (podobno kot pri tabeli), drugi pa hranjenju podatkov, kjer za sklicevanje uporabimo nek ključ - podatki so v tem primeru tipa (ključ, vrednost).

Oba vmesnika imate veliko konkretnih implementacij. Nekatere med njimi so:

Collection  
    Set             <- HashSet  
        SortedSet   <- TreeSet  
    List            <- ArrayList  
                    <- LinkedList  
 
Map                 <- HashMap  
    SortedMap       <- TreeMap

Podrobneje na  http://java.sun.com/docs/books/tutorial/collections/

8.1 Vmesnik java.util.Collection

Vmesnik java.util.Collection predvideva osnovne operacije nad zbirkami unarnih podatkov. Med drugimi predpisuje naslednje metode:

Metoda Opis




boolean add(Object o)

Dodaj element v zbirko


boolean remove(Object o)

Odstrani element iz zbirke


int size()

Vrni velikost zbirke


boolean contains(Object o)

Ali zbirka vsebuje element?


boolean isEmpty()

Ali je zbirnka prazna?


void clear()

Sprazni zbirko


Iterator iterator()

Omogoča sprehod po vseh elementih zbirke
 

Razrede, ki implementirajo vmesnik Collection delimo na dva dela - razredi za delo z množicami in razredi za delo s seznami.

Štiri najbolj znani razredi, ki implementirajo vmesnik Collection so: HashSet, TreeSet, ArrayList in LinkedList. Iz uporabniškega stališča je glavna razlika med omenjenimi razredi

  1. nekateri hranijo elemente v urejenem vrstnem redu, drugi pa ne
  2. hitrost operacij dodaj/išči/briši...

 

8.1.1 Iterator

Vmesnik Collection predvideva metodo iterator() - ta vrne objekt, ki implementira vmesnik Iterator. Iterator uporabimo za sprehod čez podatke, med sprehodom lahko podatke tudi spreminjamo ali brišemo. Iterator pozna naslednje metode:

Metoda Opis




public boolean hasNext()

Ali je na voljo še kakšen podatek?


public Object next()

Naslednji podatek


public void remove()

Zbriši trenutni podatek

 

Naloga 8-I. Napiši program, v katerem boš imena dni v tednu shranil v strukturi množica. Vsa imena nato izpiši s pomočjo iteratorja.  
Rešitev naloge 8-I.: Dnevi v tednu zbirke/Teden.java

 

8.1.2 Množice (Set)

Vmesnik Set (podrazred razreda Collection) definira operacije podatkovne strukture množica. V množici ni duplikatov. Poznamo dve izvedbi množic:

HashSet ..... množica implementirana je s pomočjo zgoščene tabele; elementi niso urejeni (niti ne nastopajo v vrstnem redu, kot smo jih dodajali!).

SortedSet ... množica implementirana s pomočjo uravnoteženega binarnega drevesa; elementi so urejeni po abecednem vrstnem redu

8.1.3 Seznam (List)

Vmesnik List (podrazred razreda Collection) definira operacije podatkovne strukture seznam. V seznamu so elementi v določenem vrstnem redu. Poznamo pojem i-ti element (podobno kot pri tabeli). Dodatne metode:

Metoda Opis




boolean get(int index)

Vrne element pri danem indeksu


boolean set(int index, Object elm)

Spremeni element pri danem indeksu


boolean add(int index, Object elm)

Doda element na točno določeno mesto


boolean remove(int index)

Odstrani element


int indexOf(Object elm)

Vrne indeks elementa


ListIterator listIterator()

Omogoča sprehod čez podatke

 

Med razredi, ki implementirajo vmesnik List se najpogosteje uporablja razred ArrayList. Uporabljamo ga na podoben način kot navadno tabelo (sklicevanje po celoštevilskem indeksu), najpomembnejša razlika pa je v tem, da velikost (število podatkov, ki jih lahko hrani) ni določena na začetku (gre torej za neke vrste tabelo, ki “diha”).

Naloga 8-II. Napiši metodo seznamDeliteljev(int n), ki vrne seznam (ArrayList) deliteljev števila n. V metodi main s pomočjo iteratorja izpiši vsebino seznama, ki ga vrne klic metode seznamDeliteljev(42).  

Rešitev naloge 8-III.: Seznam deliteljev danega števila zbirke/Delitelji.java

 

8.2 Slovarji - vmesnik java.util.Map

Slovar je zbirka podatkov, v kateri do posameznega podatka dostopamo preko ključa. V slovarju torej hranimo pare (ključ, vrednost). Razlika med slovarjem in tabelo: pri tabeli do posameznega elementa dostopamo preko celoštevilskega indeksa (a[i]), pri slovarju pa preko ključa (simbolično bi to lahko zapisali kot a[kljuc]), pri čemer je ključ poljuben objekt. Ključi morajo biti enolično določeni (t.j. enemu ključu lahko pripada samo ena vrednost). Kljuci se medseboj primerjajo z metodo equals - dva ključa sta enaka, če velja key1.equals(key2).

Osnovne metode vmesnika java.util.Map:

Metoda Opis




public int size()

Velikost zbirke


public boolean isEmpty()

Ali je zbirka prazna?


public boolean containsKey(Object key)

Ali zbirka vsebuje dani ključ?


public boolean containsValue(Object value)

Ali zbirka vsebuje dano vrednost?


public Object get(Object key)

Vrne vrednost pri danem ključu


public Object put(Object key, Object value)

Nastavi vrednost pri danem ključu


public Object remove(Object key)

Odstrani vrednost pri danem ključu


public Set keySet()

Vrne množice vseh ključev v zbirki


public Collection values()

Vrne množico vseh vrednosti v zbirki

 

Naloga 8-III. Napiši program, ki v slovarju hrani število dni posameznega meseca. Vse podatke iz slovarja nato izpiši s pomočjo iteratorja.  

Rešitev naloge 8-III.: Meseci v letu zbirke/Meseci.java

 

8.3 Orodja za delo z zbirkami

Pri delu z zbirkami Java ponuja mnogo metod, ki olajšajo delo. Spodaj so naštete le nekatere od njih.

java.util.Collections.sort(List list)  
    sorl(List)      ... uredi seznam  
    max(Collection) ... vrne najvecji element zbirke  
    min(Collection) ... vrne najmanjsi element zbirke  
    replaceAll(List, Object, Object) ... zamenja vse pojavitve  
    swap(List list, int i, int j) ... zamenja dva elementa zbirke  
 
java.util.Array.sort(Object[]) ... uredi tabelo objektov  
java.util.Array.sort(Object[], Comparator c)

8.4 Razbitje niza na dele

Programer se pogosto sreča z naslednjim problemom: imamo niz, ki vsebuje podnize, ločene z nekim ločilom (npr. podniz1 : podniz2 : podniz3). Niz bi radi razbili na posamezne komponente (podniz1, podniz2, ...). Problem lahko rešimo vsaj na dva načina:

Reitev 1: na objektu razreda String lahko kličemo metodo split, ki vrne tabelo podnizov

 

  String a="Micka:Kovaceva"; 
  String podnizi[] = a.split(":"); 
  System.out.println(podnizi[0]); // Micka

Reitev 2: Uporabimo StringTokenizer - ta vsebuje metode hasMoreElements() in nextElement().

 

  String a="Micka:Kovaceva"; 
  StringTokenizer stk = new StringTokenizer(a, ":"); 
  while (stk.hasMoreElements()) 
    System.out.println(stk.nextElement());

StringTokenizer se uporablja podobno kot Iterator, razlika je predvsem v tem, da gre pri StringTokenizer-u za starejšo obliko sprehoda čez podatke, kar posledično med drugim pomeni, da podatkov med sprehodom ne moremo spreminjati.

8.5 Primer uporabe podatkovnih zbirk - smučarsko tekmovanje

Naloga 8-IV. V datoteki drzave.txt so zapisani podatki o državah, ki sodelujejo na smučarskih tekmovanjih (glej spodaj). Izdelaj razred Drzava za hranjenje podatkov o eni državi, nato preberi podatke iz datoteke drzave.txt v slovar (ključ: kratica države, vrednost: objekt razreda Drzava). Pravilnost delovanja ugotovi z naslednjimi testi:

 

Del datoteke drzave.txt:

RUS:Moskva:142754000  
SMR:San Marino:27336  
SVK:Bratislava:5414937  
SLO:Ljubljana:2040788  
SRB:Beograd:10147398  
ESP:Madrid:45283259  
SWE:Stockholm:9110972  
CHE:Bern:7782900  
TUR:Ankara:71158647

Rešitev naloge 8-IV. - 1. del: Razred Drzava – podatki o državi udeleženki OI fis/Drzava.java

 

Rešitev naloge 8-IV. - 2. del: Branje podatkov o državah in test delovanja fis/Drzave.java

 

Naloga 8-V. Podatki o najboljših smučarkah so napisani v datoteki tocke.txt. Ustvari razred Tekmovalec, ki hrani podatke o enem tekmovalcu, nato preberi podatke iz datoteke tocke.txt v pomnilnik. Tekmovalce izpiši urejene po abecednem vrstnem redu po priimkih.  

Primer datoteke slalom.txt:

T. MAZE:SLO  
D. KARBON:ITA  
M. ROBNIK:SLO  
E. GORGL:AVT  
A. DREV:SLO  
T. POUTIAINEN:FIN  
J. MANCUSO:ZDA  
K. ZETTEL:AVT  
N. HOSP:AVT  
K. HOLZL:NEM  
I. JACQUEMOD:FRA  
N. GIUS:ITA

Podatke o tekmovalkah bomo prebrali v Arraylist (ker ne vemo, koliko jih je, ne moremo uporabiti navadne tabele). Za urejanje izpisa bomo uporabili vgrajeno metodo sort (zato moramo implementirati vmesnik Comparable ).

Rešitev naloge 8-V. - 1. del: Razred Tekmovalec – podatki o tekmovalcu fis/Tekmovalec.java

 

Rešitev naloge 8-V. - 2. del: Branje tekmovalcev in izpis fis/Tekmovalci.java

 

Naloga 8-VI. Izpiši države najboljših tekmovalk, urejene po abecednem redu.  

Uporabili bomo urejeno množico (da preprečimo podvajanje in da zagotovimo urejenost).

Rešitev naloge 8-VI.: Izpis držav po abecednem redu fis/DrzaveTekmovalk.java