PDF de programación - Algoritmos y Estructuras de Datos: Introducción

Algoritmos y Estructuras de Datos:

Introducción

Guillermo Román Díez

groman@fi.upm.es

Universidad Politécnica de Madrid

Curso 2015-2016

Guillermo Román, UPM

AED: Introducción

1/42

Repaso Conceptos de Programación en Java

Expresiones, constantes, métodos, comandos, . . .

Variables, declaración e inicialización, . . .

Bloques de código, flujo de control, condiciones, bucles, . . .
Objetos, new, campos, herencia, interfaces, . . .
Tipos básicos, operadores aritméticos, operadores lógicos, . . .

Arrays, declaración y acceso mediante índices, . . .
Excepciones, try-catch-finally, . . .

Guillermo Román, UPM

AED: Introducción

2/42

Asignación y variables

Las variables tienen un tipo y un ámbito
Declaración de variables:

Atributos de clase → Visibles en toda la clase (o más. . . )
Parámetros de los métodos → Visibles en todo el método
Las variables locales → Visibles en su ámbito

Inicialización por defecto

Si son de tipo primitivo → 0, 0.0, ’\0’
Si son de tipo referencia → null

Asignación de variables: l-value vs r-value

int x , y ;
y = 7;
x = y = 3;
// Valor de x e y ?
while (( x = y /2) != 0) {...}

Guillermo Román, UPM

AED: Introducción

3/42

EJERCICIO: Asignaciones

1 public static void main ( String [] args ) {
2

int v1 = 3;
int v2 = 5;
int v3 ;

3

4

5

6

7

8

9

10
11 }

Ejercicio

v3 = v1 ;
v1 = v2 ;
v3 = v1 = 6;
v3 = 6 = v5 ;
v3 = 7;

// Error

¿cuáles son los valores de las variables después de ejecutar cada punto de
programa?

Guillermo Román, UPM

AED: Introducción

4/42

Ámbito de las variables

Java tiene sus reglas de visibilidad establecidas

Otros lenguajes pueden tener sus propias reglas de visibilidad
Puede ocurrir shadowing: Si hay dos variables que se llaman
igual una puede ocultar a la otra

public class C {

int x ;
public C ( int x ) { x = x ; } // ??
public void m1 ( int x ) {

for ( int x = 1; x < 10; x ++) // ??

x ++;

if ( x < 0) {

int x = 1; // ??
this . x = x ; // ??

}

}
public void m2 ( int c ) { x = c ; } // ??

}

Guillermo Román, UPM

AED: Introducción

5/42

Paso de Parámetros por Valor

Un ejemplo de código para intercambiar dos variables:

int x = 5;
int y = 4;
// codigo del i n t e r c a m b i o (" s w a p p i n g ")
int tmp = x ;
x = y ;
y = tmp ;

Pregunta

¿Podemos hacer esto llamando a un método que reciba x e y como
parámetros?

Guillermo Román, UPM

AED: Introducción

6/42

Paso de Parámetros por Valor

public static void swap ( int a , int b ) {

int tmp = a ;
a = b ;
b = tmp ;

}

public static void main ( String [] args ) {

int x = 5;
int y = 7;
swap (x , y ) ;
System . out . println ( x + ” ” + y ) ;

}

Pregunta

¿Qué saldrá por pantalla?

Guillermo Román, UPM

AED: Introducción

7/42

Ejercicio Variables

Ejercicio

Dibujar las variables durante la ejecución

public static void main ( String [] args ) {

int a = 3;
int b = 3;
a = 2;

int c = 3;
int d = c ;
c = 2;

int e = 3;
e = 2;
int d = e ;

}

Guillermo Román, UPM

AED: Introducción

8/42

Evaluación de expresiones

Java evalúa las expresiones en cortocircuito
Si tenemos un && corta en el momento en el que no se cumpla
una condición → evalúa a false

v != null && v [ i ] == 0

Si tenemos un || corta en el momento en el que se cumpla
una condición → evalúa a true

v == null || v [ i ] == 0

Guillermo Román, UPM

AED: Introducción

9/42

Arrays (vectores)

Podemos declarar arrays de cualquier tipo

Tipos primitivos (int, double, char)
Como referencias (objetos, interfaces, clases abstractas, arrays)

La declaración de la variable no establece el tamaño
Es necesario inicializar el tamaño antes de utilizarlo

En caso contrario NullPointerException

El rango de elementos de un array es [0..longitud-1]
Si accedemos a una posición negativa o mayor que el tamaño
del array → ArrayIndexOutOfBoundsException

Guillermo Román, UPM

AED: Introducción

10/42

Ejemplos Arrays

int [] a ;
a [0] = 4;

int [] a2 = null ;
a [2] = 10;

int [] b = new int [20];
b [0] = 7;
int [] c = new int [ g e t I n t e g e r F r o m U s e r () ];

String [] d = new String [10];
d [0] = new String ( ” H o l a ” ) ;

int [] e = new int [0];
int [] f = { };
int [] g = { 7 , 9 , 8 };

Clase [] h = new Sub Cla se [5];

Guillermo Román, UPM

AED: Introducción

11/42

Paso de Parámetros por Referencia

public static void swap ( int array []) {

int tmp = array [0];
array [0] = array [1];
array [1] = tmp ;

}

public static void main ( String [] args ) {

int array [] = {3 ,4};
swap ( array ) ;
System . out . println ( array [0] + ” ” + array [1]) ;

}

Pregunta

¿Qué saldrá por pantalla?

Guillermo Román, UPM

AED: Introducción

12/42

Bucles

Bucle while

INIT
while ( COND )

BODY

Bucle do-while

do

BODY

while ( COND )

Bucle for

for ( INIT ; COND ; POST )

BODY

Guillermo Román, UPM

AED: Introducción

13/42

Equivalencia Bucles

Equivalencia while - do-while

BODY
while ( COND ) {

BODY

}

do {

BODY

}
while ( COND )

Equivalencia while - for

for ( INIT ; COND ; POST ) {

BODY

}

INIT
while ( COND ) {

BODY
POST

}

Guillermo Román, UPM

AED: Introducción

14/42

Recorrido de Arrays

Ejercicio

Recorrer un Array con un bucle while

Guillermo Román, UPM

AED: Introducción

15/42

Recorrido de Arrays

Ejercicio

Recorrer un Array con un bucle while

int i = 0;
while ( i < array . length ) {

System . out . println ( ” P o s i c i o n ” + array [ i ]) ;

}

Guillermo Román, UPM

AED: Introducción

15/42

Recorrido de Arrays

Ejercicio

Recorrer un Array con un bucle while

int i = 0;
while ( i < array . length ) {

System . out . println ( ” P o s i c i o n ” + array [ i ]) ;

}

Ejercicio

Recorrer un Array con un bucle for

Guillermo Román, UPM

AED: Introducción

15/42

Recorrido de Arrays

Ejercicio

Recorrer un Array con un bucle while

int i = 0;
while ( i < array . length ) {

System . out . println ( ” P o s i c i o n ” + array [ i ]) ;

}

Ejercicio

Recorrer un Array con un bucle for

for ( int i = 0; i < array . length ; i ++) {

System . out . println ( ” P o s i c i o n ” + array [ i ]) ;

}

Guillermo Román, UPM

AED: Introducción

15/42

Busqueda en un Array

Ejercicio

¿Cómo podemos buscar el elemento ’*’ en un array?

Guillermo Román, UPM

AED: Introducción

16/42

Busqueda en un Array

Ejercicio

¿Cómo podemos buscar el elemento ’*’ en un array?

int i = 0;
while ( i < v . length && v [ i ] != ’∗ ’ ) {

i ++;

}
return i < v . length ;

Guillermo Román, UPM

AED: Introducción

16/42

Salida de los bucles

No es aconsejable salir de los bucles con break o return
Tampoco es aconsejable el uso de continue
Complica la comprensión y mantenimiento del código

Hay que razonar sobre todo el bucle y no sólo sobre la
condición

No se respeta la invariante de bucle

Guillermo Román, UPM

AED: Introducción

17/42

Clases, objetos y variables

Las clases definen los atributos y métodos que tendrán los
objetos de la clase

Ejemplo

Ver el código de la clase Vehiculo

Los objetos se crean en tiempo de ejecución con new
Cuando se declara una variable de tipo clase o interfaz se
inicializa a null
Si se intenta usar ese objeto → NullPointerException
Es necesario hacer un new o utilizar una asignación a un objeto
creado previamente

Las variables de tipo clase o interfaz referencian a objetos
Se pueden cambiar el objeto al que referencia una variable
El recolector de basura (garbage collector ) eliminará los
objetos que no son referenciados

Guillermo Román, UPM

AED: Introducción

18/42

Ejercicio objetos

Ejercicio

Dibujar los objetos y las referencias de las variables

A u t o m o v i l v1 = new A u t o m o v i l (10 ,10 ,10) ;
A u t o m o v i l v2 = new A u t o m o v i l (20 ,20 ,20) ;
A u t o m o v i l v3 ;

v3 = v1 ;
v1 = v2 ;
v3 = new A u t o m o v i l (30 ,30 ,30) ;
v2 = null ;

Pregunta

¿Liberará el Garbage Collector (recolector de basura) algún objeto?

Guillermo Román, UPM

AED: Introducción

19/42

Identidad vs. estado de un objeto

La identidad de un objeto es la dirección de memoria en la
que está el objeto
El estado de un objeto son los valores que tienen los
atributos de un objeto
Las comparaciones son diferentes

Para comparar la identidad comparamos con ==
Para comparar el estado utilizamos el método equals

Guillermo Román, UPM

AED: Introducción

20/42

Identidad vs. estado de un objeto

La identidad de un objeto es la dirección de memoria en la
que está el objeto
El estado de un objeto son los valores que tienen los
atributos de un objeto
Las comparaciones son diferentes

Para comparar la identidad comparamos con ==
Para comparar el estado utilizamos el método equals

A u o t o m o v i l v1 = new A u o t o m o v i l (10 ,10 ,10) ;
Ve hic ulo v2 = v1 ;
System . out . println ( v1 . equals ( v2 ) )
System . out . println ( v1 == v2 )

// cierto
// cierto

v2 = new A u o t o m o v i l (10 ,10 ,10) ;
System . out . println ( v1 . equals ( v2 ) )
System . out . println ( v1 == v2 )

// cierto
// falso

Guillermo Román, UPM

AED: Introducción

20/42

Tipos básicos y clases envoltorio

Los tipos básicos se comportan de forma diferente a los
objetos
Las comparaciones de tipos básicos siempre son con ==
Hay unas clases envoltorio que se comportan como clases y
como tipos básicos

Integer, Double, Float, . . .
Se pueden comparar con ==, pero mucho cuidado!! Mejor usar
equals
Se pueden crear objetos asignando directamente valores (sin
hacer new)

Ejemplo

Ver código TestEnvoltorio

Guillermo Román, UPM

AED: Introducción

21/42

Herencia: relación “es-un”

Un objeto de clase Automovil también es-un objeto de la
clase Vehiculo

public class V ehi cul o { ... }
public class A u t o m o v i l extends V ehi cul o { ... }

Vehiculo

Automovil

La clase Automovil hace más específico el Vehiculo con
nuevos atributos y métodos (o sobrescribiendo)

Guillermo Román, UPM

AED: Introducción

22/42

Herencia: Utilidad

La herencia permite reutilizar código

Un Au