Estructura de datos

INSTITUTO TECNOLÓGICO DE LÁZARO CÁRDENAS

“ESTRUCTURA DE DATOS”

TRABAJO DE INVESTIGACIÓN

POR:
MITZI NELLY MALDONADO CARRILLO.
EDSON TAYDE MACIEL RUMBO.
DORINA QUINTANA CARMONA.
EDGAR SALVATORE ESPINDOLA FLORES.

3ER. SEMESTRE
GRUPO 31T

ING. EN SISTEMAS COMPUTACIONALES

LÁZARO CÁRDENAS, MICH. 30 DE NOVIEMBRE DEL 2011

INTRODUCCIÓN

Las estructuras de datos son unacolección de datos cuya organización se caracteriza por las funciones de acceso que se usan para almacenar y acceder a elementos individuales de datos.
La información que es procesada en una computadora es un conjunto de datos, que pueden ser simples o estructurados. Los datos simples son los que ocupan sólo una localidad de memoria, y los estructurados son un conjunto de casillas de memoria a lascuales hacemos referencia mediante un identificador único.
Ya que por lo general tenemos que trabajar con conjuntos de datos y no con datos simples, es necesario tratar con estructuras de datos adecuadas a cada necesidad.
A continuación mostramos todas las componentes de este tema, y algunos ejemplos de programas, que ejemplifican una manera de estructurar datos en un sistema.

Índice.INTRODUCCIÓN 2
1.- ANÁLISIS DE ALGORITMOS Y GESTIÓN DE MEMORIA. 5
1.1.- Concepto de algoritmo y gestión de memoria 5
1.2.-Aritmetica notación “O” 5
1.3.- Complejidad, espacio y tiempo de ejecución 8
1.4.- Gestión de memoria estática 10
1.5.- Gestión de memoria dinámica 12
2.- ESTRUCTURAS LINEALES 12
2.1.- Pilas 12
2.1.1.- Concepto y operaciones básicas en pilas. 13
2.1.2.- Uso yaplicaciones de pilas 13
2.2.- Colas 13
2.2.1.- Concepto y operaciones básicas en colas. 14
2.2.2.- Uso y aplicaciones de colas. 14
2.3.- Listas enlazadas 15
2.3.1.- Concepto y operaciones básicas en listas enlazadas. 15
2.3.2.- Uso y aplicaciones de listas enlazadas. 17
3. - RECURSIVIDAD 37
3.1.- Definición 37
3.2.- Procedimientos recursivos. 38
3.3.- Mecánica de recursión. 383.4.- Recursividad en el diseño. 40
3.5.- Transformación de algoritmos recursivos a iterativos. 41
4.- ESTRUCTURAS NO LINEALES 45
4.1 concepto y clasificación de arboles 45
4.2 operaciones básicas sobre arboles binarios 48
4.3 balanceo de arboles binarios. 51
4.4 uso y aplicaciones de arboles binarios 51
5.-METODOS DE ORDENAMIENTO INTERNAS Y EXTERNOS 58
5.1 algoritmos de ordenamientopor intercambio. 58
5.2 algoritmos de ordenamiento por distribución 63
5.3 algoritmos de ordenamiento por intercalación 70
6.- MÉTODOS DE BÚSQUEDA 74
6.1 algoritmos de búsqueda secuencial 74
6.2 Algoritmos de búsqueda binaria. 76
6.3 algoritmos búsqueda hash 78
CONCLUSIÓN 82

1.- ANÁLISIS DE ALGORITMOS Y GESTIÓN DE MEMORIA.
1.1.- Concepto de algoritmo y gestión de memoria
Unalgoritmo será más eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.
La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad:
* Complejidad Temporal o Tiempo de ejecución: Tiempo de cómputo necesario para ejecutar algún programa.
* Complejidad Espacial: Memoria que utilizaun programa para su ejecución, La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoria estática de un algoritmo se suma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, el cálculo no estan simple ya que, este depende de cada ejecución del algoritmo.
Este análisis se basa en las Complejidades Temporales, con este fin, para cada problema determinaremos una medida N, que llamaremos tamaño de la entrada o número de datos a procesar por el programa, intentaremos hallar respuestas en función de dicha N.
El concepto exacto que cuantifica N dependerá de la naturaleza del problema,...