Tipos de datos abstractos estáticos y dinámicos

wow

Estructura de Datos

Mtra. Azucena Nuño

Go!

wow

Tipos de datos abstractos estáticos y dinámicos

Listas

Go!

TDA´s

Los Tipos de Datos Abstractos (TDA) son una abstracción en programación que se refiere a la especificación de un conjunto de operaciones sin definir la implementación concreta. Los TDAs pueden ser estáticos o dinámicos.

TDA´s

TDA Estático: Son estructuras de datos cuyo tamaño se determina en tiempo de compilación. Ejemplos incluyen arrays y structs. Se gestionan en la pila de memoria.

TDA Dinámico: Su tamaño se determina en tiempo de ejecución, utilizando memoria dinámica. Ejemplos son listas enlazadas, pilas y colas. Requieren una gestión cuidadosa de la memoria para evitar fugas.

Lista como TDA Dinámico: Una lista puede implementarse como un TDA dinámico en C++. Permite la manipulación de elementos de manera flexible (inserción, eliminación).

Búsquedas en TDA´s: Las búsquedas en TDAs varían según la estructura. En listas, se pueden realizar búsquedas secuenciales o binarias dependiendo de la implementación.

Concepto

A nivel macro, una lista es un conjunto de elementos ordenados. Este concepto es utilizado todo el tiempo en nuestra vida contidiana, por ejemplo:

• Cuando queremos comprar ciertos alimentos en el supermercado.
• Cuando queremos tener la información de todos los invitados a un cumpleaños.
• Cuando queremos organizarnos para hacer ciertas tareas en un día.
• Coincidentemente, esto es una lista.

Informática En la informática hay ciertas operaciones que se pueden realizar sobre una lista, aunque dependiendo del problema a ser resuelto, puede sufrir variaciones.

• Crear.
• Destruir.
• Insertar en posición n.
• Eliminar en posición n.
• ¿Esta vacía?.
• Ver elemento en posición n.

Las operaciones mas comunes que se hacen sobre una lista son:

En C++, una lista generalmente se refiere a una estructura de datos llamada "lista enlazada". Una lista enlazada es una colección de elementos organizados de manera secuencial, donde cada elemento (nodo) contiene datos y un puntero que apunta al siguiente nodo. Esta estructura permite la inserción y eliminación eficientes de elementos en cualquier posición de la lista.

Lista, concepto en C++

Lista estática en C++

En el contexto de estructuras de datos, una lista estática en C++ se refiere a una lista cuyo tamaño está predefinido y no cambia durante la ejecución del programa. Generalmente, se implementa utilizando un array de tamaño fijo para almacenar los elementos.

Búsquedas en los TDA'S

Las búsquedas en los Tipos de Datos Abstractos (TDA) en C++ dependen del TDA específico y la implementación que se esté utilizando. Aquí se destacan algunas consideraciones comunes:

TDA Árboles Binarios de Búsqueda (ABB): Las búsquedas en un ABB suelen realizarse de manera eficiente, aprovechando la propiedad de ordenamiento. Se comparan los elementos y se decide si moverse a la rama izquierda o derecha del árbol según el valor buscado. Ejemplo de primitivas para un ABB: constructor, búsqueda, inserción, eliminación

TDA Lista: Las búsquedas en una lista pueden ser secuenciales. Se recorre la lista desde el principio hasta encontrar el elemento buscado o llegar al final si no se encuentra. Se pueden utilizar algoritmos de búsqueda, como la búsqueda secuencial o binaria, según la naturaleza de la lista

Es importante revisar la documentación específica del TDA que estás utilizando y entender la eficiencia de las operaciones de búsqueda en esa implementación particular.

Las listas ligadas en C++ son estructuras de datos dinámicas que permiten almacenar y acceder a datos de manera flexible.

Diferencia entre Lista Ligada y Arreglo

Estructura Estática:

Estructura Dinámica:

La lista ligada es una estructura de datos dinámica que asigna memoria a medida que se agregan elementos. Los elementos se almacenan en nodos que contienen datos y un puntero al siguiente nodo.

Los arreglos son estructuras de datos estáticas con tamaño fijo predefinido en la declaración.

Tamaño Fijo:

Tamaño Dinámico:

Tienen un tamaño fijo que se determina en tiempo de compilación y no puede cambiar durante la ejecución.

Pueden cambiar de tamaño fácilmente, ya que la memoria se asigna dinámicamente.

Acceso Directo:

Inserción y Eliminación Eficientes:

Permite un acceso directo a los elementos mediante índices, sin necesidad de recorrer la estructura.

Las operaciones de inserción y eliminación son eficientes, ya que solo se ajustan los punteros.

Inserción y Eliminación Costosas:

Acceso Secuencial:

Las operaciones de inserción y eliminación pueden ser costosas, especialmente en el medio del arreglo, ya que requieren desplazar elementos.

El acceso a los elementos es secuencial y requiere recorrer la lista desde el principio.

Resumen:

Las listas ligadas son flexibles en tamaño y eficientes para operaciones de inserción/eliminación, pero el acceso es secuencial. Los arreglos tienen tamaño fijo, permiten acceso directo, pero las operaciones de inserción/eliminación pueden ser costosas

Visual beings

Narrative beings

We can understand images from millions of years ago, even from other cultures.

We tell thousands and thousands of stories. ⅔ of our conversations are stories.