Mostra la font per a DAM-M3-UF5. Estructures de dades

torna [[ M3 - Programació ]]

== Estructures de dades ==

=== Tipus de dades ===

La majoria de llenguatges de programació classifiquen les dades de la següent manera


{| border="1" cellspacing="1" cellpadding="8" class="table"
|-
| rowspan="3" | Tipus de dades simples 
| valign="TOP" | Numèriques 
| valign="TOP" | ''Enter, Real''
|-
| Alfanumèriques 
| ''Caràcter''
|-
| Lògiques 
| ''Booleà''
|-
| rowspan="7" | Tipus de dades compostes o estructures de dades
| valign="TOP" | Estàtiques 
| valign="TOP" | ''Vectors, matrius, registres''
|-
| Dinàmiques
| ''Piles, cues, llistes, arbres, conjunts''
|-
| Homogènies
| ''Vectors, matrius, piles, cues, llistes, arbres, conjunts''
|-
| Heterogènies
| ''Registres''
|-
| Accés per posició
| ''Vectors, matrius''
|-
| Accés per nom
| ''Registres''
|-
| Accés per clau
| ''Piles, cues, llistes, arbres, conjunts''
|}


Les estructures de dades són agrupacions d’elements que alhora poden ser dades simples o altres estructures.

Classificació segons l’emmagatzemament de les dades

* Estructures de dades '''estàtiques''': Es componen per un nombre fixa d’elements.

* Estructures de dades '''dinàmiques''': Es componen per un nombre variable d’elements. 	Per tant es poden afegir i treure elements en temps d’execució.

Classificació segons el tipus d’elements que les componen

* Estructures de dades '''homogènies''': Els elements que les componen són tots del mateix tipus

* Estructures de dades '''heterogènies''': Es componen per elements que poden ser de diferent tipus.

Classificació segons el mètode d’accés

* Per posició: Cal indicar la posició per accedir a un element.

* Per nom: Cal indicar el nom per accedir als diferents elements.

* Per clau: Cada element té una clau que permet accedir-hi.

A més per a cada estructura també cal definir quines són les operacions que s’hi pot realitzar

Per exemple amb un enter es poden fer sumes, restes, etc. Mentre que amb un booleà es faran operacions lògiques.

Amb les estructures de dades també cal definir les operacions disponibles, per exemple sobre un vector podem tenir una operació de lectura d’un element o una altra d’ordenació dels seus elements.

=== Estructures dinàmiques ===

En Java, les estructures de dades estàtiques s'implementen amb vectors simples i els registres amb classes sense mètodes.

Són més interessants les estructures dinàmiques, breu explicació.

Una estructura dinàmica és un conjunt variable d’elements, aquests elements s'anomenen '''nodes''', i estan '''enllaçats''' (lligats)  uns amb els altres, així un node està format per,
* Un o més enllaços
* Dades, en general un objecte per node

Aquestes estructures les podem recórrer, afegir i treure elements i d’altres operacions específiques.

Cal destacar que les estructures dinàmiques s'emmagatzemen en un espai diferent de memòria (heap, en comptes de a l'espai de dades), i que en principi no tenen limitacions de mida, al contrari que les estructures estàtiques.

Aquestes estructures poden ser de molts tipus diferents segons el seu comportament, el nombre d'índex que defineixen, el nombre d'elements que relacionen, però es poden agrupar segons si són:

* Estructures Lineals: cada node s'enllaça només amb el següent i opcionalment amb l'anterior
** '''Cua'''. Una cua és una estructura de dades de tipus FIFO. Només es pot accedir a la cua pel final (No està permès colar-se). Els elements entren per la cua i surten pel principi.
** '''Pila'''. Una pila és una estructura de dades de tipus LIFO. Només es pot accedir a la pila pel seu cim (top). Els elements entren pel cim i surten per aquest, de manera que no es pot desempilar un element mentre tingui altre elements per sobre.
** '''Llista'''. Una llista és una seqüència de nodes ordenada on cada elements manté referències al següent i/o anterior. És una estructura més general que les piles o les cues ja que permet afegir i treure elements de qualsevol punt de la llista. De fet piles i cues es poden implementar a partir de les llistes.
** '''Conjunts'''. Un conjunt és una col·lecció d’objectes. Aquests objectes han de ser diferenciables. En un conjunt no importa l’ordre i els elements no estan mai repetits. Es defineix el conjunt buit com el que no té cap element. C = {}, el conjunt universal aquell que els té tots. Es diu que dos conjunts són iguals si tenen els mateixos elements.
* Estructures no lineals: cada node s'enllaça amb múltiples nodes
** '''Arbres'''. Els arbres per contra són estructures no lineals. En general un node té molts successors i un únic predecessor. Donada la seva estructura són de gran utilitat per a realitzar cerques amb un cost molt baix.
** '''Grafs'''. Aquesta és la estructura més complexe doncs permet enllaçar un node amb qualsevol altre.

=== API. Classes d'utilitat ===

[[File: collectionapi.png]]

[[File:CollectionHierarchy.png]]


Aquest esquema representa de manera sintetitzada una relació de les interfases (<< ... >>) i classes que ofereix Java per treballar amb les estructures dinàmiques.

Cal notar que aquestes classes tenen moltes operacions i per tant abans de fer servir una estructura dinàmica i posar-se a implementar-la és aconsellable donar una ullada a l’API i comprovar si tot allò que necessitem ja està fet.

L’únic inconvenient és que Java no ofereix encara estructures específiques per a arbres.

Totes aquestes classes (pq implementen interfaces comuns) tenen molts mètodes similars.


* '''Collection''': Interface genèrica que representa un conjunt d'elements sense ordre
** '''List''': ''Collection'' amb ordre, admet duplicats
** '''Set''': ''Collection'' sense ordre, sense duplicats
*** '''SortedSet''': Afegeix ordre entre els elements
** '''Queue''': ''Collection'' amb operacions per al funcionament de Cua, afegir pel final (offer), treure pel principi (poll) i consultar el cap de la cua (peek)

Com a comentari, tenir en compte que sempre que una col·lecció gestioni l'ordre dels seus elements, cal que aquests (La classe dels objectes que la componen), implementin la interface Comparable i per tant defineixin quin és l'ordre entre objectes.


A part de la necessitat d'establir o no un ordre entre els elements, o bé el requeriment de comportaments específics (Cua o Pila per exemple), les diferències entre unes estructures o altres resideix en temes de rendiment, per exemple unes són millors per inserció i d'altres per l'accés a un element.


Per exemple, ús de la classe ''LinkedList''. Afegir, treure, conté? i mida

<html>
<pre>
<code class='java'>
    System.out.println ("Llista Java Demo");
    System.out.println ("--------------------");
    List l = new LinkedList();
    for (int i=0; i<=100; i++ ) {
       l.add(new Integer(i));
    }

    System.out.println("Està 35 " + l.contains(new Integer(35)));
    System.out.println("longitud " + l.size());
    for (int i=100; i>=0; i-- ) {
       l.remove(new Integer(i));
    }
    System.out.println("longitud " + l.size());
    System.out.println ();
    System.out.println ("--------------------");

</code>
</pre>
</html>

=== Iteradors ===

Un Iterador és una eina que permet recòrrer una col·lecció d'elements.

El concepte d'Iterador apareix en múltiples llenguatges i en infinitat de situacions.

Totes les estructures de l'API de java implementen la interface ''<<Iterable>>'', aquesta interface obliga a crear un mètode ''iterator()'' que retorna un iterador sobre els elements.


Un iterador té les operacions següents:
* <code class='java'>hasNext(): boolean</code>  per detectar si encara hi ha elements
* <code class='java'>next(): element</code>  retorna el següent objecte de la col·lecció
* <code class='java'>remove()</code>  esborra el darrer element retornat


Per exemple
<html>
<pre>
<code class='java'>
        List l = new LinkedList();
        Iterator iter = l.iterator();
        int element = 0;
        while (iter.hasNext()) {
           System.out.println("Element " + element + " " + iter.next());
           element++;
        }
</code>
</pre>
</html>

=== Tipus genèrics ===

Les col·leccions admeten qualsevol tipus de dada.

Per evitar la problemàtica del casting, Java permet definir classes i mètodes genèrics, sense usar aquest sistema caldria treballar  amb elements de la classe Object.

Per usar els tipus genèrics s'utilitza els símbols "< ''tipus'' >".

Les interfaces, classes i mètodes de l'arbre de les col·leccions estan adaptades per permetre l'ús dels genèrics.

A l'API es pot detectar quines classes i mètodes admeten genèrics si tenen la cadena '''"<E>"'''.

<html>
<pre>
<code class='java'>
public class Persona implements Comparable<Persona> {
...
}

TreeSet<Persona> persones = new TreeSet<Persona>();


Iterator<Persona> iter = persones.iterator();
</code>
</pre>
</html>

=== Control de repetits ===

Les implementacions de Set han de tenir dues propietats, sense ordre i sense duplicats ==> (HashSet)

Aquesta responsabilitat queda per al responsable de la implementació, a través dels mètodes
* ''hashCode():int'', aquest mètode indica com calcular la clau hash per accedir a l'element. Dos elements iguals han de generar la mateixa clau.
* ''equals(o:Object):boolean'', aquest mètode defineix quan dos elements són iguals

Per exemple
<html>
<pre>
<code class='java'>
public class Persona {
    private String nom;
    private String dni;
    private int edat;
    public Persona(String nom, String dni, int edat) {
        super();
        this.nom = nom;
        this.dni = dni;
        this.edat = edat;
    }
    public String getNom() {
        return nom;
    }
    public void setNom(String nom) {
        this.nom = nom;
    }
    public String getDni() {
        return dni;
    }
    public void setDni(String dni) {
        this.dni = dni;
    }
    public int getEdat() {
        return edat;
    }
    public void setEdat(int edat) {
        this.edat = edat;
    }
    // Sense definir "equals", no es pot determinar quan dos elements són iguals
    // (No controla repetits)
    public boolean equals(Object a) {
        return this.nom.equals(((Persona) a).getNom());
    }
   
    // hashCode calcula la clau hash que permet recuperar un element
    // Si dos elements tenen la mateixa clau van al mateix lloc
    public int hashCode () {
        return this.nom.hashCode();
    }
}


// Ús de la classe

        Persona p;
       
        // Sense duplicats
        HashSet persones = new HashSet();
        persones.add(new Persona("P1", "1111111Z", 23));
        persones.add(new Persona("P2", "2222222Z", 24));
        persones.add(new Persona("P3", "3333333Z", 25));
        persones.add(new Persona("P3", "3333333Z", 25));
   
        // Sense ordre i sense definir operació hashCode aquesta iteració retorna ordres aleatoris
        // Cada vegada es calcula hashCode diferent
        Iterator<Persona> iter = persones.iterator();
        while (iter.hasNext()) {
            p = iter.next();
            System.out.println(p.getNom() + " " +p.getDni() + " " + p.getEdat());
        }
</code>
</pre>
</html>

=== Ordenació ===

Les implementacions de SortedSet gestionen sense duplicats i amb ordre  ==> (TreeSet)

Aquesta responsabilitat recau en el responsable de la implementació
* Interface <code class='java'>Comparable<E></code>
* mètode <code class='java'>compareTo(o:Object):int</code>

Si no s'implementa aquest mètode es genera una excepció quan es treballa amb aquesta estructura

<html>
<pre>
<code class='java'>
public class Persona implements Comparable<Persona> {
    private String nom;
    private String dni;
    private int edat;
    public Persona(String nom, String dni, int edat) {
        super();
        this.nom = nom;
        this.dni = dni;
        this.edat = edat;
    }
    public String getNom() {
        return nom;
    }
    public void setNom(String nom) {
        this.nom = nom;
    }
    public String getDni() {
        return dni;
    }
    public void setDni(String dni) {
        this.dni = dni;
    }
    public int getEdat() {
        return edat;
    }
    public void setEdat(int edat) {
        this.edat = edat;
    }
   
    public int compareTo(Persona p) {
        return this.nom.compareTo(p.getNom());
    }
}
</code>
</pre>
</html>

=== Mapes ===

Accés indexat. Sense repetits per clau '''HashMap''' (Sense ordre, per garantir l'ordre dels elements '''TreeMap''')

<html>
<pre>
<code class='java'>
Map<Integer, String> exempleBuit = new HashMap<Integer, String>();


exempleBuit.put(1, "text qualsevol");
System.out.println(exempleBuit.get(new Integer(100))); // Clau no existeix

Map<Integer, String> exempleErrors = new HashMap<Integer, String>() {{
	put(100, "Aquest projecte ja existeix");
	put(101, "Cal indicar la empresa");
	put(102, "Cal indicar les tasques");
	put(103, "El salari no pot ser negatiu");
	put(104, "Cal incloure alguna tecnologia");
	put(200, "No existeix aquest projecte");
	put(400, "El valors permesos per al sexe són \"H\" i \"D\"");
	put(500, "Error desant el Curriculum");
	put(501, "Error carregant el Curriculum");

}};

exempleErrors.put(601, "Altre missatge");

System.out.println(exempleErrors.get(new Integer(100)));


Map<String, String> exempleErrorsCodi = new	HashMap<String, String>() {{
	put("ERROREXI", "Aquest projecte ja existeix");
	put("ERROREMP", "Cal indicar la empresa");
	put("ERRORTAS", "Cal indicar les tasques");
}};

exempleErrorsCodi.put("ERRALT", "Altre missatge"); 

System.out.println(exempleErrorsCodi.get("ERRORALT"));  

</code>
</pre>
</html>


Compte!! El mètode '''put''' en cas d'indicar una clau repetida, reemplaça el valor existent

Altres mètodes per HashMap<K,V>

<html>
<pre>
<code class='java'>
clear()

size():int

remove(Object key): V;

values(): Collection<V>

keySet(): Set<K>
</code>
</pre>
</html>