CONETNIDO
INTRODUCCION DE LOS TRADUCTORES x
PROLOGO xii
1. ESTRUCTURAS FUNDAMENTALES DE DATOS 1
1.1. Introducción 1
1.2. Concepto de tipo de datos 4
1.3. Tipos elementales de datos 7
1.4. Tipos elementales normalizados 8
1.5. Tipos subcampo 11
1.6. La estructura array 12
1.7. La estructura registro 17
1.8. Variantes de las estructuras registro 22
1.9. La estructura conjunto (set) 25
1.10. Representación de las estructuras array, registro y conjunto 30
1.10.1. Representación de los arrays 32
1.10.2. Representación de las estructuras registro 35
1.10.3. Representación de los conjuntos La estructura fichero secuencial 36
1.11. La estructura fichero secuencial 37
1.11.1. Operadores elementales de ficheros 40
1.11.2. Ficheros con subestructura 43
1.11.3. Textos 45
1.11.4. Un programa para edición de ficheros 53
Ejercicios 57
Referencias 59
2. ORDENACION 61
2.1. Introducción 61
2.2. Ordenación de arrays 64
2.2.1. Ordenación por inserción directa 65
2.2.2. Ordenación por selección directa 68
2.2.3. Ordenación por intercambio directo 71
2.2.4. Ordenación por inserción con incrementos decrecientes 74
2.2.5. Ordenación según un árbol 76
2.2.6. Ordenación por partición 82
2.2.7. Obtención de la mediana 89
2.2.8. Comparación de los métodos de ordenación de arrays 91
1.3. Ordenación de ficheros secuenciales 93
2.3.1. Método de mezcla directa 93
2.3.2. Mezcla natural 99
2.3.3. Mezcla equilibrada múltiple 106
2.3.4. Ordenación polifásica 112
2.3.5. Distribución de los tramos iniciales 125
Ejercicios 130
Referencias 132
3. ALGORITMOS RECURSIVOS 134
3.1. Introducción 134
3.2. Cuándo no utilizar la recursión 137
3.3. Dos ejemplos de programas recursivos 140
3.4. Algoritmos de vuelta atrás 147
3.5. El problema de las ocho reinas 153
3.6. El problema de los matrimonios estables 158
3.7. El problema de la selección óptima 165
Ejercicios 169
Referencias 171
4. ESTRUCTURAS DINAMICAS DE INFORMACION 173
4.1. Tipos recursivos de datos 173
4.2. Punteros o referencias 177
4.3. Listas lineales 182
4.3.1. Operaciones básicas 182
4.3.2. Listas ordenadas v listas reorganizables 186
4.3.3. Una aplicación: ordenación topo lógica 194
4.4. Estructuras árbol 202
4.4.1. Definiciones y conceptos básicos 202
4.4.2. Operaciones básicas con árboles binarios 211
4.4.3. Búsqueda e inserción en árboles 215
4.4.4. Borrado en árboles 224
4.4.5. Análisis de la búsqueda e inserción en árboles 226
4.4.6. Arboles equilibrados 229
4.4.7. Inserción en árboles equilibrados 231
4.4.8. Borrado en árboles equilibrados 236
4.4.9. Arboles de búsqueda óptimos 240
4.4.10. Presentación de estructuras árbol 247
4.5. Arboles multicamino 258
4.5.1. Arboles B 261
4.5.2. Arboles B binarios 273
4.6. Transformaciones de claves hashing 281
4.6.1. Elección de la función de transformación 282
4.6.2. Manejo de colisiones 283
4.6.3. Análisis del Método de transformación de claves 288
Ejercicios 291
Referencias 296
5. ESTRUCTURAS Y COMPILADORES DE LENGUAJES 297
5.1. Definición y estructura de los lenguajes 297
5.2. Análisis de frases 300
5.3. Construcción de un grafo sintáctico 306
5.4. Construcción de un analizador para una sintaxis dada 310
5.5. Construcción de un programa analizador dirigido por tabla 314
5.6. Un traductor de BNF en estructuras de datos para dirigir analizadores 318
5.7. El lenguaje de programación PL/O 326
5.8. Un analizador sintáctico para PL/O 330
5.9. Tratamiento de errores sintácticos 339
5.10. Un procesador PL/O 350
5.11. Generación de código 354
Ejercicios 367
Referencias 369
APENDICES
A. EL CONJUNTO DE CARACTERES ASCII 371
B. DIAGRAMAS SINTACTICOS DE PASCAL 372
INDICE DE MATERIAS 379
INDICE DE PROGRAMAS 382