Implementación de Estructuras de Datos: Colas y Listas Doblemente Enlazadas en Pseudocódigo

1. Procedimiento `Agregar_cola`

Este procedimiento inserta un nuevo nodo al final de una cola.

Procedimiento Agregar_cola(var cola: t_cola, nuevo: pnodo)
tipo
  pnodo: *nodo
  nodo: Registro
    sig: pnodo
    dato: tipo_dato
  Fin_Registro

  t_cola: Registro
    i, f: pnodo  // Inicio y fin de la cola
    c: entero    // Contador de elementos
  Fin_Registro

Var
  cola: t_cola

inicio
  si (cola.f = null) entonces  // Si la cola está vacía
    cola.f <- nuevo
    cola.i <- nuevo
    cola.c <- 1
  sino
    (cola.f).sig <- nuevo // El siguiente del último nodo es el nuevo nodo
    cola.f <- nuevo       // El nuevo nodo se convierte en el último
    cola.c <- cola.c + 1  // Incrementa el contador
  fin si
fin

Funciones `cola_vacia` y `final_cola`

La función cola_vacia verifica si la cola está vacía. La función final_cola devuelve el último nodo de la cola (sin eliminarlo).

Funcion cola_vacia(e cola: t_cola): booleano
inicio
  cola_vacia <- (cola.i = null) // Devuelve verdadero si la cola está vacía
fin

Funcion final_cola(e cola: t_cola): pnodo
var
  i: pnodo
inicio
  si (cola.i = null) entonces //Si la cola esta vacia
    i <- null
  sino
    i <- cola.f  // Devuelve el puntero al final de la cola
  fin si
  final_cola <- i
fin

2. Función `Quitar_inicio`

Esta función elimina y devuelve el primer nodo de una lista doblemente enlazada.

Funcion Quitar_inicio(Var L: lista): pnodo
var
  i: pnodo
inicio
  si (L.i = null) entonces // Si la lista está vacía
    i <- null
  sino
    si (L.i = L.f) entonces // Si la lista tiene un solo elemento
      i <- L.i
      L.i <- null
      L.f <- null
      
    sino // La lista tiene más de un elemento
      i       <- L.i
      L.i     <- (L.i).sig
      (L.i).ant <- null

    fin si
     i.sig <- null //Aislar el nodo
     i.ant <- null
  fin si
  Quitar_inicio <- i
fin

Función `Quitar_nodo` (Corrección y Mejora)

Esta función busca un nodo con un dato específico y lo elimina de la lista doblemente enlazada. Se ha corregido y mejorado la lógica para manejar todos los casos correctamente.

Funcion Quitar_nodo(var L: lista, E buscado: tipo_dato): pnodo
var
  i: pnodo
inicio
  si (L.i = null) entonces  // Si la lista está vacía
    i <- null
  sino
    i <- L.i
    Mientras (i <> null Y i.dato <> buscado) hacer // Buscar el nodo
      i <- i.sig
    Fin Mientras

    si (i <> null) entonces // Se encontró el nodo
      si (i = L.i) entonces // Es el primer nodo
        L.i <- i.sig
        si L.i <> null entonces
          (L.i).ant <- null
        fin si
      sino si (i = L.f) entonces // Es el último nodo
        L.f <- i.ant
        (L.f).sig <- null
      sino // Nodo intermedio
        (i.ant).sig <- i.sig
        (i.sig).ant <- i.ant
      fin si
      i.sig <- null // Aislar el nodo
      i.ant <- null
    sino
      i <- null // No se encontro el dato
    fin si
  fin si
  Quitar_nodo <- i
fin

3. Lista Doblemente Enlazada: Definición y Procedimientos

Se define la estructura de una lista doblemente enlazada y los procedimientos para inicializarla, agregar nodos (al inicio o al final) y un procedimiento "oculto".

tipo
  pnodo: *nodo
  nodo: Registro
    sig, ant: pnodo
    dato: tipo_dato
  Fin_Registro

  Lista: Registro
    i: pnodo  // Puntero al inicio de la lista
    c: entero // Contador de elementos (opcional)
  Fin_Registro

Var
  L: lista

Procedimiento Iniciar_Lista(var L: lista)
inicio
  L.i <- null
  L.c <- 0
fin

Procedimiento `Agregar_nodo` (Interactivo)

Procedimiento Agregar_nodo(Var L: lista, E nuevo: pnodo)
Var
  op: entero
Inicio
  Escribir "Ingrese 1: para insertar al inicio, 2: para insertar al final"
  leer op
  segun op hacer
    1: agregar_inicio(L, nuevo)
    2: agregar_final(L, nuevo)
    otro:  Escribir "Opción no válida"
  fin segun
fin

Procedimiento `agregar_inicio`

Procedimiento agregar_inicio(Var L: lista, nuevo: pnodo)
Inicio
  Si L.i = null entonces // Lista vacía
    L.i <- nuevo
    nuevo.sig <- null
    nuevo.ant <- null
  sino
    nuevo.sig <- L.i
    nuevo.ant <- null
    (L.i).ant <- nuevo
    L.i <- nuevo
  Fin si
Fin

Procedimiento `Agregar_final`

Procedimiento Agregar_final(Var L: lista, nuevo: pnodo)
var
  p: pnodo
Inicio
  Si L.i = null entonces // Lista vacía
    L.i <- nuevo
    nuevo.sig <- null
    nuevo.ant <- null
  sino
    p <- L.i
    Mientras (p.sig <> null) hacer
      p <- p.sig
    fin mientras
    p.sig <- nuevo
    nuevo.ant <- p
    nuevo.sig <- null
  fin si
fin

4. Procedimiento `desconocido` (Análisis y Corrección)

El procedimiento "oculto" (ahora llamado `desconocido`) inserta un nuevo nodo *antes* del nodo apuntado por `a`. Si `a` es `null`, inserta al inicio. Se ha corregido para que funcione correctamente.

Procedimiento desconocido(e/s a: pnodo, e nuevo: pnodo)
var
  aux: pnodo
inicio
  si (a = null) entonces // Insertar al principio si 'a' es null
      a <- nuevo
      nuevo.sig <- null
      nuevo.ant <- null

  sino  // Insertar antes de 'a'

      nuevo.sig <- a
      nuevo.ant <- a.ant

      si a.ant <> null entonces
          (a.ant).sig <- nuevo
      fin si

      a.ant <- nuevo

  fin si

fin

Explicación del procedimiento `desconocido`:

1. Verificación de lista vacía o inserción al inicio: Si el puntero a es null, el nuevo nodo se convierte en el primer elemento de la lista.
2. Inserción antes del nodo 'a': Si a no es null:
   • El nuevo.sig apunta a a.
   • El nuevo.ant apunta al nodo anterior de a (a.ant).
   • Si existe un nodo anterior a a, se enlaza correctamente.
   • Finalmente, el puntero ant del nodo a se actualiza para que apunte al nuevo nodo.