Índice general Prologo Agradecimientos Nota de los autores Índice general 1 Problemas, algoritmos y programas

I III V VII 1

1.1 Programas y la actividad de la programación . . . . . . . . . . . . . . . . . . . .

4

1.2 Lenguajes y modelos de programación . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3 La programación orientada a objetos. El lenguaje Java . . . . . . . . . . . . . .

9

1.4 Un mismo ejemplo en diferentes lenguajes . . . . . . . . . . . . . . . . . . . . . .

11

2 Objetos, clases y programas

15

2.1 Estructura básica de una clase: atributos y métodos . . . . . . . . . . . . . . . .

20

2.2 Creación y uso de objetos: operadores new y “.” . . . . . . . . . . . . . . . . . .

23

2.3 La organización en paquetes del lenguaje Java. . . . . . . . . . . . . . . . . . . .

25

2.4 La herencia. Jerarquía de clases, la clase Object . . . . . . . . . . . . . . . . . .

27

2.5 Edición, compilación y ejecución en Java . . . . . . . . . . . . . . . . . . . . . . .

28

2.5.1 Errores en los programas. Excepciones . . . . . . . . . . . . . . . . . . . . . . .

29

2.6 Uso de comentarios. Documentación de programas . . . . . . . . . . . . . . . . .

31

2.7 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

VII

Índice general

3 Variables y asignación. Tipos de datos elementales. Bloques 3.1 Tipos de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

3.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

3.3 Expresiones y asignación. Compatibilidad de tipos . . . . . . . . . . . . . . . . .

42

3.4 Constantes. Modificador final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

3.5 Algunas consideraciones sintácticas sobre identificadores . . . . . . . . . . . . .

44

3.6 Tipos numéricos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

3.6.1 Tipos enteros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

3.6.2 Tipos reales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

3.6.3 Compatibilidad y conversión de tipos. . . . . . . . . . . . . . . . . . . . . . . .

47

3.6.4 Operadores aritméticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

3.6.5 Desbordamiento. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.7 Tipo carácter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

3.8 Tipo lógico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3.8.1 Operadores relacionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3.8.2 Operadores lógicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

3.9 Precedencia de operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

3.10 Bloques de instrucciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

3.11 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

4 Tipos de datos: clases y referencias

VIII

39

67

4.1 Un nuevo ejemplo de definición de una clase . . . . . . . . . . . . . . . . . . . . .

68

4.2 Inicialización de los atributos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

4.3 Representación en memoria de los objetos. Variables referencia . . . . . . . .

71

4.3.1 Declaración de variables. Operador new . . . . . . . . . . . . . . . . . . . . . .

72

4.3.2 El operador de acceso “.” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

4.3.3 La asignación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

4.3.4 Copia de objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

4.3.5 El operador == y el método equals . . . . . . . . . . . . . . . . . . . . . . . . .

78

4.3.6 El garbage collector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

4.4 Información de clase. Modificador static . . . . . . . . . . . . . . . . . . . . . . .

79

4.5 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

Índice general

5 Métodos

85

5.1 Definición y uso de métodos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

5.1.1 Definición de métodos: métodos de clase y de objeto . . . . . . . . . . . . . .

86

5.1.2 Llamadas a métodos: perfil y sobrecarga. . . . . . . . . . . . . . . . . . . . . .

90

5.2 Declaración de métodos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

5.2.1 Modificadores de visibilidad o acceso . . . . . . . . . . . . . . . . . . . . . . . .

94

5.2.2 Tipo de retorno. Instrucción return . . . . . . . . . . . . . . . . . . . . . . . .

95

5.2.3 Lista de parámetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

5.2.4 Cuerpo del método. Acceso a variables. Referencia this . . . . . . . . . . . .

96

5.3 Clases Programa: el método main . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.4 Ejecución de una llamada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 5.4.1 Registro de activación. Pila de llamadas . . . . . . . . . . . . . . . . . . . . . . 102 5.4.2 Paso de parámetros por valor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

5.5 Clases Tipo de Dato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.5.1 Funcionalidad básica de una clase . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.5.2 Sobrescritura de los métodos implementados en Object . . . . . . . . . . . . 109

5.6 Clases de utilidades. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.7 Documentación de métodos: javadoc . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.8 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

6 Algunas clases predefinidas: String, Math. Clases envolventes 127 6.1 La clase String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 6.1.1 Aspectos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6.1.2 Concatenación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6.1.3 Formación de literales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6.1.4 Comparación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.1.5 Algunos métodos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

6.2 La clase Math . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 6.2.1 Constantes y métodos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 6.2.2 Algunos ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

6.3 Clases Envolventes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 6.4 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

IX

Índice general

7 Entrada y salida elemental

147

7.1 Salida por pantalla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 7.1.1 System.out.println y System.out.print . . . . . . . . . . . . . . . . . . . . . 148 7.1.2 Salida formateada con printf . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

7.2 Entrada desde teclado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 7.2.1 La clase Scanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

7.3 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

8 Estructuras de control: selección

165

8.1 Instrucciones condicionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 8.1.1 Instrucción if...else... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 8.1.2 Instrucción switch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

8.2 El operador ternario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 8.3 Algunos ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 8.4 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

9 Estructuras de control: iteración

195

9.1 Iteraciones. El bucle while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 9.2 Diseño de iteraciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 9.2.1 Estructura iterativa del problema . . . . . . . . . . . . . . . . . . . . . . . . . . 199 9.2.2 Terminación de la iteración . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

9.3 La instrucción for . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 9.4 La instrucción do ... while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 9.5 Algunos ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 9.6 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

10 Arrays: definición y aplicaciones

221

10.1 Arrays unidimensionales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 10.1.1 Declaración y creación. Atributo length . . . . . . . . . . . . . . . . . . . . . 222 10.1.2 Acceso a las componentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 10.1.3 Uso. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

10.2 Arrays multidimensionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 10.2.1 Declaración y creación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 10.2.2 Acceso a las componentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

X

Índice general

10.3 Tratamiento secuencial y directo de un array . . . . . . . . . . . . . . . . . . . . 237 10.3.1 Acceso secuencial: recorrido y búsqueda . . . . . . . . . . . . . . . . . . . . . 237 10.3.2 Acceso directo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

10.4 Representación de una secuencia de datos dinámica usando un array . . . . 254 10.5 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

11 Recursividad

271

11.1 Diseño de un método recursivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 11.2 Tipos de recursividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 11.3 Recursividad y pila de llamadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 11.4 Algunos ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280 11.5 Recursividad con arrays: recorrido y búsqueda . . . . . . . . . . . . . . . . . . . 285 11.5.1 Esquemas recursivos de recorrido . . . . . . . . . . . . . . . . . . . . . . . . . 287 11.5.2 Esquemas recursivos de búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . 292

11.6 Recursividad con objetos de tipo String. . . . . . . . . . . . . . . . . . . . . . . 295 11.6.1 Representación de objetos de tipo String y su implicación en la operación substring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

11.7 Recursividad versus iteración . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 11.8 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

12 Análisis del coste de los algoritmos

307

12.1 Análisis de algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 12.2 El coste temporal y espacial de los programas . . . . . . . . . . . . . . . . . . . 309 12.2.1 El coste temporal medido en función de los tiempos de las operaciones elementales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 12.2.2 El coste como una función del tamaño del problema. Talla del problema . 312 12.2.3 Paso de programa. El coste temporal definido por conteo de pasos . . . . . 313

12.3 Complejidad asintótica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 12.3.1 Comparación de los costes de los algoritmos . . . . . . . . . . . . . . . . . . . 316 12.3.2 Introducción a la notación asintótica . . . . . . . . . . . . . . . . . . . . . . . 319 12.3.3 Algunas propiedades de los conjuntos Θ, O y Ω . . . . . . . . . . . . . . . . 321 12.3.4 La jerarquía de complejidades . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 12.3.5 Uso de la notación asintótica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323

12.4 Análisis por casos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324 12.4.1 Caso mejor, caso peor y coste promedio . . . . . . . . . . . . . . . . . . . . . 324

XI

Índice general

12.4.2 Ejemplos: algoritmos de recorrido y búsqueda. . . . . . . . . . . . . . . . . . 325

12.5 Análisis del coste de los algoritmos. . . . . . . . . . . . . . . . . . . . . . . . . . . 326 12.6 Análisis del coste de los algoritmos iterativos . . . . . . . . . . . . . . . . . . . . 327 12.6.1 Otra unidad de medida temporal: la instrucción crítica . . . . . . . . . . . . 327 12.6.2 Eficiencia de los algoritmos de recorrido . . . . . . . . . . . . . . . . . . . . . 327 12.6.3 Eficiencia de los algoritmos de búsqueda secuencial . . . . . . . . . . . . . . 328 12.6.4 Estudio del coste promedio del algoritmo de búsqueda secuencial . . . . . . 330

12.7 Análisis del coste de los algoritmos recursivos . . . . . . . . . . . . . . . . . . . 330 12.7.1 Planteamiento de la función de coste. Ecuaciones de recurrencia . . . . . . 331 12.7.2 Resolución de las ecuaciones de recurrencia. Teoremas . . . . . . . . . . . . 334 12.7.3 Coste espacial de la recursividad . . . . . . . . . . . . . . . . . . . . . . . . . . 338

12.8 Complejidad de algunos algoritmos numéricos recursivos . . . . . . . . . . . . 339 12.8.1 La multiplicación de números naturales. . . . . . . . . . . . . . . . . . . . . . 339 12.8.2 Exponenciación modular. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343

12.9 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

13 Ordenación y otros algoritmos sobre arrays

353

13.1 Selección directa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 13.2 Inserción directa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 13.3 Intercambio directo o algoritmo de la burbuja . . . . . . . . . . . . . . . . . . . 359 13.4 Ordenación por mezcla o mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . 361 13.5 Otros algoritmos sobre arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 13.5.1 El algoritmo de mezcla natural . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 13.5.2 El algoritmo de búsqueda binaria . . . . . . . . . . . . . . . . . . . . . . . . . 367

13.6 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371

14 Extensión del comportamiento de una clase. Herencia

375

14.1 Jerarquía de clases. Clases base y derivadas. . . . . . . . . . . . . . . . . . . . . 376 14.2 Diseño de clases base y derivadas: extends, protected y super . . . . . . . 378 14.3 Uso de una jerarquía de clases. Polimorfismo . . . . . . . . . . . . . . . . . . . . 384 14.3.1 Tipos estáticos y dinámicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386 14.3.2 Ejemplo de uso del polimorfismo . . . . . . . . . . . . . . . . . . . . . . . . . . 387

14.4 Más herencia en Java: control de la sobrescritura . . . . . . . . . . . . . . . . . 393 14.4.1 Métodos y clases finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393

XII

Índice general

14.4.2 Métodos y clases abstractos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394 14.4.3 Interfaces y herencia múltiple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396

14.5 Organización de las clases en Java . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 14.5.1 La librería de clases del Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 14.5.2 Uso de packages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399

14.6 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

15 Tratamiento de errores

407

15.1 Fallos de ejecución y su modelo Java . . . . . . . . . . . . . . . . . . . . . . . . . 408 15.1.1 La jerarquía Throwable. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 15.1.2 Ampliación de la jerarquía Throwable con excepciones de usuario. . . . . . 414

15.2 Tratamiento de excepciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415 15.2.1 Captura de excepciones: try/catch/finally . . . . . . . . . . . . . . . . . . 416 15.2.2 Propagación de excepciones: throw versus throws . . . . . . . . . . . . . . . 419 15.2.3 Excepciones checked/unchecked . . . . . . . . . . . . . . . . . . . . . . . . . . 422

15.3 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423

16 Entrada y salida: ficheros y flujos

429

16.1 La clase File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431 16.2 Ficheros de texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434 16.2.1 Escritura en un fichero de texto . . . . . . . . . . . . . . . . . . . . . . . . . . 434 16.2.2 Lectura de un fichero de texto . . . . . . . . . . . . . . . . . . . . . . . . . . . 435

16.3 Ficheros binarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440 16.3.1 Escritura en un fichero binario . . . . . . . . . . . . . . . . . . . . . . . . . . . 440 16.3.2 Lectura de un fichero binario

. . . . . . . . . . . . . . . . . . . . . . . . . . . 441

16.3.3 Ficheros binarios de acceso aleatorio . . . . . . . . . . . . . . . . . . . . . . . 444

16.4 Otros tipos de flujos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 16.4.1 Flujos de bytes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 16.4.2 Flujos de caracteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449

16.5 E/S de objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 16.6 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459

XIII

Índice general

17 Tipos lineales. Estructuras enlazadas

467

17.1 Representación enlazada de secuencias . . . . . . . . . . . . . . . . . . . . . . . . 468 17.1.1 Definición recursiva de secuencias. La clase Nodo . . . . . . . . . . . . . . . . 468 17.1.2 Recorrido y búsqueda en secuencias enlazadas . . . . . . . . . . . . . . . . . 474 17.1.3 Inserción y borrado en secuencias enlazadas . . . . . . . . . . . . . . . . . . . 477

17.2 Tipos lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486 17.2.1 Pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486 17.2.2 Colas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492 17.2.3 Listas con punto de interés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499

17.3 Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512

Bibliografía

517

Índice de Figuras

521

Índice de Tablas

529

Contenidos complementarios (ejercicios, etc.)

http://users.dsic.upv.es/pubdocente/LibroIIPPRG/

XIV