Estructuras de datos - Un enfoque orientado a objetos
Enviado por rodolfoarana • 27 de Abril de 2016 • Apuntes • 49.343 Palabras (198 Páginas) • 271 Visitas
APUNTES DE ESTRUCTURAS DE DATOS
Un enfoque orientado a objetos
RODOLFO E. ARANA GONZALES
SASCI
01/01/2009
APUNTES DE ESTRUCTURAS DE DATOS
Un enfoque orientado a objetos
RODOLFO E. ARANA GONZALES
APUNTES DE ESTRUCTURAS DE DATOS
Un enfoque orientado a objetos
RODOLFO E. ARANA GONZALES
SASCI
01/01/2009
APUNTES DE ESTRUCTURAS DE DATOS
Un enfoque orientado a objetos
RODOLFO E. ARANA GONZALES
Prefacio
Este material ha sido escrito en forma paralela al desenvolvimiento de cursos de Estructuras de datos dictados en las universidades de Santa Cruz de la Sierra, con el afán de proporcionar al estudiante una guía para aprender estructuras de datos en forma práctica. Asimismo, se quiere presentar y dar a entender conceptos, que a menudo, no se abordan con la claridad necesaria, como ser el manejo de punteros. También se aborda la temática de las estructuras de datos desde un enfoque orientado a objetos, explicando que esta metodología es una especie de “evolución natural” de los Tipos Abstractos de Datos en cuanto a su implementación.
Estos apuntes están dedicados a todos aquellos que están dispuestos a sacrificar horas de descanso o diversión, con el fin de superarse permanentemente, hacerse mejores para hacer un mundo mejor.
El autor
Tabla de contenido
PREFACIO 3
1. ESTRUCTURAS Y ABSTRACCIÓN DE DATOS 6
1.1. INTRODUCCIÓN A LAS ESTRUCTURAS DE DATOS 6
1.2. ABSTRACCIÓN DE DATOS 6
1.2.1 ESTRUCTURA DE DATOS 2
1.3. CLASIFICACIÓN DE LAS ESTRUCTURAS DE DATOS (VILLALOBOS, 1996) 3
1.4. TIPOS ABSTRACTOS DE DATOS 4
Operaciones con arreglos 6
1.6 BÚSQUEDA Y CLASIFICACIÓN DE ARREGLOS 6
Búsqueda secuencial 6
Búsqueda binaria 7
Clasificación 8
Método de intercambio o de Burbuja 9
Método de la Baraja 9
Metodo QuickSort 10
1.7 COMPLEJIDAD DE ALGORITMOS 11
MOTIVACIÓN 13
INSTRUCCIONES DE CONTEO 13
ANÁLISIS WORST-CASE O DEL PEOR CASO 15
ASYMPTOTIC BEHAVIOR O COMPORTAMIENTO ASINTÓTICO 15
COMPLEJIDAD 18
2. ESTRUCTURA DE LENGUAJES DE PROGRAMACIÓN ORIENTADOS A OBJETO. 23
2.1 . ASPECTOS GENERALES DE LOS LENGUAJES 23
2.2 LENGUAJES ORIENTADOS A OBJETO 25
PROGRAMACIÓN ORIENTADA A OBJETO 26
2.2. ESTRUCTURAS DE DATOS ORIENTADAS A OBJETOS 27
2.4. RECURSIVIDAD Y LENGUAJES DE PROGRAMACIÓN OO 28
Concepto de Recursividad 28
CASO BASE 28
CASO GENERAL 29
1. Cálculo de la potencia 31
2. La suma de forma recursiva 31
3. Búsqueda lineal recursiva (con dos casos base) 31
4. Búsqueda Binaria recursiva 32
3. ALMACENAMIENTO ESTÁTICO EN SECUENCIA – LISTAS 33
3.1 ASPECTOS GENERALES DE LISTAS 33
3.2. PILAS 33
APLICACIÓN DE PILA: EVALUACIÓN DE EXPRESIONES 34
PROCESO PARA EVALUACIÓN DE UNA EXPRESIÓN ARITMÉTICA 35
TRANSFORMACIÓN DE INFIJA A POSTFIJA 35
3.3. COLAS 37
OPERACIONES BÁSICAS 38
IMPLEMENTACIÓN DE LA OPERACIONES 38
Aplicaciones 39
IMPLEMENTACIÓN DE COLAS EN C++ 39
Tipos de colas 40
3.4. PROBLEMAS DE APLICACIÓN DE PILAS, COLAS Y LISTAS 41
4. ALMACENAMIENTO DINÁMICO 44
4.1 MANEJO DINÁMICO DE LA MEMORIA – LOS PUNTEROS 44
¿Cómo se almacena una variable? 44
¿Qué son los punteros? 46
4.2. LISTAS ENCADENADAS 48
4.3 DISEÑO E IMPLEMENTACIÓN DINÁMICA DE LISTAS ENCADENADAS 49
Estructura de Nodo 49
Estructura de Lista encadenada 50
Esquema y diseño de una lista enlazada 50
Operación de Recorrido 52
Operación de Inserción 53
Operación de Borrado 54
Operación de Búsqueda 54
4.4. IMPLEMENTACIÓN DINÁMICA DE ESTRUCTURAS DE DATOS 54
Implementación de pilas con punteros 54
5. ARBOLES 55
5.1 ARBOLES BINARIOS 55
Definición de árbol 56
Formas de representación 56
Declaración de árbol binario 57
Recorridos sobre árboles binarios 57
Construcción de un árbol binario 59
5.2 ÁRBOL BINARIO DE BÚSQUEDA 61
Operaciones básicas sobre árboles binarios de búsqueda 62
Ejercicio resuelto 65
Aplicación práctica de un árbol binario de búsqueda 65
Ejercicios propuestos 66
5.3. ÁRBOLES B 68
Utilización de los Arboles B 68
Funcionamiento 69
¿Qué es un Arbol B? 71
Costos 75
Casos especiales 76
Conclusión 77
TRABAJOS PRACTICOS 78
BIBLIOGRAFÍA 82
1. Estructuras y abstracción de datos
1.1. Introducción a las estructuras de datos
Los programas están constituidos fundamentalmente por algoritmos y estructuras de datos. Esto significa que los algoritmos se ejecutan sobre estas estructuras de datos. Esto permite ver que las estructuras de datos son una parte fundamental de la programación de computadoras, en particular; y del procesamiento de información, en general
Una estructura de datos es una colección de datos que pueden ser caracterizados por su organización y las operaciones que se definen sobre ella.
Se trata de un conjunto de variables de un determinado tipo agrupadas y organizadas de alguna manera
...