Diferència entre revisions de la pàgina «DAM-M3-UF5. Estructures de dades»

Revisió del 18:11, 7 set 2012

torna M3 - Programació

Estructures de dades

Tipus de dades

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

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

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

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

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

API. Classes d'utilitat

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.

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

	 	 	 	        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 ("--------------------");

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:

• hasNext(): boolean per detectar si encara hi ha elements
• next(): element retorna el següent objecte de la col·lecció
• remove() esborra el darrer element retornat

Per exemple

        List l = new LinkedList();
        Iterator iter = l.iterator();
        int element = 0;
        while (iter.hasNext()) {
           System.out.println("Element " + element + " " + iter.next());
           element++;
        }