Descarga la aplicación para disfrutar aún más
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 .........................................................................................................................
Compartir