Estructuras de datos en java TM compatible con java TM2 /
Weiss, Mark Allen.
Estructuras de datos en java TM compatible con java TM2 / Mark Allen Weiss. - Madrid : Pearson, 2000. - 740 p.
CONTENIDO
PRIMERA PARTE. Un recorrido por Java
1. Java básico 3
1.1. El entorno general 4
1.2. El primer programa 5
1.2.1. Comentarios 5
1.2.2. main 5
1.2.3. Salida por pantalla 6
1.3. Tipos primitivos 6
1.3.1. Los tipos primitivos 6
1.3.2. Las constantes 7
1.3.3. Declaración e inicialización de tipos primitivos 7
1.3.4. Entrada y salida por Terminal 8
1.4. Operadores básicos 8
1.4.1. Operadores de asignación 8
1.4.2. Operadores aritméticos binarios 9
1.4.3. Operadores unarios 10
1.4.4. Conversiones de tipo 10
1.5. Instrucciones condicionales 11
1.5.1. Operadores relacionales y de igualdad 11
1.5.2. Operadores lógicos 11
1.5.3. La instrucción if 12
1.5.4. La instrucción while 13
1.5.5. La instrucción for 14
1.5.6. La instrucción do 15
1.5.7. break y continue 15
1.5.8. La instrucción switch 16
1.5.9. El operador condicional 17
1.6. Métodos 18
1.6.1. Sobrecarga de los nombres de los métodos 18
1.6.2. Clases de almacenamiento 19
2. Referencias 25
2.1. ¿Qué es una referencia? 25
2.2. Nociones básicas sobre objetos y referencias 27
2.2.1. El operador punto (.) 28
2.2.2. Declaración de objetos 28
2.2.3. Recogida de basura 29
2.2.4. El significado de 29
2.2.5. Paso de parámetros 30
2.2.6. El significado de 31
2.2.7. Sobrecarga de operadores para objetos 31
2.3. Cadenas de caracteres 31
2.3.1. Conceptos básicos de la manipulación de Strings 32
2.3.2. Concatenación de cadenas 32
2.3.3. Comparando cadenas 33
2.3.4. Otros métodos del tipo String 33
2.3.5. Conversión entre cadenas y tipos primitivos 33
2.4. Vectores 34
2.4.1. Declaración, asignación y métodos 34
2.4.2. Expansión dinámica de vectores 36
2.4.3. Vectores multidimensionales 37
2.4.4. Argumentos de la línea de comandos 39
2.5. Manejo de excepciones 39
2.5.1. Procesamiento de excepciones 39
2.5.2. La cláusula finally 40
2.5.3. Excepciones más comunes 41
2.5.4. Las cláusulas throw y throws 42
2.6. Entrada y salida 42
2.6.1. Operaciones básicas de E/S 43
2.6.2. El objeto StringTokenizer 44
2.6.3. Ficheros de acceso secuencial 45
3. Objetos y clases 51
3.1. ¿Qué es la programación orientada a objetos? 51
3.2. Un ejemplo sencillo 53
3.3. Javadoc 54
3.4. Métodos básicos 57
3.4.1. Constructores 57
3.4.2. Métodos modificadores y de acceso 57
3.4.3. Salida y toString 58
3.4.4. equals 58
3.4.5. Métodos static 59
3.4.6. main 60
3.5. Paquetes 60
3.5.1. La directiva import 60
3.5.2. La instrucción package 61
3.5.3. La variable de entorno CLASSPATH 62
3.5.4. Reglas de visibilidad amistosa dentro de un paquete 63
3.5.5. Compilación separada 64
3.6. Construcciones adicionales 64
3.6.1. La referencia this 64
3.6.2. La abreviatura this para constructores 65
3.6.3. El operador instanceof 65
3.6.4. Atributos estáticos 65
3.6.5. Inicializadores estáticos 66
4. Herencia 73
4.1. ¿Qué es la herencia? 73
4.2. Sintaxis básica de Java 76
4.2.1. Reglas de visibilidad 76
4.2.2. El constructor y super 77
4.2.3. Métodos y clases finales 78
4.2.4. Sobreescribiendo un método 79
4.2.5. Métodos y clases abstractos 79
4.3. Ejemplo: extensión de la clase Figura 82
4.3.1. Disgresión: una introducción a la ordenación 84
4.4. Herencia múltiple 87
4.5. El interfaz 88
4.5.1. Especificación de una interfaz 88
4.5.2. Implementación de una interfaz 89
4.5.3. Varias interfaces 91
4.6. Implementación de componentes genéricas 91
SEGUNDA PARTE. Algoritmos y fundamentos de programación
5. Análisis de algoritmos 103
5.1. ¿Qué es el análisis de algoritmos? 104
5.2. Ejemplos de tiempo de ejecución de algoritmos 107
5.3. El problema de la subsecuencia de suma máxima 108
5.3.1. El algoritmo O(N3) obvio 109
5.3.2. Un algoritmo mejorado O(N2) 112
5.3.3. Un algoritmo lineal 113
5.4. Reglas generales para la notación O 114
5.5. Logaritmos 119
5.6. Problema de la búsqueda estática 121
5.6.1. Búsqueda secuencial 121
5.6.2. Búsqueda binaria 122
5.6.3. Búsqueda interpolada 124
5.7. Comprobar el análisis de un algoritmo 125
5.8. Limitaciones del análisis O 127
6. Estructuras de datos 137
6.1. ¿Por qué necesitamos estructuras de datos? 137
6.2. Las pilas 139
6.2.1. Las pilas y los lenguajes de programación 141
6.3. Las colas 142
6.4. Listas enlazadas 144
6.5. Arboles generales 147
6.6. Arboles binarios de búsqueda 149
6.7. Tablas hash 153
6.8. Colas de prioridad 155
7. Recursión 165
7.1. ¿Qué es la recursión? 165
7.2. Fundamentos: demostraciones por inducción matemática 166
7.3. Recursión básica 170
7.3.1. Impresión de números en cualquier base 170
7.3.2. ¿Por qué funciona? 172
7.3.3. Cómo funciona 174
7.3.4. Demasiada recursión puede ser peligrosa 175
7.3.5. Ejemplos adicionales 176
7.4. Aplicaciones numéricas 180
7.4.1. Aritmética modular 181
7.4.2. Exponenciación modular 181
7.4.3. Máximo común divisor e inversos multiplicativos 183
7.4.4. El sistema de criptografía RSA 185
7.5. Algoritmos divide y vencerás 188
7.5.1. El problema de la subsecuencia de suma máxima 188
7.5.2. Análisis de un algoritmo divide y vencerás sencillo 190
7.5.3. Una cota superior general para los tiempos de ejecución de los algoritmos divide y vencerás 195
7.6. Programación dinámica 197
7.7. Algoritmos de vuelta atrás 201
8. Algoritmos de ordenación 213
8.1. ¿Por qué es importante la ordenación? 213
8.2. Preliminares 215
8.3. Análisis de la ordenación por inserción y otras ordenaciones simples 215
8.4. Shellsort 217
8.4.1. Rendimiento de Shellsort 219
8.5. Mergesort 221
8.5.1. Mezcla lineal de vectores ordenados 221
8.5.2. El algoritmo mergesort 224
8.6. Quicksort 225
8.6.1. El algoritmo quicksort 225
8.6.2. Análisis de quicksort 227
8.6.3. Seleccionando el pivote 230
8.6.4. Estrategia de partición 232
8.6.5. Elementos iguales al pivote 234
8.6.6. Partición con la mediana de tres 234
8.6.7. Vectores pequeños 235
8.6.8. Rutina de quicksort en Java 236
8.7. Selección rápida 238
8.8. Una cola inferior para la ordenación 240
9. Números aleatorios 249
9.1. ¿Por qué son necesarios los números aleatorios? 249
9.2. Generadores de números aleatorios 250
9.3. Números aleatorios no uniformes 256
9.4. Generación de una permutación aleatoria 258
9.5. Algoritmos aleatorios 259
9.6. Test aleatorio de primalidad 261
TERCERA PARTE. Aplicaciones
10. Juegos y diversión 273
10.1. Sopas de letras 273
10.1.1 Teoría 274
10.1.2. Implementación en Java 276
10.2. El juego de las tres en raya 281
10.2.1. Poda alfa-beta 281
10.2.2. Tablas de transposición 282
10.3. El ajedrez 285
11. Las pilas y los compiladores 291
11.1. Analizador de símbolos equilibrados 291
11.1.1. El algoritmo básico 291
11.1.2. Implementación 293
11.2. Una calculadora sencilla 301
11.2.1. Máquinas postfijas 302
11.2.2. Conversión de notación infija a postfija 302
11.2.3. Implementación 305
11.2.4. Arboles sintácticos de expresiones 312
12. Utilidades 317
12.1. Compresión de ficheros 317
12.1.1. Códigos sin prefijos 318
12.1.2. Algoritmo de Huffman 320
12.1.3. La fase de codificación 322
12.1.4. La fase de decodificación 323
12.1.5. Consideraciones prácticas 324
12.2. Generador de referencias cruzadas 324
12.2.1. Ideas básicas 324
12.2.2. Implementación en Java 325
13. Simulación 335
13.1. El problema Josephus 335
13.1.1. La solución simple 336
13.1.2. Un algoritmo más eficiente 338
13.2. Simulación dirigida por eventos 340
13.2.1. Ideas básicas 340
13.2.2. Ejemplo: simulación de un banco de módems 341
14. Grafos y caminos 353
14.1. Definiciones 353
14.1.1. Representación 355
14.2. Problema del camino mínimo sin pesos 366
14.2.1. Teoría 366
14.2.2. Implementación en Java 370
14.3. Problema de los caminos mínimos con pesos positivos 371
14.3.1. Teoría: algoritmo de Dijkstra 371
14.3.2. Implementación en Java 375
14.4. Problema del camino mínimo con costes negativos 376
14.4.1. Teoría 376
14.4.2. Implementación en Java 377
14.5. Problemas de caminos en grafos acíclicos 379
14.5.1. Ordenación topológica 379
14.5.2. Teoría del algoritmo de caminos mínimos con un grafo acíclico 381
14.5.3. Implementación en Java 382
14.5.4. Una aplicación: análisis de caminos críticos 382
CUARTA PARTE. Implementaciones
15. Pilas y colas 395
15.1. Implementación dinámica de vectores 395
15.1.1. Pilas 395
15.1.2. Colas 399
15.2. Implementaciones con listas enlazadas 404
15.2.1. Pilas 404
15.2.2. Colas 408
15.3. Comparación de los dos métodos 409
15.4. Colas dobles 411
16. Listas enlazadas 415
16.1. Ideas básicas 415
16.1.1. Nodos cabecera 417
16.1.2. Clases iteradoras 418
16.2. Implementación en Java 419
16.3. Listas doblemente enlazadas y listas enlazadas circulares 426
16.4. Listas enlazadas ordenadas 428
17. Arboles 435
17.1. Arboles generales 435
17.1.1. Definiciones 435
17.1.2. Implementación 437
17.1.3. Una aplicación: sistemas de ficheros 437
17.2. Arboles binarios 441
17.3. Arboles y recursión 448
17.4. Recorrido de árboles: clases iteradoras 450
17.4.1. Recorrido en postorden 453
17.4.2. Recorrido en orden simétrico 457
17.4.3. Recorrido en preorden 458
17.4.4. Recorrido por niveles 459
18. Arboles binarios de búsqueda 467
18.1. Ideas básicas 467
18.1.1. Las operaciones 468
18.1.2. Implementación en Java 470
18.2. Búsqueda por posición en el orden 477
18.2.1. Implementación en Java 477
18.3. Análisis de las operaciones de los árboles binarios de búsqueda 481
18.4. Arboles AVL 484
18.4.1. Propiedades 485
18.4.2. Rotación simple 487
18.4.3. Rotación doble 490
18.4.4. Resumen de la inserción en un árbol AVL 492
18.5. Arboles rojinegros 492
18.5.1. Inserción ascendente 493
18.5.2. Arboles rojinegros descendentes 495
18.5.3. Implementación en Java 497
18.5.4. Eliminación descendente 503
18.6. AA-Arboles 505
18.6.1. Inserción 506
18.6.2. Eliminación 509
18.6.3. Implementación en Java 509
18.7. B-Arboles 512
19. Tablas hash 527
19.1. Ideas básicas 527
19.2. Función de localización 529
19.3. Exploración lineal 531
19.3.1. Análisis de la exploración lineal 532
19.3.2. Lo que sucede realmente: la agrupación primaria 533
19.3.3. Análisis de la operación buscar 534
19.4. Exploración cuadrática 536
19.4.1. Implementación en Java 541
19.4.2. Análisis de la exploración cuadrática 544
19.5. Hashing enlazado 545
20. Una cola de prioridad: el montículo binario 553
20.1. Ideas básicas 553
20.1.1. Propiedad estructural 554
20.1.2. Propiedad de ordenación de los montículos 555
20.1.3. Operaciones permitidas 556
20.2. Implementación de las operaciones básicas 559
20.2.1. insertar 559
20.2.2. eliminarMin 562
20.3. arreglarMontículo: construcción en tiempo lineal del montículo 564
20.4. Operaciones avanzadas: reducirClave y mezclar 568
20.5. Ordenación interna: método del montículo 568
20.6. Ordenación externa 571
20.6.1. Por qué necesitamos nuevos algoritmos 572
20.6.2. Modelo de ordenación externa 572
20.6.3. El algoritmo sencillo 572
20.6.4. Mezcla multiaria 574
20.6.5. Mezcla multifase 575
20.6.6. Selección del reemplazo 576
QUINTA PARTE. Estructuras de datos avanzadas
21. Arboles de ensanchamiento 587
21.1. Auto-ajustamiento y análisis amortizado 587
21.1.1. Cotas de tiempo amortizadas 588
21.1.2. Una estrategia simple de auto-ajustamiento (que no funciona) 589
21.2. Arboles básicos de ensanchamiento ascendente 591
21.3. Operaciones básicas de los árboles de ensanchamiento 593
21.4. Análisis del ensanchamiento ascendente 594
21.4.1. Demostración de la cota de ensanchamiento 597
21.5. Arboles de ensanchamiento descendente 600
21.6. Implementación de los árboles con ensanchamiento descendente 602
21.7. Comparaciones de los árboles de ensanchamiento con otros árboles de búsqueda 608
22. Colas de prioridad con mezcla 613
22.1. Los montículos sesgados 613
22.1.1. La mezcla es importante 613
22.1.2. Mezcla simple de árboles con ordenación de montículos 614
22.1.3. El montículo sesgado: una modificación sencilla 615
22.1.4. Análisis del montículo sesgado 616
22.2. Los montículos de emparejamientos 618
22.2.1. Operaciones del montículo de emparejamientos y teoría 618
22.2.2. Implementación del montículo de emparejamientos 620
22.2.3. Aplicación: el algoritmo de Dijkstra para la obtención de caminos mínimos 626
23. Estructura de partición 633
23.1. Relaciones de equivalencia 633
23.2. Equivalencia dinámicas y dos aplicaciones 634
23.2.1. Aplicación #1: árboles de recubrimiento mínimo 635
23.2.2. Aplicación #2: el problema del antecesor común mas próximo 637
23.3. El algoritmo de búsqueda rápida 641
23.4. El algoritmo de unión rápida 642
23.4.1. Algoritmos de unión inteligentes 643
23.4.2. Compresión de caminos 645
23.5. Implementación en Java 647
23.6. Caso peor de la unión por rango y la compresión de caminos 648
23.6.1. Análisis del algoritmo unir/buscar 649
APENDICES
A. Plataformas para Java
B. Operadores
C. Algunas rutinas de librerías
D. Interfaces gráficas de usuario
Indice analítico
8478290354
PROGRAMACION DE COMPUTADORAS
LENGUAJE DE PROGRAMACION
JAVA
004.438JAVA W436
Estructuras de datos en java TM compatible con java TM2 / Mark Allen Weiss. - Madrid : Pearson, 2000. - 740 p.
CONTENIDO
PRIMERA PARTE. Un recorrido por Java
1. Java básico 3
1.1. El entorno general 4
1.2. El primer programa 5
1.2.1. Comentarios 5
1.2.2. main 5
1.2.3. Salida por pantalla 6
1.3. Tipos primitivos 6
1.3.1. Los tipos primitivos 6
1.3.2. Las constantes 7
1.3.3. Declaración e inicialización de tipos primitivos 7
1.3.4. Entrada y salida por Terminal 8
1.4. Operadores básicos 8
1.4.1. Operadores de asignación 8
1.4.2. Operadores aritméticos binarios 9
1.4.3. Operadores unarios 10
1.4.4. Conversiones de tipo 10
1.5. Instrucciones condicionales 11
1.5.1. Operadores relacionales y de igualdad 11
1.5.2. Operadores lógicos 11
1.5.3. La instrucción if 12
1.5.4. La instrucción while 13
1.5.5. La instrucción for 14
1.5.6. La instrucción do 15
1.5.7. break y continue 15
1.5.8. La instrucción switch 16
1.5.9. El operador condicional 17
1.6. Métodos 18
1.6.1. Sobrecarga de los nombres de los métodos 18
1.6.2. Clases de almacenamiento 19
2. Referencias 25
2.1. ¿Qué es una referencia? 25
2.2. Nociones básicas sobre objetos y referencias 27
2.2.1. El operador punto (.) 28
2.2.2. Declaración de objetos 28
2.2.3. Recogida de basura 29
2.2.4. El significado de 29
2.2.5. Paso de parámetros 30
2.2.6. El significado de 31
2.2.7. Sobrecarga de operadores para objetos 31
2.3. Cadenas de caracteres 31
2.3.1. Conceptos básicos de la manipulación de Strings 32
2.3.2. Concatenación de cadenas 32
2.3.3. Comparando cadenas 33
2.3.4. Otros métodos del tipo String 33
2.3.5. Conversión entre cadenas y tipos primitivos 33
2.4. Vectores 34
2.4.1. Declaración, asignación y métodos 34
2.4.2. Expansión dinámica de vectores 36
2.4.3. Vectores multidimensionales 37
2.4.4. Argumentos de la línea de comandos 39
2.5. Manejo de excepciones 39
2.5.1. Procesamiento de excepciones 39
2.5.2. La cláusula finally 40
2.5.3. Excepciones más comunes 41
2.5.4. Las cláusulas throw y throws 42
2.6. Entrada y salida 42
2.6.1. Operaciones básicas de E/S 43
2.6.2. El objeto StringTokenizer 44
2.6.3. Ficheros de acceso secuencial 45
3. Objetos y clases 51
3.1. ¿Qué es la programación orientada a objetos? 51
3.2. Un ejemplo sencillo 53
3.3. Javadoc 54
3.4. Métodos básicos 57
3.4.1. Constructores 57
3.4.2. Métodos modificadores y de acceso 57
3.4.3. Salida y toString 58
3.4.4. equals 58
3.4.5. Métodos static 59
3.4.6. main 60
3.5. Paquetes 60
3.5.1. La directiva import 60
3.5.2. La instrucción package 61
3.5.3. La variable de entorno CLASSPATH 62
3.5.4. Reglas de visibilidad amistosa dentro de un paquete 63
3.5.5. Compilación separada 64
3.6. Construcciones adicionales 64
3.6.1. La referencia this 64
3.6.2. La abreviatura this para constructores 65
3.6.3. El operador instanceof 65
3.6.4. Atributos estáticos 65
3.6.5. Inicializadores estáticos 66
4. Herencia 73
4.1. ¿Qué es la herencia? 73
4.2. Sintaxis básica de Java 76
4.2.1. Reglas de visibilidad 76
4.2.2. El constructor y super 77
4.2.3. Métodos y clases finales 78
4.2.4. Sobreescribiendo un método 79
4.2.5. Métodos y clases abstractos 79
4.3. Ejemplo: extensión de la clase Figura 82
4.3.1. Disgresión: una introducción a la ordenación 84
4.4. Herencia múltiple 87
4.5. El interfaz 88
4.5.1. Especificación de una interfaz 88
4.5.2. Implementación de una interfaz 89
4.5.3. Varias interfaces 91
4.6. Implementación de componentes genéricas 91
SEGUNDA PARTE. Algoritmos y fundamentos de programación
5. Análisis de algoritmos 103
5.1. ¿Qué es el análisis de algoritmos? 104
5.2. Ejemplos de tiempo de ejecución de algoritmos 107
5.3. El problema de la subsecuencia de suma máxima 108
5.3.1. El algoritmo O(N3) obvio 109
5.3.2. Un algoritmo mejorado O(N2) 112
5.3.3. Un algoritmo lineal 113
5.4. Reglas generales para la notación O 114
5.5. Logaritmos 119
5.6. Problema de la búsqueda estática 121
5.6.1. Búsqueda secuencial 121
5.6.2. Búsqueda binaria 122
5.6.3. Búsqueda interpolada 124
5.7. Comprobar el análisis de un algoritmo 125
5.8. Limitaciones del análisis O 127
6. Estructuras de datos 137
6.1. ¿Por qué necesitamos estructuras de datos? 137
6.2. Las pilas 139
6.2.1. Las pilas y los lenguajes de programación 141
6.3. Las colas 142
6.4. Listas enlazadas 144
6.5. Arboles generales 147
6.6. Arboles binarios de búsqueda 149
6.7. Tablas hash 153
6.8. Colas de prioridad 155
7. Recursión 165
7.1. ¿Qué es la recursión? 165
7.2. Fundamentos: demostraciones por inducción matemática 166
7.3. Recursión básica 170
7.3.1. Impresión de números en cualquier base 170
7.3.2. ¿Por qué funciona? 172
7.3.3. Cómo funciona 174
7.3.4. Demasiada recursión puede ser peligrosa 175
7.3.5. Ejemplos adicionales 176
7.4. Aplicaciones numéricas 180
7.4.1. Aritmética modular 181
7.4.2. Exponenciación modular 181
7.4.3. Máximo común divisor e inversos multiplicativos 183
7.4.4. El sistema de criptografía RSA 185
7.5. Algoritmos divide y vencerás 188
7.5.1. El problema de la subsecuencia de suma máxima 188
7.5.2. Análisis de un algoritmo divide y vencerás sencillo 190
7.5.3. Una cota superior general para los tiempos de ejecución de los algoritmos divide y vencerás 195
7.6. Programación dinámica 197
7.7. Algoritmos de vuelta atrás 201
8. Algoritmos de ordenación 213
8.1. ¿Por qué es importante la ordenación? 213
8.2. Preliminares 215
8.3. Análisis de la ordenación por inserción y otras ordenaciones simples 215
8.4. Shellsort 217
8.4.1. Rendimiento de Shellsort 219
8.5. Mergesort 221
8.5.1. Mezcla lineal de vectores ordenados 221
8.5.2. El algoritmo mergesort 224
8.6. Quicksort 225
8.6.1. El algoritmo quicksort 225
8.6.2. Análisis de quicksort 227
8.6.3. Seleccionando el pivote 230
8.6.4. Estrategia de partición 232
8.6.5. Elementos iguales al pivote 234
8.6.6. Partición con la mediana de tres 234
8.6.7. Vectores pequeños 235
8.6.8. Rutina de quicksort en Java 236
8.7. Selección rápida 238
8.8. Una cola inferior para la ordenación 240
9. Números aleatorios 249
9.1. ¿Por qué son necesarios los números aleatorios? 249
9.2. Generadores de números aleatorios 250
9.3. Números aleatorios no uniformes 256
9.4. Generación de una permutación aleatoria 258
9.5. Algoritmos aleatorios 259
9.6. Test aleatorio de primalidad 261
TERCERA PARTE. Aplicaciones
10. Juegos y diversión 273
10.1. Sopas de letras 273
10.1.1 Teoría 274
10.1.2. Implementación en Java 276
10.2. El juego de las tres en raya 281
10.2.1. Poda alfa-beta 281
10.2.2. Tablas de transposición 282
10.3. El ajedrez 285
11. Las pilas y los compiladores 291
11.1. Analizador de símbolos equilibrados 291
11.1.1. El algoritmo básico 291
11.1.2. Implementación 293
11.2. Una calculadora sencilla 301
11.2.1. Máquinas postfijas 302
11.2.2. Conversión de notación infija a postfija 302
11.2.3. Implementación 305
11.2.4. Arboles sintácticos de expresiones 312
12. Utilidades 317
12.1. Compresión de ficheros 317
12.1.1. Códigos sin prefijos 318
12.1.2. Algoritmo de Huffman 320
12.1.3. La fase de codificación 322
12.1.4. La fase de decodificación 323
12.1.5. Consideraciones prácticas 324
12.2. Generador de referencias cruzadas 324
12.2.1. Ideas básicas 324
12.2.2. Implementación en Java 325
13. Simulación 335
13.1. El problema Josephus 335
13.1.1. La solución simple 336
13.1.2. Un algoritmo más eficiente 338
13.2. Simulación dirigida por eventos 340
13.2.1. Ideas básicas 340
13.2.2. Ejemplo: simulación de un banco de módems 341
14. Grafos y caminos 353
14.1. Definiciones 353
14.1.1. Representación 355
14.2. Problema del camino mínimo sin pesos 366
14.2.1. Teoría 366
14.2.2. Implementación en Java 370
14.3. Problema de los caminos mínimos con pesos positivos 371
14.3.1. Teoría: algoritmo de Dijkstra 371
14.3.2. Implementación en Java 375
14.4. Problema del camino mínimo con costes negativos 376
14.4.1. Teoría 376
14.4.2. Implementación en Java 377
14.5. Problemas de caminos en grafos acíclicos 379
14.5.1. Ordenación topológica 379
14.5.2. Teoría del algoritmo de caminos mínimos con un grafo acíclico 381
14.5.3. Implementación en Java 382
14.5.4. Una aplicación: análisis de caminos críticos 382
CUARTA PARTE. Implementaciones
15. Pilas y colas 395
15.1. Implementación dinámica de vectores 395
15.1.1. Pilas 395
15.1.2. Colas 399
15.2. Implementaciones con listas enlazadas 404
15.2.1. Pilas 404
15.2.2. Colas 408
15.3. Comparación de los dos métodos 409
15.4. Colas dobles 411
16. Listas enlazadas 415
16.1. Ideas básicas 415
16.1.1. Nodos cabecera 417
16.1.2. Clases iteradoras 418
16.2. Implementación en Java 419
16.3. Listas doblemente enlazadas y listas enlazadas circulares 426
16.4. Listas enlazadas ordenadas 428
17. Arboles 435
17.1. Arboles generales 435
17.1.1. Definiciones 435
17.1.2. Implementación 437
17.1.3. Una aplicación: sistemas de ficheros 437
17.2. Arboles binarios 441
17.3. Arboles y recursión 448
17.4. Recorrido de árboles: clases iteradoras 450
17.4.1. Recorrido en postorden 453
17.4.2. Recorrido en orden simétrico 457
17.4.3. Recorrido en preorden 458
17.4.4. Recorrido por niveles 459
18. Arboles binarios de búsqueda 467
18.1. Ideas básicas 467
18.1.1. Las operaciones 468
18.1.2. Implementación en Java 470
18.2. Búsqueda por posición en el orden 477
18.2.1. Implementación en Java 477
18.3. Análisis de las operaciones de los árboles binarios de búsqueda 481
18.4. Arboles AVL 484
18.4.1. Propiedades 485
18.4.2. Rotación simple 487
18.4.3. Rotación doble 490
18.4.4. Resumen de la inserción en un árbol AVL 492
18.5. Arboles rojinegros 492
18.5.1. Inserción ascendente 493
18.5.2. Arboles rojinegros descendentes 495
18.5.3. Implementación en Java 497
18.5.4. Eliminación descendente 503
18.6. AA-Arboles 505
18.6.1. Inserción 506
18.6.2. Eliminación 509
18.6.3. Implementación en Java 509
18.7. B-Arboles 512
19. Tablas hash 527
19.1. Ideas básicas 527
19.2. Función de localización 529
19.3. Exploración lineal 531
19.3.1. Análisis de la exploración lineal 532
19.3.2. Lo que sucede realmente: la agrupación primaria 533
19.3.3. Análisis de la operación buscar 534
19.4. Exploración cuadrática 536
19.4.1. Implementación en Java 541
19.4.2. Análisis de la exploración cuadrática 544
19.5. Hashing enlazado 545
20. Una cola de prioridad: el montículo binario 553
20.1. Ideas básicas 553
20.1.1. Propiedad estructural 554
20.1.2. Propiedad de ordenación de los montículos 555
20.1.3. Operaciones permitidas 556
20.2. Implementación de las operaciones básicas 559
20.2.1. insertar 559
20.2.2. eliminarMin 562
20.3. arreglarMontículo: construcción en tiempo lineal del montículo 564
20.4. Operaciones avanzadas: reducirClave y mezclar 568
20.5. Ordenación interna: método del montículo 568
20.6. Ordenación externa 571
20.6.1. Por qué necesitamos nuevos algoritmos 572
20.6.2. Modelo de ordenación externa 572
20.6.3. El algoritmo sencillo 572
20.6.4. Mezcla multiaria 574
20.6.5. Mezcla multifase 575
20.6.6. Selección del reemplazo 576
QUINTA PARTE. Estructuras de datos avanzadas
21. Arboles de ensanchamiento 587
21.1. Auto-ajustamiento y análisis amortizado 587
21.1.1. Cotas de tiempo amortizadas 588
21.1.2. Una estrategia simple de auto-ajustamiento (que no funciona) 589
21.2. Arboles básicos de ensanchamiento ascendente 591
21.3. Operaciones básicas de los árboles de ensanchamiento 593
21.4. Análisis del ensanchamiento ascendente 594
21.4.1. Demostración de la cota de ensanchamiento 597
21.5. Arboles de ensanchamiento descendente 600
21.6. Implementación de los árboles con ensanchamiento descendente 602
21.7. Comparaciones de los árboles de ensanchamiento con otros árboles de búsqueda 608
22. Colas de prioridad con mezcla 613
22.1. Los montículos sesgados 613
22.1.1. La mezcla es importante 613
22.1.2. Mezcla simple de árboles con ordenación de montículos 614
22.1.3. El montículo sesgado: una modificación sencilla 615
22.1.4. Análisis del montículo sesgado 616
22.2. Los montículos de emparejamientos 618
22.2.1. Operaciones del montículo de emparejamientos y teoría 618
22.2.2. Implementación del montículo de emparejamientos 620
22.2.3. Aplicación: el algoritmo de Dijkstra para la obtención de caminos mínimos 626
23. Estructura de partición 633
23.1. Relaciones de equivalencia 633
23.2. Equivalencia dinámicas y dos aplicaciones 634
23.2.1. Aplicación #1: árboles de recubrimiento mínimo 635
23.2.2. Aplicación #2: el problema del antecesor común mas próximo 637
23.3. El algoritmo de búsqueda rápida 641
23.4. El algoritmo de unión rápida 642
23.4.1. Algoritmos de unión inteligentes 643
23.4.2. Compresión de caminos 645
23.5. Implementación en Java 647
23.6. Caso peor de la unión por rango y la compresión de caminos 648
23.6.1. Análisis del algoritmo unir/buscar 649
APENDICES
A. Plataformas para Java
B. Operadores
C. Algunas rutinas de librerías
D. Interfaces gráficas de usuario
Indice analítico
8478290354
PROGRAMACION DE COMPUTADORAS
LENGUAJE DE PROGRAMACION
JAVA
004.438JAVA W436