Conceptos Fundamentales de Programación: Cadenas y Colas

Escrito el 3 de Julio de 2025 en español con un tamaño de 9,04 KB

Operaciones Fundamentales con Cadenas (Hileras)

ASIGNACIÓN
Asigna un valor a una cadena.
LONGITUD ( )
Retorna el número de caracteres de una cadena.
SUBHILERA (i, j)
Crea una nueva cadena a partir del carácter que se halla en la posición i de la cadena que invoca el método, copiando j caracteres.
La cadena que invoca el método permanece intacta.
CONCATENA (Hilera s)
A partir de una cadena. Copia la cadena que invoca el método y a continuación agrega una copia de la cadena enviada como parámetro.
INSERTAR (entero i, hilera s)
Modifica la cadena que invoca el método: a partir de la posición i, de la cadena que invoca el método, inserta una copia de la cadena enviada como parámetro.
BORRAR (i, j)
Modifica la cadena que invoca el método: a partir del carácter que se halla en la posición i, de la cadena que invoca el método, elimina j caracteres.
REPLACE (entero i, entero j, hilera s)
Modifica la cadena que invoca el método: a partir del carácter que se halla en la posición i, de la cadena que invoca el método, reemplaza j caracteres por una copia de la cadena s enviada como parámetro.
POSICIÓN (hilera s)
Busca la cadena, enviada como parámetro, en la cadena que invoca el método.
Si la encuentra, retorna la posición a partir de la cual se halla; de lo contrario, retorna 0.

Algoritmos de Frecuencia

Frecuencia de Letras


void frecuenciaLetras(hilera alfabeto)
  m = alfabeto.longitud()
  int fre = new int[m]

  for i = 1 to m do
    fre[i] = 0
  end for

  n = texto.longitud()
  for i = 1 to n do
    car = texto.subHilera(i, 1) // Assuming subHilera is a method of texto
    k = alfabeto.posicion(car)
    if (k != 0) then
      fre[k] = fre[k] + 1
    end if
  end for

  for i = 1 to m do
    write(alfabeto.subhilera(i, 1), fre[i])
  end for
fin (frecuenciaLetras)

Frecuencia de Palabras (Implementación con Arreglos)


void frecuenciaPalabras(hilera texto, hilera alfabeto) // Added texto parameter for clarity
  n = texto.longitud()
  // Assuming 'palabras' and 'frec' arrays are declared elsewhere,
  // and 'm' tracks the number of unique words found.
  // Assuming 1-based indexing for arrays palabras and fre.
  m = 0 // Initialize m to 0 unique words
  i = 1

  while i <= n do
    // Skip delimiters before a word
    while i <= n and alfabeto.posicion(texto.subHilera(i, 1)) == 0 do
      i = i + 1
    end while

    // If end of text reached, break
    if i > n then break end if

    // Mark start of word
    j = i

    // Find end of word
    while i <= n and alfabeto.posicion(texto.subHilera(i, 1)) != 0 do
      i = i + 1
    end while

    // Extract word
    palabra = texto.subHilera(j, i - j)

    // Search for word in 'palabras' array
    encontrado = falso
    indice = 1
    while indice <= m and not encontrado do // Use <= m as m is count, indices 1..m
      if palabras[indice] == palabra then
        encontrado = verdadero
      else
        indice = indice + 1
      end if
    end while

    // Update frequency or add new word
    if encontrado then
      frec[indice] = frec[indice] + 1
    else
      m = m + 1 // Increment unique word count
      palabras[m] = palabra
      frec[m] = 1
    end if
  end while // End of processing text

  // Print frequencies
  for i = 1 to m do
    write(palabras[i], fre[i])
  end for
fin (frecuenciaPalabras)

Frecuencia de Palabras (Implementación con Lista Enlazada)


// Assuming 'p' is a structure/object containing a pointer 'primero' to the head
// and 'ultimo' is a pointer to the tail node of a linked list of nodoPalabra.
// Assuming 'palabra' variable holds the current word being processed (from previous section logic)

// Search for the word in the list
pActual = p.primero // Assuming p is a structure holding the head
while pActual != null and pActual.retornaPalabra() != palabra do
  pActual = pActual.retornaLiga()
end while

// Update frequency or add new node
if pActual != null then
  pActual.asignaContador(pActual.retornaContador() + 1)
else
  x = new nodoPalabra(palabra, 1)
  if p.primero == null then // Handle empty list case
    p.primero = x
    ultimo = x
  else
    ultimo.asignaLiga(x)
    ultimo = x
  end if
end if

// Note: This block represents the logic for processing a single 'palabra'
// within a larger loop that extracts words from the text.

Implementación de Colas

Cola Circular en Vector


// Assuming V is the array of size n, indices 0 to n-1.
// primero and ultimo are indices in [0, n-1].
// Empty: primero == ultimo
// Full: (ultimo + 1) % n == primero

void encolarVector(Object d)
  // Check if full BEFORE updating ultimo
  if ( (ultimo + 1) % n == primero ) then
    write("Cola llena")
    return
  end if

  ultimo = (ultimo + 1) % n
  V[ultimo] = d
fin (encolarVector)


Object desencolarVector()
  // Check if empty
  if (primero == ultimo) then
    write("Cola vacía")
    return null // Or throw exception
  end if

  primero = (primero + 1) % n
  Object dato = V[primero]
  return dato
fin (desencolarVector)

Cola Simple en Lista Enlazada


// Assuming nodoSimple has 'dato' and 'liga' fields.
// Assuming primero and ultimo are pointers to the head and tail nodes.

void encolarLista(Object d)
  x = new nodoSimple(d)
  if (primero == null) then
    primero = x
  else
    ultimo.asignaLiga(x) // Assuming asignaLiga is a method
  end if
  ultimo = x
fin (encolarLista)


Object desencolarLista() // Removed 'd' and 'lsl P' parameters as they seem unused/redundant
  if (primero == null) then
    write("Cola vacía")
    return null // Or throw exception
  end if

  Object dato = primero.retornaDato() // Assuming retornaDato is a method
  primero = primero.retornaLiga() // Assuming retornaLiga is a method

  // Optional: If list becomes empty, update ultimo
  if (primero == null) then
    ultimo = null
  end if

  return dato
fin (desencolarLista)

Múltiples Colas en Listas Enlazadas


// Assuming Primeros and Ultimos are arrays of pointers to nodoSimple,
// where Primeros[i] is the head and Ultimos[i] is the tail of the i-th queue.

void encolarNLista(Object d, int i)
  x = new nodoSimple(d)
  if (Primeros[i] == null) then
    Primeros[i] = x
  else
    Ultimos[i].asignaLiga(x) // Assuming asignaLiga is a method
  end if
  Ultimos[i] = x
fin (encolarNLista)


Object desencolarNLista(int i) // Removed 'd' parameter as it seems unused/redundant
  if (Primeros[i] == null) then
    write("Cola vacía")
    return null // Or throw exception
  else
    Object dato = Primeros[i].retornaDato() // Assuming retornaDato is a method
    Primeros[i] = Primeros[i].retornaLiga() // Assuming retornaLiga is a method

    // Optional: If queue i becomes empty, update Ultimos[i]
    if (Primeros[i] == null) then
      Ultimos[i] = null
    end if

    return dato
  end if
fin (desencolarNLista)

Dos Colas en un Vector (Doble Extremo?)


// This implementation seems to use a single array V for two queues.
// Let's assume V has size m.
// Queue 1 uses indices 0 to n-1. p1, u1 are indices in [0, n-1]. Size n.
// Queue 2 uses indices n to m-1. p2, u2 are indices in [n, m-1]. Size m-n.
// Q1 Empty: p1 == u1. Q1 Full: (u1 + 1) % n == p1.
// Q2 Empty: p2 == u2. Q2 Full: (u2 - n + 1) % (m - n) + n == p2.
// Note: The modulo arithmetic for Q2 is unusual and depends on language specifics for negative numbers.

void encolar2ColasVector(Object d, int k)
  if (k == 1) then
    // Enqueue in Queue 1 (indices 0 to n-1)
    // Check if full BEFORE updating u1
    if ( (u1 + 1) % n == p1 ) then
      colallena(k) // Assuming colallena handles which queue is full
      return
    end if
    u1 = (u1 + 1) % n
    V[u1] = d
  else // k == 2
    // Enqueue in Queue 2 (indices n to m-1)
    // Check if full BEFORE updating u2
    if ( (u2 - n + 1) % (m - n) + n == p2 ) then
      colallena(k)
      return
    end if
    u2 = (u2 - n + 1) % (m - n) + n
    V[u2] = d
  end if
fin (encolar2ColasVector)


Object desencolar2ColasVector(int k) // Removed 'd' parameter, added return type
  if (k == 1) then
    // Dequeue from Queue 1 (indices 0 to n-1)
    if (u1 == p1) then
      write("Cola 1 vacía")
      return null // Or throw exception
    else
      p1 = (p1 + 1) % n
      Object dato = V[p1]
      return dato
    end if
  else // k == 2
    // Dequeue from Queue 2 (indices n to m-1)
    if (u2 == p2) then
      write("Cola 2 vacía")
      return null // Or throw exception
    else
      p2 = (p2 - n + 1) % (m - n) + n
      Object dato = V[p2]
      return dato
    end if
  end if
fin (desencolar2ColasVector)

Entradas relacionadas:

Etiquetas: