Tema 3: Tipos abstractos y estructura de datos

Son modelos teóricos de estructuras de datos que describen su comportamiento y operaciones permitidas, sin especificar cómo se implementan.

Son la implementación concreta de los TAD, encargándose de organizar y almacenar los datos de manera eficiente.

• Lista: colección ordenada de elementos con acceso por posición.
• Cola: estructura FIFO (First In, First Out).
Una cola de impresión en el ordenador sigue el principio FIFO.
• Pila: estructura LIFO (Last In, First Out).
• Conjunto: colección de elementos únicos sin orden específico.
• Árbol: estructura jerárquica con nodos padre e hijo.
• Tablas hash: acceso rápido a los datos mediante funciones hash.
• Grafos: modelan relaciones entre elementos.

Los árboles son estructuras de datos jerárquicas donde cada nodo tiene un padre y puede tener múltiples hijos.

Componentes:

• Raíz: Nodo principal.
• Nodos Hoja: Nodos sin hijos.
• Altura: Longitud del camino más largo hasta una hoja.
• Grado: Número de hijos de un nodo.

Existen varios algoritmos para encontrar caminos en grafos:

• PRIM: Empieza en un punto y va conectando los más cercanos hasta unir todo, usando las conexiones más baratas.
• KRUSKAL: Toma las conexiones más baratas y las une por orden de costo, evitando ciclos.
• Dijkstra: Encuentra el camino más corto desde un nodo a todos los demás.
• Bellman-Ford: Similar a Dijkstra, pero admite pesos negativos.
• Floyd-Warshall: Encuentra la ruta más corta entre todos los nodos.
• Algoritmo A*: Encuentra el camino de menor coste entre un nodo origen y uno objetivo.

Los algoritmos de ordenación organizan los datos en un orden específico:

• Burbuja: Intercambia elementos adyacentes.
• Quick Sort: Divide y vence ordenando recursivamente.
• Merge Sort: Divide la lista y la combina ordenada.
• Heap Sort: Basado en estructuras de montículos.

• .jpg / .jpeg: Compresión con pérdida, sin transparencia.
• .png: Compresión sin pérdida, soporta transparencia.
• .gif: Admite animaciones con 256 colores.
• .svg: Gráficos vectoriales escalables.

• .mp3: Audio comprimido con pérdida.
• .wav: Audio sin compresión.
• .webm: Formato de video optimizado para la web.
• H.264 / H.265: Códigos de compresión de video.