Fundamentos de programación McGraw Hill

Segunda Edición

Algor i tmos, Estructuras de datos y Objetos

Fundamentos de programación

Luis JOYANES AGUILAR

Libro de problemas

FUNDAMENTOSDE PROGRAMACIÓN

Libro de problemas

Segunda edición

FUNDAMENTOSDE PROGRAMACIÓN

Libro de problemas

Segunda edición

Luis Joyanes AguilarLuis Rodríguez Baena

Matilde Fernández AzuelaDepartamento de Lenguajes y Sistemas Informáticos e Ingeniería del Software

Facultad de Informática/Escuela Universitaria de InformáticaUniversidad Pontificia de Salamanca, campus Madrid

MADRID • BUENOS AIRES • CARACAS • GUATEMALA • LISBOA • MÉXICONUEVA YORK • PANAMÁ • SAN JUAN • SANTAFÉ DE BOGOTÁ • SANTIAGO • SÃO PAULO

AUCKLAND • HAMBURGO • LONDRES • MILÁN • MONTREAL • NUEVA DELHI • PARÍSSAN FRANCISCO • SIDNEY • SINGAPUR • ST. LOUIS • TOKIO • TORONTO

FUNDAMENTOS DE PROGRAMACIÓN. Libro de problemas. Segunda edición

No está permitida la reproducción total o parcial de este libro, ni su tratamientoinformático, ni la transmisión de ninguna forma o por cualquier medio, ya seaelectrónico, mecánico, por fotocopia, por registro u otros métodos, sin el permisoprevio y por escrito de los titulares del Copyright.

DERECHOS RESERVADOS © 2003, respecto a la segunda edición en español, porMcGRAW-HILL/INTERAMERICANA DE ESPAÑA, S. A. U.Edificio Valrealty, 1.ª plantaBasauri, 1728023 Aravaca (Madrid)

Editora: Concepción Fernández MadridAsist. editorial: Amelia NievaDiseño de cubierta: Design Master DIMAPreimpresión: Puntographic, S. L.

IMPRESO EN ESPAÑA - PRINTED IN SPAIN

ISBN: 978-84-481-3986-5Depósito legal: SE-1388-2011

Impreso en: Publidisa

v

CONTENIDO

Prólogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi

Capítulo 1. Algoritmos y programas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1. Configuración de una computadora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2. Lenguajes de programación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3. Resolución de problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3.1. Fase de resolución del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3.1.1. Análisis del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3.1.2. Diseño del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3.1.3. Verificación de algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.2. Fase de implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.4. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Capítulo 2. La resolución de problemas con computadoras y las herramientas de programación . . . . . . 15

2.1. Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.1.1. Constantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1.2. Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1.3. Expresiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1.4. Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2. Representación de algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.3. Diagrama de flujo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.4. Diagrama Nassi-Schneiderman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.5. Pseudocódigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.5.1. Comentarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.5.2. Palabras reservadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.5.3. Identificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.5.4. Operadores y signos de puntuación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.5.5. Literales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.6. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Capítulo 3. Estructura general de un programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.1. Estructura de un programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2. Estructura general de un algoritmo en pseudocódigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.3. La operación de asignación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.3.1. Contadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.3.2. Acumuladores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.3.3. Interruptores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42


Capítulo 4. Introducción a la programación estructurada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.1. Programación estructurada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.2. Teorema de Böhm y Jacopini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.3. Control del flujo de un programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.3.1. Estructura secuencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.3.2. Estructura selectiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.3.3. Estructura repetitiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584.3.4. Estructura anidada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.3.5. Sentencias de salto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61


Capítulo 5. Subprogramas (subalgoritmos), procedimientos y funciones . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.1. Programación modular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.2. Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5.2.1. Declaración de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805.3. Procedimientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

5.3.1. Declaración de procedimientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815.4. Estructura general de un algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815.5. Paso de parámetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 825.6. Variables locales y globales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 845.7. Recursividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 845.8. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

Capítulo 6. Estructuras de datos (arrays y registros) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

6.1. Datos estructurados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1056.2. Arrays (arreglos) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

6.2.1. Arrays unidimensionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1076.2.2. Arrays bidimensionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1076.2.3. Recorrido de los elementos del array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1086.2.4. Arrays como parámetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

6.3. Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1096.4. Registros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

6.4.1. Arrays de registros y arrays paralelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1116.5. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

Capítulo 7. Las cadenas de caracteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

7.1. Cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1497.2. Operaciones con cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1507.3. Funciones útiles para la manipulación de cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1517.4. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

Capítulo 8. Archivos (ficheros). Archivos secuenciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

8.1. Conceptos generales sobre archivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1598.1.1. Jerarquización . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1608.1.2. Clasificación de los archivos según su función . . . . . . . . . . . . . . . . . . . . . . . . . . . 1608.1.3. Operaciones básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1608.1.4. Otras operaciones usuales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1618.1.5. Soportes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

vimmContenido

8.2. Flujos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1618.3. Organización secuencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

8.3.1. Archivos de texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1628.3.2. Mantenimiento de archivos secuenciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163


Capítulo 9. Archivos directos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

9.1. Organización directa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1859.1.1. Funciones de conversión de clave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1869.1.2. Tratamiento de sinónimos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1879.1.3. Mantenimiento de archivos directos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

9.2. Organización secuencial indexada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1879.3. Modos de acceso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

9.3.1. Archivos indexados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1899.4. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

Capítulo 10. Ordenación, búsqueda e intercalación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223

10.1. Búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22310.1.1. Búsqueda secuencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22310.1.2. Búsqueda binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22410.1.3. Búsqueda por transformación de claves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

10.1.3.1. Funciones de conversión de clave . . . . . . . . . . . . . . . . . . . . . . . . . . 22410.1.3.2. Resolución de colisiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

10.2. Ordenación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22710.2.1. Ordenación interna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

10.2.1.1. Selección . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22710.2.1.2. Burbuja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22810.2.1.3. Inserción directa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22810.2.1.4. Inserción binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22810.2.1.5. Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22910.2.1.6. Ordenación rápida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

10.3. Intercalación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23010.4. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

Capítulo 11. Búsqueda, ordenación y fusión externas (archivos) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

11.1. Conceptos generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23911.2. Búsqueda externa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23911.3. Fusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23911.4. Ordenación externa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

11.4.1. Partición de archivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24011.4.1.1. Partición por contenido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24011.4.1.2. Partición en secuencias de longitud 1 . . . . . . . . . . . . . . . . . . . . . . . . 24011.4.1.3. Partición en secuencias de longitud N . . . . . . . . . . . . . . . . . . . . . . . 24011.4.1.4. Partición en secuencias de longitud N con clasificación interna de di-

chas secuencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24011.4.1.5. Partición según el método de selección por sustitución . . . . . . . . . . . 24111.4.1.6. Partición por el método de selección natural . . . . . . . . . . . . . . . . . . 241

11.4.2. Ordenación por mezcla directa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24111.4.3. Ordenación por mezcla natural . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

11.5. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

Capítulo 12. Estructuras dinámicas lineales de datos (listas enlazadas, pilas, colas) . . . . . . . . . . . . . . . . . 261

12.1. Estructuras dinámicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26112.2. Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

Contenidommvii

12.3. Pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26512.3.1. Aplicaciones de las pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266

12.4. Colas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26612.4.1. Doble cola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26612.4.2. Aplicaciones de las colas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267


Capítulo 13. Estructuras de datos no lineales (árboles y grafos) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

13.1. Árboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30713.1.1. Terminología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30813.1.2. Árboles binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

13.1.2.1. Conversión de un árbol general en binario . . . . . . . . . . . . . . . . . . . . 30913.1.2.2. Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31013.1.2.3. Recorridos de un árbol binario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31113.1.2.4. Árbol binario de búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

13.2. Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31213.2.1. Terminología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31313.2.1. Representación de los grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313


Capítulo 14. Recursividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

14.1. Concepto y tipos de recursividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33314.2. Uso adecuado de la recursividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33414.3. Métodos para la resolución de problemas que utilizan recursividad . . . . . . . . . . . . . . . . 33514.4. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336

Capítulo15. Introducción a la Programación Orientada a Objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357

15.1. Mecanismos de abstracción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35715.1.1. Funciones y procedimientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35715.1.2. Módulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35815.1.3. Tipos datos abstractos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

15.2. Modelado del mundo real: clases y objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35815.2.1. Atributos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35915.2.2. Comportamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36015.2.3. Identidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36015.2.4. Paso de mensajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360

15.3. El enfoque orientado a objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36015.4. Clases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

15.4.1. Declaración de clases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36315.5. Representación gráfica de una clase en UML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364

15.5.1. Atributos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36415.5.2. Operaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36515.5.3. Representación gráfica de una clase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36615.5.4. Notación de objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36615.5.5. Reglas para encontrar clases en el análisis . . . . . . . . . . . . . . . . . . . . . . . . . . . 367

15.6. Responsabilidad de una clase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36815.7. Declaración de objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36915.8. Los miembros de un objeto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36915.9. Constructores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370

15.10. Acceso a los miembros de un objeto, visibilidad y encapsulamiento . . . . . . . . . . . . . . 37015.11. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37115.12. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371

viiimmContenido

Capítulo 16. Relaciones: Asociación, Generalización, Herencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379

16.1. Relaciones entre clases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37916.2. Asociaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37916.3. Agregaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382

16.3.1. Composición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38316.4. Jerarquía de clases: Generalización y Especialización . . . . . . . . . . . . . . . . . . . . . . . . . 38416.5. Clases abstractas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39216.6. Polimorfismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39416.7. Ejercicios resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395

Apéndice A. Especificaciones del lenguaje algorítmico UPSAM. Versión 2.0 . . . . . . . . . . . . . . . . . . . . . . 407

A.1. Elementos del lenguaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407A.1.1. Identificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407A.1.2. Comentarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407A.1.3. Tipos de datos estándar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407A.1.4. Constantes de tipos de datos estándar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408A.1.5. Operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409

A.2. Estructura de un programa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409A.2.1. Declaración de tipos de datos estructurados . . . . . . . . . . . . . . . . . . . . . . . . . . . 409A.2.2. Declaración de constantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410A.2.3. Declaración de variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410A.2.4. Biblioteca de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411A.2.5. Procedimientos de entrada/salida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411A.2.6. Instrucción de asignación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412

A.3. Estructuras de control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412A.3.1. Estructuras selectivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412A.3.2. Estructuras repetitivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412

A.4. Programación modular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413A.4.1. Cuestiones generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413A.4.2. Procedimientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413A.4.3. Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414

A.5. Archivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414A.5.1. Archivos secuenciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414A.5.2. Archivos de texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415A.5.3. Archivos directos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416A.5.4. Consideraciones adicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417

A.6. Variables dinámicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417A.7. Programación orientada a objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418

A.7.1. Cables y objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418A.7.2. Atributos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419A.7.3. Métodos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420A.7.4. Herencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421

A.8. Palabras reservadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422

Apéndice B. Bibliografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425

Índice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431

Contenidommix

xi

PRÓLOGO

La iniciación de un estudiante —de informática, de ingeniería de sistemas, de ciencias de la computación,o de cualquier otra rama de las ciencias e ingeniería— en las técnicas de programación del siglo XXI re-quiere no sólo del aprendizaje clásico del diseño de algoritmos y de la comprensión de las técnicas estruc-turadas, sino también de técnicas orientadas a objetos. Por esta circunstancia, esta 2.ª edición ha introduci-do como gran novedad un capítulo completo de recursividad, que muchos lectores de la primera edición noshabían solicitado, así como dos capítulos, lo más completos posibles, sobre propiedades y técnicas de pro-gramación orientada a objetos (POO).

La POO se ha convertido en un paradigma importante en todos los campos de las Ciencias de la Com-putación y, por ello, es importante enseñar programación OO desde los primeros cursos de programación.Este libro pretende iniciar al lector en la programación orientada a objetos, enseñándole las técnicas básicascon el objetivo fundamental de poder aprender en una segunda etapa y de modo riguroso a programar conun enfoque orientado a objetos y con ayuda de algún lenguaje OO tal como C++, Java o C#, e incluso Vi-sual Basic o mejor VB .Net.

Para conseguir los objetivos del libro utilizaremos fundamentalmente el lenguaje algorítmico, con for-mato de pseudocódigo, herramienta ya probada y experimentada, no sólo en la primera edición de esta obra,sino también en las tres ediciones de la obra complementaria Fundamentos de programación, y muy utili-zada en numerosas universidades y centros de formación de todo el mundo.

La clave para desarrollar software es aplicar el concepto de abstracción en el diseño e implementaciónde proyectos software. En base a ello, se busca también enseñar a resolver problemas utilizando diversos ni-veles de abstracción, y enseñar cómo visualizar y analizar los problemas en niveles diferentes.

El libro contiene los temas más importantes de la programación tradicional tales como estructuras decontrol, funciones, estructuras de datos, métodos de ordenación y búsqueda, … junto con los conceptos fun-damentales de orientación a objetos tales como clases, objetos, herencia, relaciones, etc.

OBJETIVOS DEL LIBRO

El libro pretende enseñar a programar utilizando conceptos fundamentales tales como:

1. Algoritmos (conjunto de instrucciones programadas para resolver una tarea específica).2. Datos (una colección de datos que se proporcionan a los algoritmos que se han de ejecutar para en-

contrar una solución: los datos se organizarán en estructuras de datos).3. Objetos (el conjunto de datos y algoritmos que los manipulan, encapsulados en un tipo de dato nue-

vo conocido como objeto).

4. Clases (tipos de objetos con igual estado y comportamiento, o dicho de otro modo, los mismos atri-butos y operaciones).

5. Estructuras de datos (conjunto de organizaciones de datos para tratar y manipular eficazmente da-tos homogéneos y heterogéneos).

6. Temas avanzados (archivos, recursividad y ordenaciones/búsquedas avanzadas).

Los dos primeros aspectos, algoritmos y datos, han permanecido invariables a lo largo de la corta histo-ria de la informática/computación, pero la interrelación entre ellos sí que ha variado y continuará hacién-dolo. Esta interrelación se conoce como paradigma de programación.

Así pues y en resumen, los objetivos fundamentales de esta obra son: introducción a la programaciónestructurada, estructuras de datos y programación orientada a objetos utilizando un lenguaje algorítmicoUPSAM 2.0 que utiliza como herramienta fundamental el pseudocódigo, aunque también se enseñan las he-rramientas tradicionales tales como diagramas de flujo y diagramas N-S.

EL LIBRO COMO HERRAMIENTA DOCENTE

La experiencia de los autores desde hace muchos años con obras muy implantadas en el mundo universita-rio, pero en este caso y de modo especial, la primera edición de Fundamentos de programación. Librode problemas nos ha llevado a mantener la estructura de esta obra, actualizando el contenido que se prevépara los estudiantes del actual siglo XXI y con un lenguaje de programación como es el lenguaje algorítmicoUPSAM 2.0 que pretende contener la sintaxis y las estructuras gramaticales de lenguajes modernos comoJava y C# o los ya clásicos C y C++, sin olvidar los populares Pascal o FORTRAN. Por ello, en el conteni-do de la obra hemos tenido en cuenta no sólo las directrices de los planes de estudio españoles de ingenie-ría informática (antigua licenciatura en informática) y ciencias de la computación, sino también de inge-nierías tales como industriales, telecomunicaciones, agrónomos o minas, o las más recientes incorporadasen España, como ingeniería en geodesia, ingeniería química o ingeniería telemática. Nuestro conocimien-to del mundo educativo latinoamericano nos ha llevado a pensar también en las carreras de ingeniería de sis-temas computacionales y las licenciaturas en informática y en sistemas de información, como se las cono-ce en Latinoamérica.

Por todo lo anterior, el contenido del libro intenta seguir un programa estándar de un primer curso de in-troducción a la programación y, según situaciones, un segundo curso de programación de nivel medio, enasignaturas tales como Metodología de la programación, Fundamentos de programación, Introducción a laprogramación,... El contenido del libro abarca los citados programas y comienza con la introducción a losalgoritmos y a la programación, para llegar a estructuras de datos y objetos. Por esta circunstancia, la es-tructura del curso no ha de ser secuencial en su totalidad, sino que el profesor/maestro y el alumno/lectorpodrán estudiar sus materias en el orden que consideren más oportuno.

Se trata de describir los dos paradigmas más populares en el mundo de la programación: el procedimentaly el orientado a objetos. Los cursos de programación en sus niveles inicial y medio están evolucionandopara aprovechar las ventajas de nuevas y futuras tendencias en ingeniería de software y en diseño de len-guajes de programación, específicamente diseño y programación orientada a objetos. Algunas facultades yescuelas de ingenieros, junto con la nueva formación profesional (ciclos formativos de nivel superior) en Es-paña y en Latinoamericana, están introduciendo a sus alumnos en la programación orientada a objetos, in-mediatamente después del conocimiento de la programación estructurada, e incluso en ocasiones antes.

El contenido del libro se ha pensado en el desarrollo de dos cuatrimestres o semestres (según la termi-nología americana) y siguiendo los descriptores (temas centrales) recomendados por el Consejo de Univer-sidades de España para los planes de estudio de ingeniería en informática, ingeniería técnica en informáti-ca e ingeniería técnica en informática de gestión, así como en asignaturas tales como introducción a laprogramación y fundamentos de programación de carreras como ingeniero e ingeniero técnico de teleco-municaciones, ingeniería telemática, ingeniería industrial y carreras afines. Así mismo y dado nuestroconocimiento de numerosas universidades latinoamericanas, se ha pensado en carreras de ingeniería de sis-temas.

xiimmPrólogo

No podíamos dejar de lado las recomendaciones de la más prestigiosa organización de informáticos delmundo, ACM, sobre todo pensando en nuestros lectores de Latinoamérica. Se estudió en su momento losborradores de la Curricula de Computer Science de modo que tras su publicación el 15 de diciembre de 2001del Computing Curricula 2001 Computer Science. Como lógicamente no se podía seguir todas sus directri-ces al pie de la letra, del cuerpo de conocimiento se optó por seguir del modo más aproximado posible lasmaterias, Programming Fundamentals (PF) Algorithms and Complexity (AL) y Programming Languages(PL).

Uno de los temas más debatidos en la educación en informática o en ciencias de la computación (Com-puter Sciences) es el rol de la programación en el currículo introductorio. A través de la historia de la dis-ciplina —como fielmente reconoce en la introducción del Capítulo 7 relativo a cursos de introducción, ACMen su Computing Curricula 2001— la mayoría de los cursos de introducción a la informática se han centra-do principalmente en el desarrollo de habilidades o destrezas de programación. La adopción de un curso deintroducción a la programación proviene de una serie de factores prácticos e históricos incluyendo los si-guientes:

• La programación es una técnica esencial que debe ser dominada por cualquier estudiante de informá-tica. Su inserción en los primeros cursos de la carrera asegura que los estudiantes tengan la facilidadnecesaria con la programación para cuando se matriculan en los cursos de nivel intermedio y avanzado.

• La informática no se convirtió en una disciplina académica hasta después que la mayoría de las insti-tuciones ha desarrollado un conjunto de cursos de programación introductorias que sirvan a una granaudiencia.

• El modelo de programación del currículum del 78 de la ACM definía a estos cursos como «Introduc-ción a la Programación» y se les denominó CS1 y CS2. Hoy día se le sigue denominando así despuésde la publicación de los currículo del 91 y del 91 y del 2001.

• Los programas de informática deben enseñar a los estudiantes cómo usar bien al menos un lenguajede programación. Además, se recomienda que los programas en informática deben enseñar a los estu-diantes a ser competentes en lenguajes y que hagan uso de al menos dos paradigmas de programación.Como consecuencia de estas ideas, el currículo 2001 de la ACM contempla la necesidad de concep-tos y habilidades que son fundamentales en la práctica de la programación con independencia del pa-radigma subyacente. Como resultado de este pensamiento, el área de fundamentos de programaciónincluye unidades sobre conceptos básicos de programación, estructuras de datos básicas y procesos al-gorítmicos.

La fluidez en un lenguaje de programación es prerrequisito para el estudio de las ciencias de la compu-tación, pero la dificultad de elegir el lenguaje siempre es una dificultad más a añadir a la ya de por sí difí-cil misión del maestro o profesor. Por esta razón, ya en el lejano año de 1986 cuando publicamos la prime-ra edición del libro Fundamentos de programación y tras la experiencia de sus ediciones sucesivas y sus yacasi 18 años (la mayoría de edad en casi todos los países del mundo), la apuesta que hicimos de utilizar unlenguaje algorítmico, seguimos manteniéndola, y en esta ocasión hemos podido ofrecer la versión 2.0 dellenguaje UPSAM utilizada y probada en numerosas universidades españolas y americanas.

Este libro se ha escrito pensando en que pudiera servir de referencia, guía de estudio y sobre todo comoherramientas de prácticas de introducción a la programación, con una segunda parte que, a su vez, sirvieracomo continuación, y de introducción a las estructuras de datos y a la programación orientada a objetos;todos ellos utilizando un pseudolenguaje o lenguaje algorítmico como lenguaje de programación. El obje-tivo final que busca es no sólo describir la sintaxis de dicho lenguaje, sino y, sobre todo, mostrar las carac-terísticas más sobresalientes del lenguaje a la vez que se enseñan técnicas de programación estructurada yorientada a objetos. Así pues, los objetivos fundamentales son:

• Énfasis fuerte en el análisis, construcción y diseño de programas.• Un medio de resolución de problemas mediante técnicas de programación.• Una introducción a la informática y a las ciencias de la computación usando algoritmos y el lenguaje

algorítmico, basado en pseudocódigo.

Prólogommxiii

En resumen, este es un libro diseñado para enseñar a programar utilizando un lenguaje algorítmico conla herramienta de sintaxis, del pseudocódigo, y con una versión probada y actualizada UPSAM 2.0 cuya pri-mera versión vio la luz en la primera edición de la obra base de este libro Fundamentos de programación,en el año 1986. Así, se tratará de enseñar las técnicas clásicas y avanzadas de programación estructurada,junto con técnicas orientadas a objetos. La programación orientada a objetos no es la panacea universal delprogramador del siglo XXI, pero le ayudará a realizar tareas que, de otra manera, serían complejas y tediosas.

El contenido del libro trata de proporcionar soporte a un año académico completo (dos semestres o cua-trimestres), alrededor de 24 a 32 semanas, dependiendo lógicamente de su calendario y planificación. Losnueve primeros capítulos pueden comprender el primer semestre y los restantes capítulos pueden impartir-se en el segundo semestre. Lógicamente la secuencia y planificación real dependerá del maestro o profesorque marcará y señalará, semana a semana, la progresión que él considera lógica. Si es un estudiante autodi-dacta, su propia progresión vendrá marcada por las horas que dedique al estudio y al aprendizaje con la com-putadora, aunque no debe variar mucho del ritmo citado al principio de este párrafo.

LIBRO COMPLEMENTARIO

Aunque este libro ha sido escrito como una obra práctica de aprendizaje para la introducción a la progra-mación de computadoras y no se necesita más conocimientos que los requeridos para la iniciación a los es-tudios universitarios o de formación profesional en carreras de ingeniería o licenciatura en informática, in-geniería de sistemas, telecomunicaciones o industriales, y estudios de formación profesional en las ramastecnológicas, también ha sido escrito pensando en ser libro complementario de la obra Fundamentos de pro-gramación (Joyanes, 3.ª ed. McGraw-Hill, 2003). Para ello el contenido del libro coincide casi en su totali-dad con los diferentes capítulos de la citada obra. De esta manera, se pueden estudiar conjuntamente amboslibros con lo que se conseguirá no sólo un aprendizaje más rápido sino y sobre todo mejor formación teóri-co-práctica y mayor rigor académico y profesional en la misma. La parte teórica de este libro es suficientepara aprender los problemas y ejercicios de programación resueltos y proponer su propias soluciones, sobrela base de que muchos ejercicios propuestos en el libro de teoría ofrecen la solución en este libro de pro-blemas.

ORGANIZACIÓN DEL LIBRO

El libro, aunque no explícitamente, se puede considerar divido a efectos de organización docente por partede profesores (maestros) y alumnos o de lectores autodidactas, en cuatro partes que unidas constituyen uncurso completo de programación. Dado que el conocimiento es acumulativo, los primeros capítulos propor-cionan el fundamento conceptual para la comprensión y aprendizaje de algoritmos, y una guía a los estu-diantes a través de ejemplos y ejercicios sencillos; y los capítulos posteriores presentan de modo progresi-vo la programación en pseudocódigo en detalle, tanto en el paradigma procedimental como en el orientadoa objetos. El contenido detallado del libro es el siguiente:

Capítulo 1. Algoritmos y programas. Presenta una breve descripción del concepto y propiedades fun-damentales de los algoritmos y de los programas. Introduce al lector/estudiante en los elementos básicos deun programa, tipos de datos, operaciones básicas, etc. soportadas por la mayoría de los lenguajes de pro-gramación.

Capítulo 2. Resolución de problemas con computadoras. Se muestran los métodos fundamentales parala resolución de problemas con computadoras y las herramientas de programación necesarias para ello. Sedescriben las etapas clásicas utilizadas en la resolución de problemas, así como las herramientas clásicas ta-les como pseudocódigo, diagrama de flujo y diagrama N-S.

Capítulo 3. Estructura general de un programa. Se analiza la estructura general de un programa y suselementos básicos. Se introduce el concepto de flujo de control y se incluyen los primeros problemas pla-neados de cierta complejidad y su resolución con algunas de las herramientas descritas en el Capítulo 2.

xivmmPrólogo

Fundamentos de programación McGraw Hill

Documents

Transcript of Fundamentos de programación McGraw Hill