1. INTRODUCCIÓN Y ENCUADRE

Los programas no trabajan con información abstracta de manera indiferenciada: operan sobre representaciones concretas que ocupan memoria, admiten unas operaciones y excluyen otras. Por eso, el concepto de tipo de dato es previo al de algoritmo. Un tipo determina un dominio de valores, una representación y un repertorio de operaciones válidas. Sobre esos tipos se construyen estructuras que organizan conjuntos de elementos y, cuando la información debe sobrevivir a la ejecución del proceso, se materializa en ficheros o en otros mecanismos persistentes.

El temario distingue tres planos que conviene mantener separados. El primero es el de los tipos elementales, como enteros, reales, caracteres y booleanos. El segundo es el de las estructuras de datos, que pueden tener tamaño y disposición convencional o estática —arrays, matrices y registros— o variar durante la ejecución —listas enlazadas, árboles, grafos y tablas hash—. El tercero es el de los ficheros, donde interesa tanto el contenido lógico como la organización física, la unidad de transferencia, el método de acceso y las operaciones de mantenimiento.

La elección de una estructura nunca es puramente sintáctica. Está condicionada por el patrón de uso: número de elementos, frecuencia de consultas, inserciones y borrados, necesidad de conservar el orden, consumo de memoria, localidad de referencia, concurrencia y persistencia. Una solución correcta funcionalmente puede ser inadecuada por su complejidad temporal, por desperdiciar memoria o por obligar a recorrer un fichero completo para resolver una consulta puntual.

En sistemas de información sanitarios esta materia tiene una dimensión práctica inmediata. Un listado temporal de citas puede representarse en memoria como una colección ordenada; una cola de trabajos modela peticiones pendientes; un árbol facilita búsquedas jerárquicas; una tabla hash soporta localización por clave; y un fichero secuencial o indexado puede emplearse en procesos de intercambio, carga masiva, trazabilidad o explotación. El profesional TIC debe reconocer la abstracción utilizada, sus garantías y sus límites antes de diseñar una interfaz, un proceso batch o una integración.

2. TIPOS ELEMENTALES DE DATOS Y REPRESENTACIÓN

2.1. Concepto de Tipo de Dato

Un tipo de dato define el conjunto de valores que una variable puede tomar y las operaciones que se pueden realizar sobre esos valores. Los tipos de datos proporcionan:

• Abstracción: Ocultan detalles de representación en memoria
• Seguridad: Previenen operaciones inválidas mediante verificación de tipos
• Eficiencia: Permiten al compilador/intérprete optimizar almacenamiento y operaciones
• Legibilidad: Hacen el código más comprensible declarando qué representa cada variable

2.2. Tipos Elementales Fundamentales

Las cadenas se estudian como estructura secuencial en un apartado posterior. Algunos lenguajes las ofrecen como tipo incorporado, pero conceptualmente no son un valor elemental indivisible, sino una colección de caracteres o unidades de código con reglas propias de codificación e inmutabilidad.

2.3. Representación en Memoria

2.3.1. Enteros: Complemento a Dos

Los enteros con signo se representan típicamente usando complemento a dos, que permite aritmética eficiente:

Ejemplo 8 bits:
+5:  00000101
-5:  11111011  (invertir bits de +5 y sumar 1)

Ventaja: Suma/resta funcionan igual independientemente del signo
+5 + (-5) = 00000101 + 11111011 = 00000000 = 0

2.3.2. Reales: Formato IEEE 754

Los números de coma flotante se representan según el estándar IEEE 754:

2.3.3. Caracteres: ASCII y Unicode

• ASCII (American Standard Code for Information Interchange): 7 bits (128 códigos). La expresión «ASCII extendido» agrupa varias páginas de códigos de 8 bits y no designa un único estándar. ‘A’ = 65, ‘a’ = 97, ‘0’ = 48
• Unicode: Estándar universal con >1 millón de caracteres
  • UTF-8: Codificación variable 1-4 bytes, compatible con ASCII
  • UTF-16: 2 o 4 bytes
  • UTF-32: 4 bytes fijos

2.4. Representación, dominio y operaciones

Un tipo no se limita al número de bytes reservado. En sentido abstracto comprende el conjunto de valores posibles y las operaciones cerradas o definidas sobre ellos. Por ejemplo, la suma de enteros produce normalmente otro entero del mismo dominio, salvo desbordamiento; la división entera puede truncar; y la comparación booleana produce un valor lógico. Esta visión permite razonar con independencia de un lenguaje concreto.

Los tamaños de los tipos primitivos no son universales. Algunos lenguajes fijan tamaños concretos para determinados tipos, mientras que otros los vinculan a la plataforma, a la implementación o a un perfil normativo. Por ello, en material técnico resulta más correcto hablar de rangos cuando el lenguaje los garantiza y evitar presentar como universal que todo int ocupa cuatro bytes.

Los enteros sin signo representan valores no negativos. Con n bits abarcan de 0 a 2^n−1, aunque la etiqueta ^ no está permitida en la plantilla y debe interpretarse aquí como potencia. En los enteros con signo basados en complemento a dos, un bit participa en la codificación del signo y el rango es asimétrico: existe un valor negativo más que positivos distintos de cero. El desbordamiento puede producir excepción, saturación, aritmética modular o comportamiento dependiente del lenguaje.

La coma flotante IEEE 754 representa valores finitos normalizados y subnormales, ceros con signo, infinitos y valores NaN. No todos los decimales tienen representación binaria exacta; por ello, comparaciones como 0.1 + 0.2 == 0.3 pueden no comportarse como espera quien razona en decimal. Para importes monetarios o cálculos que exigen decimal exacto suelen preferirse tipos decimales, enteros escalados o bibliotecas de precisión arbitraria.

3. SISTEMAS DE TIPOS, CONVERSIONES Y SEMÁNTICA

3.1. Tipado fuerte y tipado débil

La oposición entre tipado fuerte y débil no dispone de una definición única aceptada por todos los autores. Se utiliza para describir hasta qué punto un lenguaje impide mezclar valores incompatibles, exige conversiones explícitas y evita reinterpretaciones inseguras. Por ello conviene tratarla como un espectro y explicar la regla concreta, no limitarse a una etiqueta.

3.2. Tipado estático y tipado dinámico

En el tipado estático, la compatibilidad de tipos se comprueba principalmente antes de ejecutar, aunque pueden existir comprobaciones dinámicas adicionales. Java, C#, C++, Rust y Go son ejemplos. Favorece detección temprana, refactorización y optimización, pero no garantiza por sí solo ausencia de errores.

En el tipado dinámico, los valores llevan información de tipo que se comprueba durante la ejecución. Python, JavaScript y Ruby son ejemplos. Aporta flexibilidad y metaprogramación; los errores de tipo aparecen cuando se ejecuta la ruta afectada, aunque pruebas, anotaciones y analizadores estáticos pueden detectarlos antes.

El rendimiento no se deduce únicamente del sistema de tipos: compilación JIT, representación de objetos, especialización y optimizaciones de la implementación pueden reducir o ampliar la diferencia.

3.3. Conversión, promoción y coerción

La conversión de tipos puede ser explícita, cuando el programador solicita una transformación, o implícita, cuando la realiza el lenguaje. Una promoción suele ampliar el dominio sin pérdida —por ejemplo, de un entero pequeño a otro mayor—, mientras que una conversión estrecha puede perder rango, precisión o información. Convertir un real a entero puede truncar o redondear según la operación empleada; convertir texto a número puede fallar si la cadena no cumple el formato.

La coerción es una conversión implícita aplicada para hacer compatibles operandos. Facilita la escritura, pero puede ocultar errores: concatenar accidentalmente texto y números, comparar valores de dominios diferentes o aceptar valores nulos donde no proceden. Los lenguajes y herramientas de análisis estático intentan equilibrar comodidad y seguridad.

3.4. Nulidad, opcionalidad y valores centinela

La ausencia de valor debe modelarse deliberadamente. Usar 0, −1 o una cadena vacía como centinela mezcla el dominio real con un significado especial. Los tipos opcionales, anulables o algebraicos distinguen entre “hay valor” y “no hay valor”, obligando a tratar ambos casos. Esta distinción es especialmente relevante en información clínica y administrativa, donde “desconocido”, “no aplicable”, “no informado” y “valor cero” no son equivalentes.

3.5. Tipos por valor y por referencia

En una semántica por valor, la asignación copia el contenido lógico; en una semántica por referencia, varias variables pueden referirse al mismo objeto. El aliasing permite compartir estructuras, pero introduce efectos laterales: una modificación visible a través de una referencia puede aparecer por otra. La inmutabilidad reduce este riesgo y facilita razonamiento, concurrencia y pruebas.

4. ESTRUCTURAS CONVENCIONALES: ARRAYS, MATRICES Y REGISTROS

4.1. Concepto de Estructura de Datos

Una estructura de datos es una forma particular de organizar y almacenar datos para que puedan ser accedidos y modificados eficientemente. La elección de la estructura de datos apropiada depende de:

• Operaciones requeridas: Búsqueda, inserción, eliminación, ordenación, recorrido
• Frecuencia de operaciones: Qué operaciones son más comunes
• Restricciones de espacio: Memoria disponible
• Restricciones de tiempo: Requisitos de rendimiento
• Complejidad de implementación: Simplicidad vs. sofisticación

4.2. Arrays (Arreglos/Vectores)

4.2.1. Operaciones en Arrays

4.2.2. Arrays Multidimensionales

Los arrays multidimensionales se pueden almacenar en memoria de dos formas:

• Row-major order (fila principal): Elementos de una fila están contiguos. Usado en C, C++, Python

  Array 2D: [1 2 3]    Memoria: [1 2 3 4 5 6 7 8 9]
            [4 5 6]
            [7 8 9]

• Column-major order (columna principal): Elementos de una columna están contiguos. Usado en Fortran, MATLAB

  Array 2D: [1 2 3]    Memoria: [1 4 7 2 5 8 3 6 9]
            [4 5 6]
            [7 8 9]

4.3. Registros (Records/Structs)

Un registro es una estructura de datos heterogénea que agrupa elementos de diferentes tipos bajo un único nombre.

            // Ejemplo en C
struct Empleado {
    int id;
    char nombre[50];
    float salario;
    struct Fecha fechaContratacion;
};

// Ejemplo en Python (usando dataclass)
from dataclasses import dataclass

@dataclass
class Empleado:
    id: int
    nombre: str
    salario: float
    fecha_contratacion: datetime

4.3.1. Características de Registros

• Heterogeneidad: Campos pueden ser de diferentes tipos
• Acceso por nombre: empleado.nombre, empleado.salario
• Memoria: Campos almacenados secuencialmente (con posible padding para alineación)
• Anidación: Registros pueden contener otros registros
• Uso: Modelar entidades del mundo real con múltiples atributos

4.4. Localidad de referencia y coste real del array

El acceso indexado de un array es O(1) porque la dirección del elemento se calcula a partir de la dirección base, el índice y el tamaño del elemento. Esta complejidad asintótica no describe todo el rendimiento: la contigüidad mejora la localidad espacial y permite aprovechar líneas de caché, prelectura y operaciones vectorizadas. Por ello, recorrer un array puede ser más rápido que recorrer una lista enlazada incluso cuando ambas operaciones son lineales.

La inserción en una posición intermedia exige desplazar elementos y suele ser O(n). Los arrays dinámicos reservan capacidad superior al tamaño lógico y crecen por bloques; así obtienen inserción al final de coste amortizado O(1), aunque una ampliación concreta requiere reservar otra zona y copiar elementos.

4.5. Alineación y relleno en registros

Los campos de un registro pueden incorporar bytes de relleno para satisfacer requisitos de alineación. Por eso, el tamaño de una estructura no siempre es la suma exacta de sus campos. Serializar directamente la imagen de memoria de un registro puede fallar entre compiladores, arquitecturas o versiones por diferencias de alineación, endianness y representación. Un formato persistente debe definir explícitamente tamaños, orden de bytes, codificación y versión.

5. CADENAS, ENUMERACIONES Y OTRAS COLECCIONES CONVENCIONALES

5.1. Cadenas de Caracteres (Strings)

Las cadenas son secuencias de caracteres. Su implementación varía según lenguaje:

• C: Array de char terminado en ‘’ (null-terminated)

  char saludo[] = "Hola";  // Internamente: ['H','o','l','a','']

• Java/C#: Objetos inmutables con longitud explícita

  String saludo = "Hola";  // Objeto String inmutable

• Python: Secuencias inmutables de caracteres Unicode

  saludo = "Hola"  # str inmutable, soporta Unicode nativo

5.1.1. Operaciones Comunes en Cadenas

• Concatenación: «Hola» + » Mundo» → «Hola Mundo»
• Subcadenas: «Hola»[0:2] → «Ho»
• Longitud: len(«Hola») → 4
• Búsqueda: «Hola».find(«la») → 2
• Reemplazo: «Hola».replace(«o», «a») → «Hala»
• División: «uno,dos,tres».split(«,») → [«uno», «dos», «tres»]

5.2. Enumeraciones (Enums)

Tipo de dato que consiste en un conjunto de constantes nombradas:

// Java
enum DiaSemana {
    LUNES, MARTES, MIERCOLES, JUEVES, VIERNES, SABADO, DOMINGO
}

// Python
from enum import Enum

class DiaSemana(Enum):
    LUNES = 1
    MARTES = 2
    MIERCOLES = 3
    JUEVES = 4
    VIERNES = 5
    SABADO = 6
    DOMINGO = 7

Ventajas de Enumeraciones:

• Código más legible (nombres descriptivos vs. números mágicos)
• Seguridad de tipos (solo valores válidos permitidos)
• Facilita refactorización
• Autodocumentación del conjunto de valores posibles

5.3. Tuplas, conjuntos y mapas

Una tupla agrupa un número fijo de componentes, potencialmente de tipos diferentes, y suele utilizar acceso posicional. Puede verse como un registro sin nombres de campo o como un producto de tipos. Es útil para devolver varios resultados, formar claves compuestas o modelar coordenadas, aunque un registro nombrado mejora la legibilidad cuando cada componente tiene significado estable.

Un conjunto representa elementos sin duplicados y ofrece operaciones de pertenencia, unión, intersección y diferencia. Su implementación puede basarse en tabla hash, árbol equilibrado o vector de bits. La abstracción es la misma, pero cambian orden, complejidad y consumo. Un conjunto hash suele ofrecer pertenencia promedio O(1); un conjunto ordenado basado en árbol suele ofrecer O(log n) y recorrido ordenado.

Un mapa, diccionario o array asociativo relaciona claves con valores. No es un array porque la clave no tiene por qué ser un entero contiguo. Puede implementarse mediante hash o árbol. La elección determina si se conserva orden, si se admiten consultas por rango y cuál es el comportamiento en el peor caso.

5.4. Tipos algebraicos y variantes

Los tipos suma o variantes permiten que un valor pertenezca a una de varias alternativas etiquetadas. Modelan estados mutuamente excluyentes mejor que una estructura con muchos campos opcionales. Combinados con tipos producto —registros y tuplas— permiten representar dominios complejos de forma segura.

6. MEMORIA DINÁMICA Y LISTAS ENLAZADAS

6.1. Concepto de Estructura Dinámica

Las estructuras dinámicas utilizan asignación dinámica de memoria (heap) y punteros/referencias para crecer y decrecer en tiempo de ejecución según necesidad. A diferencia de arrays con tamaño fijo, las estructuras dinámicas se adaptan a volúmenes de datos variables.

6.2. Listas Enlazadas

6.2.1. Lista Simplemente Enlazada

Secuencia de nodos donde cada nodo contiene datos y referencia al siguiente nodo.

Estructura Nodo:
┌─────────┬──────┐
│ Dato: 5 │ Next │─── →
└─────────┴──────┘

Lista: [10] → [20] → [30] → NULL

Implementación Python:
class Nodo:
    def __init__(self, dato):
        self.dato = dato
        self.siguiente = None

class ListaEnlazada:
    def __init__(self):
        self.cabeza = None

    def insertar_inicio(self, dato):
        nuevo = Nodo(dato)
        nuevo.siguiente = self.cabeza
        self.cabeza = nuevo

6.2.2. Ventajas y Desventajas de Listas Enlazadas

6.2.3. Variantes de Listas Enlazadas

• Lista doblemente enlazada: Cada nodo tiene punteros a siguiente Y anterior, permite recorrido bidireccional

  NULL ← [10] ↔ [20] ↔ [30] → NULL

• Lista circular: Último nodo apunta al primero, no hay NULL

      ┌────────────────┐

  ↓ │
  [10] → [20] → [30]┘

• Lista con nodo centinela: Nodo especial ficticio simplifica lógica de inserción/eliminación

6.3. Asignación dinámica, ciclo de vida y fragmentación

La memoria dinámica se solicita durante la ejecución y se libera cuando deja de ser necesaria. En gestión manual, una fuga aparece cuando se pierde la última referencia a un bloque no liberado; un puntero colgante conserva una dirección cuyo objeto ya no existe; y una doble liberación intenta devolver dos veces el mismo bloque. En sistemas con recolector de basura desaparecen algunas clases de error, pero no el consumo excesivo producido por referencias que siguen vivas innecesariamente.

La fragmentación externa deja huecos libres dispersos que pueden impedir una reserva grande pese a existir memoria total suficiente. La fragmentación interna aparece cuando un bloque asignado contiene espacio no utilizado. Asignadores, pools y arenas intentan reducir estos costes. En estructuras con muchos nodos pequeños, el overhead del asignador y los punteros puede superar el tamaño del dato almacenado.

6.4. Listas y operaciones locales

Una lista enlazada permite inserción o eliminación O(1) cuando se dispone de la referencia al nodo o a su predecesor. Buscar la posición sigue siendo O(n). Decir simplemente que “insertar en una lista es O(1)” es incompleto: si antes hay que localizar el lugar por índice o clave, el coste total incluye esa búsqueda.

Las listas dobles facilitan eliminación y recorrido inverso, pero añaden memoria y más enlaces que mantener. Las listas circulares son útiles en planificación rotatoria y buffers, mientras que los nodos centinela reducen casos especiales en extremos.

7. PILAS, COLAS, DEQUES Y COLAS DE PRIORIDAD

7.1. Pilas (Stacks)

Estructura LIFO (Last In, First Out – Último en Entrar, Primero en Salir)

Visualización:
      ┌───┐
      │ 3 │ ← tope (push 3)
      ├───┤
      │ 2 │
      ├───┤
      │ 1 │
      └───┘

Aplicaciones:
- Evaluación de expresiones (notación postfija)
- Gestión de llamadas a funciones (call stack)
- Deshacer/Rehacer en editores
- Navegación hacia atrás en navegadores
- Parsing de lenguajes

7.2. Colas (Queues)

Estructura FIFO (First In, First Out – Primero en Entrar, Primero en Salir)

Visualización:
  frente                    final
    ↓                         ↓
   [1] → [2] → [3] → [4] → [5]

enqueue(6): añadir al final
dequeue(): eliminar desde frente (retorna 1)

Aplicaciones:
- Buffers de impresión
- Manejo de procesos en CPU (scheduling)
- Breadth-First Search (BFS) en grafos
- Gestión de tareas asíncronas
- Colas de mensajes en sistemas distribuidos

7.2.1. Variantes de Colas

• Cola circular: Implementación eficiente usando array con índices wrap-around
• Cola de prioridad: Elementos tienen prioridad, se extrae el de mayor prioridad (implementada típicamente con heap)
• Deque (Double-Ended Queue): Permite inserción/eliminación en ambos extremos

7.3. Implementaciones sobre array y lista

Una pila puede implementarse sobre un array dinámico usando el final como cima. Así, push y pop tienen coste amortizado O(1). Sobre lista enlazada se opera en la cabeza y el coste es O(1) estricto, a cambio de un nodo y una referencia por elemento. Una cola sobre array debe evitar desplazar todos los elementos al extraer; la solución habitual es un buffer circular con índices de frente y final.

Una deque permite insertar y eliminar por ambos extremos. No equivale a permitir operaciones eficientes en cualquier posición. Una cola de prioridad tampoco es una cola FIFO ordinaria: extrae según prioridad, con frecuencia mediante un heap, y conserva el orden de llegada solo si se añade un criterio secundario.

7.4. Aplicaciones en procesamiento y concurrencia

Las pilas aparecen en llamadas de funciones, evaluación de expresiones, retroceso y recorrido en profundidad. Las colas modelan productores y consumidores, trabajos pendientes, eventos y recorrido en anchura. En concurrencia, una cola debe especificar si es bloqueante, limitada, segura para múltiples hilos y qué política aplica cuando se llena.

8. ÁRBOLES Y ESTRUCTURAS JERÁRQUICAS

8.1. Árboles

Estructura jerárquica donde cada nodo tiene un padre (excepto raíz) y cero o más hijos.

8.1.1. Terminología de Árboles

• Raíz: Nodo superior sin padre
• Hoja: Nodo sin hijos
• Nivel: Distancia de un nodo a la raíz (raíz en nivel 0)
• Altura: Nivel máximo en el árbol
• Grado: Número de hijos de un nodo
• Subárbol: Árbol formado por un nodo y sus descendientes

8.1.2. Árbol Binario

Cada nodo tiene como máximo dos hijos (izquierdo y derecho)

Representación:
        (10)
       /    
     (5)    (15)
    /      /  
  (3) (7)(12)(20)

Implementación:
class NodoArbol:
    def __init__(self, dato):
        self.dato = dato
        self.izquierdo = None
        self.derecho = None

8.1.3. Árbol Binario de Búsqueda (BST)

Árbol binario con propiedad de ordenación: para cada nodo, todos los valores en subárbol izquierdo son menores y todos en subárbol derecho son mayores.

8.1.4. Recorridos de Árboles Binarios

8.2. Árboles equilibrados, heaps y tries

Un árbol binario de búsqueda solo garantiza operaciones logarítmicas cuando su altura se mantiene proporcional al logaritmo del número de nodos. Si se insertan claves ordenadas sin balanceo puede degenerar en una cadena y alcanzar O(n). Árboles AVL y rojo-negro aplican rotaciones para limitar la altura; difieren en el equilibrio exigido y en el coste relativo de búsquedas y actualizaciones.

Un heap binario mantiene una propiedad de prioridad entre padre e hijos, pero no el orden total de un BST. Permite consultar el mínimo o máximo en O(1) e insertar o extraer la raíz en O(log n). Es apropiado para colas de prioridad y algoritmos como heapsort, pero no para buscar una clave arbitraria en tiempo logarítmico.

Un trie organiza cadenas por prefijos. El coste depende de la longitud de la clave y permite autocompletado o búsqueda de prefijos, a cambio de consumo de memoria. Los árboles B y B+ aumentan el factor de ramificación para reducir accesos a bloque; son fundamentales en índices de ficheros y bases de datos. En un B+, los datos o referencias se concentran en hojas enlazadas, lo que facilita recorridos por rango.

9. GRAFOS Y TABLAS HASH

9.1. Grafos

Conjunto de vértices (nodos) conectados por aristas (edges). Generalizan árboles permitiendo ciclos y múltiples padres.

9.1.1. Tipos de Grafos

• Dirigidos vs. No dirigidos: Aristas con/sin dirección
• Ponderados vs. No ponderados: Aristas con/sin peso asociado
• Conexos vs. Disconexos: Existe/no existe camino entre cualquier par de vértices
• Cíclicos vs. Acíclicos: Contienen/no contienen ciclos

9.1.2. Representaciones de Grafos

9.1.3. Algoritmos Fundamentales en Grafos

• Recorrido: DFS (Depth-First Search), BFS (Breadth-First Search)
• Camino más corto: Dijkstra, Bellman-Ford, Floyd-Warshall
• Árbol de Expansión Mínima: Kruskal, Prim
• Ordenación Topológica: Para grafos dirigidos acíclicos (DAG)
• Detección de Ciclos: Mediante DFS con colores
• Componentes Conexas: Identificar subgrafos desconectados

9.2. Tablas Hash (Hash Tables)

Estructura que mapea claves a valores mediante función hash, proporcionando acceso en tiempo promedio O(1).

9.2.1. Resolución de Colisiones

9.3. Coste de las representaciones

Para un grafo con V vértices y E aristas, una matriz de adyacencia consume O(V²) y permite comprobar una arista en O(1). Una lista de adyacencia consume O(V+E) y resulta preferible en grafos dispersos. La respuesta a “qué representación es mejor” depende de densidad, operaciones y necesidad de modificar el grafo.

BFS encuentra caminos mínimos en número de aristas en grafos no ponderados. Dijkstra requiere pesos no negativos; Bellman-Ford admite pesos negativos y detecta ciclos negativos alcanzables; Floyd-Warshall calcula distancias entre todos los pares con coste cúbico. En un DAG, un orden topológico solo existe si no hay ciclos dirigidos.

9.4. Funciones hash, carga y peor caso

Una buena función hash distribuye claves de forma uniforme y es determinista. El factor de carga relaciona elementos y cubetas; al crecer aumenta la probabilidad de colisiones. Muchas implementaciones redimensionan y reinsertan cuando se supera un umbral. El acceso O(1) es promedio o amortizado, no una garantía universal: colisiones adversas pueden degradar a O(n).

El encadenamiento almacena varios elementos por cubeta. El direccionamiento abierto mantiene todos los elementos en el array y busca posiciones alternativas mediante sondeo lineal, cuadrático o doble hash. El borrado en direccionamiento abierto requiere marcas especiales para no romper cadenas de sondeo.

10. CONCEPTO, ATRIBUTOS Y CLASIFICACIÓN DE FICHEROS

10.1. Concepto de Fichero

Un fichero (archivo) es una colección de información relacionada almacenada en dispositivo de almacenamiento secundario (disco duro, SSD, etc.) que persiste más allá de la ejecución del programa. Los ficheros permiten:

• Persistencia: Datos sobreviven al cierre del programa
• Compartición: Múltiples programas pueden acceder al mismo fichero
• Almacenamiento masivo: Datos que no caben en memoria RAM
• Backup y recuperación: Copias de seguridad de información crítica
• Transferencia: Intercambio de datos entre sistemas

10.2. Atributos de Ficheros

Los sistemas de ficheros asocian metadatos a cada fichero:

10.3. Tipos de Ficheros según Contenido

10.3.1. Ficheros de Texto

• Contenido: Secuencia de caracteres legibles (ASCII, UTF-8)
• Estructura: Líneas separadas por caracteres newline (n, rn)
• Legibilidad: Pueden abrirse con editores de texto
• Portabilidad: Alta entre sistemas operativos (aunque newline varía)
• Ejemplos: .txt, .csv, .json, .xml, .html, código fuente
• Ventajas: Legibles por humanos, fácil debugging, versionado amigable (git)
• Desventajas: Mayor tamaño, parsing necesario, menor eficiencia

10.3.2. Ficheros Binarios

• Contenido: Secuencia de bytes interpretada según una especificación de formato.
• Estructura: Puede incluir cabeceras, campos de longitud, offsets, compresión y checksums.
• Legibilidad: Requiere herramientas que conozcan el formato; no es texto directamente editable.
• Portabilidad: Puede ser alta si el formato define orden de bytes, tamaños y versión; serializar memoria nativa sin contrato sí es poco portable.
• Ejemplos: JPEG, PNG, PDF, ejecutables, archivos ZIP y formatos de bases de datos.
• Ventajas: Puede ser compacto y eficiente, y permitir localización estructurada.
• Desventajas: Exige parsing conforme al formato, validación y software compatible.

10.4. Fichero lógico, sistema de ficheros y formato

Conviene distinguir el fichero lógico que maneja una aplicación, el formato que interpreta sus bytes y el sistema de ficheros que administra nombres, directorios, permisos y bloques. Un CSV y un JSON son formatos de datos; NTFS, ext4 o XFS son sistemas de ficheros; y la llamada de lectura o escritura opera sobre un descriptor o manejador proporcionado por el sistema operativo.

La extensión es una convención y no garantiza el contenido. La identificación fiable puede requerir cabeceras, números mágicos, metadatos o validación contra un esquema. Un formato binario no es “cifrado” ni “seguro” por ser ilegible a simple vista; confidencialidad e integridad requieren controles criptográficos y de acceso.

10.5. Registros, campos y longitud

Los ficheros orientados a registros pueden usar longitud fija, variable o delimitada. La longitud fija permite calcular posiciones, pero desperdicia espacio y dificulta campos grandes. La variable aprovecha mejor el almacenamiento, aunque necesita delimitadores, prefijos de longitud, tablas de offsets o estructuras equivalentes. En texto, el delimitador debe escaparse o citarse cuando puede aparecer dentro del campo.

Un registro lógico puede ocupar uno o varios bloques físicos. El factor de bloqueo expresa cuántos registros caben en un bloque cuando son de tamaño fijo. Leer por bloques reduce operaciones físicas y aprovecha que la entrada/salida suele ser mucho más costosa que procesar bytes ya presentes en memoria.

11. ORGANIZACIÓN DE FICHEROS

11.1. Organización de Ficheros

11.1.1. Ficheros Secuenciales

Registros almacenados uno tras otro en orden de entrada.

Representación:
┌─────────┬─────────┬─────────┬─────────┬─────────┐
│ Reg 1   │ Reg 2   │ Reg 3   │ Reg 4   │ Reg 5   │
└─────────┴─────────┴─────────┴─────────┴─────────┘

Para leer Registro 4: leer Reg 1, Reg 2, Reg 3, Reg 4

Ejemplo Python:
# Escritura
with open('empleados.txt', 'a') as f:
    f.write(f"{id},{nombre},{salario}n")

# Lectura secuencial
with open('empleados.txt', 'r') as f:
    for linea in f:
        procesar(linea)

11.1.2. Ventajas y Desventajas de Ficheros Secuenciales

11.1.3. Ficheros Directos (Acceso Aleatorio)

Registros de tamaño fijo almacenados de modo que cualquier registro puede accederse directamente mediante su posición.

Representación (registros de 100 bytes cada uno):
Byte:  0       100     200     300     400     500
      ┌───────┬───────┬───────┬───────┬───────┐
      │ Reg 0 │ Reg 1 │ Reg 2 │ Reg 3 │ Reg 4 │
      └───────┴───────┴───────┴───────┴───────┘

Para leer Registro 3: seek(3 * 100 = 300), read(100 bytes)

Ejemplo Python:
import struct

# Definir formato registro (id: int, nombre: 50 chars, salario: float)
formato = '<I50sf'  # orden little-endian definido: uint32, 50 bytes, float32
tam_registro = struct.calcsize(formato)

# Leer registro específico
def leer_registro(fichero, num_registro):
    with open(fichero, 'rb') as f:
        f.seek(num_registro * tam_registro)
        datos = f.read(tam_registro)
        return struct.unpack(formato, datos)

# Escribir registro en posición
def escribir_registro(fichero, num_registro, id, nombre, salario):
    with open(fichero, 'r+b') as f:
        f.seek(num_registro * tam_registro)
        datos = struct.pack(formato, id, nombre.encode(), salario)
        f.write(datos)

11.1.4. Ventajas y Desventajas de Ficheros Directos

11.1.5. Ficheros Indexados

Combinan datos almacenados secuencialmente con índices separados que permiten acceso directo.

Estructura:

Fichero Índice (ordenado por ID):
┌────────┬──────────┐
│  ID    │ Dirección│
├────────┼──────────┤
│  101   │   0      │
│  205   │   150    │
│  310   │   300    │
│  415   │   480    │
└────────┴──────────┘

Fichero de Datos:
Byte:  0           150         300         480
      ┌───────────┬───────────┬───────────┬───────────┐
      │ Reg ID101 │ Reg ID205 │ Reg ID310 │ Reg ID415 │
      └───────────┴───────────┴───────────┴───────────┘

Buscar empleado ID=310:
1. Búsqueda binaria en índice → encuentra dirección 300
2. Seek a posición 300 en fichero datos
3. Leer registro

11.1.6. Tipos de Índices

• Índice primario: Ordenado según clave primaria, fichero datos también ordenado por esa clave
• Índice secundario: Sobre campo no clave, permite búsquedas por campos alternativos
• Índice denso: Entrada en índice por cada registro
• Índice disperso: Entradas solo para algunos registros (fichero datos debe estar ordenado)
• Índice multinivel: Índice sobre índice, árbol B+

11.1.7. Ventajas y Desventajas de Ficheros Indexados

11.2. Organización secuencial ordenada y no ordenada

En una organización secuencial no ordenada los registros se añaden normalmente al final y las búsquedas por clave requieren exploración. Si el fichero se mantiene ordenado, el recorrido y las operaciones por rango mejoran, pero insertar puede exigir reescritura, uso de áreas de desbordamiento o procesos periódicos de reorganización. El procesamiento por lotes explota bien la secuencia ordenada: dos ficheros ordenados pueden combinarse mediante un recorrido de mezcla lineal.

11.3. Organización directa o relativa

En un fichero relativo, los registros de longitud fija se identifican mediante un número relativo de registro. La posición puede calcularse como cabecera más número de registro multiplicado por longitud. Es eficiente cuando la clave puede transformarse de manera directa y el espacio de direcciones no es excesivamente disperso. Deben gestionarse posiciones vacías, borrados y crecimiento.

11.4. Organización indexada e indexada-secuencial

El índice contiene pares de clave y dirección o punteros a bloques. Puede ser denso —una entrada por registro— o disperso —una entrada por bloque o grupo—; primario o secundario; único o no único; de uno o varios niveles. Los índices multinivel reducen búsquedas a pocos accesos de bloque. Los árboles B/B+ mantienen orden y equilibrio frente a inserciones y eliminaciones.

La organización indexada-secuencial combina un área principal ordenada, índices y, en modelos clásicos, áreas de desbordamiento. Facilita tanto recorrido secuencial como acceso por clave. Requiere mantenimiento: dividir páginas, actualizar entradas, fusionar nodos y reorganizar cuando se acumulan desbordamientos.

11.5. Organización hash

La dirección se deriva de una función sobre la clave. Es adecuada para igualdad exacta y puede ser muy rápida en promedio. No preserva el orden y es poco apropiada para rangos. Las colisiones se resuelven mediante cubetas, encadenamiento, áreas de desbordamiento o direccionamiento abierto. Una mala distribución o un factor de carga alto degrada el rendimiento.

12. MÉTODOS DE ACCESO EN EL TRATAMIENTO DE FICHEROS

12.1. Métodos de Acceso a Ficheros

12.1.1. Acceso Secuencial

Lectura de registros en orden, desde el principio hasta el final.

# Python - Acceso secuencial
with open('datos.txt', 'r') as f:
    for linea in f:
        procesar(linea)

# Java - Acceso secuencial
BufferedReader br = new BufferedReader(new FileReader("datos.txt"));
String linea;
while ((linea = br.readLine()) != null) {
    procesar(linea);
}
br.close();

Características:

• Simple y eficiente para procesar todo el fichero
• Aprovecha lectura anticipada del sistema operativo (read-ahead)
• Óptimo para ficheros en medios secuenciales (cintas magnéticas históricamente)
• No requiere seek, posición avanza automáticamente

12.1.2. Acceso Directo/Aleatorio

Lectura/escritura en cualquier posición del fichero mediante seek.

# Python - Acceso aleatorio
with open('datos.bin', 'r+b') as f:
    # Leer byte en posición 1000
    f.seek(1000)
    dato = f.read(4)

    # Escribir en posición 5000
    f.seek(5000)
    f.write(nuevo_dato)

    # Posicionamiento relativo
    f.seek(100, 1)  # Avanzar 100 bytes desde posición actual
    f.seek(-50, 2)  # Retroceder 50 bytes desde final

# Java - Acceso aleatorio
RandomAccessFile raf = new RandomAccessFile("datos.bin", "rw");
raf.seek(1000);
int dato = raf.readInt();
raf.seek(5000);
raf.writeInt(nuevoDato);
raf.close();

Operaciones seek:

• seek(offset, whence): Posicionar puntero de fichero
  • whence=0: Desde inicio (absoluto)
  • whence=1: Desde posición actual (relativo)
  • whence=2: Desde final
• tell(): Obtener posición actual del puntero

12.1.3. Acceso Indexado

Uso de índices para localizar rápidamente registros por clave.

# Pseudocódigo acceso indexado
def buscar_por_clave(indice, fichero_datos, clave_buscada):
    # 1. Búsqueda en índice
    entrada = indice.buscar(clave_buscada)  # Búsqueda binaria O(log n)

    if entrada:
        # 2. Acceso directo a datos
        fichero_datos.seek(entrada.direccion)
        registro = fichero_datos.read(entrada.tamaño)
        return registro
    else:
        return None

12.1.4. Acceso Hash

Uso de función hash para calcular posición directa del registro.

# Pseudocódigo de acceso hash persistente
def buscar_por_hash(fichero, clave):
    cubeta = hash_estable(clave) % numero_cubetas
    offset = cabecera + cubeta * tamano_cubeta
    fichero.seek(offset)
    registros = leer_cubeta(fichero, tamano_cubeta)
    return buscar_clave_o_desbordamiento(registros, clave)

# La función debe estar especificada y ser estable entre ejecuciones.
# No debe usarse sin más un hash aleatorizado del runtime.

Ventajas del acceso hash:

• Acceso en tiempo O(1) promedio
• No requiere índices separados
• Muy eficiente para grandes volúmenes de datos

Desventajas del acceso hash:

• Colisiones requieren resolución
• Espacio desperdiciado si factor de carga bajo
• No mantiene orden de claves
• Búsquedas por rango ineficientes

12.2. El método de acceso como interfaz de tratamiento

La organización describe cómo están dispuestos los registros; el método de acceso es el conjunto de operaciones mediante el que el programa los trata. Una misma organización puede admitir más de un método. Un fichero indexado puede recorrerse secuencialmente por clave y también consultarse directamente a través del índice.

El acceso secuencial mantiene una posición corriente y procesa registros en orden. Es natural para lecturas completas, copias, clasificación externa y procesos batch. El acceso directo posiciona mediante un desplazamiento o número relativo; requiere que la posición pueda calcularse o conocerse. El acceso indexado traduce una clave a una ubicación por medio de una estructura auxiliar. El acceso hash calcula la cubeta a partir de la clave.

12.3. Acceso por rango, clave primaria y claves secundarias

Las consultas por rango necesitan orden. Un índice B+ permite localizar el primer valor y continuar por hojas enlazadas. Un índice hash resuelve bien igualdad, pero no “entre fecha A y fecha B”. Las claves secundarias pueden no ser únicas; su índice apunta a listas de referencias o a múltiples entradas. El coste de actualización aumenta con cada índice adicional.

12.4. Posicionamiento y desplazamientos

Operaciones como seek cambian el desplazamiento asociado a un manejador. En un fichero de bytes permiten situarse respecto al inicio, posición actual o final, pero no convierten automáticamente un formato variable en acceso semántico por registro. En texto con codificación variable, un desplazamiento arbitrario puede caer dentro de una secuencia multibyte.

13. OPERACIONES, BUFFERING, CONCURRENCIA E INTEGRIDAD

13.1. Operaciones sobre Ficheros

13.1.1. Operaciones Básicas

13.1.2. Modos de Apertura de Ficheros

13.1.3. Gestión de Recursos: Context Managers

# Python - Uso recomendado con context manager (with)

# Cierra automáticamente el fichero incluso si hay excepción

with open('datos.txt', 'r') as f:

    contenido = f.read()

    procesar(contenido)

# Fichero cerrado automáticamente aquí

# Equivalente sin context manager (menos recomendado)
f = open('datos.txt', 'r')
try:
    contenido = f.read()
    procesar(contenido)
finally:
    f.close()  # Asegurar cierre incluso con excepción

13.2. Buffering, caché y entrada/salida

Las bibliotecas interponen buffers para agrupar lecturas y escrituras. La aplicación puede creer que ha escrito cuando los datos solo están en memoria de usuario o del sistema operativo. flush fuerza el vaciado hacia capas inferiores, pero la durabilidad frente a caída puede requerir primitivas adicionales y depende del sistema de ficheros y dispositivo. Cerrar correctamente el manejador libera recursos y completa operaciones pendientes.

13.3. Actualización, borrado y compactación

Actualizar un registro de longitud fija puede sobrescribirlo in situ. Si la longitud variable crece, puede ser necesario moverlo y dejar un puntero, reservar espacio libre o reescribir el fichero. El borrado lógico marca registros y permite reutilizar huecos; la compactación física recupera espacio y mejora localidad, a costa de una operación más costosa.

13.4. Concurrencia y bloqueo

Cuando varios procesos acceden al mismo fichero deben coordinarse. Los bloqueos pueden aplicarse al fichero completo, a regiones o a registros y ser compartidos o exclusivos. Sin coordinación aparecen actualizaciones perdidas, lecturas parciales y condiciones de carrera. Los bloqueos asesores solo funcionan si todos los participantes respetan el protocolo; los obligatorios son menos habituales y dependen de plataforma.

13.5. Integridad, atomicidad y recuperación

Una actualización compuesta debe evitar estados intermedios visibles. Patrones como escribir en un fichero temporal, sincronizar y renombrar atómicamente reducen el riesgo para reemplazos completos. Los diarios o logs de escritura anticipada permiten rehacer o deshacer cambios. Las sumas de verificación detectan corrupción accidental, pero no sustituyen autenticación criptográfica frente a alteración intencionada.

13.6. Clasificación externa y fusión

Cuando los datos no caben en memoria se emplea clasificación externa: se generan tramos ordenados que sí caben en RAM y después se fusionan. La mezcla de k vías usa buffers y, con frecuencia, una cola de prioridad para seleccionar el menor elemento de los tramos. Es un ejemplo de cómo estructuras en memoria y organización de ficheros se combinan.

14. COMPLEJIDAD Y CRITERIOS DE SELECCIÓN

14.1. Notaciones O, Ω y Θ

La notación O expresa una cota superior asintótica; Ω una cota inferior y Θ una cota ajustada. En preguntas de estructuras suele usarse O de forma informal para describir el crecimiento dominante. Debe especificarse si se habla de caso peor, promedio, esperado o amortizado. Una tabla hash tiene acceso esperado O(1), pero peor caso O(n); un array dinámico tiene inserción al final amortizada O(1), aunque una ampliación individual es O(n).

14.2. Tiempo frente a espacio

Los índices, tablas auxiliares y caches consumen espacio para reducir tiempo. Una matriz de adyacencia sacrifica O(V²) para consultar aristas en O(1); una lista enlazada ahorra desplazamientos, pero añade punteros y pierde localidad; un fichero indexado añade almacenamiento y coste de mantenimiento para evitar exploraciones completas. No existe una estructura óptima para todas las operaciones.

14.3. Criterios de selección

14.4. Medición y perfilado

La complejidad guía el diseño, pero debe complementarse con medición. Distribución de claves, tamaño de registros, caché, almacenamiento, concurrencia y lenguaje pueden cambiar el resultado. El perfilado identifica cuellos de botella reales y evita optimizar partes irrelevantes.

15. APLICACIÓN EN SISTEMAS DE INFORMACIÓN DEL SAS

15.1. Uso en aplicaciones sanitarias y administrativas

Los sistemas del Servicio Andaluz de Salud procesan grandes volúmenes de información clínica, administrativa y técnica. Sin atribuir una implementación concreta a cada producto, los principios del tema aparecen en cualquier arquitectura: colecciones de profesionales o citas, colas de integración, índices por identificadores, árboles para clasificaciones jerárquicas, grafos para dependencias y ficheros para cargas, exportaciones, logs y documentos.

En un proceso de carga masiva, por ejemplo, el fichero de entrada debe definir codificación, delimitadores, esquema, obligatoriedad, claves y tratamiento de errores. Leerlo secuencialmente resulta natural; una tabla hash en memoria puede detectar duplicados; una cola puede desacoplar validación y persistencia; y un fichero de rechazos conserva las líneas no procesadas con su causa. La estructura elegida afecta a trazabilidad y capacidad de reanudación.

15.2. Identificadores y claves

Los identificadores sanitarios o administrativos no deben confundirse con posiciones físicas. Una clave estable identifica una entidad; el índice traduce esa clave a una ubicación cambiante. Guardar directamente offsets externos crea acoplamiento con la organización física y dificulta reorganización. La aplicación debe validar formato y dominio, pero no inferir significados no garantizados.

15.3. Intercambio y persistencia

Los formatos de intercambio textuales facilitan interoperabilidad y diagnóstico, pero requieren validación y pueden aumentar tamaño. Los binarios pueden ser compactos y rápidos, aunque exigen especificación y herramientas. En ambos casos deben establecerse versión, codificación, esquema y compatibilidad. Un fichero recibido no es confiable por provenir de un sistema interno: debe limitarse tamaño, validar estructura y evitar rutas, nombres o contenidos manipulados.

15.4. Seguridad y protección de datos

Los ficheros con datos personales requieren controles de acceso, cifrado cuando proceda, registro de operaciones, retención y borrado conforme a la política aplicable. Las copias temporales y exportaciones son especialmente sensibles porque pueden quedar fuera de los controles del sistema principal. El diseño debe minimizar datos, separar entornos y evitar incluir información clínica en nombres de fichero o logs no protegidos.

16. IDEAS CLAVE, TRAMPAS Y REPASO FINAL

16.1. Distinciones que deben memorizarse

• Tipo frente a variable: el tipo define dominio y operaciones; la variable es una instancia o referencia.
• Estructura abstracta frente a implementación: pila, cola o mapa describen comportamiento; array, lista, heap o árbol materializan ese comportamiento.
• Tamaño lógico frente a capacidad: un array dinámico puede reservar más espacio del que contiene.
• Acceso directo frente a indexado: el directo calcula o conoce la posición; el indexado consulta una estructura auxiliar.
• Organización frente a formato: secuencial, indexada o hash describen disposición; CSV, JSON o binario describen representación.
• Hash promedio frente a peor caso: O(1) esperado no elimina colisiones ni degradación.
• Texto frente a Unicode: un fichero de texto necesita una codificación; los caracteres no son bytes sin contexto.

16.2. Errores frecuentes de diseño

Entre los errores más habituales están elegir una lista por su inserción O(1) ignorando la búsqueda previa, serializar estructuras de memoria sin especificar formato, comparar flotantes por igualdad exacta, usar un índice hash para rangos, recorrer repetidamente un fichero secuencial para consultas puntuales, o mantener demasiados índices sin considerar el coste de actualización.

También es frecuente confundir un sistema de ficheros con una organización de registros, asumir que el cierre de una API implica persistencia física inmediata, o tratar el valor nulo como equivalente a cero. En un examen, estas confusiones se explotan mediante opciones técnicamente próximas pero de distinto nivel de abstracción.

17. MAPA CONCEPTUAL