Estructures de dades

Segons Niklaus Wirth (i altres autors) un programa és:

programa = algorismes + estructures de dades

En aquest apartat veurem les formes mes estàndard d'organitzar les dades i proposarem alguns exercicis en Python.

És important aclarir que parlarem de TADs o Tipus Abstractes de Dades. Aquests es defineixen per uns elements contenidors de les dades i unes operacions sobre aquestes. La implementació que se'n pugui fer d'aquestes pot utilitzar eines molt diverses. Per exemple, el TAD stack té les operacions push() i pop() i sempre s'utilitzarà igual, però podem tenir implementacions realitzades amb vectors o amb llistes enllaçades, cadascuna d'aquestes implementacions amb els seus avantatges i inconvenients.

Tipus bàsics que no analitzarem

No poso apunts sobre aquests perquè ja els hem anat veient al llarg del curs, però sempre està bé fer un esment. Per aprofundir podeu llegir l'article d'estructures de dades a la Viquipèdia (aquest cop en català).

• Vector: arranjament d'elements contigus als que accedim per indexació.
  • Avantatges: accés més ràpid
  • Desavantatges: estructura estàtica (tamany fix).
• Matriu: vectors de 2 o més dimensions. De vegades es parla de vector i matriu indistintament.
• Llista: conjunt d'elements dispersos als que es pot accedir seqüencialment.
  • Avantatges: estructura dinàmica (podem afegir, esborrar i insertar elements més eficientment).
  • Desavantatges: accés més lent (seqüencial).

Cua

Una cua (enllaç Wikipedia) és una estructura de dades de tipus FIFO: First In First Out. Té dos extrems (front i back). Les operacions permeses son:

• encuar(e): insertar l'element "e" al final (back) de la cua.
• desencuar(): extreure element del principi (front) de la cua.

No es pot insertar en posicions intermitges ni es poden extreure elements del mig. Les operacions, doncs, estan limitades a aquestes dues. Podem afegir una funció auxiliar que resulta útil:

• esbuida(): retorna True si està buida i False si hi ha algun element.

Exemple en Python

Suposant que tenim la class Cua() implementada (ja veieu que us tocarà a vosaltres fer-la ;P ), s'utilitzaria d'aquesta manera:

class Cua(object):
   ...
>>> c = Cua()
>>> c.encua(10)         # c = [10]
>>> c.encua(23)         # c = [10,23]
>>> c.encua(79)         # c = [10,23,79]
>>> num = c.desencua()  # num = 10 ; c = [23,79]
>>> print num           # comportament FIFO: ha sortit el primer d'entrar (10)
10

Pila o stack

Una pila (enllaç Wikipedia) és una estructura de dades de tipus LIFO: Last In First Out. Té un sol extrem: el top. Les operacions permeses s'efectuen sempre en el "top" i son:

• Push: insertar element.
• Pop: extreure element.
• Peek: llegir l'element del top però sense extreure'l.

No es pot insertar ni extreure en posicions intermitges ni per cap altre extrem que no sigui el "top".

Exemple en Python

Suposant que tenim la class Pila() implementada (ja veieu que també us tocarà a vosaltres fer-la ;P ), s'utilitzaria d'aquesta manera:

class Pila(object):
   ...
>>> p = Pila()
>>> p.push(10)       # c = [10]
>>> p.push(23)       # c = [10,23]
>>> p.push(79)       # c = [10,23,79]
>>> num = p.pop()    # num = 79 ; c = [10,23]
>>> print num        # comportamet LIFO: ha sortit l'últim d'entrar (79)
79

Aplicacions típiques de la pila:

• Resolució d'operacions matemàtiques algebraiques.
• Mecanismes d'aniuament com els contexts d'execució d'una CPU.
  • Segur que tots heu consultat alguna dia la web Stack Overflow: http://stackoverflow.com . Aviam si algú sap explicar de què va aquest nom.
• Algorismes de backtracking (exploració de totes les possibilitats de resolució d'un problema).
• ...

Arbres

...

Diccionaris o hash tables

...

Exercicis

1- Implementacions en Python

Implementeu les classes Cua() i Pila() derivant-les de la classe list nativa de Python. La classe list ja disposa de mètodes que poden equivaldre al de les estructures cua i pila, però volem que tinguin els noms dels mètodes tal i com estan en el TAD.

• Cua: mètodes encua(elem), desencua() i esbuida()
• Pila: mètodes push(elem), pop(), peek() i esbuida()

Per saber més mireu les descripcions dels mètodes fetes més amunt.

2- Comprovador d'operacions matemàtiques algebraiques

...