if (estaVacia()) { // Caso 1: Primera inserción primero = nuevoNodo; nuevoNodo->setSiguiente(nuevoNodo); // Apunta a sí mismo nuevoNodo->setAnterior(nuevoNodo); // Apunta a sí mismo } else { // Caso 2: Inserción en lista no vacía NodoAvion* ultimo = primero->getAnterior(); // Obtener último
Avion* ListaCircularDoble::buscar(std::string numeroRegistro){ if (estaVacia()) returnnullptr;
NodoAvion* actual = primero; // Recorrer hasta volver al inicio do { if (actual->getAvion()->getNumeroRegistro() == numeroRegistro) { return actual->getAvion(); } actual = actual->getSiguiente(); } while (actual != primero); // Detener cuando vuelva al inicio
if (estaVacia()) { // Primer elemento frente = fin = nuevoNodo; } else { // Agregar al final fin->setSiguiente(nuevoNodo); nuevoNodo->setAnterior(fin); fin = nuevoNodo; } tamanio++; }
/* VISUALIZACIÓN FIFO: Encolar (A): FRENTE [A] FIN Encolar (B): FRENTE [A] <-> [B] FIN Encolar (C): FRENTE [A] <-> [B] <-> [C] FIN */
// 2. Mover frente frente = frente->getSiguiente(); if (frente == nullptr) { // La cola quedó vacía fin = nullptr; } else { // El nuevo frente no tiene anterior frente->setAnterior(nullptr); }
voidPila::push(Equipaje* equipaje){ // 1. Crear nuevo nodo NodoEquipaje* nuevoNodo = newNodoEquipaje(equipaje); // 2. El nuevo nodo apunta a la cima actual nuevoNodo->setSiguiente(cima); // 3. El nuevo nodo es la nueva cima cima = nuevoNodo; tamanio++; }
/* VISUALIZACIÓN LIFO: Push (A): CIMA ▼ [A] BASE Push (B): CIMA ▼ [B] ▼ [A] BASE */
if (estaVacia()) { // Caso 1: Primera inserción primero = ultimo = nuevoNodo; } else { // Caso 2: Buscar posición ordenada NodoPasajero* actual = primero;
// BÚSQUEDA: Recorrer hasta encontrar la posición correcta while (actual != nullptr) { // Comparación 1: Por número de vuelo if (pasajero->getVuelo() < actual->getPasajero()->getVuelo()) { // El nuevo pasajero va antes break; } // Comparación 2: Si mismo vuelo, comparar por asiento elseif (pasajero->getVuelo() == actual->getPasajero()->getVuelo()) { if (pasajero->getAsiento() < actual->getPasajero()->getAsiento()) { // El nuevo pasajero va antes break; } } // Continuar buscando actual = actual->getSiguiente(); }
// INSERCIÓN en la posición encontrada if (actual == primero) { // Caso 2a: Insertar al INICIO nuevoNodo->setSiguiente(primero); primero->setAnterior(nuevoNodo); primero = nuevoNodo; } elseif (actual == nullptr) { // Caso 2b: Insertar al FINAL ultimo->setSiguiente(nuevoNodo); nuevoNodo->setAnterior(ultimo); ultimo = nuevoNodo; } else { // Caso 2c: Insertar en MEDIO NodoPasajero* anterior = actual->getAnterior(); anterior->setSiguiente(nuevoNodo); nuevoNodo->setAnterior(anterior); nuevoNodo->setSiguiente(actual); actual->setAnterior(nuevoNodo); } } tamanio++; }
/* EJEMPLO DE INSERCIÓN ORDENADA: Insertar: (John, A100, 12) Lista: vacía Resultado: [John: A100-12] Insertar: (Jane, A200, 5) Lista: [John: A100-12] Resultado: [John: A100-12] <-> [Jane: A200-5] Insertar: (Carlos, A100, 15) Lista: [John: A100-12] <-> [Jane: A200-5] Búsqueda: A100 < A200, y 15 > 12, así que va después de John Resultado: [John: A100-12] <-> [Carlos: A100-15] <-> [Jane: A200-5] Insertar: (Pedro, A100, 8) Lista: [John: A100-12] <-> [Carlos: A100-15] <-> [Jane: A200-5] Búsqueda: A100 == A100, pero 8 < 12, así que va antes de John Resultado: [Pedro: A100-8] <-> [John: A100-12] <-> [Carlos: A100-15] <-> [Jane: A200-5] */
Complejidad del Algoritmo
1 2 3
Búsqueda: O(n) - peor caso: recorre toda la lista Inserción: O(1) - una vez encontrada la posición Total: O(n) - dominado por la búsqueda
Algoritmos Principales
1. Algoritmo de Ordenamiento por Inserción (Inserción Ordenada)
Tipo: Ordenamiento por inserción Complejidad: O(n) en búsqueda + O(1) en inserción Estabilidad: Estable (mantiene orden relativo)
// PSEUDOCÓDIGO function insertarOrdenado(pasajero): nuevoNodo =crearNodo(pasajero) if lista vacía: primero = nuevoNodo return // Búsqueda lineal actual = primero while actual != NULL: if pasajero < actual: // Comparación (vuelo, luego asiento) break actual = siguiente // Inserción en posición encontrada if actual == primero: insertarAlInicio(nuevoNodo) elseif actual == NULL: insertarAlFinal(nuevoNodo) else: insertarEnMedio(nuevoNodo, actual)
// En ListaDoble Pasajero* ListaDoble::buscar(std::string numeroPasaporte){ NodoPasajero* actual = primero; // Recorrer linealmente while (actual != nullptr) { if (actual->getPasajero()->getNumeroPasaporte() == numeroPasaporte) { return actual->getPasajero(); // Encontrado } actual = actual->getSiguiente(); } returnnullptr; // No encontrado }
// Complejidad: // Mejor caso: O(1) - encontrado al inicio // Peor caso: O(n) - encontrado al final o no existe // Promedio: O(n/2) ≈ O(n)
Mejora posible: Si la lista está ordenada por pasaporte, usar búsqueda binaria.
3. Algoritmo de Búsqueda Circular
Tipo: Búsqueda en estructura circular Complejidad: O(n) Uso: ListaCircularDoble
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Avion* ListaCircularDoble::buscar(std::string numeroRegistro){ if (estaVacia()) returnnullptr;
NodoAvion* actual = primero; // DO-WHILE: Garantiza visitar todos los nodos do { if (actual->getAvion()->getNumeroRegistro() == numeroRegistro) { return actual->getAvion(); } actual = actual->getSiguiente(); } while (actual != primero); // Detener al volver al inicio
returnnullptr; }
// Clave: La condición "actual != primero" detecta cuando // se volvió al inicio después de recorrer todo el círculo
4. Algoritmo de Eliminación Circular
Tipo: Eliminación en lista circular Complejidad: O(n) búsqueda + O(1) eliminación Dificultad: Manejar el caso especial del primero
Avion* ListaCircularDoble::eliminar(std::string numeroRegistro){ if (estaVacia()) returnnullptr;
NodoAvion* actual = primero; do { if (actual->getAvion()->getNumeroRegistro() == numeroRegistro) { Avion* avionEliminado = actual->getAvion(); actual->setAvion(nullptr);
if (tamanio == 1) { // CASO ESPECIAL: Único elemento primero = nullptr; } else { // Obtener vecinos NodoAvion* anterior = actual->getAnterior(); NodoAvion* siguiente = actual->getSiguiente();
// Desconectar el nodo anterior->setSiguiente(siguiente); siguiente->setAnterior(anterior);
// CASO ESPECIAL: Si eliminamos primero, actualizar if (actual == primero) { primero = siguiente; } }
delete actual; tamanio--; return avionEliminado; } actual = actual->getSiguiente(); } while (actual != primero);
returnnullptr; }
/* VISUALIZACIÓN ELIMINACIÓN: Caso 1: Un solo elemento Antes: [A] <-> [A] (circular) Después: NULL Caso 2: Elemento al inicio Antes: [A] <-> [B] <-> [C] <-> [A] Eliminar A: Después: [B] <-> [C] <-> [B] primero = B (actualizar) Caso 3: Elemento en medio Antes: [A] <-> [B] <-> [C] <-> [A] Eliminar B: Después: [A] <-> [C] <-> [A] Caso 4: Elemento al final (mismo que 3 en circular) */
5. Algoritmo de Gestión de Memoria
Tipo: Recorrido con liberación Complejidad: O(n) Uso: Destructores
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// Destructor de ListaCircularDoble ListaCircularDoble::~ListaCircularDoble() { if (!estaVacia()) { NodoAvion* actual = primero; NodoAvion* siguiente; // DO-WHILE: Visitar todos los nodos en círculo do { siguiente = actual->getSiguiente(); delete actual; // Liberar memoria actual = siguiente; } while (actual != primero); // Detener al volver al inicio } }
// Clave: Guardar "siguiente" ANTES de delete, porque // después de delete el puntero es inválido
6. Algoritmo de Procesamiento de Movimientos
Tipo: Parsing y procesamiento de comandos Complejidad: O(m * n) - m líneas, n búsqueda Ubicación: main.cpp
voidprocesarMovimientos(){ std::string ruta; std::cout << "Ingrese la ruta del archivo de movimientos: "; std::cin >> ruta;
std::ifstream archivo(ruta); std::string linea;
if (!archivo.is_open()) { std::cout << "Error al abrir el archivo" << std::endl; return; }
// Leer línea por línea while (getline(archivo, linea)) { // TIPO 1: IngresoEquipajes if (linea.find("IngresoEquipajes") != std::string::npos) { // Desencolar pasajero de la cola Pasajero* pasajero = colaRegistro->desencolar(); if (pasajero != nullptr) { // Insertar en lista ordenada listaPasajeros->insertarOrdenado(pasajero);
Verificar codificación del archivo (debe ser UTF-8)
Verificar que no hay caracteres especiales
Debugging con GDB
El flag -g en el makefile incluye símbolos de debug.
1 2 3 4 5 6 7 8 9 10 11 12
# Iniciar debugger gdb aeropuerto.exe
# Comandos útiles (gdb) break main # Punto de quiebre en main (gdb) break Avion::insertar # Punto de quiebre en método (gdb) run # Ejecutar (gdb) next # Siguiente línea (gdb) step # Entrar en función (gdb) print variable_name # Mostrar valor (gdb) backtrace # Ver pila de llamadas (gdb) quit # Salir
Todo el código fuente compartido en este blog se encuentra bajo la licencia MIT. Puedes usar, modificar y distribuir el código para cualquier propósito, siempre y cuando incluyas la nota de copyright y la licencia original.
