Estructura De Datos

ÍNDICE

INTRODUCCION……………………………………………………………………. 03

ANTECEDENTES……………………………………………………………………. 04

OBJETIVO……………………………………………………………………………. 04

1. INTRODUCCIÓN A LA ESTRUCTURA DE DATOS………………………… 05

1.1 TIPOS DE DATOS ABSTRACTOS (TDA)………………………………… 05

1.2 MODULARIDAD……………………………………………………………… 05

1.3 USO DE TDA………………………………………………………………….. 05

1.4 MEMORIA ESTÁTICA………………………………………………………. 06

1.5 MEMORIA DINÁMICA……………………………………………………… 08

2. RECURSIVIDAD………………………………………………………………….. 08

2.1 DEFINICIÓN………………………………………………………………….. 08

2.2 PROCEDIMIENTOS RECURSIVOS……………………………………….. 09

3. ESTRUCTURAS LINEALES…………………………………………………….. 10

3.1 LISTAS………………………………………………………………………… 10

3.2 PILAS………………………………………………………………………….. 12

3.3 COLAS………………………………………………………………………… 13

4. ESTRUCTURAS NO LINEALES………………………………………………... 14

4.1 ÁRBOLES……………………………………………………………………… 14

4.2 GRAFOS………………………………………………………………………. 16

5. MÉTODOS DE ORDENAMIENTO……………………………………………... 17

5.1 INTERNO……………………………………………………………………... 17

5.2 EXTERNO…………………………………………………………………….. 19

6. MÉTODOS DE BÚSQUEDA……………………………………………………... 20

6.1 SECUENCIAL…………………………………………………………………. 21

6.2 BINARIA……………………………………………………………………….. 21

6.3 FUNCIONES HASH…………………………………………………………... 21

CONCLUSIONES…………………………………………………………………….. 23

REFERENCIAS………………………………………………………………………. 23

INTRODUCCIÓN

En presente trabajo conformado de seis capítulos busca la aplicación del conocimiento en un proyecto integrador que incorpore de manera progresiva los temas vistos en el siguiente trabajo.

En la primera unidad contamos con una introducción a la estructura de datos, los tipos de datos abstractos, aplicaciones de la modularidad, el uso de TDA y la definición de la memoria estática y dinámica.

En la segunda unidad abordamos definiciones, mecanismos y características de la recursividad, aplicando a estos a la creación de procedimientos.

La tercera unidad trata sobre las estructuras lineales: listas, pilas y colas. La representación de pilas y colas puede darse a través de vectores (memoria estática) apuntadores y/o referencia (memoria dinámica). Se analizan otras variantes como el cado de las colas circulares, listas simples y doblemente enlazadas.

En la cuarta unidad trata de la estructuras no lineales conocidas como árboles y grafos que permiten dar solución a problemas complejos a través de la recursividad y la utilización de memoria dinámica.

En la quinta unidad se encuentra los tipos de ordenamiento interno y externo.

En la sexta unidad se muestran los métodos de búsqueda, como la secuencial, binaria y las funciones HASH.

ANTECEDENTES

La humanidad se ha interesado pos los datos, y aunque en la actualidad a menudo se asocia el concepto de datos con la computadora, históricamente han existido otros métodos primitivos de manejo de información; en realidad, algunos siguen siendo utilizados.

El desarrollo de las base de datos en las primeras épocas de procesamiento automático de datos, la mayor parte del tiempo y de la atención en el desarrollo de la aplicación se invertía en los programas, en vez de dedicarlos a los datos y las estructuras de éstos.

El hardware era costoso y limitado en cuando a la velocidad de la recuperación de los datos. La programación era una nueva disciplina y había mucho que hacer a fin de lograr un procesamiento eficiente. La mecanización parcial del proceso de programación o aun la estandarización de estilo, se desconocían. En este medio el tratamiento de los datos difícilmente era la preocupación de mayor prioridad. Conforme creció el procesamiento de datos, empezaron a cambiar ciertas circunstancias básicas. El hardware se volvió más barato, el desarrollo del software tomo una forma más estandarizada y estructurada, y se acumularon muchas aplicaciones nuevas que debían realizarse, provocando que la gran cantidad de tiempo dedicado a mantener programas existentes resultara cada vez menos aceptable. Se volvió más claro que la forma en la que se manejaban los datos en el pasado, era uno de los principales factores en el problema de mantenimiento de programas al que se enfrentaban los programadores.

Así insatisfechos por las técnicas aplicadas para la soluciones de los problemas planteados, algunos diseñadores de sistemas empezaron a buscar, a finales de la década de los setenta, diversas formas de consolidar las actividades utilizando un método de base de datos.

OBJETIVO

Enseñar la correcta selección y aplicación de las estructuras de datos en la solución de problemas, así como determinar la eficiencia de algoritmos que permitan la selección de los mismos con el fin de desarrollar soluciones eficientes, siendo este tema fundamental para el análisis, diseño y desarrollo de sistemas de información.

1. INTRODUCCIÓN A LA ESTRUCTURA DE DATOS

Se define como dato una representación simbólica de un atributo o variable cuantitativa, puede ser de tipo numérico, alfabético, algorítmica etc. con los datos se puede describir hechos empíricos, sucesos o entidades. La estructura de datos o de archivos puede definirse como aquellos datos que denotan un conjunto de hechos, que pueden servir como operadores en una base de datos y cuya estructura es la manifestación de las relaciones, si es que existen, entre los elementos de aquel conjunto.

1.1. TIPOS DE DATOS ABSTRACTOS (TDA)

Se define abstracción como un mecanismo fundamental para la comprensión de fenómenos o situaciones que implican gran cantidad de detalles, suprimiendo los detalles irrelevantes y enfatizar los más relevantes o significativos.

1.2. MODULARIDAD

La modularidad es la posibilidad de dividir una aplicación en piezas más pequeñas llamadas módulos. El objetivo de descomponer el problema en partes más simples es para facilitar la comprensión del sistema y de cada una de sus partes. Así, si se produce un error en un módulo, éste sólo afecta a dicho módulo.

Cuando se realizan las correcciones debidas, los cambios en la especificación afectan a un número reducido de módulos, y el sistema está compuesto de una serie de módulos independientes comunicados entre sí.

En las aplicaciones el módulo debe dejar bien claro cómo hacer uso de él, el acceso a los servicios de un módulo debe ser homogéneo y debe estar listo para su uso pero a su vez debe poder mejorarse, además de que el lenguaje de programación utilizado debe soportar el uso de módulos.

1.3. USO DE TDA

Uno de los principios importantes del diseño de software es el de la abstracción y ocultación de la información. En programación, la abstracción facilita pensar acerca del problema a resolver.

La abstracción de datos es una técnica que permite inventar nuevos tipos de datos que sean más adecuados a una aplicación y, por consiguiente, facilitar la escritura del programa

TDA o Tipo de Dato Abstracto es un tipo de dato definido por el usuario para representar una abstracción a través de sus atributos y sus funciones. Se representa usualmente como una interfaz publica, mientras que la implementación como la parte privada del TDA está al cliente que la utiliza.

1.4. MEMORIA ESTÁTICA

La memoria de una computadora es administrada por el sistema operativo, ya que la cantidad de memoria es limitada y debe compartirla entre distintos usuarios o aplicaciones.

El tiempo de ejecución de un lenguaje de programación (RTM) administra la memoria para cada programa en ejecución.

Los diversos elementos que se almacenan

...