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

Tipus de dades simples	Numèriques	Enter, Real
	Alfanumèriques	Caràcter
	Lògiques	Booleà
Tipus de dades compostes o estructures de dades	Estàtiques	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, 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.

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.