Estructura de datos

Autor: Víctor Marzal vmarzal@retemail.es Última actualización: 18 de noviembre de 2000 Este curso pertenece a la web: http://rinconprog.metropoli2000.com/

Curso de Estructuras de Datos

Víctor Marzal

Curso de Estructuras de Datos
Este curso pretende servir a todos aquellos interesados en el aprendizaje de las estructuras: t eoría y aplicaciones. Por el momento, estos son los capítulosque han ido apareciendo: Capítulo 1 Introducción Tipos de datos Estructuras de datos Tipos abstractos de datos Tablas, vectores o arrays Fundamentos y representación Recuperación de información Búsqueda secuencial Búsqueda dicotómica El problema de la ordenación. Métodos directos de ordenación Inserción Selección Intercambio Pilas y colas Fundamentos Representación Aplicaciones Pilas y colasmúltiples Listas Fundamentos Listas enlazadas Pilas y colas enlazadas Operaciones sobre listas enlazadas Listas doblemente enlazadas Listas generalizadas Arboles Arboles Fundamentos y terminología básica Arboles binarios Representación de los árboles binarios Recorrido de árboles binarios Operaciones con árboles binarios Arboles binarios enlazados Arboles Representación de árboles generales como árbolesbinarios Arboles binarios de búsqueda Montículos binarios Grafos Fundamentos y terminología básica Representación de grafos Recorrido de grafos Arboles de extensión de un grafo Arbol de extensión de coste mínimo

Capítulo 2 Capítulo 2 (i)

Capítulo 2 (ii)

Capítulo 3

Capítulo 4

Capítulo 5 Capítulo 5 (i)

Capítulo 5 (ii)

Capítulo 6

Ultima modificación: 18 de noviembre de 2000Autor: Víctor Marzal

http://rinconprog.metropoli2000.com

-2-

Curso de Estructuras de Datos

Víctor Marzal

Curso de Estructuras de Datos 1. Tipos de datos, estructuras de datos y tipos abstractos de datos
La abstracción es un mecanismo fundamental para la comprensión de fenómenos o situaciones que implican gran cantidad de detalles. La idea de abstracción es uno de los conceptos máspotentes en el proceso de resolución de problemas. Se entiende por abstracción la capacidad de manejar un objeto (tema o idea) como un concepto general, sin considerar la enorme cantidad de detalles que pueden estar asociados con dicho objeto. Sin abstracción no sería posible manejar, ni siquiera entender, la gran complejidad de ciertos problemas. Por ejemplo, sería inimaginable pensar en elpresidente de una gran multinacional que viese la empresa en términos de cada trabajador in dividual o de cada uno de los objetos que fabrica, en vez de departamentos especializados. El proceso de abstracción presenta dos aspectos complementarios: i. ii. descartar los aspectos relevantes del objeto ignorar aspectos irrelevantes del mismo (la irreleva ncia depende del nivel de abstracción, ya que si sepasa a niveles más concretos, es posible que ciertos aspectos pasen a ser relevantes).

Se puede decir que la abstracción permite estudiar los fenómenos complejos siguiendo un método jerárquico, es decir, por sucesivos niveles de detalle. Generalmente, se sigue un sentido descendente, desde los niveles más generales a los niveles más concretos. Los programas son objetos complejos que puedencontener varios miles de instrucciones, cada una de las cuales puede dar lugar a un error del programa y que, por lo tanto, necesitan mecanismos de definición que eviten en la medida de lo posible que el programador cometa errores. Así, los lenguajes de programación de alto nivel permiten al programador abstraerse del s in fin de detalles de los lenguajes ensambladores y permiten trabajar de maneraindependiente respecto a las máquinas sobre las que finalmente se hará funcionar el programa. En el proceso de programación se puede extender el concepto de abstracción tanto a las acciones, mediante la llamada abstracción procedural (uso de procedimientos), como a los datos, mediante los llamados tipos abstractos de datos. La idea de programación procedural aparece ya en los primeros lenguajes de...