Fundamentos de programación Quinta edición - Luis Joyanes Aguilar

Vista previa del material en texto

Quinta edición
Luis Joyanes Aguilar
ALGORITMOS, ESTRUCTURA 
 DE DATOS Y OBJETOS
FUNDAMENTOS DEFUNDAMENTOS DE
 
 
Luis Joyanes Aguilar
Dr. Ingeniero en Informática y Dr. en Sociología
Catedrático de Lenguajes y Sistemas Informáticos
Universidad Pontificia de Salamanca
MÉXICO • BOGOTÁ • BUENOS AIRES • GUATEMALA • LONDRES
MADRID • MILÁN • NUEVA DELHI • NUEVA YORK• SAN JUAN
SANTIAGO • SAO PAULO • SIDNEY • SINGAPUR •TORONTO
Quinta edición
 
Director general de Latinoamérica: Martín Chueco
Director editorial Latinoamérica: Hans Serrano
Gerente de portafolio de Universidad Latinoamérica: Gabriela López Ballesteros
Senior Editor: Guillermo Domínguez Chávez
Gerente de preprensa: José Palacios Hernández
Supervisor de preprensa: José Palacios
Esta publicación no puede ser reproducida ni en todo ni en parte, ni registrada en/o trasmitida por un sistema de 
recuperación de información, en ninguna forma ni por ningún medio, sea mecánico, fotocopiado, electrónico, ni 
magnético, electroóptico o cualquier otro tipo, sin el permiso previo y por escrito de la editorial.
Fundamentos de programación
Algoritmos, estructura de datos y objetos
Quinta edición
Derechos reservados copyright © 2020, 2008 respecto a la quinta edición por 
McGraw-Hill Interamericana Editores, S.A. de C.V.
Prolongación Paseo de la Reforma 1015, Torre A,
Piso 16, Col. Desarrollo Santa Fe,
Alcaldía Álvaro Obregón, 
CP 01376, Ciudad de México.
Miembro de la Cámara Nacional de la Industria Editorial Mexicana, Reg. Núm. 
736.
ISBN 13: 978-1-4562-7944-8
 
A mis queridas nietas Inés y Olivia, quienes siempre están 
en mis pensamientos y cuyo gran cariño y recuerdos siempre 
me acompañan, tanto en mi vida profesional 
como en mi vida personal y familiar. 
Dedicatoria
 
 
Prólogo a la quinta edición ......................................................................................................................................................... XIX
PARTE I ALGORITMOS Y HERRAMIENTAS DE PROGRAMACIÓN ........................................................... 1
Capítulo 1 Introducción a las computadoras y a los lenguajes de programación ................................................................. 3
INTRODUCCIÓN .................................................................................................................................................. 3
1.1. El origen de las computadoras y su evolución ...................................................................................................... 4
1.2. Las computadoras modernas: una breve taxonomía ............................................................................................. 5
1.3. Organización de una computadora ....................................................................................................................... 7
1.3.1. Memoria central de la computadora .......................................................................................................... 9
1.3.2. Memoria caché .......................................................................................................................................... 10
1.3.3. Unidades de medida de memoria ............................................................................................................. 11
1.3.4. Dispositivos de entrada y salida ................................................................................................................ 12
1.3.5. Dispositivos de almacenamiento secundario ............................................................................................. 13
1.3.6. Sistemas de comunicación ........................................................................................................................ 13
1.4. Software: conceptos básicos y clasificación ........................................................................................................... 13
1.4.1. Software de sistema ................................................................................................................................... 15
1.4.2. Software de aplicaciones ........................................................................................................................... 15
1.4.3. Software propietario ................................................................................................................................. 16
1.4.4. Software de código abierto ........................................................................................................................ 16
1.5. Sistema operativo .................................................................................................................................................. 17
1.6. El lenguaje de la computadora .............................................................................................................................. 20
1.6.1.  Representación de la información 
 en las computadoras (códigos de caracteres) ............................................................................................. 20
1.7. La programación de las computadoras 
 en perspectiva ....................................................................................................................................................... 21
1.8. Lenguajes de programación .................................................................................................................................. 22
1.8.1.  Tipos de lenguajes de programación: máquina, ensamblador y de alto nivel ............................................ 23
1.9. Traductores de lenguaje: el proceso de traducción de un programa ..................................................................... 26
1.9.1. Intérpretes ................................................................................................................................................. 26
1.9.2. Compiladores ............................................................................................................................................ 27
1.9.3. Compiladores versus intérpretes ............................................................................................................... 27
1.9.4. La compilación y sus fases ........................................................................................................................ 28
1.10. Evolución de los lenguajes de programación ....................................................................................................... 29
1.11. Paradigmas de programación .............................................................................................................................. 30
1.12. Internet y la Web ................................................................................................................................................. 31
1.12.1. Desarrollo de programas web ................................................................................................................... 32
1.13. Cloud computing (computación en la nube como servicio) ..................................................................................... 33
1.13.1. Software como servicio (SaaS) ................................................................................................................. 33
1.13.2. Plataforma como servicio (PaaS) .............................................................................................................. 34
1.13.3. Infraestructura como servicio (IaaS) ......................................................................................................... 34
Contenido
 
VIII Contenido
1.14. Internet de las cosas ............................................................................................................................................. 35
1.15. Big Data. Los grandes volúmenes de datos ...........................................................................................................35
1.16. Los lenguajes de programación más populares: índice TIOBE.............................................................................. 36
1.17. Nacimiento de la programación moderna: lenguajes de programación 
de referencia (C, C++, Java, Python y C#) ............................................................................................................. 37
RESUMEN ...................................................................................................................................................................... 40
Capítulo 2 Metodología de la programación y desarrollo de software ................................................................................. 41
INTRODUCCIÓN ........................................................................................................................................................... 41
2.1. Fases en la resolución de problemas ..................................................................................................................... 42
2.1.1. Análisis del problema .............................................................................................................................. 43
2.1.2. Diseño del algoritmo ................................................................................................................................ 44
2.1.3. Herramientas de programación ............................................................................................................... 44
2.1.4. Codificación de un programa .................................................................................................................. 47
2.1.5. Compilación y ejecución de un programa ................................................................................................ 48
2.1.6. Verificación y depuración de un programa .............................................................................................. 48
2.1.7. Documentación y mantenimiento ............................................................................................................ 49
2.2. Metodología de la programación .......................................................................................................................... 50
2.2.1. Programación modular ............................................................................................................................ 50
2.3. Programación estructurada ................................................................................................................................... 51
2.3.1. Datos locales y datos globales .................................................................................................................. 52
2.3.2. Técnicas de programación estructurada ................................................................................................... 52
2.3.3. Modelado del mundo real ........................................................................................................................ 53
2.4. Programación orientada a objetos ......................................................................................................................... 54
2.4.1. Abstracción .............................................................................................................................................. 55
2.5. Concepto y características de algoritmos .............................................................................................................. 59
2.5.1. Características de los algoritmos .............................................................................................................. 60
2.5.2. Diseño del algoritmo ................................................................................................................................ 61
2.6. Escritura de algoritmos ......................................................................................................................................... 63
2.7. Representación gráfica de los algoritmos .............................................................................................................. 64
2.7.1. Pseudocódigo ........................................................................................................................................... 65
2.7.2. Diagramas de flujo ................................................................................................................................... 66
2.7.3. Diagramas de Nassi-Schneiderman (N-S) ................................................................................................ 74
2.8. Herramientas y entornos de desarrollo de programación ..................................................................................... 76
2.8.1. Editores de texto ...................................................................................................................................... 76
2.8.2. Programa ejecutable ................................................................................................................................. 76
2.8.3. Proceso de compilación/ejecución de un programa ................................................................................. 77
2.8.4. Entorno de desarrollo integrado .............................................................................................................. 78
2.8.5. Panorama de los entornos de programación ............................................................................................ 78
ACTIVIDADES DE APRENDIZAJE ................................................................................................................................. 79
ACTIVIDADES COMPLEMENTARIAS ............................................................................................................................ 79
RESUMEN ...................................................................................................................................................................... 80
EJERCICIOS ................................................................................................................................................................... 80
Capítulo 3 Estructura general de un programa .................................................................................................................... 83
INTRODUCCIÓN ........................................................................................................................................................... 83
3.1. Concepto de programa ......................................................................................................................................... 84
3.2. Estructura de un programa ................................................................................................................................... 84
3.3. Instrucciones y tipos de instrucciones .................................................................................................................. 85
3.3.1. Tipos de instrucciones ............................................................................................................................. 85
3.3.2. Instrucciones de asignación ..................................................................................................................... 86
3.3.3. Instrucciones de lectura de datos (entrada).............................................................................................. 87
3.3.4. Instrucciones de escritura de resultados (salida) ...................................................................................... 87
3.3.5. Instrucciones de bifurcación .................................................................................................................... 87
3.4. Elementos básicos de un programa ...................................................................................................................... 89
 
IXContenido3.5. Datos, tipos de datos y operaciones primitivas ..................................................................................................... 90
3.5.1. Datos numéricos ...................................................................................................................................... 90
3.5.2. Datos lógicos (booleanos) .......................................................................................................................... 92
3.5.3. Datos tipo carácter y tipo cadena ............................................................................................................. 92
3.6. Constantes y variables .......................................................................................................................................... 92
3.6.1. Declaración de constantes y variables ...................................................................................................... 94
3.7. Expresiones y operadores ..................................................................................................................................... 94
3.7.1. Expresiones aritméticas ........................................................................................................................... 95
3.7.2. Reglas de prioridad .................................................................................................................................. 97
3.7.3. Expresiones lógicas (booleanas) ................................................................................................................. 99
3.7.4. Reglas generales de prioridad y asociatividad .......................................................................................... 102
3.8. Funciones internas ................................................................................................................................................ 102
3.8.1. Funciones matemáticas de Java ................................................................................................................ 104
3.9. Operación de asignación ....................................................................................................................................... 105
3.9.1. Asignación aritmética .............................................................................................................................. 105
3.9.2. Asignación lógica ..................................................................................................................................... 106
3.9.3. Asignación de cadenas de caracteres ....................................................................................................... 106
3.9.4. Asignación múltiple ................................................................................................................................. 106
3.9.5. Conversión de tipo ................................................................................................................................... 107
3.10. Operadores avanzados .......................................................................................................................................... 108
3.10.1. Operador condicional ?: (C/C++, Java) ................................................................................................... 108
3.10.2. Operador coma ........................................................................................................................................ 109
3.10.3. Operadores especiales: ( ), [ ] ............................................................................................................. 109
3.10.4. Operador sizeof ..................................................................................................................................... 110
3.10.5. Operadores de manipulación de bits (bitwise, Java) ................................................................................. 111
3.10.6. Prioridad y asociatividad .......................................................................................................................... 111
3.10.7. Conversiones de tipos .............................................................................................................................. 112
3.11. Entrada y salida de información ........................................................................................................................... 113
3.12. Escritura de algoritmos/programas ....................................................................................................................... 114
3.12.1. Cabecera del programa o algoritmo ......................................................................................................... 114
3.12.2. Declaración de variables .......................................................................................................................... 114
3.12.3. Declaración de constantes numéricas ...................................................................................................... 115
3.12.4. Declaración de constantes y variables carácter ........................................................................................ 115
3.12.5. Comentarios ............................................................................................................................................ 116
3.12.6. Estilo de escritura de algoritmos/programas ............................................................................................ 117
ACTIVIDADES DE PROGRAMACIÓN RESUELTAS ........................................................................................................ 118
CONCEPTOS CLAVE ..................................................................................................................................................... 129
RESUMEN ...................................................................................................................................................................... 129
EJERCICIOS ................................................................................................................................................................... 130
Capítulo 4 Flujo de control I: estructuras selectivas ............................................................................................................ 133
INTRODUCCIÓN ........................................................................................................................................................... 133
4.1. El flujo de control de un programa ....................................................................................................................... 134
4.2. Estructura secuencial ............................................................................................................................................ 134
4.3. Estructuras selectivas ............................................................................................................................................ 136
4.4. Alternativa simple (si-entonces/if-then) ...................................................................................................... 137
4.4.1. Alternativa doble (si-entonces-sino/if-then-else) ....................................................................... 138
4.5. Alternativa múltiple (según_sea, caso de; switch-case) ................................................................................. 143
4.6. Estructuras de decisión anidadas (en escalera) ..................................................................................................... 150
4.7. La sentencia ir-a (goto) [no recomendable su uso, con excepciones] ........................................................ 154
ACTIVIDADES DE PROGRAMACIÓN RESUELTAS ........................................................................................................ 157
CONCEPTOS CLAVE .....................................................................................................................................................160
RESUMEN ...................................................................................................................................................................... 160
EJERCICIOS ................................................................................................................................................................... 161
Capítulo 5 Flujo de control II: estructuras repetitivas ........................................................................................................... 163
INTRODUCCIÓN ........................................................................................................................................................... 163
 
X Contenido
5.1. Estructuras repetitivas .......................................................................................................................................... 164
5.2. Estructura mientras (''while'') ............................................................................................................................. 166
5.2.1. Ejecución de un bucle cero veces ............................................................................................................. 168
5.2.2. Bucles infinitos ......................................................................................................................................... 169
5.2.3. Terminación de bucles con datos de entrada ........................................................................................... 169
5.3. Estructura hacer-mientras (''do-while'') .............................................................................................................. 171
5.4. Diferencias entre mientras (while) y hacer-mientras (do-while): una aplicación en C++ ..................... 173
5.5. Estructura repetir (''repeat'') .......................................................................................................................... 174
5.6. Estructura desde/para (''for'') ........................................................................................................................... 177
5.6.1. Otras representaciones de estructuras repetitivas desde/para (for) ...................................................... 177
5.6.2. Realización de una estructura desde con estructura mientras .............................................................. 180
5.7. Salidas internas de los bucles ............................................................................................................................... 181
5.8. Sentencias de salto interrumpir (break) y continuar (continue) ............................................................... 182
5.8.1. Sentencia interrumpir (break) ............................................................................................................ 182
5.8.2. Sentencia continuar (continue) .......................................................................................................... 183
5.9. Comparación de bucles while, for y do-while: una aplicación en C++ ................................................................ 184
5.10. Diseño de bucles (lazos) ........................................................................................................................................ 185
5.10.1. Bucles para diseño de sumas y productos ................................................................................................ 185
5.10.2. Fin de un bucle ........................................................................................................................................ 186
5.11. Estructuras repetitivas anidadas ........................................................................................................................... 187
5.11.1. Bucles (lazos) anidados: una aplicación en C++ ............................................................................................ 189
5.12. Sentencias de salto en C++, Java y Python: break, continue, return, goto ......................................................... 192
ACTIVIDADES DE PROGRAMACIÓN RESUELTAS ........................................................................................................ 194
CONCEPTOS CLAVE ..................................................................................................................................................... 206
RESUMEN ...................................................................................................................................................................... 206
EJERCICIOS ................................................................................................................................................................... 207
REFERENCIAS BIBLIOGRÁFICAS .................................................................................................................................. 208
Capítulo 6 Subprogramas (subalgoritmos): funciones .......................................................................................................... 209
INTRODUCCIÓN ........................................................................................................................................................... 209
6.1. Introducción a los subalgoritmos o subprogramas ................................................................................................ 210
6.2. Funciones .............................................................................................................................................................. 211
6.2.1. Declaración de funciones ......................................................................................................................... 212
6.2.2. Invocación a las funciones ....................................................................................................................... 213
6.3. Procedimientos (subrutinas) ................................................................................................................................. 218
6.3.1. Sustitución de argumentos/parámetros ................................................................................................... 219
6.4. Ámbito: variables locales y globales ...................................................................................................................... 222
6.5 Comunicación con subprogramas: paso de parámetros ........................................................................................ 226
6.5.1. Paso de parámetros .................................................................................................................................. 227
6.5.2. Paso por valor .......................................................................................................................................... 227
6.5.3. Paso por referencia .................................................................................................................................. 228
6.5.4. Comparaciones de los métodos de paso de parámetros ........................................................................... 229
6.5.5. Síntesis de la transmisión de parámetros .................................................................................................. 231
6.6. Funciones y procedimientos como parámetros ..................................................................................................... 233
6.7. Los efectos laterales .............................................................................................................................................. 235
6.7.1. En procedimientos ................................................................................................................................... 235
6.7.2. En funciones ............................................................................................................................................ 236
6.8 Recursión (recursividad) .......................................................................................................................................237
6.9. Funciones en C/C++, Java y C# ........................................................................................................................... 239
6.10. Ámbito (alcance) y almacenamiento en C/C++ y Java ......................................................................................... 241
6.11. Sobrecarga de funciones en C++ y Java ............................................................................................................... 243
ACTIVIDADES DE PROGRAMACIÓN RESUELTAS ........................................................................................................ 246
CONCEPTOS CLAVE ..................................................................................................................................................... 250
RESUMEN ...................................................................................................................................................................... 250
EJERCICIOS ................................................................................................................................................................... 251
 
XIContenido
PARTE II ESTRUCTURA DE DATOS ..................................................................................................................... 253
Capítulo 7 Estructuras de datos I (arrays –arreglos– y estructuras) ...................................................................................... 255
INTRODUCCIÓN .................................................................................................................................................. 255
7.1. Introducción a las estructuras de datos ................................................................................................................. 256
7.2. Arrays (arreglos) unidimensionales: los vectores .................................................................................................. 257
7.3. Operaciones con vectores ..................................................................................................................................... 259
7.3.1. Asignación ............................................................................................................................................... 260
7.3.2. Lectura/escritura de datos........................................................................................................................ 260
7.3.3. Acceso secuencial al vector (recorrido) .................................................................................................... 261
7.3.4. Actualización de un vector ....................................................................................................................... 262
7.4. Arrays (arreglos) de varias dimensiones ............................................................................................................... 265
7.4.1. Arrays bidimensionales (tablas/matrices) ................................................................................................ 265
7.5. Arrays (arreglos) multidimensionales ................................................................................................................... 267
7.6. Almacenamiento de arrays en memoria ............................................................................................................... 269
7.6.1. Almacenamiento de un vector ................................................................................................................. 269
7.6.2. Almacenamiento de arrays multidimensionales....................................................................................... 270
7.7. Estructuras versus registros ................................................................................................................................... 272
7.7.1. Registros .................................................................................................................................................. 272
7.8. Arrays (arreglos) de estructuras ............................................................................................................................ 273
7.9. Uniones ................................................................................................................................................................. 275
7.9.1. Unión versus estructura ............................................................................................................................ 275
7.10. Enumeraciones ..................................................................................................................................................... 277
ACTIVIDADES DE PROGRAMACIÓN RESUELTAS ........................................................................................................ 279
CONCEPTOS CLAVE ..................................................................................................................................................... 290
RESUMEN ...................................................................................................................................................................... 290
EJERCICIOS ................................................................................................................................................................... 291
Capítulo 8 Las cadenas de caracteres ................................................................................................................................... 293
INTRODUCCIÓN ........................................................................................................................................................... 293
8.1. Introducción ......................................................................................................................................................... 294
8.2. El juego de caracteres ........................................................................................................................................... 294
8.2.1. Código ASCII ........................................................................................................................................... 294
8.2.2. Código EBCDIC ....................................................................................................................................... 295
8.2.3. Código universal Unicode para Internet .................................................................................................. 295
8.2.4. Secuencias de escape ............................................................................................................................... 297
8.3. Cadena de caracteres ............................................................................................................................................ 297
8.4. Datos tipo carácter ................................................................................................................................................ 299
8.4.1. Constantes ............................................................................................................................................... 299
8.4.2. Variables .................................................................................................................................................. 299
8.4.3. Instrucciones básicas con cadenas ........................................................................................................... 300
8.5. Operaciones con cadenas...................................................................................................................................... 301
8.5.1. Cálculo de la longitud de una cadena ...................................................................................................... 301
8.5.2. Comparación ............................................................................................................................................302
8.5.3. Concatenación ......................................................................................................................................... 303
8.5.4. Subcadenas .............................................................................................................................................. 304
8.5.5. Búsqueda ................................................................................................................................................. 305
8.6. Otras funciones de cadenas .................................................................................................................................. 305
8.6.1. Insertar .................................................................................................................................................... 306
8.6.2. Borrar ....................................................................................................................................................... 306
8.6.3. Cambiar ................................................................................................................................................... 307
8.6.4. Conversión de cadenas/números ............................................................................................................. 307
ACTIVIDADES DE PROGRAMACIÓN RESUELTAS ........................................................................................................ 308
CONCEPTOS CLAVE ..................................................................................................................................................... 313
 
XII Contenido
RESUMEN ...................................................................................................................................................................... 313
EJERCICIOS ................................................................................................................................................................... 314
Capítulo 9 Archivos (ficheros) .............................................................................................................................................. 317
INTRODUCCIÓN ........................................................................................................................................................... 317
9.1. Archivos y flujos (stream): la jerarquía de datos .................................................................................................... 318
9.1.1. Campos .................................................................................................................................................... 319
9.1.2. Registros .................................................................................................................................................. 319
9.1.3. Archivos (ficheros) ................................................................................................................................... 320
9.1.4. Bases de datos .......................................................................................................................................... 320
9.1.5. Estructura jerárquica ................................................................................................................................ 320
9.1.6. Jerarquía de datos .................................................................................................................................... 320
9.2. Conceptos y definiciones: terminología ................................................................................................................ 321
9.2.1. Clave (indicativo) ..................................................................................................................................... 321
9.2.2. Registro físico o bloque ............................................................................................................................ 322
9.2.3. Factor de bloqueo ..................................................................................................................................... 322
9.3. Soportes secuenciales y direccionables ................................................................................................................. 323
9.4. Organización de archivos ...................................................................................................................................... 323
9.4.1. Organización secuencial .......................................................................................................................... 324
9.4.2. Organización directa ................................................................................................................................ 324
9.4.3. Organización secuencial indexada ........................................................................................................... 326
9.5. Operaciones sobre archivos .................................................................................................................................. 327
9.5.1. Creación de un archivo ............................................................................................................................ 328
9.5.2. Consulta de un archivo ............................................................................................................................ 328
9.5.3. Actualización de un archivo ..................................................................................................................... 329
9.5.4. Clasificación de un archivo ...................................................................................................................... 329
9.5.5. Reorganización de un archivo .................................................................................................................. 330
9.5.6. Destrucción de un archivo ....................................................................................................................... 330
9.5.7. Reunión, fusión de un archivo ................................................................................................................. 330
9.5.8. Rotura/estallido de un archivo ................................................................................................................. 331
9.6. Gestión de archivos .............................................................................................................................................. 331
9.6.1. Crear un archivo ...................................................................................................................................... 332
9.6.2. Abrir un archivo ...................................................................................................................................... 332
9.6.3. Cerrar archivos ........................................................................................................................................ 334
9.6.4. Borrar archivos ......................................................................................................................................... 334
9.7. Flujos .................................................................................................................................................................... 334
9.7.1. Tipos de flujos .......................................................................................................................................... 334
9.7.2. Flujos en C++ .......................................................................................................................................... 335
9.7.3. Flujos en Java ........................................................................................................................................... 335
9.7.4. Consideraciones prácticas en Java y C# ...................................................................................................336
9.8. Mantenimiento de archivos .................................................................................................................................. 336
9.8.1. Operaciones sobre registros ..................................................................................................................... 337
9.9. Procesamiento de archivos secuenciales (algoritmos) ........................................................................................... 338
9.9.1. Creación ................................................................................................................................................... 338
9.9.2. Consulta ................................................................................................................................................... 339
9.9.3. Actualización ........................................................................................................................................... 341
9.10. Procesamiento de archivos directos (algoritmos) .................................................................................................. 344
9.10.1. Operaciones con archivos directos ........................................................................................................... 344
9.10.2. Clave-dirección ........................................................................................................................................ 351
9.10.3. Tratamiento de las colisiones ................................................................................................................... 351
9.10.4. Acceso a los archivos directos mediante indexación ................................................................................ 351
9.11. Procesamiento de archivos secuenciales indexados .............................................................................................. 353
9.12. Tipos de archivos: consideraciones prácticas en C/C++ y Java ............................................................................ 353
9.12.1. Archivos de texto ..................................................................................................................................... 354
9.12.2. Archivos binarios .................................................................................................................................... 355
9.12.3. Lectura y escritura de archivos ................................................................................................................ 355
 
XIIIContenido
ACTIVIDADES DE PROGRAMACIÓN RESUELTAS ........................................................................................................ 356
CONCEPTOS CLAVE ..................................................................................................................................................... 363
RESUMEN ...................................................................................................................................................................... 363
EJERCICIOS ................................................................................................................................................................... 364
Capítulo 10 Ordenación, búsqueda e intercalación .............................................................................................................. 365
INTRODUCCIÓN ........................................................................................................................................................... 365
10.1. Introducción ...................................................................................................................................................... 366
10.2. Ordenación ........................................................................................................................................................ 367
10.2.1. Método de intercambio o de burbuja ................................................................................................... 368
10.2.2. Ordenación por inserción .................................................................................................................... 373
10.2.3. Ordenación por selección ..................................................................................................................... 375
10.2.4. Método de Shell ................................................................................................................................... 378
10.2.5. Método de ordenación rápida (quicksort)....................................................................................... 380
10.3. Búsqueda ........................................................................................................................................................... 384
10.3.1. Búsqueda secuencial ............................................................................................................................. 384
10.3.2. Búsqueda binaria .................................................................................................................................. 389
10.3.3. Búsqueda mediante transformación de claves (hashing) .................................................................. 393
 10.3.3.1. Métodos de transformación de claves ...................................................................................... 395
 10.3.3.2. Colisiones ............................................................................................................................ 397
10.4. Intercalación ...................................................................................................................................................... 398
ACTIVIDADES DE PROGRAMACIÓN RESUELTAS ........................................................................................................ 401
CONCEPTOS CLAVE ..................................................................................................................................................... 413
RESUMEN ...................................................................................................................................................................... 413
EJERCICIOS ................................................................................................................................................................... 414
Capítulo 11 Ordenación, búsqueda y fusión externa (archivos) ........................................................................................... 415
INTRODUCCIÓN ........................................................................................................................................................... 415
11.1. Introducción ...................................................................................................................................................... 416
11.2. Archivos ordenados ........................................................................................................................................... 416
11.3. Fusión de archivos ............................................................................................................................................. 416
11.4. Partición de archivos ......................................................................................................................................... 420
11.4.1. Clasificación interna ............................................................................................................................. 420
11.4.2. Partición por contenido ........................................................................................................................ 420
11.4.3. Selección por sustitución ...................................................................................................................... 421
11.4.4. Partición por secuencias .......................................................................................................................423
11.5. Clasificación de archivos.................................................................................................................................... 424
11.5.1. Clasificación por mezcla directa ........................................................................................................... 425
11.5.2. Clasificación por mezcla natural .......................................................................................................... 428
11.5.3. Clasificación por mezcla de secuencias equilibradas ............................................................................ 432
ACTIVIDADES DE PROGRAMACIÓN RESUELTAS ........................................................................................................ 433
CONCEPTOS CLAVE .................................................................................................................................................... 437
RESUMEN ..................................................................................................................................................................... 437
EJERCICIOS .................................................................................................................................................................. 438
Capítulo 12 Estructuras dinámicas lineales de datos (pilas, colas y listas enlazadas) ........................................................... 439
INTRODUCCIÓN ........................................................................................................................................................... 439
12.1. Introducción a las estructuras de datos........................................................................................................................ 440
12.1.1. Estructuras dinámicas de datos ............................................................................................................ 440
12.2. Listas ................................................................................................................................................................. 441
12.3. Listas enlazadas ................................................................................................................................................. 443
12.4. Procesamiento de listas enlazadas ..................................................................................................................... 446
12.4.1. Implementación de listas enlazadas con punteros ............................................................................... 446
12.4.2. Implementación de listas enlazadas con arrays (arreglos) .................................................................... 453
 
XIV Contenido
12.5. Listas circulares ................................................................................................................................................. 460
12.6. Listas doblemente enlazadas .............................................................................................................................. 461
12.6.1. Inserción .............................................................................................................................................. 462
12.6.2. Eliminación .......................................................................................................................................... 463
12.7. Pilas ................................................................................................................................................................... 463
12.7.1. Aplicaciones de las pilas ....................................................................................................................... 469
12.8. Colas .................................................................................................................................................................. 471
12.8.1. Representación de las colas .................................................................................................................. 472
12.8.2. Aprovechamiento de la memoria ......................................................................................................... 478
12.9. Doble cola .......................................................................................................................................................... 480
ACTIVIDADES DE PROGRAMACIÓN RESUELTAS ........................................................................................................ 480
CONCEPTOS CLAVE ..................................................................................................................................................... 489
RESUMEN ...................................................................................................................................................................... 489
EJERCICIOS ................................................................................................................................................................... 489
Capítulo 13 Estructura de datos no lineales (árboles y grafos) ............................................................................................. 491
INTRODUCCIÓN ........................................................................................................................................................... 491
13.1. Introducción ...................................................................................................................................................... 492
13.2. Árboles .............................................................................................................................................................. 492
13.2.1. Terminología y representación de un árbol general ............................................................................. 493
13.3. Árbol binario ..................................................................................................................................................... 494
13.3.1. Terminología de los árboles binarios .................................................................................................... 495
13.3.2. Árboles binarios completos .................................................................................................................. 496
13.3.3. Conversión de un árbol general en árbol binario ................................................................................. 497
13.3.4. Representación de los árboles binarios ................................................................................................ 501
 13.3.4.1. Representación por punteros .............................................................................................. 501
 13.3.4.2. Representación por listas enlazadas .................................................................................... 502
 13.3.4.3. Representación por arrays ................................................................................................... 503
13.3.5. Recorrido de un árbol binario .............................................................................................................. 505
13.4. Árbol binario de búsqueda ................................................................................................................................ 507
13.4.1. Búsqueda de un elemento .................................................................................................................... 509
13.4.2. Insertar un elemento ............................................................................................................................ 510
13.4.3. Eliminación de un elemento ................................................................................................................. 511
13.5. Grafos ................................................................................................................................................................518
13.5.1. Terminología de grafos ......................................................................................................................... 519
13.5.2. Representación de grafos ..................................................................................................................... 521
 13.5.2.1. Matriz de adyacencia ........................................................................................................... 521
 13.5.2.2. Lista de adyacencia ............................................................................................................. 523
ACTIVIDADES DE PROGRAMACIÓN RESUELTAS ........................................................................................................ 524
CONCEPTOS CLAVE ..................................................................................................................................................... 529
RESUMEN ...................................................................................................................................................................... 529
EJERCICIOS .................................................................................................................................................................. 530
Capítulo 14 Recursividad ..................................................................................................................................................... 533
INTRODUCCIÓN ........................................................................................................................................................... 533
14.1. La naturaleza de la recursividad ........................................................................................................................ 534
14.2. Recursividad directa e indirecta......................................................................................................................... 538
14.2.1. Recursividad indirecta .......................................................................................................................... 541
14.2.2. Condición de terminación de la recursión ........................................................................................... 542
14.3. Recursión versus iteración .................................................................................................................................. 542
14.4. Recursión infinita .............................................................................................................................................. 544
14.5. Resolución de problemas complejos con recursividad ....................................................................................... 549
14.5.1. Torres de Hanoi .................................................................................................................................... 549
14.5.2. Búsqueda binaria recursiva .................................................................................................................. 555
14.5.3. Ordenación rápida (quicksort) ............................................................................................................... 556
 14.5.3.1. Algoritmo quicksort.............................................................................................................. 560
 
XVContenido
14.5.4. Ordenación mergesort ........................................................................................................................... 560
 14.5.4.1. Algoritmo mergesort en Java ................................................................................................ 561
CONCEPTOS CLAVE ..................................................................................................................................................... 562
RESUMEN ...................................................................................................................................................................... 562
EJERCICIOS ................................................................................................................................................................... 563
PROBLEMAS .................................................................................................................................................................. 564
PARTE III PROGRAMACIÓN ORIENTADA A OBJETOS Y UML 2.5.1 ......................................................... 565
Capítulo 15 Tipos abstractos de datos, objetos y modelado con UML 2.5.1 ......................................................................... 567
INTRODUCCIÓN ........................................................................................................................................................... 567
15.1. Programación estructurada (procedimental) ........................................................................................................ 568
15.1.1. Limitaciones de la programación estructurada..................................................................................... 568
15.1.2. Modelado de objetos del mundo real: el camino a los objetos ............................................................. 569
15.2. Programación orientada a objetos ..................................................................................................................... 570
15.2.1. Objetos ................................................................................................................................................. 571
15.2.2. Tipos abstractos de datos: CLASES ...................................................................................................... 572
15.3. Modelado e identificación de objetos ................................................................................................................ 574
15.4. Propiedades fundamentales de orientación a objetos ........................................................................................ 575
15.4.1. Abstracción .......................................................................................................................................... 575
15.4.2. La abstracción en el software ................................................................................................................ 576
15.4.3. Encapsulamiento y ocultación de datos ................................................................................................ 576
15.4.4. Herencia ............................................................................................................................................... 577
15.4.5. Reutilización o reusabilidad ................................................................................................................... 578
15.4.6. Polimorfismo ........................................................................................................................................ 578
15.5. Modelado de aplicaciones: UML........................................................................................................................ 579
15.5.1. Lenguaje de modelado ......................................................................................................................... 580
15.5.2. UML: el Lenguaje Unificado de Modelado ........................................................................................... 581
15.6. Modelado y modelos .......................................................................................................................................... 581
15.7. Diagramas de UML 2.5.1 ................................................................................................................................... 583
15.8. Bloques de construcción (componentes) de UML 2.5.1 ..................................................................................... 586
15.8.1. Elementos estructurales .......................................................................................................................586
15.8.2. Elementos de comportamiento ............................................................................................................. 587
15.8.3. Elementos de agrupación ..................................................................................................................... 588
15.9. Especificaciones de UML ................................................................................................................................... 588
15.10. Historia de UML ................................................................................................................................................. 589
CONCEPTOS CLAVE ..................................................................................................................................................... 590
RESUMEN ...................................................................................................................................................................... 590
ANEXO: TERMINOLOGÍA DE ORIENTACIÓN A OBJETOS ........................................................................................... 591
EJERCICIOS ................................................................................................................................................................... 591
Capítulo 16 Diseño de clases y objetos: representaciones gráficas en UML ......................................................................... 593
INTRODUCCIÓN ........................................................................................................................................................... 593
16.1. Diseño y representación gráfica de objetos en UML ......................................................................................... 594
16.1.1. Representación gráfica en UML ........................................................................................................... 595
16.1.2. Características de los objetos ................................................................................................................ 596
16.1.3. Estado .................................................................................................................................................. 597
16.1.4. Múltiples instancias de un objeto ......................................................................................................... 599
16.1.5. Evolución de un objeto ......................................................................................................................... 599
16.1.6. Comportamiento .................................................................................................................................. 600
16.1.7. Identidad .............................................................................................................................................. 602
16.1.8. Los mensajes ........................................................................................................................................ 602
16.1.9. Responsabilidad y restricciones............................................................................................................ 604
16.2. Diseño y representación gráfica de clases en UML ........................................................................................... 604
16.2.1. Representación gráfica de una clase ...................................................................................................... 605
 
XVI Contenido
16.2.2. Declaración de una clase ........................................................................................................................ 608
16.2.3. Reglas de visibilidad .............................................................................................................................. 610
16.2.4. Sintaxis .................................................................................................................................................. 611
16.3. Declaración de objetos de clases ........................................................................................................................ 612
16.3.1. Acceso a miembros de la clase: encapsulamiento .................................................................................. 614
16.3.2. Declaración de métodos ......................................................................................................................... 616
16.3.3. Tipos de métodos ................................................................................................................................... 619
16.4. Constructores .................................................................................................................................................... 619
16.4.1. Constructor por defecto (predeterminado) ............................................................................................ 620
16.5. Destructores ...................................................................................................................................................... 623
16.6. Implementación de clases en C++ ............................................................................................................................. 625
16.6.1. Archivos de cabecera y de clases ............................................................................................................ 625
16.6.2. Clases compuestas ................................................................................................................................. 626
16.7. Recolección de basura ........................................................................................................................................ 627
16.7.1. El método finalize () .................................................................................................................................. 628
CONCEPTOS CLAVE ..................................................................................................................................................... 628
RESUMEN ...................................................................................................................................................................... 629
EJERCICIOS ................................................................................................................................................................... 630
LECTURAS RECOMENDADAS ...................................................................................................................................... 632
Capítulo 17 Relaciones entre clases: delegaciones, asociaciones, agregaciones, herencia .................................................... 633
INTRODUCCIÓN ........................................................................................................................................................... 633
17.1. Relaciones entre clases ...................................................................................................................................... 634
17.2. Dependencia ...................................................................................................................................................... 635
17.3. Asociación ......................................................................................................................................................... 635
17.3.1. Multiplicidad ........................................................................................................................................ 637
17.3.2. Restricciones en asociaciones ............................................................................................................... 638
17.3.3. Asociación cualificada .......................................................................................................................... 639
17.3.4. Asociaciones reflexivas .........................................................................................................................