ESTRUCTURAS DE DATOS/ FUNDAMENTOS PRACTICOS

Capítulo 1. Excepciones y aserciones
17
1.1 Temática a desarrollar
17
1.2 Introducción.
17
1.3 Tipos de excepciones.
18
1.4 Sentencias try, catch, finally.
19
1.5 Implementación de las excepciones.
19
1.6 La importancia de usar excepciones.
20
1.7 Excepciones comunes
20
1.8 Ejercicios propuestos
22
1.9 Aserciones
23
1.10 Ejercicios propuestos
26

Capítulo 2. Recursividad y estructuras de datos
27
2.1 Temáticas a desarrollar
27
2.2 Introducción
27
2.3 Características de la recursividad.
28
2.4 Tipos de recursividad.
29
2.5 Ejercicios propuestos.
36
2.6 Estructura de datos
36
2.6.1 Estructuras de datos estáticas
37
2.6.2 Estructuras de datos dinámicas
38

Capítulo 3. Arreglos unidimensionales o vectores
41
3.1 Temática a desarrollar.
41
3.2 Introducción
41
3.3 Arreglos.
42
3.3.1 Características de un arreglo
42
ESTRUCTURAS DE DATOS - HERNÁNDEZ, M., BAQUERO, L.

3.3.2 Tipos de arreglos. .................................................. 43
3.4 Arreglos unidimensionales o vectores .................. 44
3.5 Operaciones con vectores. .................................... 46
3.6 Implementación de operaciones con vectores .......... 51
3.7 Ordenamiento de arreglos. .................................... 60
3.8 Introducción a la complejidad computacional. .......... 67
3.8.1 Complejidad ciclo for. ........................................... 69
3.9 Ejercicios propuestos ............................................ 75
3.10 Proyectos propuestos ........................................... 92

Capítulo 4. Arreglos bidimensionales o matrices. ............ 97
4.1 Temática a desarrollar. .......................................... 97
4.2 Introducción. ........................................................ 97
4.3 Declaración de matrices en Java. ............................ 98
4.4 Operaciones con matrices. .................................... 100
4.5 Ejercicios propuestos .......................................... 109

Capítulo 5. Cadenas ........................................................ 121
5.1 Temática a desarrollar. ........................................ 121
5.2 Introducción. ....................................................... 121
5.3 Clase String. ........................................................ 122
5.4 Clase StringTokenizer. .......................................... 130
5.5 Clase StringBuffer. ............................................... 131
5.6 Arreglos de objetos .............................................. 133
5.7 Ejercicios propuestos. .......................................... 135

Capítulo 6. Listas con enlace sencillo ............................ 141
6.1 Temática a desarrollar. ........................................ 141
6.2 Introducción. ....................................................... 141
6.3 Estructuras de datos dinámicas lineales ................ 141
6.4 Representación gráfica de un nodo. ....................... 142
6.5 Representación gráfica de una lista. ..................... 143
6.6 Operaciones en listas enlazadas ............................ 144
6.7 Construcción de una lista en Java .......................... 148
6.7.1 Creación de un objeto de la clase Nodo. .............. 149
6.7.2 Implementación de operaciones básicas. ............. 151
6.7.3 Modelamiento del problema. ................................ 160
6.7.4 Clase Nodo ......................................................... 161
6.7.5 La clase Lista ..................................................... 163

8
6.7.6 Validar lista................ 166
6.7.7 Clase Aplicación Lista. 167
6.7.8 Ejecución de la aplicación.... 171
6.8 Ejercicios propuestos...... 172

Capítulo 7. Listas de acceso restringido - Estructura pila 177
7.1 Temática a desarrollar 177
7.2 Introducción..........177
7.3 Definición de una pila.......178
7.4 Operaciones con las pilas 180
7.5 Representación de una pila. 182
7.6 Implementación de las operaciones básicas en una pila 183
7.6.1 Validación de contenido.........183
7.6.2 Método de inserción o push 183
7.6.3 Método de borrado o pop..... 184
7.6.4 Modelamiento y codificación. 186
7.7 Ejercicios propuestos 193

Capítulo 8. Listas de acceso restringido - Estructura cola.. 197
8.1 Temática a desarrollar 197
8.2 Introducción. 197
8.3 Operaciones básicas. 198
8.4 Implementación de las operaciones básicas.. 199
8.5 Ejercicios propuestos 211

Capítulo 9. Listas con doble enlace. 213
9.1 Temática a desarrollar. 213
9.2 Introducción. 213
9.3 Listas doblemente enlazadas. 214
9.4 Operaciones con las listas de doble enlace 216
9.5 Implementación de las operaciones. 220
9.6 Ejercicios propuestos 233

Capítulo 10. Listas circulares enlazadas. 235
10.1 Temática a desarrollar 235
10.2 Introducción 235
10.3 Lista circular sencilla 235
10.4 Operaciones con las listas de circulares sencillas 237
10.5 Modelamiento e implementación de operaciones.
10.6 Lista circular doblemente enlazada
240
244
10.7 Operaciones con las listas de circulares doblemente enlazadas........245
10.8 Ejercicios propuestos.
246

Capítulo 11. Estructuras de datos dinámicas no lineales
249
11.1 Temática a desarrollar.
249
11.2 Introducción......
249
11.3 Árboles......
250
11.3.1 Características de los árboles.
250
11.3.2 Representación gráfica de un árbol.
251
11.4 Árbol binario....
252
11.4.1 Elementos de un árbol
252
11.4.2 Representación de un árbol binario en la memoria
253
11.4.3 Operaciones en un árbol binario.
254
11.5 Árboles binarios de búsqueda.
254
11.5.1 Creación de un ABB
254
11.5.2 Recorridos en los ABB
257
11.6 Modelamiento e implementación en un ABB.
260
11.7 Árboles AVL
269
11.7.1 Operaciones con árboles AVL
269
11.7.2 Rotaciones
270
11.7.3 Factor de equilibro.
270
11.8 Árboles n-arios
283
11.8.1 Representación gráfica del nodo de un árbol n-ario.
284
11.8.2 Representación gráfica en memoria de un árbol n-ario
284
11.8.3 Recorridos de un árbol n-ario
284
11.8.4 Árbol genealógico...
285
11.9 Ejercicios propuestos.
285

Capítulo 12. Grafos.
287
12.1 Temática a desarrollar.
287
12.2 Introducción..
287
12.3 Matriz de adyacencia
288
12.4 Lista de adyacencia.
291
12.5 Recorridos de los grafos.
294
12.5.1 Recorrido en profundidad.
294
12.5.2 Recorrido en anchura.
297
12.6 Árboles de expansión mínima.
300
12.7 Algoritmos de grafos.
301
12.8 Implementaciones
12.9 Ejercicios propuestos.
12.7.1 Algoritmo de Dijkstra.
12.7.2 Algoritmo de Prim.
12.7.3 Algoritmo de Kruskal

CONTENIDO

301
308
315
318
334

Capítulo 13. Colecciones
337
13.1 Temática a desarrollar
337
13.2 Introducción.
337
13.3 Colecciones..
339
13.4 Jerarquía de las colecciones
340
13.5 La interfaz Collection
342
13.6 La interfaz List.
343
13.7 La interfaz Set
354
13.8 HashSet
354
13.9 La interfaz Map..
361
13.10 HashMap<Clave, Valor>.
361
13.10.1 HashTable<Clave, Valor>
362
13.10.2 TreeMap<Clave, Valor>.
366
13.11 La interfaz Comparable
377
13.12 La interfaz Queue y Deque
379
13.13 Programación de las colecciones.
379
13.14 Ejercicios propuestos
384

Capítulo 14. Programación genérica
389
14.1 Temática a desarrollar.
389
14.2 Introducción
389
14.3 Clase genérica.
389
14.4 Lista sencilla
392
14.5 Pila....
396
14.6 Ejercicios propuestos
400

Referencias bibliográficas.
401
Índice de figuras
Figura 1. Concepto de excepción........................................................................................................................ 18
Figura 2. Concepto de aserción......................................................................................................................... 24
Figura 3. Concepto de recursividad.................................................................................................................... 28
Figura 4. Comportamiento recursivo............................................................................................................... 31
Figura 5. Representación gráfica del método recursivo....................................................................................... 32
Figura 6. Concepto de estructuras de datos......................................................................................................... 37
Figura 7. Concepto de estructuras de datos estáticas.......................................................................................... 38
Figura 8. Concepto de estructuras de datos dinámicas........................................................................................ 39
Figura 9. Concepto de arreglos........................................................................................................................... 42
Figura 10. Concepto de arreglo unidimensional vector...................................................................................... 44
Figura 11. Arreglo v (10) de tipo entero.............................................................................................................. 47
Figura 12. Arreglo v () para búsqueda binaria.................................................................................................. 49
Figura 13. Resistencia eléctrica.......................................................................................................................... 94
Figura 14. Concepto de matriz........................................................................................................................... 98
Figura 15. Clase String.................................................................................................................................... 122
Figura 16. Concepto de pila.............................................................................................................................. 178
Figura 17. Concepto de cola.............................................................................................................................. 198
Figura 18. Concepto de lista de doble enlace................................................................................................... 214
Figura 19. Concepto de listas circulares sencillas.......................................................................................... 236
Figura 20. Concepto de árbol binario............................................................................................................... 250
Figura 21. Concepto de grafo........................................................................................................................... 288
Figura 22. API de colecciones en Java............................................................................................................. 339
Figura 23. Concepto de colecciones............................................................................................................... 340
Figura 24. Concepto de colecciones............................................................................................................... 341

En las estructuras de datos dinámicas el tamaño y su forma es variable a lo largo de un programa, es decir, la memoria se reserva a tiempo de corrida del programa; este tipo de estructuras está conformada por nodos, los cuales tienen como mínimo dos campos: uno de información (clientes, pasajeros, cuenta bancaria, entre otros) y otro que contiene la referencia del siguiente nodo; los nodos se crean y destruyen en tiempo de ejecución. Esto hace dimensionar la estructura de datos de una forma precisa permitiendo la asignación de memoria en tiempo de ejecución según se va requiriendo.

Con el propósito de lograr lo anterior, esta obra se divide en catorce capítulos, cada uno distribuido de la siguiente manera: relación general de la temática a desarrollar, una introducción al tema central donde se complementa con un mapa mental, el desarrollo de la temática respectiva incluyendo ejemplos, se recomiendan unas lecturas que posibilitan ampliar el tema, unas preguntas de revisión de conceptos y, finalmente, se propone una serie de ejercicios como apoyo complementario y fortalecimiento de los conceptos abordados.

Guía práctica
✔ Ejemplos desarrollados
✔ Ejercicios propuestos

Miguel Hernández Bejarano
Ingeniero de sistemas de la Universidad Autónoma de Colombia, con especialización en diseño y soluciones telemáticas de la misma Universidad, Magíster en comercio electrónico del Instituto Tecnológico de Monterrey (México) Magister en seguridad informática y Magister en Ingeniería de Software de la Universidad Internacional de La Rioja (España), cursando estudios de Doctorado en Ingeniería de Sistemas e Informática. Profesor investigador y coinvestigador de varios proyectos de investigación; con reconocimiento de la Sociedad Latinoamericana de Ciencia y Tecnología en el 2015-2019. ORCID https://orcid.org/0000-0001-8509-6731

Luis Eduardo Baquero Rey
Graduado como Ingeniero de Sistemas de la Universidad Autónoma de Colombia, con maestría en Auditoría de Sistemas y Computación de la Universidad Santo Tomás (Colombia) y en Seguridad Informática de la Universidad Internacional de La Rioja (España). Actualmente cursa su segundo año del doctorado en Ingeniería de Sistemas e Informática en la Universidad de Zaragoza (España), Profesor investigador y Par evaluador reconocido por Minciencias. ORCID iD: https://orcid.org/0000-0002-2520-1541