Mostra la font per a Estructures de dades

[[Fitxer:Wirth.jpg|thumb|dreta]]

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'[http://ca.wikipedia.org/wiki/Estructura_de_dades 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 ==
[[Fitxer:queue.png|thumb|dreta]]

Una cua ([http://es.wikipedia.org/wiki/Cola_%28inform%C3%A1tica%29 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:
<syntaxhighlight lang="Python">
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
</syntaxhighlight>
<br>

== Pila o ''stack'' ==
[[Fitxer:stack.png|thumb|dreta]]

Una pila ([http://es.wikipedia.org/wiki/Pila_%28inform%C3%A1tica%29 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(e)''': inserta l'element "e" a la pila.
* '''pop()''': llegir i extreure l'element del ''top''.
* '''peek()''': llegir (sense extreure) l'element del ''top''.

No es pot insertar ni extreure en posicions intermitges ni per cap altre extrem que no sigui el "top". També podem definir la funció auxiliar:
* '''esbuida()''': retorna ''True'' si la pila està buida i ''False'' si hi ha algun element a dins.

=== 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:
<syntaxhighlight lang="Python">
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
</syntaxhighlight>
<br>

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). El típic sol ser el de cercar la sortida d'un laberint.
* Aquí trobareu alguns [http://gilberto2112.brinkster.net/programaconkarel/ejemplos_aplicacion_pilas.pdf exemples d'aplicacions de piles] dels que hem comentat, en particular el del laberint i el de resolució d'operacions algebraiques.

<br>

== Arbres ==
...
<br>

== Diccionaris o ''hash tables'' ==
...
<br>

== 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'expressions matemàtiques algebraiques ===
Utilitzeu les classes Cua() i Pila() definides en l'anterior exercici per resoldre un comprovador d'expressions matemàtiques.

Un exemple d'expressió algebraica correcta seria:
 25+3*(1+2+(30*4))/2

Exemples erronis:
 25+3*(1+2+(30*4))/'''('''2
 25+3*(1+2+(30*4))/''')'''2'''('''
 25+3*(1+2)+(30*4)''')'''/2

Com que realitzar el càlcul d'una expressió algebraica és complicat, limitarem l'exercici a comprovar que els parèntesis siguin correctes.

L'algorisme ha de fer:
# Extreure els parèntesis de l'expressió i ficar-los en la '''Cua'''. En l'exemple (bo) de més amunt ens quedarien els següents elements a la cua: <pre>['(','(',')',')']</pre>
# Extreure element per element de la '''Cua''' i avaluar-lo utilitant la '''Pila''':
#* Si és "(" el fiquem a la pila.
#* Si és ")" extraiem un element de la pila. Si és un "(" tot ok. Si hem esgotat la pila, és que hi ha un error.
# Al final de l'algorisme la pila ha d'estar buida, altrament és que hi ha algun error.
<br>

=== 3- Avaluador d'expressions matemàtiques ===
Farem una versió simplificada d'un avaluador d'expressions matemàtiques. Aplicarem certes restriccions per facilitar l'aplicació.

Restriccions (constraints):
* A l'expressió només hi pot haver:
** Nombres sencers positius: 1, 10, 215, etc.
** Parèntesis: ( i )
** Operadors: + - / *
* Les operacions s'han de fer obligatòriament en grups de 2 operands. No podem fer 2+10+12, per exemple. Si volem fer això caldrà fer (2+10)+12
* S'han de posar parèntesis explícits per avaluar l'expressió (en grups de dos).

Exemples correctes:
 (3+5)
 (6+((1+12)/2))
 (((18+3)*2)+4)

Exemples incorrectes:
 3+5      => (3+5)
 (6+3/2)  => ((6+3)/2)

Amb aquestes restriccions serà més fàcil fer l'aplicació de resolució d'expressions matemàtiques.

==== Tokenitzador ====
Abans que res caldrà '''tokenitzar''' l'expressió que ens ve en un string. Un "token" és  un element significatiu per l'aplicació, com un número, un operador o un parèntesi.

Cal fer una funció ''tokenitza(s)'' que ens transformarà l'expressió en elements lògics: un string són caràcters sense significat; en canvi, després de "tokenitzar" tindrem elements significatius amb els què operar:

Exemple: abans de tokenitzar:
 (6+((1+12)/2))

Després de tokenitzar, tindrem els següents elements (en una llista).
 ( , 6 , + , ( , ( , 1 , + , 12 , ) , / , 2 , ) , )

La dificultat està en extreure els nombres. Els altres elements són molt fàcils perquè son d'un sol caràcter (parèntesis i operands).

==== Algorisme simplificat ====
Penseu que aquest algorisme de resolució d'expressions és una versió simplificada per les expressions que hem descrit anteriorment.

# Entrar expressió
# Tokenitzar-la i introduïr-la a l'objecte Cua()
# Avaluar l'expressió amb l'ajuda de l'objecte Pila(). Anem tibant els elements de la cua i...
## Si és qualsevol cosa menys un ")" ho posem a la pila.
## Si és un ")" avaluem els 3 darrers elements (número + operador + número)
## Extraiem el "(" de la pila (si no hi és, és que hi ha error)
## Col·loquem el resultat a la pila

Al final el resultat ha d'estar disponible a la pila.

[[Fitxer:expressions matematiques.png|800px]]

<br>

=== 4- Laberint (Maze) ===
Resoldrem la sortida d'un laberint amb 2 algorismes diferents: recursiu i amb pila (stack).

Contindrem el laberint en una matriu. Indica a cadascuna de les cel·les si té:
* * = mur
* . = espai buit
* I = Inici (només pot haver 1)
* F = Final (només pot haver 1)

S'entén que no es pot sortir de la matriu (ens envolta un mur) i que cal començar per la cel·la d'inici (I) i resoldrem el joc quan arribem al final (F).

El programa ha de poder:
# Generar un laberint (matriu) a partir d'un fitxer de text. Podeu agafar el del final per provar, però genereu-ne vosaltres més. Convindria que chequejés que té 1 sol inici (I) i un sol final (F).
# Mostrar laberint.
# Trobar la sortida del laberint. Ha retornar una llista amb les posicions a recórrer des del inici (I) fins el final (F).
# Mostrar laberint + camí de sortida.
# Sortir

Podeu agafar aquest exemple per començar el laberint:
 I*....
 .*.***
 ...*..
 ..*...
 ....*.
 **.*.F

És el mateix que en aquesta web, però invertit perquè quadrin les files:
http://www.laurentluce.com/posts/solving-mazes-using-python-simple-recursivity-and-a-search/

Llegeix també l'article sobre [[Algorisme de backtracking]] a cacauet.org

<div class="exercici">
IMPORTANT PER ENTREGAR:
* Implementar el programa en un objecte Laberint com s'indica a [[Algorisme de backtracking]].
* Afegir les funcionalitats que demana l'exercici (menú)
* Implementar un '''mètode ''soluciona(nom_fitxer)''''' que busqui la cel·la d'inici i retorni una llista amb la solució fins la sortida.
</div>

<br>