1. Tipos de Datos Abstractos

#estructuraDeDatos #universidad

a. Definición de estructuras de datos

Estructuras de datos son formas de organizar y almacenar datos de manera que se puedan utilizar de manera eficiente. Permiten gestionar y manipular datos de acuerdo con las necesidades específicas de una aplicación.

i. Estructuras de datos estáticas

• Definición: Son aquellas cuya memoria es asignada de manera fija durante la compilación. El tamaño de estas estructuras no puede cambiar durante la ejecución del programa.

• Características:

  • Uso eficiente de la memoria cuando el tamaño es conocido de antemano.
  • Acceso rápido a los elementos.
  • Limitaciones en cuanto a la flexibilidad.

• Ejemplos:

  • Arreglos (Arrays)
  • Registros (Records)

ii. Estructuras de datos dinámicas

• Definición: Permiten la asignación y liberación de memoria durante la ejecución del programa. Su tamaño puede ajustarse según las necesidades.

• Características:

  • Mayor flexibilidad.
  • Puede manejar tamaños variables de datos.
  • Mayor complejidad en la gestión de memoria.

• Ejemplos:

  • Listas enlazadas (Linked Lists)
  • Árboles
  • Grafos

b. Introducción a los tipos de datos abstractos (TDA)

Tipos de Datos Abstractos (TDA) son modelos matemáticos para tipos de datos, donde se define su comportamiento desde el punto de vista del usuario, sin especificar cómo se implementan internamente.

i. Definición de tipos de datos abstractos

Un TDA especifica:

• Operaciones: Qué se puede hacer con los datos (por ejemplo, insertar, eliminar, buscar).
• Propiedades: Las reglas y características que las operaciones deben cumplir.

ii. Aplicaciones de los tipos de datos abstractos

• Facilitan el diseño modular: Permiten separar la interfaz de la implementación.
• Promueven la reutilización del código: Los mismos TDA pueden ser implementados de diferentes maneras.
• Mejoran la mantenibilidad: Cambios en la implementación interna no afectan a quienes usan el TDA.

Ejemplos de TDA:

• Pilas (Stacks): LIFO (Último en entrar, primero en salir)
• Colas (Queues): FIFO (Primero en entrar, primero en salir)
• Listas: Secuencia ordenada de elementos
• Diccionarios (Maps): Asociación clave-valor

Ejemplos Prácticos

Ejemplo 1: Implementación de una pila utilizando un arreglo (Estructura estática)

#define MAX 100
typedef struct {
    int datos[MAX];
    int cima;
} Pila;

void inicializarPila(Pila *p) {
    p->cima = -1;
}

int estaVacia(Pila *p) {
    return p->cima == -1;
}

int estaLlena(Pila *p) {
    return p->cima == MAX - 1;
}

void apilar(Pila *p, int elemento) {
    if (!estaLlena(p)) {
        p->datos[++(p->cima)] = elemento;
    }
}

int desapilar(Pila *p) {
    if (!estaVacia(p)) {
        return p->datos[(p->cima)--];
    }
    return -1; // Indicador de error
}

Ejemplo 2: Implementación de una lista enlazada simple (Estructura dinámica)

typedef struct Nodo {
    int dato;
    struct Nodo *siguiente;
} Nodo;

Nodo* crearNodo(int valor) {
    Nodo *nuevo = (Nodo*)malloc(sizeof(Nodo));
    nuevo->dato = valor;
    nuevo->siguiente = NULL;
    return nuevo;
}

void insertarInicio(Nodo **cabeza, int valor) {
    Nodo *nuevo = crearNodo(valor);
    nuevo->siguiente = *cabeza;
    *cabeza = nuevo;
}

Ejercicios

1. Definición de TDA:

   • Define qué es un TDA y da tres ejemplos diferentes de TDA que no se hayan mencionado anteriormente.

2. Implementación de una cola:

   • Implementa una cola (FIFO) utilizando una lista enlazada en el lenguaje de programación de tu preferencia. Incluye operaciones de encolar, desencolar y verificar si está vacía.

3. Comparación de estructuras:

   • Explica las ventajas y desventajas de utilizar una estructura de datos estática frente a una dinámica en el contexto de una aplicación que maneja una cantidad variable de usuarios.