Estructura datos

Estructura de Datos

Temario
• Abstracción en lenguajes de programación
– Tipos Abstractos de Datos – Especificación de los TAD

• Pilas
– Especificación del TAD Pila – Representación estática – Representación dinámica

• Colas
– Especificación del TAD Cola – Representación estática – Representación dinámica – Colas circulares – Colas de prioridades

Temario
• Listas enlazadas –Operaciones en listas enlazadas – Listas doblemente enlazadas • Tablas Hash – Operaciones de una tabla hash • Recursividad – Directa e indirecta – Backtracking • Arboles binarios – Recorridos de un árbol – Arboles de Expresión – Árboles de Búsqueda

Temario
• Árbol Equilibrado de Búsqueda
– Rotación simple – Rotación doble • Árboles B – Tipo Abstracto Árbol • Ejemplos de Aplicaciones conEstructuras de Datos • Implementación de aplicaciones – Definición y análisis del problema – Diseño y Programación

Bibliografia
Allen Weiss Mark, Estructuras y Algoritmos 2a. Ed.,. Addison­­Wesley. Cairo Osvaldo, Estructuras de Datos, Mc. Graw­Hill Heileman Gregory L., Estructuras de Datos, Algoritmos y Programación Orientada a Objetos, Mc. Graw Hill Ros Muñoz Salvador, Estructura De Datos YAlgoritmos, Pearson Educación Tenenbaum Aaron, Langsam Yedidyah, Estructuras de Datos en C, 2a Edición

Introducción
• Una computadora es una máquina que manipula información. Es importante para un ingeniero en sistemas comprender como se organiza, manipula y emplea la información en la computadora.

Memoria
• La memoria de una computadora esta dividida en tres secciones: la memoriaprincipal, la memoria secundaria (persistente) y la memoria cache.

Memoria principal
• La memoria principal, también conocida como memoria de acceso aleatorio (RAM), es donde se almacenan las instrucciones (programas) y datos. Es importante recordar que esta memoria es volátil y la información se perderá una vez que se apague la computadora.

Memoria secundaria
• La memoria secundaria es undispositivo de almacenamiento externo tal como un disco duro, la cual también almacena datos e instrucciones. La información almacenada en estos dispositivos es persistente.

Memoria cache
• La memoria cache es utilizada para almacenar instrucciones que se utilizan de manera frecuente, así como datos que han sido o serán utilizados por la unidad central de proceso. • Un segmento de la memoriacaché es conocido como registro. Un registro se utiliza para almacenar de manera temporal instrucciones y datos.

Almacenamiento
• Una unidad de memoria generalmente almacena un byte de información, sin embargo los datos usados en un programa pueden ser grandes y requerir de más bytes para su almacenamiento. • Es por esta razón que cualquier dato que se vaya a almacenar en la computadora requiereinformarle a la máquina cuanto memoria necesita reservar para el tipo de dato que utilizaremos.

Tipos de datos
• Los tipos de datos más comunes son:
– Entero – Flotante – Caracter – Booleano

Organización de la memoria
• La memoria la podemos representar como una serie de cajas organizadas en grupos de 8 bits. • A cada una de las 8 cajas se le asigna un número único llamado dirección dememoria. • Generalmente las direcciones de memoria se representan a través de números hexadecimales.

Organización de la memoria

23FF41

23FF42

23FF43

23FF44

Abstracción
• A pesar de que todas las computadoras cuentan con arquitecturas similares (CPU, Memoria, Dispositivos E/S) difieren en la forma en la que se administran estos recursos. • La cantidad de memoria que se reservapara un dato de tipo entero varia dependiendo de la arquitectura.

Abstracción
• Cuando se desea plantear un algoritmo no se consideran algunos detalles particulares de la arquitectura en la cual se implementará. • Esto ayuda a que la solución propuesta pueda ser fácilmente adaptada. • A esta característica se le llama abstracción.

Tipo de dato abstracto (TDA)
• Un tipo de dato...