Fundamentos de programación : libro de problemas ...

1 Segunda Edici n libro de problemas Fundamentos de programaci n A l g o r i t m o s , E s t r u c t u ra s d e d a t o s y O b j e t o s L u i s J O YA N E S A G U I L A R. Fundamentos . DE PROGRAMACI N. libro de problemas Segunda edici n Fundamentos DE PROGRAMACI N. libro de problemas . Segunda edici n No est permitida la reproducci n total o parcial de este libro , ni su tratamiento inform tico, ni la transmisi n de ninguna forma o por cualquier medio, ya sea electr nico, mec nico, por fotocopia, por registro u otros m todos, sin el permiso previo y por escrito de los titulares del Copyright. DERECHOS RESERVADOS 2003, respecto a la segunda edici n en espa ol, por McGRAW-HILL/INTERAMERICANA DE ESPA A, S. A. U. Edificio Valrealty, 1.

2 Planta Basauri, 17. 28023 Aravaca (Madrid). ISBN: 84-481-3986-0. Dep sito legal: M. Editora: Concepci n Fern ndez Madrid Asist. editorial: Amelia Nieva Dise o de cubierta: Design Master DIMA. Preimpresi n: Puntographic, S. L. Impreso en: Fareso, S. A. IMPRESO EN ESPA A - PRINTED IN SPAIN. Fundamentos . DE PROGRAMACI N. libro de problemas Segunda edici n Luis Joyanes Aguilar Luis Rodr guez Baena Matilde Fern ndez Azuela Departamento de Lenguajes y Sistemas Inform ticos e Ingenier a del Software Facultad de Inform tica/Escuela Universitaria de Inform tica Universidad Pontificia de Salamanca, campus Madrid MADRID BUENOS AIRES CARACAS GUATEMALA LISBOA M XICO. NUEVA YORK PANAM SAN JUAN SANTAF DE BOGOT SANTIAGO S O PAULO. AUCKLAND HAMBURGO LONDRES MIL N MONTREAL NUEVA DELHI PAR S.

3 SAN FRANCISCO SIDNEY SINGAPUR ST. LOUIS TOKIO TORONTO. CONTENIDO. Pr logo .. xi Cap tulo 1. Algoritmos y programas .. 1. Configuraci n de una computadora .. 1. Lenguajes de programaci n .. 2. Resoluci n de problemas .. 3. Fase de resoluci n del problema .. 3. An lisis del problema .. 3. Dise o del algoritmo .. 3. Verificaci n de algoritmos .. 5. Fase de implementaci n .. 5. Ejercicios resueltos .. 6. Cap tulo 2. La resoluci n de problemas con computadoras y las herramientas de programaci n .. 15. Datos .. 15. Constantes .. 16. Variables .. 16. Expresiones .. 16. Funciones .. 17. Representaci n de algoritmos .. 18. Diagrama de flujo .. 18. Diagrama Nassi-Schneiderman .. 19. Pseudoc digo .. 20. Comentarios .. 20. Palabras reservadas.

4 21. Identificadores .. 21. Operadores y signos de puntuaci n .. 22. Literales .. 22. Ejercicios resueltos .. 22. Cap tulo 3. Estructura general de un programa .. 39. Estructura de un programa .. 39. Estructura general de un algoritmo en pseudoc digo .. 40. La operaci n de asignaci n .. 41. v vimmContenido Contadores .. 41. Acumuladores .. 41. Interruptores .. 42. Ejercicios resueltos .. 42. Cap tulo 4. Introducci n a la programaci n estructurada .. 55. Programaci n estructurada .. 55. Teorema de B hm y Jacopini .. 55. Control del flujo de un programa .. 56. Estructura secuencial .. 56. Estructura selectiva .. 56. Estructura repetitiva .. 58. Estructura anidada .. 60. Sentencias de salto .. 61. Ejercicios resueltos .. 61. Cap tulo 5.

5 Subprogramas (subalgoritmos), procedimientos y funciones .. 79. Programaci n modular .. 79. Funciones .. 80. Declaraci n de funciones .. 80. Procedimientos .. 81. Declaraci n de procedimientos .. 81. Estructura general de un algoritmo .. 81. Paso de par metros .. 82. Variables locales y globales .. 84. Recursividad .. 84. Ejercicios resueltos .. 85. Cap tulo 6. Estructuras de datos (arrays y registros) .. 105. Datos estructurados .. 105. Arrays (arreglos) .. 106. Arrays unidimensionales .. 107. Arrays bidimensionales .. 107. Recorrido de los elementos del array .. 108. Arrays como par metros .. 109. Conjuntos .. 109. Registros .. 111. Arrays de registros y arrays paralelos .. 111. Ejercicios resueltos .. 112. Cap tulo 7. Las cadenas de caracteres.

6 149. Cadenas .. 149. Operaciones con cadenas .. 150. Funciones tiles para la manipulaci n de cadenas .. 151. Ejercicios resueltos .. 151. Cap tulo 8. Archivos (ficheros). Archivos secuenciales .. 159. Conceptos generales sobre archivos .. 159. Jerarquizaci n .. 160. Clasificaci n de los archivos seg n su funci n .. 160. Operaciones b sicas .. 160. Otras operaciones usuales .. 161. Soportes .. 161. Contenidommvii Flujos .. 161. Organizaci n secuencial .. 161. Archivos de texto .. 162. Mantenimiento de archivos secuenciales .. 163. Ejercicios resueltos .. 164. Cap tulo 9. Archivos directos .. 185. Organizaci n directa .. 185. Funciones de conversi n de clave .. 186. Tratamiento de sin nimos .. 187. Mantenimiento de archivos directos.

7 187. Organizaci n secuencial indexada .. 187. Modos de acceso .. 189. Archivos indexados .. 189. Ejercicios resueltos .. 190. Cap tulo 10. Ordenaci n, b squeda e intercalaci n .. 223. B squeda .. 223. B squeda secuencial .. 223. B squeda binaria .. 224. B squeda por transformaci n de claves .. 224. Funciones de conversi n de clave .. 224. Resoluci n de colisiones .. 226. Ordenaci n .. 227. Ordenaci n interna .. 227. Selecci n .. 227. Burbuja .. 228. Inserci n directa .. 228. Inserci n binaria .. 228. Shell .. 229. Ordenaci n r pida .. 229. Intercalaci n .. 230. Ejercicios resueltos .. 232. Cap tulo 11. B squeda, ordenaci n y fusi n externas (archivos) .. 239. Conceptos generales .. 239. B squeda externa .. 239. Fusi n .. 239. Ordenaci n externa.

8 240. Partici n de archivos .. 240. Partici n por contenido .. 240. Partici n en secuencias de longitud 1 .. 240. Partici n en secuencias de longitud N .. 240. Partici n en secuencias de longitud N con clasificaci n interna de di- chas secuencias .. 240. Partici n seg n el m todo de selecci n por sustituci n .. 241. Partici n por el m todo de selecci n natural .. 241. Ordenaci n por mezcla directa .. 241. Ordenaci n por mezcla natural .. 241. Ejercicios resueltos .. 242. Cap tulo 12. Estructuras din micas lineales de datos (listas enlazadas, pilas, colas) .. 261. Estructuras din micas .. 261. Listas .. 262. viiimmContenido Pilas .. 265. Aplicaciones de las pilas .. 266. Colas .. 266. Doble cola .. 266. Aplicaciones de las colas.

9 267. Ejercicios resueltos .. 267. Cap tulo 13. Estructuras de datos no lineales ( rboles y grafos) .. 307. rboles .. 307. Terminolog a .. 308. rboles binarios .. 308. Conversi n de un rbol general en binario .. 309. Implementaci n .. 310. Recorridos de un rbol binario .. 311. rbol binario de b squeda .. 312. Grafos .. 312. Terminolog a .. 313. Representaci n de los grafos .. 313. Ejercicios resueltos .. 315. Cap tulo 14. Recursividad .. 333. Concepto y tipos de recursividad .. 333. Uso adecuado de la recursividad .. 334. M todos para la resoluci n de problemas que utilizan recursividad .. 335. Ejercicios resueltos .. 336. Cap tulo15. Introducci n a la Programaci n Orientada a Objetos .. 357. Mecanismos de abstracci n .. 357. Funciones y procedimientos.

10 357. M dulos .. 358. Tipos datos abstractos .. 358. Modelado del mundo real: clases y objetos .. 358. Atributos .. 359. Comportamiento .. 360. Identidad .. 360. Paso de mensajes .. 360. El enfoque orientado a objetos .. 360. Clases .. 363. Declaraci n de clases .. 363. Representaci n gr fica de una clase en UML .. 364. Atributos .. 364. Operaciones .. 365. Representaci n gr fica de una clase .. 366. Notaci n de objetos .. 366. Reglas para encontrar clases en el an lisis .. 367. Responsabilidad de una clase .. 368. Declaraci n de objetos .. 369. Los miembros de un objeto .. 369. Constructores .. 370. Acceso a los miembros de un objeto, visibilidad y encapsulamiento .. 370. Resumen .. 371. Ejercicios resueltos .. 371. Contenidommix Cap tulo 16.