Apunte interactivo de Algoritmos y Estructuras de Datos
El material organiza el resumen de la materia en una secuencia didáctica. Cada estructura se explica desde su representación lógica, su representación en memoria y su implementación típica en C++. Los laboratorios permiten modificar pilas, colas, listas, ABB y AVL para observar cómo cambian los enlaces.
Tema 0 · Retomando desde Fundamentos de Programación
Un algoritmo es una secuencia finita, clara y no ambigua de instrucciones. Un programa es un algoritmo expresado en un lenguaje que la computadora puede ejecutar. Por eso, el foco de esta materia no es sólo escribir instrucciones, sino elegir una forma de organizar los datos para que esas instrucciones sean correctas y eficientes.
if, if...else o switch.while, do...while o for.Abstracción y struct
La abstracción selecciona sólo los datos relevantes del dominio. Un struct permite agrupar varios campos bajo una sola entidad lógica. En lugar de manipular variables sueltas, el programa puede tratar una cuenta, una fecha o un nodo como una unidad.
Laboratorio · Relación entre struct y memoria
Pasar el mouse por el código resalta el campo representado.struct CuentaCD { double saldo; double tasa_interes; int plazo;};CuentaCD mi_cuenta;mi_cuenta.saldo = 0;
struct funciona como tipo. Las variables miembro existen dentro de cada variable de ese tipo.Tema 1 · Asignación dinámica de memoria
Un puntero almacena una dirección de memoria. El operador & obtiene la dirección de una variable y el operador * desreferencia el puntero para leer o modificar el valor apuntado. Con new se reserva memoria en el heap durante la ejecución; con delete se libera esa memoria.
Variables automáticas, dinámicas y estáticas
Una variable automática aparece y desaparece según el bloque en el que vive. Una variable dinámica existe hasta que se libera explícitamente. Esa diferencia es crítica: el programa puede conservar datos más allá de una función, pero también puede producir fugas de memoria o punteros colgantes.
delete puntero;, el puntero conserva un valor no confiable. Desreferenciarlo puede provocar comportamiento indefinido.new que no sea transferido a una estructura responsable debe tener su delete. Para arreglos dinámicos se usa delete[], porque se libera una secuencia de elementos, no un único objeto.Laboratorio · Punteros, heap y puntero colgante
Ejecuta los pasos para ver cómo cambia la dirección apuntada.int numero = 5;int* p = №cout << *p;p = new int;*p = 4;delete p;p = nullptr;
new no tiene nombre directo: se accede mediante el puntero.Laboratorio · Arreglo dinámico y aritmética de punteros
Se observa quep+i avanza por posiciones del arreglo.*(p+i) accede al elemento ubicado i posiciones después.int t = 5;int* p = new int[t];p[0] = 10;cout << *(p + 1);delete[] p;
delete p; en lugar de delete[] p; es un error conceptual cuando la reserva fue de arreglo.Tema 2 · Estructuras lineales y nodos
Las estructuras lineales dinámicas se construyen con nodos. Cada nodo contiene un dato y uno o más punteros que conectan ese nodo con otros. El acceso a la estructura se realiza mediante uno o varios punteros externos: por ejemplo, tope en una pila, frente y fondo en una cola, o inicio en una lista.
dato y sig. Es la base de pilas, colas dinámicas y listas simplemente enlazadas.ant, dato y sig. Permite recorrer hacia adelante y hacia atrás.nullptr; apunta al primero. La estructura queda cerrada.Pilas · Stack
Una pila es una estructura restrictiva y de acceso destructivo. La política es LIFO: el último elemento que entra es el primero que sale. Las operaciones centrales son push, pop e isEmpty.
Laboratorio · Pila dinámica
Push agrega sobre el tope; pop elimina el tope.void push(Nodo*& tope, int x) { Nodo* nuevo = new Nodo{x, tope}; tope = nuevo;}int pop(Nodo*& tope) { if (tope == nullptr) throw underflow; Nodo* aux = tope; int dato = aux->dato; tope = tope->sig; delete aux; return dato;}
Colas · Queue
Una cola respeta la política FIFO: el primer elemento que entra es el primero que sale. En una implementación dinámica se usan dos punteros: frente, desde donde se desencola, y fondo, donde se encola.
Laboratorio · Cola dinámica
Enqueue agrega al fondo; dequeue quita del frente.void enqueue(Cola& c, int x) { Nodo* nuevo = new Nodo{x, nullptr}; if (c.frente == nullptr) c.frente = nuevo; else c.fondo->sig = nuevo; c.fondo = nuevo;}int dequeue(Cola& c) { if (c.frente == nullptr) throw underflow; Nodo* aux = c.frente; c.frente = c.frente->sig; if (c.frente == nullptr) c.fondo = nullptr; delete aux;}
Cola circular con arreglo
La cola circular resuelve el problema de las posiciones desperdiciadas en un arreglo lineal. Cuando frente o fondo llegan al final, vuelven al índice 0 mediante módulo. La estructura conserva capacidad fija, pero reutiliza las celdas liberadas.
Laboratorio · Índices circulares
La posición siguiente se calcula como(i + 1) % capacidad.const int CAP = 6;int v[CAP];int frente = 0, fondo = -1, cantidad = 0;fondo = (fondo + 1) % CAP;v[fondo] = dato;frente = (frente + 1) % CAP;
Listas enlazadas
Una lista simplemente enlazada no es restrictiva como una pila o una cola. Puede recorrerse, insertar o eliminar nodos según la posición buscada. La lista circular cambia el enlace final: el último nodo vuelve al primero. La lista doblemente enlazada agrega un enlace hacia el nodo anterior.
Laboratorio · Lista simple, circular y doble
El mismo conjunto de datos puede verse con distintas políticas de enlace.struct Nodo { int dato; Nodo* sig; };void insertarInicio(Nodo*& inicio, int x) { Nodo* nuevo = new Nodo{x, inicio}; inicio = nuevo;}void eliminarInicio(Nodo*& inicio) { Nodo* aux = inicio; inicio = inicio->sig; delete aux;}for (Nodo* p = inicio; p != nullptr; p = p->sig) procesar(p->dato);
nullptr, sino volver al nodo inicial.Tema 3 · Estructuras de datos no lineales
Un árbol es una estructura recursiva formada por nodos y ramas. Existe una raíz desde la cual se accede a todo el árbol. Cada nodo puede tener hijos; los nodos sin hijos son hojas. A diferencia de una lista, el recorrido no sigue una única dirección lineal, sino que desciende por subárboles.
Árbol binario de búsqueda · ABB
Un ABB es un árbol binario donde, para cada nodo, los valores del subárbol izquierdo son menores y los valores del subárbol derecho son mayores. Esta regla permite buscar, insertar y eliminar siguiendo un camino de comparación.
Laboratorio · Inserción, búsqueda, eliminación y recorridos
El árbol se dibuja según sus enlaces reales.if (x < nodo->dato) buscar(nodo->izq, x);else if (x > nodo->dato) buscar(nodo->der, x);else insertarComoHoja(x);si tiene 0 hijos: eliminar hojasi tiene 1 hijo: enlazar padre con hijosi tiene 2 hijos: reemplazar por sucesor/predecesorRID: raíz, izquierda, derechaIRD: izquierda, raíz, derechaIDR: izquierda, derecha, raíz
Árbol AVL y rotaciones
Un AVL es un ABB equilibrado. Para cada nodo se controla la diferencia entre la altura del subárbol derecho y la altura del subárbol izquierdo. Si la diferencia absoluta supera 1, el árbol se reestructura con rotaciones para recuperar el equilibrio.
B = hD - hI. Si B vale -2 o 2, el nodo perdió equilibrio.Laboratorio · Secuencias que fuerzan rotaciones AVL
Se pueden reproducir los cuatro casos clásicos.int balance = altura(n->der) - altura(n->izq);// Caso izquierda-izquierdan->izq = n1->der;n1->der = n;// Caso derecha-derechan->der = n1->izq;n1->izq = n;// Caso izquierda-derecha: rotación doblen->izq = rotarIzquierda(n->izq);n = rotarDerecha(n);// Caso derecha-izquierda: rotación doblen->der = rotarDerecha(n->der);n = rotarIzquierda(n);
Laboratorio final · Diagnóstico rápido
El objetivo de esta sección es verificar comprensión conceptual. La consigna no busca memorizar definiciones, sino distinguir políticas de acceso, enlaces y efectos de memoria.