PDF de programación - Estructuras de datos

AUTORES

José Fager

W. Libardo Pantoja Yépez

Marisol Villacrés

Luz Andrea Páez Martínez

Daniel Ochoa

Ernesto Cuadros-Vargas

Estructuras de Datos

1a ed. - Iniciativa Latinoamericana de Libros de Texto Abiertos (LATIn), 2014. 222 pag.

Primera Edición: Marzo 2014
Iniciativa Latinoamericana de Libros de Texto Abiertos (LATIn)
http://www.proyectolatin.org/

Los textos de este libro se distribuyen bajo una licencia Reconocimiento-CompartirIgual 3.0 Unported
(CC BY-SA 3.0) http://creativecommons.org/licenses/by-sa/3.0/deed.es_ES

Esta licencia permite:
Compartir: copiar y redistribuir el material en cualquier medio o formato.
Adaptar: remezclar, transformar y crear a partir del material para cualquier finalidad.

Siempre que se cumplan las siguientes condiciones:

Reconocimiento. Debe reconocer adecuadamente la autoría, proporcionar un enlace a la
licencia e indicar si se han realizado cambios. Puede hacerlo de cualquier manera razonable,
pero no de una manera que sugiera que tiene el apoyo del licenciador o lo recibe por el uso
que hace.

CompartirIgual — Si remezcla, transforma o crea a partir del material, deberá difundir sus
contribuciones bajo la misma licencia que el original.

Las figuras e ilustraciones que aparecen en el libro son de autoría de los respectivos au-
tores. De aquellas figuras o ilustraciones que no son realizadas por los autores, se coloca la

referencia respectiva.

Este texto forma parte de la Iniciativa Latinoamericana de Libros de Texto abiertos (LATIn), proyecto
financiado por la Unión Europea en el marco de su Programa ALFA III EuropeAid.

El Proyecto LATIn está conformado por: Escuela Superior Politécnica del Litoral, Ecuador (ESPOL);
Universidad Autónoma de Aguascalientes, México (UAA), Universidad Católica de San Pablo, Perú
(UCSP); Universidade Presbiteriana Mackenzie, Brasil(UPM); Universidad de la República, Uruguay
(UdelaR); Universidad Nacional de Rosario, Argentina(UR); Universidad Central de Venezuela, Venezuela
(UCV), Universidad Austral de Chile, Chile (UACH), Universidad del Cauca, Colombia (UNICAUCA),
Katholieke Universiteit Leuven, Bélgica (KUL), Universidad de Alcalá, España (UAH), Université Paul
Sabatier, Francia (UPS).

Índice general

1
Introducción a las Estructuras de Datos . . . . . . . . . . . . . . . . . . . . . . 11
Conceptos básicos sobre estructuras de datos
11
1.1
1.1.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.2 Operaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2
12
Clasificación
Estructuras de Datos Estáticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.1
1.2.2
Estructuras de Datos Dinámicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2
Introducción al Diseño y Análisis de Algoritmos . . . . . . . . . . . . . . 13
14
Tipos de Datos
2.1
Tipos de Datos Abstractos
14
2.2
Especificación de un TDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1
Tipos de Operaciones de los TDAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2
Ejemplo de un TAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.3
Ejercicios Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.4
2.3
23
Clasificación de los Tipos de Datos
2.3.1 Clasificación desde el punto de vista funcional . . . . . . . . . . . . . . . . . . . . . . 23
2.3.2 Clasificación desde el punto de vista de Estructuras de Datos . . . . . . . . . . 27
Análisis de Algoritmos
2.4
28
2.4.1
Los Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.2 Análisis de Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.3
Función de Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.4 Operaciones elementales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.5 Calcular T(n) para Ciclos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4.6 Orden de Magnitud (Notación O Grande) . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4.7
Recursividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4.8 Complejidad de un Algoritmo Recursivo . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.5
45
2.5.1 Algoritmos de Búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.5.2 Algoritmos de Ordenamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

Algoritmos de Búsqueda y Ordenamiento

3
3.1

Algoritmos de Búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
69
Introducción a los algoritmos de búsqueda

Búsqueda Secuencial

3.2
69
3.2.1 Conceptos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.2.2 Complejidad computacional de la búsqueda secuencial
. . . . . . . . . . . . . 70
Búsqueda Binaria
3.3
70
3.3.1
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3.2 Complejidad de la búsqueda binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.3.3 Versión recursiva de la búsqueda binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.3.4 Complejidad de la búsqueda binaria recursiva . . . . . . . . . . . . . . . . . . . . . . 72
Búsqueda Hash
3.4
73
3.4.1
Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.4.2 Colisiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.5
77

Ejercicios sobre búsquedas

4
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8

Algoritmos de Ordenamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
79
Introducción a los algoritmos de Ordenamiento
Ordenamiento por selección
79
81
Ordenamiento burbuja
Ordenamiento por inserción
83
85
Ordenamiento Shell
88
Merge Sort
Quick Sort
90
93
Ejercicios sobre algoritmos de ordenamiento

Función de Complejidad

Complejidad computacional
Conceptos

5
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.1
95
5.1.1 Definición de algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.1.2
Factores que influyen en la eficiencia de un algoritmo . . . . . . . . . . . . . . . . 95
5.1.3 Análisis de Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.2
97
5.2.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.2.2
Tipos de operaciones Elementales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.2.3 Cálculo del T(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3
105
5.4
106
5.4.1 Método del árbol de recursión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.5
108

Algoritmos recursivos
Complejidad computacional de los algoritmos recursivos

Ejercicios sobre análisis de algoritmos

6
Tipos Abstractos de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Conceptos TADs
111
6.1
Tipos Abstractos de Datos (TAD’s) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.1.1
6.1.2 Aspectos Teóricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.1.3
La modularidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

6.1.4 Métodos para Especificar un TAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.1.5 Clasificación de las Operaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.1.6
Ejemplo de un TAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
116
Ejercicios sobre TADs
6.2

7
TDAs Lineales: Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.1
117
Definición y Formas de Uso
7.1.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
7.1.2
Formas de Uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.2
121
Implementación
7.2.1 Mediante Arreglos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
7.2.2 Mediante Referencias a Objetos
Casos de estudio
7.3
130
Tienda de Libros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.3.1
7.3.2
TDA String con Listas
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
7.3.3 Materias y Estudiantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.3.4 Análisis del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.4
136

Ejercicios propuestos

8
TDAs Lineales: Pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8.1
Definición y Formas de Uso
139
8.1.1 Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
8.1.2
Formas de Uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Implementaciones y Algoritmos fundamentales.
8.2
141
Implementación en Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
8.2.1
8.2.2
Implementación en C++ . . .