El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Què són les estructures de dades?

Següent ►
►

Benvingut al curs d'Estructures de Dades. En aquesta primera lliçó respondrem la pregunta fonamental que dona nom al curs: què és exactament una estructura de dades? Entendre bé aquesta definició —i la diferència entre allò que una estructura promet fer i com ho fa per dins— et donarà el marc mental sobre el qual es recolza tota la resta. A més, coneixeràs TaskFlow, l'aplicació de gestió de tasques que construirem peça a peça al llarg del curs i que ens servirà de fil conductor perquè cada concepte tingui una aplicació real des del primer dia.

Contingut

  1. Definició formal: dades, relacions i operacions
  2. Analogies quotidianes per entendre-ho millor
  3. Tipus Abstracte de Dades (TAD) vs implementació concreta
  4. Presentem TaskFlow: el nostre projecte del curs
  5. Les necessitats de dades de TaskFlow

Definició formal: dades, relacions i operacions

Una estructura de dades és una manera d'organitzar informació a la memòria d'un ordinador per poder treballar-hi de manera eficaç. Però aquesta frase, tot i ser correcta, es queda curta. La definició formal té tres components, i tots tres són igual d'importants:

  • Dades: els valors que volem emmagatzemar (nombres, textos, objectes...).
  • Relacions: com es connecten aquests valors entre si (l'un darrere l'altre, en jerarquia, en xarxa...).
  • Operacions: quines accions podem fer-hi (inserir, cercar, esborrar, recórrer...).

Ho podem resumir en una fórmula informal:

Estructura de dades = Dades + Relacions entre les dades + Operacions permeses

Vegem què significa cada component amb un exemple mínim en Python:

# Dades: tres titols de tasques
tasques = ["Dissenyar el logo", "Escriure l'informe", "Revisar el pressupost"]

# Relacions: l'ordre importa. "Dissenyar el logo" va ABANS que "Escriure l'informe".
# L'estructura (una llista) mante aquesta relacio d'ordre per nosaltres.

# Operacions: l'estructura defineix que podem fer
tasques.append("Enviar la factura")     # inserir al final
primera = tasques[0]                    # accedir per posicio
tasques.remove("Escriure l'informe")    # eliminar un element

print(tasques)
# ['Dissenyar el logo', 'Revisar el pressupost', 'Enviar la factura']

Analitzem l'exemple línia a línia:

  • tasques = [...] crea l'estructura i emmagatzema les dades (tres cadenes de text).
  • La relació aquí és l'ordre seqüencial: cada tasca té una posició, i aquesta posició significa alguna cosa (per exemple, prioritat d'execució). Si l'ordre no importés, potser una altra estructura seria més adequada.
  • append, l'accés amb [0] i remove són les operacions que aquesta estructura ens ofereix. Cada estructura de dades ofereix un catàleg diferent d'operacions, i aquí hi ha la clau de tot el curs: triar l'estructura les relacions i operacions de la qual encaixin amb el teu problema.

Un mateix conjunt de dades es pot organitzar de moltes maneres. Els títols d'aquestes tres tasques es podrien desar en una seqüència ordenada, en un conjunt sense ordre, o associats cadascun a un identificador. Les dades són les mateixes; el que canvia són les relacions i les operacions, és a dir, l'estructura.

Idea clau: una estructura de dades no és "un lloc on ficar coses", sinó un contracte: defineix quines relacions es mantenen entre les dades i quines operacions hi pots fer.

Analogies quotidianes per entendre-ho millor

Les estructures de dades existeixen des de molt abans que els ordinadors. Els humans fa segles que organitzem informació física, i aquestes organitzacions quotidianes són analogies perfectes:

Objecte quotidià Com organitza la informació Què facilita Què dificulta
Llista de la compra Elements l'un darrere l'altre Afegir al final, llegir en ordre Trobar un producte concret entre centenars
Pila de plats L'últim que hi deixes és el primer que agafes Apilar i desapilar per dalt Agafar el plat de baix sense desmuntar-ho tot
Cua del supermercat El primer que arriba és el primer atès Atendre per ordre d'arribada Colar-se (i està mal vist!)
Agenda telefònica per lletra Cada nom sota la seva inicial Saltar directament a la "M" Llistar contactes per data d'alta
Arbre genealògic Jerarquia de pares i fills Veure ascendència i descendència Relacionar cosins llunyans directament
Mapa de carreteres Ciutats connectades per vies Trobar rutes entre punts No hi ha cap "ordre" únic de ciutats

Fixa't en un detall important de la taula: cada organització facilita unes coses i en dificulta unes altres. La pila de plats és comodíssima per al que fa una pila (deixar i agafar per dalt), però terrible si necessites el plat del fons. No existeix l'organització perfecta per a tot; existeix l'organització adequada per a cada ús. Aquest principi, que a la cuina és obvi, és exactament el mateix en programació.

Cada fila d'aquesta taula correspon, a més, a una estructura de dades real que estudiarem en aquest curs: la llista, la pila, la cua, la taula hash, l'arbre i el graf. De moment queda't només amb la intuïció; el panorama complet de tipus el veurem a la lliçó 01-03.

Tipus Abstracte de Dades (TAD) vs implementació concreta

Aquest és el concepte més important de la lliçó, i un dels que distingeixen un desenvolupador que "usa" estructures d'un que les entén.

Un Tipus Abstracte de Dades (TAD) és l'especificació d'una estructura: defineix quines operacions ofereix i com es comporten, sense dir res de com estan programades per dins. La implementació concreta és el codi real que compleix aquesta especificació.

L'analogia clàssica és el cotxe:

  • TAD: "un cotxe té un volant per girar, un accelerador per anar més de pressa i un fre per aturar-se". Qualsevol persona que sàpiga conduir pot fer servir qualsevol cotxe, perquè el contracte és el mateix.
  • Implementació: un cotxe concret pot ser de benzina, elèctric o híbrid. Per dins són radicalment diferents, però el volant, l'accelerador i el fre es comporten igual.

Vegem-ho en codi. Definim el TAD "Pila" (l'estudiarem a fons al mòdul 3; aquí només ens interessa com a exemple de contracte):

TAD Pila:
  - apilar(element):     afegeix un element al cim
  - desapilar():         treu i retorna l'element del cim
  - cim():               consulta l'element del cim sense treure'l
  - es_buida():          indica si no hi ha elements

Observa que l'especificació no esmenta llistes de Python, ni memòria, ni punters. Només diu què fa cada operació. Ara, dues implementacions concretes del mateix TAD:

class PilaAmbLlista:
    """Implementacio del TAD Pila usant una llista de Python."""

    def __init__(self):
        self._elements = []           # l'estat intern es una llista

    def apilar(self, element):
        self._elements.append(element)

    def desapilar(self):
        return self._elements.pop()   # pop() treu l'ultim element

    def es_buida(self):
        return len(self._elements) == 0


class PilaAmbDiccionari:
    """Una altra implementacio del MATEIX TAD, amb un estat intern diferent."""

    def __init__(self):
        self._elements = {}           # l'estat intern es un diccionari
        self._comptador = 0           # portem el compte de posicions

    def apilar(self, element):
        self._elements[self._comptador] = element
        self._comptador += 1

    def desapilar(self):
        self._comptador -= 1
        return self._elements.pop(self._comptador)

    def es_buida(self):
        return self._comptador == 0

I ara, el més important: el codi que fa servir la pila no necessita saber quina de les dues implementacions té al davant.

def processar(pila):
    """Aquesta funcio funciona amb QUALSEVOL implementacio del TAD Pila."""
    pila.apilar("accio 1")
    pila.apilar("accio 2")
    while not pila.es_buida():
        print("Desfent:", pila.desapilar())

processar(PilaAmbLlista())        # Desfent: accio 2 / accio 1
processar(PilaAmbDiccionari())    # Desfent: accio 2 / accio 1

Explicació detallada de l'exemple:

  • processar només coneix el contracte: sap que existeixen apilar, desapilar i es_buida, i què se suposa que fan. No mira dins de la pila.
  • Les dues classes desen les dades de manera completament diferent (una llista vs un diccionari amb comptador), però des de fora es comporten igual: totes dues retornen els elements en ordre invers al que es van apilar.
  • El guionet baix inicial de self._elements és una convenció de Python que significa "això és intern, no ho toquis des de fora". Reforça la idea que l'usuari del TAD només ha d'usar les operacions públiques.

Aquesta separació té conseqüències pràctiques enormes:

  • Pots canviar la implementació sense trencar el codi que la fa servir (per exemple, per una de més ràpida quan aprenguis a mesurar rendiment).
  • Pots raonar sobre el teu programa en termes de contractes, sense carregar amb els detalls interns de cada peça.
  • És la base de com estudiarem cada estructura del curs: primer el TAD (què promet), després una o diverses implementacions (com ho compleix).

Presentem TaskFlow: el nostre projecte del curs

Al llarg del curs construirem, peça a peça, TaskFlow: una aplicació de gestió de tasques i projectes escrita en Python. La idea és senzilla: en lloc d'estudiar cada estructura de dades amb exemples desconnectats, cadascuna resoldrà una necessitat real de l'aplicació, de manera que en acabar el curs tindràs tant els coneixements com un projecte tangible.

Què fa TaskFlow? El que faries amb qualsevol gestor de tasques tipus Trello o Todoist, en versió simplificada:

  • Crear tasques amb títol, descripció, prioritat i estat.
  • Organitzar-les en un tauler i moure-les entre estats ("pendent", "en curs", "feta").
  • Desfer l'última acció si t'equivoques.
  • Rebre i processar notificacions.
  • Cercar qualsevol tasca a l'instant pel seu identificador.
  • Classificar tasques en categories i subcategories.
  • Declarar que una tasca depèn d'una altra i calcular en quin ordre fer-les.

La nostra primera peça de TaskFlow pot ser tan simple com això:

# taskflow.py — versio 0.1: una tasca es un diccionari amb els seus atributs
tasca = {
    "id": 1,
    "titol": "Preparar la demo de divendres",
    "prioritat": "alta",       # alta / mitjana / baixa
    "estat": "pendent",        # pendent / en curs / feta
}

print(f"[{tasca['id']}] {tasca['titol']} ({tasca['prioritat']})")
# [1] Preparar la demo de divendres (alta)

Aquí un diccionari de Python agrupa els atributs d'una sola tasca: cada clau ("id", "titol"...) s'associa a un valor. És la representació mínima amb què començarem; al mòdul 2 la farem créixer.

Les necessitats de dades de TaskFlow

Si TaskFlow només tingués una tasca, no necessitaríem aquest curs. El repte apareix quan hi ha moltes tasques i moltes maneres de relacionar-les. Enumerem les necessitats de dades de l'aplicació, perquè cadascuna anticipa un mòdul del curs:

Necessitat de TaskFlow Quina relació hi ha entre les dades? Mòdul on la resoldrem
Un tauler amb les tasques en ordre Seqüència: una tasca darrere l'altra Mòdul 2 (llistes)
Desfer l'última acció L'últim que s'ha fet és el primer que es desfà Mòdul 3 (piles)
Processar notificacions per ordre d'arribada La primera d'arribar és la primera de sortir Mòdul 4 (cues)
Trobar una tasca pel seu id a l'instant Associació identificador → tasca Mòdul 5 (taules hash)
Categories amb subcategories Jerarquia: pares i fills Mòdul 6 (arbres)
"La tasca B no pot començar fins que acabi l'A" Xarxa de dependències entre tasques Mòdul 7 (grafs)

Fixa't que cada fila descriu una relació diferent entre les mateixes dades (tasques). Aquesta és exactament la definició amb què hem obert la lliçó: les dades són les mateixes, però les relacions que necessitem mantenir —i les operacions que hi volem fer— canvien segons el cas d'ús. Per això no existeix "la millor estructura de dades", sinó l'adequada per a cada necessitat.

Errors Comuns i Consells

  • Confondre les dades amb l'estructura. "Tinc una llista de clients" barreja dues coses: els clients (dades) i la llista (estructura triada). Acostuma't a preguntar-te: quines relacions necessito mantenir i quines operacions hi faré? Aquesta pregunta decideix l'estructura.
  • Creure que en Python "tot es fa amb llistes i diccionaris". És cert que Python et dona estructures molt potents de sèrie, i les farem servir, però si no entens el TAD que hi ha al darrere, no sabràs quan una list és una mala tria (ho veuràs molt clar a la lliçó 01-02).
  • Saltar-se l'especificació i anar directe al codi. Abans d'implementar, escriu (encara que sigui en un comentari) quines operacions ha d'oferir la teva estructura. És l'hàbit TAD: primer el contracte, després el codi.
  • Consell: crea ja una carpeta taskflow/ al teu equip i desa-hi els exemples del curs. Al final tindràs una aplicació completa construïda per tu.

Exercicis

Exercici 1: identificar els tres components

Per a cada escenari, identifica les dades, les relacions i almenys dues operacions que necessitaries:

  1. L'historial de pàgines visitades d'un navegador web.
  2. Els seients reservats d'una sala de cinema.
  3. Els comentaris i respostes (a altres comentaris) d'un vídeo.

Exercici 2: especificar un TAD

Escriu l'especificació (només el contracte, sense codi) d'un TAD LlistaDeTasques per a TaskFlow amb aquestes capacitats: afegir una tasca, marcar una tasca com a feta, comptar quantes tasques queden pendents i obtenir la següent tasca pendent. Indica per a cada operació què rep i què retorna.

Exercici 3: dues implementacions, un contracte

Implementa en Python el TAD Comptador amb les operacions incrementar(), decrementar() i valor(). Fes-ho dues vegades: una classe ComptadorEnter que desi internament un nombre, i una classe ComptadorLlista que desi internament una llista a la qual afegeix un element en incrementar i en treu un en decrementar. Comprova que una funció externa funciona igual amb totes dues.

Solucions

Solució 1:

  1. Historial del navegador — Dades: les URL visitades. Relació: ordre temporal de visita (la més recent "a sobre"). Operacions: afegir la pàgina actual, tornar a l'anterior, buidar l'historial.
  2. Seients de cinema — Dades: els seients (fila i número) i el seu estat. Relació: cada seient s'identifica de manera única per la seva posició; no hi ha cap ordre temporal rellevant. Operacions: consultar si un seient és lliure, reservar-lo, alliberar-lo.
  3. Comentaris d'un vídeo — Dades: els comentaris (autor, text, data). Relació: jeràrquica, cada resposta "penja" d'un altre comentari. Operacions: afegir un comentari arrel, respondre a un comentari, llistar les respostes d'un de donat.

Solució 2:

TAD LlistaDeTasques:
  - afegir(titol, prioritat): rep el titol i la prioritat d'una tasca
      nova; la incorpora com a pendent. No retorna res.
  - marcar_feta(titol): rep el titol d'una tasca existent i canvia
      el seu estat a "feta". Retorna True si l'ha trobada, False si no.
  - pendents(): no rep res. Retorna el nombre de tasques pendents.
  - seguent(): no rep res. Retorna la tasca pendent mes antiga,
      o None si no en queda cap.

L'important no és la redacció exacta, sinó que hagis descrit comportament sense esmentar com es desa res internament.

Solució 3:

class ComptadorEnter:
    def __init__(self):
        self._n = 0                   # estat intern: un enter

    def incrementar(self):
        self._n += 1

    def decrementar(self):
        self._n -= 1

    def valor(self):
        return self._n


class ComptadorLlista:
    def __init__(self):
        self._marques = []            # estat intern: una llista de marques

    def incrementar(self):
        self._marques.append(1)       # afegim una marca

    def decrementar(self):
        self._marques.pop()           # traiem una marca

    def valor(self):
        return len(self._marques)     # el valor es quantes marques hi ha


def provar(comptador):
    comptador.incrementar()
    comptador.incrementar()
    comptador.incrementar()
    comptador.decrementar()
    print(comptador.valor())          # ha d'imprimir 2 en tots dos casos

provar(ComptadorEnter())   # 2
provar(ComptadorLlista())  # 2

Totes dues classes compleixen el mateix contracte amb estats interns diferents: és exactament la diferència entre TAD i implementació. (Nota: ComptadorLlista gasta més memòria; mesurar aquesta mena de diferències és just el que aprendrem a les properes lliçons.)

Conclusió

En aquesta lliçó has après que una estructura de dades és la combinació de dades, relacions i operacions, i que convé separar el TAD (el contracte: què fa) de la implementació (el codi: com ho fa). També has conegut TaskFlow, la nostra aplicació de gestió de tasques, i has vist que cadascuna de les seves necessitats —tauler, desfer, notificacions, cerca, categories, dependències— exigeix mantenir relacions diferents entre les mateixes dades.

Queda una pregunta a l'aire: si diverses estructures poden emmagatzemar les mateixes dades, importa de debò quina triïs? La resposta és un sí rotund, i a la lliçó següent ho comprovaràs amb nombres reals: veuràs com una mala tria pot fer que TaskFlow trigui milers de vegades més a fer el mateix.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2026. Tots els drets reservats