(PDF) Algoritmos y estructura de datos : implementaciones en Java / F ...

Universidad de Murcia Depto. Ingenier´ıa de la Informaci´on y las Comunicaciones

Texto-Gu´ıa

ALGORITMOS Y ESTRUCTURA DE DATOS. IMPLEMENTACIONES EN JAVA Fernando Jim´enez Barrionuevo Gracia S´anchez Carpena 9 de abril de 2002

´Indice General

Pr´ ologo

I

11

Las asignaturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

Evaluaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

Organizaci´on del texto-gu´ıa . . . . . . . . . . . . . . . . . . . . . . . . . .

16

Algoritmos y Estructura de Datos

1 Tipos de Datos Abstractos y Programaci´ on Orientada a Objetos

19 21

Contenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

A. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

B. Desarrollo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

1.1

Concepto de Tipo de Datos Abstracto

. . . . . . . . . . . . . . . . .

22

1.2

Clasificaci´on de Tipos de Datos Abstractos . . . . . . . . . . . . . . .

25

1.3

Especificaci´on de Tipos de Datos Abstractos . . . . . . . . . . . . . .

25

1.3.1

Especificaciones informales . . . . . . . . . . . . . . . . . . . .

27

1.3.2

Especificaciones formales . . . . . . . . . . . . . . . . . . . . .

29

Programaci´on Orientada a Objetos . . . . . . . . . . . . . . . . . . .

33

1.4.1

Clases y Objetos . . . . . . . . . . . . . . . . . . . . . . . . .

33

1.4.2

Propiedades y M´etodos . . . . . . . . . . . . . . . . . . . . . .

35

1.4.3

Herencia y Polimorfismo . . . . . . . . . . . . . . . . . . . . .

38

1.4.4

Pautas generales en dise˜ no orientado a objetos . . . . . . . . .

41

1.4.5

T´ecnicas de implementaci´on . . . . . . . . . . . . . . . . . . .

41

1.4.6

Utilizaci´on correcta de objetos . . . . . . . . . . . . . . . . . .

47

C. Aplicaci´on de los conocimientos . . . . . . . . . . . . . . . . . . . . . .

55

D. Desarrollo de las pr´acticas . . . . . . . . . . . . . . . . . . . . . . . . .

59

1.4

´ INDICE GENERAL

4 1.5

Entorno de Programaci´on VisualCaf´e . . . . . . . . . . . . . . . . . .

59

1.5.1

Hola Mundo . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

Clases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

1.6.1

Utilizaci´on de clases . . . . . . . . . . . . . . . . . . . . . . .

61

1.6.2

Creaci´on de Clases . . . . . . . . . . . . . . . . . . . . . . . .

63

1.6.3

Documentaci´on correcta de nuestras clases . . . . . . . . . . .

68

E. Evaluaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

F. Notas Bibliogr´aficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

1.6

2 Listas

85

Contenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

A. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

B. Desarrollo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

2.1

Descripci´on del TDA Lista . . . . . . . . . . . . . . . . . . . . . . . .

86

2.2

Especificaci´on del TDA Lista

. . . . . . . . . . . . . . . . . . . . . .

89

2.3

Ejemplos de uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

2.4

Implementaciones del TDA Lista . . . . . . . . . . . . . . . . . . . .

96

2.4.1

Representaciones contiguas . . . . . . . . . . . . . . . . . . . .

97

2.4.2

Representaciones enlazadas . . . . . . . . . . . . . . . . . . . 103

2.4.3

Comparaci´on de las implementaciones . . . . . . . . . . . . . . 118

2.5

Otras alternativas en la definici´on del TDA Lista . . . . . . . . . . . 120

2.6

Modalidades de listas . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

C. Aplicaci´on de los conocimientos . . . . . . . . . . . . . . . . . . . . . . 126 D. Desarrollo de las pr´acticas . . . . . . . . . . . . . . . . . . . . . . . . . 129 2.7

Paquetes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 2.7.1

Creaci´on de paquetes . . . . . . . . . . . . . . . . . . . . . . . 129

2.7.2

Utilizaci´on de paquetes . . . . . . . . . . . . . . . . . . . . . . 135

E. Evaluaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 F. Notas Bibliogr´aficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 3 Colas

145

Contenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

Algoritmos y Estructura de Datos. Implementaciones en Java

´ INDICE GENERAL

5

A. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 B. Desarrollo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 3.1

Descripci´on del TDA Cola . . . . . . . . . . . . . . . . . . . . . . . . 146

3.2

Especificaci´on del TDA Cola . . . . . . . . . . . . . . . . . . . . . . . 147

3.3

Ejemplos de uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

3.4

Implementaciones del TDA Cola . . . . . . . . . . . . . . . . . . . . . 152

3.5

3.4.1

Implementaci´on basada en el TDA Lista . . . . . . . . . . . . 152

3.4.2

Implementaci´on con vectores circulares . . . . . . . . . . . . . 153

3.4.3

Implementaci´on con apuntadores . . . . . . . . . . . . . . . . 156

3.4.4

Comparaci´on de las implementaciones . . . . . . . . . . . . . . 157

Modalidades de colas . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 3.5.1

Dicolas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

3.5.2

Colas de Prioridad . . . . . . . . . . . . . . . . . . . . . . . . 158

C. Aplicaci´on de los conocimientos . . . . . . . . . . . . . . . . . . . . . . 161 D. Desarrollo de las pr´acticas . . . . . . . . . . . . . . . . . . . . . . . . . 164 3.6

M´etodo de ordenaci´on Radix . . . . . . . . . . . . . . . . . . . . . . . 164

E. Evaluaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 F. Notas Bibliogr´aficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 4 Pilas

167

Contenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 A. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 B. Desarrollo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 4.1

Descripci´on de TDA Pila . . . . . . . . . . . . . . . . . . . . . . . . . 168

4.2

Especificaci´on del TDA Pila . . . . . . . . . . . . . . . . . . . . . . . 169

4.3

Ejemplos de uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171

4.4

Implementaciones del TDA Pila . . . . . . . . . . . . . . . . . . . . . 173 4.4.1

Implementaci´on basada en el TDA Lista . . . . . . . . . . . . 173

4.4.2

Implementaci´on con vectores . . . . . . . . . . . . . . . . . . . 175

4.4.3

Implementaci´on con apuntadores . . . . . . . . . . . . . . . . 177

4.4.4

Comparaci´on de las implementaciones . . . . . . . . . . . . . . 178

C. Aplicaci´on de los conocimientos . . . . . . . . . . . . . . . . . . . . . . 179

Algoritmos y Estructura de Datos. Implementaciones en Java

´ INDICE GENERAL

6

D. Desarrollo de las pr´acticas . . . . . . . . . . . . . . . . . . . . . . . . . 181 4.5

Problema de las Torres de Hanoi . . . . . . . . . . . . . . . . . . . . 181

E. Evaluaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 F. Notas Bibliogr´aficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 ´ 5 Arboles

185

Contenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 A. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 B. Desarrollo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 5.1 5.2 5.3 5.4

Descripci´on y terminolog´ıa fundamental . . . . . ´ Especificaci´on del TDA Arbol . . . . . . . . . . . ´ Ejemplos de uso del TDA Arbol . . . . . . . . . . ´ Implementaciones del TDA Arbol . . . . . . . . .

. . . . . . . . . . . 186 . . . . . . . . . . . 187 . . . . . . . . . . . 192 . . . . . . . . . . . 194

5.8

´ Especificaci´on del TDA Arbol Binario . . . . . . . . . ´ Ejemplos de uso del TDA Arbol Binario . . . . . . . ´ Implementaciones del TDA Arbol Binario . . . . . . ´ Arboles Parcialmente Ordenados: Colas de Prioridad

5.9

´ Arboles Binarios de B´ usqueda . . . . . . . . . . . . . . . . . . . . . . 214

5.5 5.6 5.7

. . . . . . . . . 199 . . . . . . . . . 203 . . . . . . . . . 205 . . . . . . . . . 209

C. Aplicaci´on de los conocimientos . . . . . . . . . . . . . . . . . . . . . . 220 D. Desarrollo de las pr´acticas . . . . . . . . . . . . . . . . . . . . . . . . . 222 5.10 N´ umero de hojas de un ´arbol. . . . . . . . . . . . . . . . . . . . . . . 222 5.11 N´ umero de hojas de un ´arbol binario. . . . . . . . . . . . . . . . . . . 222 E. Evaluaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 F. Notas Bibliogr´aficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 6 M´ etodos de Clasificaci´ on

225

Contenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 A. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 B. Desarrollo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 6.1

El M´etodo de Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

6.2

Clasificaci´on R´apida . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

6.3

Clasificaci´on por Mezcla . . . . . . . . . . . . . . . . . . . . . . . . . 232

Algoritmos y Estructura de Datos. Implementaciones en Java

´ INDICE GENERAL

6.4

7

Clasificaci´on por Mont´ıculos . . . . . . . . . . . . . . . . . . . . . . . 235

C. Aplicaci´on de los conocimientos . . . . . . . . . . . . . . . . . . . . . . 237 D. Desarrollo de las pr´acticas . . . . . . . . . . . . . . . . . . . . . . . . . 240 6.5

Problema de la b´ usqueda de la mediana

. . . . . . . . . . . . . . . . 240

E. Evaluaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 F. Notas Bibliogr´aficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

II

Laboratorio de Programaci´ on

7 Desarrollo, evaluaci´ on y prueba de programas en Java

245 247

Contenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 A. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 B. Desarrollo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 7.1

Algoritmos Voraces: Camino m´ınimo entre un nodo inicial y el resto de nodos de un grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . 248

7.2

Divide y Vencer´as: Problema de la b´ usqueda de la mediana . . . . . . 250

7.3

Evaluaci´on y Prueba: M´etodo de ordenaci´on Radix . . . . . . . . . . 251

7.4

Programaci´on Din´amica: Camino m´ınimo entre todo par de nodos de un grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

7.5

Algoritmos Probabilistas: El problema del viajante de comercio mediante algoritmos evolutivos . . . . . . . . . . . . . . . . . . . . . . . . 256

C. Normas de presentaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 D. Notas Bibliogr´aficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 A Introducci´ on a Java

261

A.1 Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 A.2 Tipos de Datos Primitivos . . . . . . . . . . . . . . . . . . . . . . . . 261 A.2.1 Tipos Primitivos . . . . . . . . . . . . . . . . . . . . . . . . . 261 A.2.2

Declaraci´on de variables

A.2.3

Declaraci´on de constantes

. . . . . . . . . . . . . . . . . . . . 263 . . . . . . . . . . . . . . . . . . . 264

A.2.4 Conversiones de tipos . . . . . . . . . . . . . . . . . . . . . . . 264 A.3 Clases y Objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

Algoritmos y Estructura de Datos. Implementaciones en Java

´ INDICE GENERAL

8 A.3.1

El uso de paquetes . . . . . . . . . . . . . . . . . . . . . . . . 265

A.3.2 Declaraci´on de clases . . . . . . . . . . . . . . . . . . . . . . . 266 A.3.3 Declaraci´on de objetos . . . . . . . . . . . . . . . . . . . . . . 266 A.3.4 Declaraci´on de campos . . . . . . . . . . . . . . . . . . . . . . 267 A.3.5 Acceso a campos . . . . . . . . . . . . . . . . . . . . . . . . . 268 A.3.6 Declaraci´on de m´etodos . . . . . . . . . . . . . . . . . . . . . 268 A.3.7 Llamadas a m´etodos . . . . . . . . . . . . . . . . . . . . . . . 269 A.3.8 Declaraci´on de m´etodos constructores . . . . . . . . . . . . . . 270 A.3.9 Llamadas a m´etodos constructores . . . . . . . . . . . . . . . 270 A.3.10 Modelo de un Programa . . . . . . . . . . . . . . . . . . . . . 271 A.3.11 Herencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 A.3.12 Propiedades de los objetos . . . . . . . . . . . . . . . . . . . . 275 A.3.13 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 A.4 Control del flujo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 A.4.1 Selecci´on con if-else . . . . . . . . . . . . . . . . . . . . . . 278 A.4.2 Sucesivos else-if . . . . . . . . . . . . . . . . . . . . . . . . . . 279 A.4.3 La instrucci´on switch . . . . . . . . . . . . . . . . . . . . . . 279 A.4.4 Repetici´on con bucles for . . . . . . . . . . . . . . . . . . . . 281 A.4.5 Bucles for indeterminados . . . . . . . . . . . . . . . . . . . . 282 A.4.6 Bucles condicionales while . . . . . . . . . . . . . . . . . . . . 282 A.4.7 Bucles condicionales do while . . . . . . . . . . . . . . . . . . 283 A.5 Entrada y Salida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 A.5.1 Cadenas de caracteres: La clase String . . . . . . . . . . . . . 284 A.5.2 Salida por pantalla . . . . . . . . . . . . . . . . . . . . . . . . 285 A.5.3 Entrada desde teclado . . . . . . . . . . . . . . . . . . . . . . 286 A.5.4 Entrada desde archivos . . . . . . . . . . . . . . . . . . . . . . 287 A.5.5 Salida a archivos . . . . . . . . . . . . . . . . . . . . . . . . . 287 A.6 Excepciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 A.6.1 Detecci´on y manejo de excepciones . . . . . . . . . . . . . . . 287 A.6.2 Excepciones definidas por el usuario . . . . . . . . . . . . . . . 288 Bibliograf´ıa

289

Algoritmos y Estructura de Datos. Implementaciones en Java

´ INDICE GENERAL

9

´Indice de Figuras

293

´Indice de Tablas

295

´Indice de T´ erminos

297

Algoritmos y Estructura de Datos. Implementaciones en Java

Pr´ ologo Podr´ıamos decir que la Programaci´ on de Ordenadores es la parte pr´actica de la Algoritmia, ciencia ´esta con un car´acter notablemente te´orico que consiste b´asicamente en el an´alisis y dise˜ no de algoritmos as´ı como en el estudio de las estructuras de datos sobre las que recaen los algoritmos. Ya que las asignaturas que pretendemos cubrir con el texto-gu´ıa recogen aspectos tanto te´oricos (Algoritmos y Estructura de Datos) como pr´acticos (Algoritmos y Estructura de Datos, y Laboratorio de Programaci´ on) esto nos lleva a una obligada integraci´on, en ning´ un caso obvia, de los aspectos te´oricos y pr´acticos de ambos campos, el de la Algoritmia y el de la Programaci´on. Para llevar a cabo tal integraci´on debemos tener en cuenta los siguientes aspectos: 1. Los descriptores BOE impuestos por el Consejo de Universidades para las materias troncales as´ı como los establecidos por la Universidad de Murcia para las materias obligatorias. 2. La orientaci´on apropiada para impartir los contenidos. 3. La elecci´on del Lenguaje de Programaci´on. 4. La Metodolog´ıa Docente. 5. El entorno ingenieril en el que se llevan a cabo los estudios. 6. El ambiente socio-acad´emico en el que se encuentran los potenciales ingenieros. Los descriptores BOE para la asignatura troncal Algoritmos y Estructura de Datos son Tipos abstractos de datos, y estructuras de datos y algoritmos de manipulaci´ on, y los establecidos por la universidad para la materia obligatoria Laboratorio de Programaci´on son Desarrollo, evaluaci´on y prueba de programas en lenguajes de alto nivel. Estos descriptores, junto con una experiencia docente de diez a˜ nos impartiendo estas materias o similares en otras titulaciones, nos dan una aproximaci´on de c´omo deben orientarse ambas asignaturas. As´ı pues, el concepto de Tipo de Datos Abstracto

´ PROLOGO

12

debe estar presente a la hora de orientar los contenidos de estas asignaturas, por las propiedades deseables que ofrece en la construcci´on de software tales como modularidad, reusabilidad, legibilidad y, por supuesto, la reducci´on de la complejidad (mental) en el dise˜ no y an´alisis de algoritmos, as´ı como en la correcci´on (verificaci´on formal), evaluaci´on y prueba de programas. La elecci´on del Lenguaje de Programaci´on adecuado es un punto de vital importancia, y debe hacerse teniendo en cuenta que las asignaturas se desarrollan en un marco ingenieril y que debe posibilitar una integraci´on r´apida y segura del alumno en su ambiente socio-acad´emico. Estos requerimientos junto con, de nuevo, nuestra experiencia docente, nos llevan a pensar en Java como un apropiado Lenguaje de Programaci´on. Java es un lenguaje orientado a objetos, lo que permite un f´acil dise˜ no de programas bas´andose en el concepto de Tipo de Datos Abstracto, y adem´as es un lenguaje multi-plataforma con reconocidas propiedades que permiten el desarrollo de programas para su integraci´on en Internet, lo que lo hace id´oneo para la formaci´on y capacitaci´on del alumno en los tiempos que corremos, ya que es en el ´ambito de las telecomunicaciones donde las nuevas tecnolog´ıas est´an cada vez m´as presentes. Resulta dif´ıcil encontrar textos en castellano que re´ unan todas las caracter´ısticas que hemos mencionado. Normalmente los libros en este campo son, o bien de Programaci´on en Java, dedic´andose fundamentalmente a los aspectos del lenguaje, o bien de Algoritmia, tratando en este caso aspectos te´oricos sin considerar un lenguaje de programaci´on comercial. El libro de texto: Weiss, M.A. (2000). Estructuras de Datos en Java. Addison-Wesley es quiz´as el que mejor re´ une las caracter´ısticas que aqu´ı hemos indicado, si bien deja en el aire algunos aspectos te´oricos que rondan alrededor del concepto de Tipo de Datos Abstracto. Por otra parte, resulta interesante integrar en el propio texto una gu´ıa de un entorno de programaci´on Java que, en nuestro caso, se ha elegido el Visual Caf´e. As´ı pues, la posibilidad de que el alumno disponga de un texto-gu´ıa que integre todas estas caracter´ısticas resulta de vital importancia, teniendo en cuenta tambi´en que es apropiado de cara a una correcta metodolog´ıa docente para impartir los contenidos de la asignatura, posibilitando de una forma m´as sencilla la preparaci´on de las clases y su seguimiento por parte del alumno. De esta forma, nuestro texto-gu´ıa, lejos de querer ser un manual de programaci´on, est´a concebido fundamentalmente para ense˜ nar, de una parte, cu´ales son los Algoritmos y Estructura de Datos. Implementaciones en Java

´ PROLOGO

13

principios sobre los que descansa el an´alisis y dise˜ no de algoritmos y, de otra, las estructuras de datos, ya que normalmente los algoritmos act´ uan sobre estructuras de datos concretas, y la elecci´on de ´estas tendr´a repercusiones en la eficiencia y en el buen dise˜ no de los algoritmos. Por otro lado, se pretende dar al alumno las herramientas b´asicas necesarias para poder llegar a desarrollar sus propios algoritmos y programas, cualquiera que sea el campo de aplicaci´on. Este objetivo, en cualquier caso, tendr´a que complementarse con otros de tipo socio-acad´emico que afectan a las competencias que tiene la Universidad como servicio p´ ublico y como entidad din´amica depositaria de conocimiento e id´onea para la transmisi´on y difusi´on del mismo. Destacamos, por tanto, como m´as notables, dos aspectos fundamentales como objetivos de la ense˜ nanza: 1. Conseguir una s´olida formaci´on te´orico-pr´actica. Es necesario que los alumnos comprendan que el trabajo te´orico, cuando se ha constrastado suficientemente, debe poder plasmarse de alguna forma en realizaciones que vengan a resolver problemas de la vida diaria. Por otro lado, tampoco hay que inclinar excesivamente la balanza hacia el lado de las aplicaciones, puesto que ´estas no son posibles sin unos rigurosos fundamentos. Nos marcamos como objetivo, por tanto, el conseguir una formaci´on equilibrada entre estas dos vertientes para conseguir, en definitiva, un perfil lo m´as integral posible que est´e, adem´as, en sinton´ıa con el entorno socio-acad´emico en el que nos desenvolvemos. 2. Proporcionar una suficiente capacitaci´on profesional. Hay que tener en cuenta que la gran parte de los alumnos que terminen sus estudios correspondientes ir´an a instalarse en empresas en las que se les exigir´a una elevada cualificaci´on profesional como ingenieros. Debemos proporcionar por tanto, junto con las ense˜ nanzas de tipo acad´emico, a las que venimos aludiendo, otras que preparen al alumno como potencial competidor en el mercado de trabajo. Hemos marcado, por consiguiente, tres objetivos que son, por una parte, la ense˜ nanza de los fundamentos del an´alisis y dise˜ no de algoritmos (incluyendo las estructuras de datos) y. por otra, el proporcionar una formaci´on te´orico-pr´actica equilibrada y adecuada al entorno y que capacite profesionalmente.

Las asignaturas En los planes de estudios de la Ingenier´ıa Superior en Inform´atica de la Universidad de Murcia, la materia correspondiente a la que se dedica el presente texto-gu´ıa Algoritmos y Estructura de Datos. Implementaciones en Java

´ PROLOGO

14

aparece organizada en las asignaturas denominadas Algoritmos y Estructura de Datos y Laboratorio de Programaci´ on. La asignatura Algoritmos y Estructura de Datos se imparte en el primer curso (segundo trimestre), es troncal y consta de 6 cr´editos, de los cuales 3 son te´oricos y 3 pr´acticos. Los descriptores son los siguientes: • Tipos abstractos de datos. • Estructuras de datos y algoritmos de manipulaci´on. La asignatura Laboratorio de Programaci´on aparece en segundo curso (segundo trimestre), es obligatoria y consta de 6 cr´editos, todos ellos con car´acter pr´actico. Los descriptores son los siguientes: • Desarrollo, evaluaci´on y prueba de programas en lenguajes de alto nivel. Este texto-gu´ıa puede seguirse tambi´en como parte de la asignatura Fundamentos de Programaci´ on de primer curso (segundo cuatrimestre) de las Ingenier´ıas T´ecnicas en Inform´atica de Sistemas y Gesti´on de la Universidad de Murcia y, en general, en cualquier curso de programaci´on con el requisito de tener nociones b´asicas de algoritmia y programaci´on. Los objetivos generales que nos planteamos a la hora de impartir las asignaturas son los siguientes: • Entender la necesidad de la abstracci´on de datos en el dise˜ no de programas. • Estudiar mecanismos de especificaci´on, implementaci´on y uso de Tipos de Datos Abstractos. • Usar la Programaci´on Orientada a Objetos como herramienta para la implementaci´on de Tipos de Datos Abstractos. • Estudiar algunos de los Tipos de Datos Abstractos fundamentales (listas, pilas, colas y ´arboles) en sus aspectos de especificaci´on, implementaci´on, uso y eficiencia. • Utilizar un lenguaje de programaci´on de alto nivel orientado a objetos (Java) para el desarrollo, evaluaci´on y prueba de programas. Para cubrir los contenidos de la asignatura Algoritmos y Estructura de Datos se han incluido seis cap´ıtulos: Algoritmos y Estructura de Datos. Implementaciones en Java

´ PROLOGO

15

• Cap´ıtulo 1 (6 h. te´oricas, 3 h. pr´acticas): Introducci´on a los Tipos de Datos Abstractos, esenciales en programaci´on, present´andose las principales t´ecnicas de especificaci´on e implementaci´on en Java. • Cap´ıtulos 2-5 (21 h. te´oricas, 24 h. pr´acticas): Aplicaci´on de las t´ecnicas estudiadas para la especificaci´on, implementaci´on y uso de Tipos de Datos Abstractos fundamentales como son las listas, las colas, las pilas y los ´arboles. Estos cuatro cap´ıtulos se han organizado consecuentemente de forma similar, conteniendo para cada Tipo de Datos Abstracto: – una descripci´on general del Tipo de Datos Abstracto, – su especificaci´on, – diversas implementaciones y comparaci´on en t´erminos de eficiencia, – algunos ejemplos de uso, – modalidades para cada caso. • Cap´ıtulo 6 (3 h. te´oricas, 3 h. pr´acticas): Recoge algunas t´ecnicas de clasificaci´on importantes que permitir´an un mayor acercamiento a las t´ecnicas de an´alisis y dise˜ no de algoritmos y a las estructuras de datos. Para un curso completo de Algoritmos y Estructura de Datos, el texto debe continuarse con una profundizaci´on en ´arboles para el estudio de las diferentes modalidades de ´arboles balanceados, con la descripci´on de otros dos Tipos de Datos Abstractos fundamentales, los grafos y los conjuntos, con una intensificaci´on en an´alisis de algoritmos, con una descripci´on de las principales t´ecnicas de dise˜ no de algoritmos como son los algoritmos voraces, la t´ecnica divide y vencer´as, la programaci´on din´amica, los algoritmos de exploraci´on de grafos y, en su caso, los algoritmos probabilistas. La asignatura Laboratorio de Programaci´on est´a concebida como la parte pr´actica de estos contenidos e incluye tambi´en pr´acticas de evaluaci´on y prueba de programas.

Evaluaci´ on La calificaci´on final del alumno en las convocatorias de Diciembre, Junio o Septiembre ser´a de Matr´ıcula de Honor, Sobresaliente, Notable, Aprobado, Suspenso o No Presentado. Para superar la asignatura Algoritmos y Estructura de Datos ser´a necesario superar un examen te´orico-pr´actico, que se calificar´a con Matr´ıcula de Honor, Sobresaliente, Notable, Aprobado o Suspenso, y superar las pr´acticas de la asignatura, que Algoritmos y Estructura de Datos. Implementaciones en Java

´ PROLOGO

16

se calificar´an con Apto o No Apto. Si la calificaci´on de las pr´acticas es de Apto, entonces la calificaci´on final del alumno ser´a la obtenida en el ex´amen te´orico-pr´actico. Si la calificaci´on de las pr´acticas es de No Apto, o ´estas no han sido entregadas en la convocatoria vigente, entonces la calificaci´on final ser´a de Suspenso. Si el alumno supera las pr´acticas en una convocatoria, pero no el ex´amen te´orico-pr´actico, entonces la calificaci´on de las pr´acticas se conserva para las siguientes convocatorias, hasta la convocatoria de Diciembre, inclusive. No se conservan para siguientes convocatorias la calificaci´on obtenida en el ex´amen te´orico-pr´actico, teniendo ´este que realizarse en cada una de ellas. Se obtendr´a la calificaci´on de No Presentado en una convocatoria cuando el alumno no se presente al ex´amen te´orico-pr´actico. La evaluaci´on para la asignatura Laboratorio de Programaci´on se obtendr´a en base a las pr´acticas entregadas y al resultado de una entrevista personal.

Organizaci´ on del texto-gu´ıa El texto-gu´ıa se ha estructurado en dos partes: Algoritmos y Estructura de Datos, y Laboratorio de Programaci´on, en equivalencia a las asignaturas que cubren cada una de ellas. En la parte de Algoritmos y Estructura de Datos, y con el objeto de proporcionar al alumno los contenidos te´oricos de la materia, as´ı como una serie de herramientas con car´acter pr´actico que le permitan trabajar de forma c´omoda y organizada, los seis cap´ıtulos se han organizado de acuerdo a un esquema com´ un que se corresponde con la siguiente estructura: • Contenidos: Inmediatamente despu´es del ep´ıgrafe que contiene el t´ıtulo del cap´ıtulo, se detallan las secciones en las que se va a estructurar el desarrollo te´orico del mismo. • Objetivos: A continuaci´on se exponen los objetivos generales que nos hemos marcado a la hora de dise˜ nar el cap´ıtulo. Dichos objetivos exponen lo que se pretende que el alumno conozca cuando termine el estudio de ese tema. • Desarrollo: Los contenidos de cada cap´ıtulo se desarrollan en detalle, exponiendo las definiciones necesarias, los algoritmos correspondientes, algunos ejemplos ilustrativos, etc. • Aplicaci´ on de los conocimientos: Una vez explicada la teor´ıa de cada tema, se exponen una serie de ejercicios resueltos, con el fin de que el alumno se familiarize con el tipo de problemas que pueden plantearse en relaci´on con los contenidos te´oricos. Algoritmos y Estructura de Datos. Implementaciones en Java

´ PROLOGO

17

• Desarrollo de las pr´ acticas: En esta secci´on se proponen ejercicios, algunos de ellos resueltos, orientados a una aplicaci´on pr´actica de los contenidos del tema. Por otro lado, es importante tener en cuenta que, independientemente de las pr´acticas propuestas en esta secci´on, pueden plantearse a lo largo del curso otras m´as amplias, que requieran aunar los conocimientos de varios cap´ıtulos de forma conjunta, con el fin de que el alumno relacione los conceptos y adquiera una visi´on global de la materia. • Evaluaci´ on: Se propone una lista de ejercicios sin resolver, que deben servir al alumno para evaluar los conocimientos adquiridos en ese cap´ıtulo concreto. • Notas bibliogr´ aficas: Al final de cada tema se apuntan las fuentes bibliogr´aficas que m´as se adaptan a los contenidos expuestos, o bien que sirven para ampliar ciertos conocimientos no desarrollados expl´ıcitamente. Las referencias completas aparecen al final de texto-gu´ıa por orden alfab´etico. La parte de Laboratorio de Programaci´on contiene un u ´nico cap´ıtulo el cual presenta sus contenidos, unos objetivos generales, la descripci´on de una o m´as pr´acticas para cubrir las diferentes t´ecnicas de dise˜ no de algoritmos as´ı como evaluaci´on y prueba de programas, unas normas de presentaci´on de las pr´acticas, y notas bibliogr´aficas. Finalmente, el texto-gu´ıa incluye un ap´endice con una introducci´on al lenguaje Java, las referencias bibliogr´aficas e ´ındices de figuras, tablas y t´erminos. Fernando Jim´enez Gracia S´anchez

Algoritmos y Estructura de Datos. Implementaciones en Java

´ PROLOGO

18

Algoritmos y Estructura de Datos. Implementaciones en Java

Parte I Algoritmos y Estructura de Datos

Algoritmos y Estructura de Datos. Implementaciones en Java

Cap´ıtulo 1 Tipos de Datos Abstractos y ´ n Orientada a Objetos Programacio Contenidos • Concepto de Tipo de Datos Abstracto • Clasificaci´on de Tipos de Datos Abstractos • Especificaci´on de Tipos de Datos Abstractos – Especificaciones informales – Especificaciones formales • Programaci´on Orientada a Objetos – Clases y Objetos – Propiedades y M´etodos – Herencia y Polimorfismo – Pautas generales en dise˜ no orientado a objetos – T´ecnicas de implementaci´on ∗ Implementaciones est´aticas y din´amicas ∗ Representaciones contiguas y enlazadas – Utilizaci´on correcta de objetos ∗ Privacidad de los objetos ∗ Prevenci´on de efectos laterales ∗ Comparaci´on de objetos ∗ Tratamiento de excepciones

´ CAP´ıTULO 1. TIPOS DE DATOS ABSTRACTOS Y PROGRAMACION ORIENTADA A OBJETOS

22

A. Objetivos • Entender el concepto de Tipo de Dato Abstracto y la necesidad de su uso. • Diferenciar entre TDAs mutables e inmutables. • Estudiar especificaciones formales e informales de TDAs. • Aprender algunos conceptos y t´ecnicas b´asicas sobre programaci´on orientada a objetos. • Estudiar diferentes implementaciones del TDA Lista. • Ver diferentes modalidades de listas.

B. Desarrollo

1.1

Concepto de Tipo de Datos Abstracto

Para llegar a entender bien el concepto de tipo de datos abstracto, comenzaremos poniendo de relieve otros conceptos que est´an muy relacionados y que el lector ya debe conocer, como son los conceptos de tipo de datos y de estructura de datos. En un lenguaje de programaci´on, el tipo de datos de una variable es el conjunto de valores que ´esta puede tomar, el cual lleva asociado un conjunto de operaciones que permiten manipular dichos valores. Los tipos de datos b´asicos var´ıan de un lenguaje a otro, siendo los m´as usuales los enteros, reales, booleanos y caracteres. La representaci´on computacional concreta utilizada para los tipos de datos incorporados por el lenguaje es invisible al programador, al cual s´olo se le permiten usar las operaciones previstas para cada tipo. Los lenguajes de programaci´on suelen incorporar tambi´en tipos de datos que pueden definirse por el programador, como el enumerado o el subrango, lo que posibilita la definici´on de tipos de datos m´as cercanos al problema que se pretende resolver. La representaci´on de estos tipos es de nuevo invisible al programador, y el lenguaje proporciona operaciones predefinidas para manipular sus valores. Los tipos de datos estructurados son un paso m´as all´a, pues introducen la idea de genericidad. El lenguaje suministra unos constructores gen´ericos de tipos que el Algoritmos y Estructura de Datos. Implementaciones en Java

1.1. CONCEPTO DE TIPO DE DATOS ABSTRACTO

23

programador ha de completar, sustituyendo los tipos formales del mismo por tipos concretos. Para la estructuras de datos, el lenguaje proporciona tambi´en operaciones predefinidas para manipular los valores de los nuevos tipos definidos. Sin embargo, la propiedad de genericidad conseguida con las estructuras de datos puede resultar, en muchas ocasiones, un inconveniente en lugar de una ventaja. La raz´on es que de esta forma no se permite definir tipos, sino m´as bien representar unos tipos por otros. Para conseguir tal genericidad, las operaciones que ofrecen los lenguajes de programaci´on para manipular los valores de los nuevos tipos deben ser tan gen´ericas que no pueden impedir la creaci´on de valores sin sem´antica. Por ejemplo, si representamos un n´ umero racional mediante un registro con dos campos (numerador y denominador), el usuario del tipo puede generar libremente un valor cuyo denominador sea 0 y, por tanto, estar´ıa indefinido. Otro ejemplo es el tipo fecha. Si representamos el tipo fecha mediante un registro con los campos de d´ıa, mes y a˜ no, no se puede impedir que se generen valores sin significado como, por ejemplo, el d´ıa 30 de febrero, o que se realicen operaciones sobre fechas que no tengan sentido. El concepto de tipo de datos abstracto (TDA), propuesto hacia 1974 por John Guttag y colaboradores, vino a clarificar esta situaci´on. Un TDA es una colecci´on de valores junto con unas operaciones definidas sobre ellos. Las operaciones se definen mediante una especificaci´ on que es independiente de cualquier representaci´on. El acceso a los valores queda limitado al uso de las operaciones que lo manejan (no podemos utilizarlos si no es a trav´es de esas operaciones). El calificativo abstracto expresa precisamente esta cualidad de independencia de la representaci´on. Para definir un nuevo tipo, el programador deber´a comenzar por decidir qu´e operaciones le parecen relevantes y u ´tiles para operar con los valores pertenecientes al mismo. Es decir, deber´a comenzar por establecer la interfaz que van a tener los usuarios con dicho tipo. Si ´estas son las u ´nicas operaciones permitidas al usuario para crear valores del nuevo tipo, resulta imposible para ´estos construir valores inv´alidos del tipo. As´ı, las operaciones s´olo permitir´an crear valores correctos, produciendo un error cuando los datos de entrada sean incorrectos. El usuario del tipo debe estar informado, a trav´es de una especificaci´on, de las situaciones de error. Una vez establecida la interfaz con los usuarios del nuevo tipo, el programador es libre de escoger la representaci´on que m´as le convenga. La definici´on de la representaci´on y de las operaciones deber´a realizarse en un ´ambito de declaraci´on inaccesible al resto del programa. Los usuarios del tipo s´olo conocer´an el nombre del tipo (lo que les permite declarar variables) y la especificaci´on de las operaciones (lo que les permite manipular las variables declaradas). Si el programador que defini´o el TDA decidiera posteriormente cambiar la representaci´on por otra, s´olo tendr´ıa que cambiar Algoritmos y Estructura de Datos. Implementaciones en Java

24

´ CAP´ıTULO 1. TIPOS DE DATOS ABSTRACTOS Y PROGRAMACION ORIENTADA A OBJETOS

el m´odulo que contiene la definici´on de la representaci´on y de las operaciones. El resto del programa, una vez recompilado, se ver´ıa inalterado en su funcionamiento por el cambio de representaci´on. De este modo, el tratamiento dado por el lenguaje a los tipos definidos por el programador ser´ıa equivalente al que da a sus propios tipos (tipos opacos), y se resume en los siguientes aspectos: • Privacidad de la representaci´on: los usuarios no conocen la representaci´on de los valores en la memoria del computador. • Protecci´ on: s´olo se pueden utilizar para el nuevo tipo las operaciones previstas por la especificaci´on. Es muy importante indicar que el conjunto de operaciones de un TDA ha de permitir generar cualquier valor del tipo, ya que los usuarios no tienen otro modo de crearlos. El programador de un TDA ha de crear dos piezas de documentaci´on bien diferenciadas: • La especificaci´ on del TDA. Es lo u ´nico que conoce el usuario del TDA y consiste en el nombre del tipo y la especificaci´on de las operaciones. Esta especificaci´on tendr´a una parte sint´actica (nombre de cada operaci´on y tipos de los par´ametros y resultados), y otra sem´antica, para la cual, como veremos, existen distintos modos de llevarla a cabo (informal o formalmente). • La implementaci´on del TDA. Conocida s´olo por el programador del TDA, se realiza bajo un lenguaje de programaci´on concreto, y consiste en la representaci´on del tipo por medio de otros tipos (tipos de datos simples predefinidos o definidos por el programador, estructuras de datos, o a su vez, TDA’s), y en la realizaci´on de las operaciones en t´erminos de dicha representaci´on. Finalmente resaltar que un TDA representa una abstracci´ on en el sentido siguiente: • Se destacan los detalles (normalmente pocos) del comportamiento observable del tipo. Es de esperar que este aspecto sea bastante estable durante la vida u ´til del programa. • Se ocultan los detalles (probablemente numerosos) de la implementaci´on. Este aspecto es, adem´as, m´as propenso a cambios. Algoritmos y Estructura de Datos. Implementaciones en Java

´ DE TIPOS DE DATOS ABSTRACTOS 1.2. CLASIFICACION

25

Estas propiedades hacen que el TDA sea el concepto ideal alrededor del cual basar la descomposici´on en m´odulos de un programa grande y, por tanto, la base del dise˜ no modular.

1.2

Clasificaci´ on de Tipos de Datos Abstractos

A la hora de tratar con TDA’s nos parece conveniente hacer una primera clasificaci´on en TDA’s simples y TDA’s contenedores. Mientras que los casos de un TDA simple solamente cambian su valor pero nunca su estructura (a consecuencia de esto el espacio de almacenamiento que ocupan permanece constante), los casos de un TDA contenedor se caracterizan por su cambio de valor y de estructura. Un caso de un TDA contenedor es una colecci´on de un n´ umero variable de elementos agrupados entre s´ı mediante alguna estructura, por lo que dispone de una serie de operaciones asociadas para la selecci´on de componentes y operaciones sobre la estructura en su conjunto (adici´on y extracci´on de componentes, y creaci´on y eliminaci´on de estructuras). La tabla 1.1 muestra algunos ejemplos t´ıpicos de TDA’s simples y contenedores. TDA’s simples: entero, real, car´acter, booleano, enumerado, subrango. TDA’s contenedores: lista, cola, pila, ´arbol, grafo, conjunto. Tabla 1.1: Ejemplos de TDA’s simples y contenedores. Por otro lado, y de acuerdo a Liscov y Guttag (1986) [LIS86], un TDA se dice que es inmutable cuando los ‘objetos’ (casos) que pertenecen a ´el no pueden modificarse (se crean y se destruyen, pero no existen operaciones para modificarlo); en otro caso, se dice que es mutable. A veces, tenemos TDA’s inmutables con representaci´on mutable. Por ejemplo, dos casos del TDA racional tales como 12 y 42 pueden ser representados de forma unificada, permaneciendo invisible de cara al usuario esta mutabilidad en la representaci´on. Otro ejemplo de TDA inmutable con representaci´on mutable puede ser el TDA polinomio (los polinomios 2x y x + x pueden ser representados de igual forma).

1.3

Especificaci´ on de Tipos de Datos Abstractos

Hemos dicho que un TDA es una colecci´on de valores junto con una serie de operaciones definidas sobre ellos, y en el cual se separa lo que es el modelo de datos y sus operaciones, de la representaci´on elegida para el modelo y la implementaci´on de las

Algoritmos y Estructura de Datos. Implementaciones en Java

´ CAP´ıTULO 1. TIPOS DE DATOS ABSTRACTOS Y PROGRAMACION ORIENTADA A OBJETOS

26

TDA → Colecci´on de valores + Operaciones l Usuario → Especificaci´on ← Implementador . Implementaci´on Representaci´on Implementaci´on → + del TDA elegida de las operaciones Figura 1.1: Especificaci´on e implementaci´on de un TDA. operaciones.

Esto nos permite olvidarnos de los detalles de la implementaci´on, pero debemos conocer c´omo se usa el TDA, por lo que requerimos de su especificaci´ on. La definici´on de un TDA nos viene, por tanto, dada mediante su especificaci´on. Distinguiremos entre especificaciones informales y especificaciones formales. La especificaci´on de un TDA tiene un doble destinatario, el usuario del TDA y el implementador del TDA, los cuales pueden seguir su trabajo por separado una vez establecida ´esta. Para que esto pueda ser posible, una especificaci´on debe ser lo sufientemente precisa pero, a su vez, breve. Las especificaciones formales re´ unen estas dos caracter´ısticas, permitiendo la verificaci´ on formal de los programas usuarios del TDA, as´ı como de los que implementan el TDA. Las especificaciones informales, que no suelen reunir estas caracter´ısticas, pueden ser, no obstante, muy informativas y se pueden escribir de forma que sus destinatarios no tengan ning´ un inconveniente en entender su significado. En este texto veremos un modelo de especificaci´on informal y otro formal. Incluiremos especificaciones informales y formales para la mayor´ıa de los TDA’s que se estudiar´an a lo largo del texto. No obstante, el car´acter que pretendemos dar a este curso est´a m´as centrado en las cuestiones de implementaci´on (t´ecnicas de representaci´on y algoritmos de manipulaci´on), por lo que no incidiremos en aspectos de verificaci´on formal de las implementaciones, que deber´an tenerse en cuenta en cursos m´as avanzados.

Algoritmos y Estructura de Datos. Implementaciones en Java

´ DE TIPOS DE DATOS ABSTRACTOS 1.3. ESPECIFICACION

1.3.1

27

Especificaciones informales

Como modelo de especificaci´on informal hemos asumido el propuesto por Liskov y Guttag (1986) [LIS86]: 1. Cabecera: Aparece el nombre de las operaciones. 2. Descripci´ on: Se describe de forma general en qu´e consiste la abstracci´on, sin decir nada acerca de la implementaci´on. Los casos del TDA pueden describirse en t´erminos de otros tipos para los cuales se espera que el lector de la especificaci´on est´e m´as familiarizado. Se pueden utilizar gr´aficos y abstracciones matem´aticas. Se puede incluir en la descripci´on si el TDA es mutable o inmutable. 3. Especificaci´ on de las operaciones: Para la especificaci´on de una abstracci´on operacional seguiremos el siguiente modelo: nombre de la operaci´ on (entrada) devuelve (salida) • requerimientos: Esta cl´ausula muestra las restricciones de uso. • modifica: Esta cl´ausula identifica las entradas que van a ser modificadas. • efecto: Esta cl´ausula define el comportamiento. Observamos los siguientes componentes: (a) Cabecera: Es la informaci´on sint´actica. Se indica el nombre de la operaci´on y el n´ umero, orden y tipos de sus entradas y salidas. Deben darse nombres para las entradas y pueden darse para las salidas. (b) Cuerpo: Es la informaci´on sem´antica. Consta de las siguientes cl´ausulas: • Requerimientos: Restringen el dominio del procedimiento o funci´on. Cuando introducimos requerimientos, obtenemos una abstracci´on operacional parcial (en caso contario se dice que la abstracci´on es total). El que use la abstracci´on es el responsable de que los requerimientos se cumplan; si ´estos no se cumplen, los resultados pueden ser impredecibles. Si la abstracci´on es total, la cl´ausula de requerimientos puede omitirse. Se supone como requerimiento impl´ıcito (y, por tanto, no tiene que ser explicitado en la cl´ausula de requerimientos) que las entradas que figuran en la lista de par´ametros de la abstracci´on han sido correctamente construidas mediante alg´ un constructor del tipo. • Modifica: Indica los argumentos de entrada que cambian de valor tras una llamada a la abstracci´on operacional. Algoritmos y Estructura de Datos. Implementaciones en Java

28

´ CAP´ıTULO 1. TIPOS DE DATOS ABSTRACTOS Y PROGRAMACION ORIENTADA A OBJETOS

• Efecto: Se indica el efecto que se produce al ejecutar la operaci´on para las entradas que cumplen los requerimientos. Debe definir qu´e salidas son producidas y tambi´en qu´e modificaciones son hechas en la lista de entradas de la cl´ausula modifica. La cl´ausula efecto se escribe bajo la asumpci´on de que se satisface la cl´ausula requerimientos, y no se dice nada sobre el efecto de la abstracci´on cuando dicha cl´ausula no se satisface.

Ejemplo: El TDA Racional A continuaci´on mostramos un ejemplo de especificaci´on informal para el TDA Racional de acuerdo al modelo de especificaci´on informal descrito anteriormente. Aunque podriamos considerar otras posibles formas para definir el TDA Racional, es claro que es un TDA simple, y lo definiremos como un TDA inmutable, por lo que no incluiremos operaciones de modificaci´on de los casos del TDA. Racional=tipo de datos es crea, num, den, suma, resta, multiplica, divide, simplifica. ´ DESCRIPCION: Los valores del TDA Racional son n´ umeros racionales. El TDA Racional es inmutable. OPERACIONES: crea(a,b:entero) devuelve (Racional) • requerimientos: b6= 0. • efecto: Devuelve un n´ umero racional cuyo numerador es a y cuyo denominador es b. num(a:Racional) devuelve (entero) • efecto: Devuelve el numerador del n´ umero racional a. den(a:Racional) devuelve (entero) • efecto: Devuelve el denominador del n´ umero racional a. suma(a,b:Racional) devuelve (Racional) • efecto: Devuelve un n´ umero racional que es la suma de los n´ umeros racionales a y b. Algoritmos y Estructura de Datos. Implementaciones en Java

´ DE TIPOS DE DATOS ABSTRACTOS 1.3. ESPECIFICACION

29

resta(a,b:Racional) devuelve (Racional) • efecto: Devuelve un n´ umero racional que es la resta de los n´ umeros racionales a y b. multiplica(a,b:Racional) devuelve (Racional) • efecto: Devuelve un n´ umero racional que es la multiplicaci´on de los n´ umeros racionales a y b. divide(a,b:Racional) devuelve (Racional) • requerimientos: num(b) 6= 0. • efecto: Devuelve un n´ umero racional que es la divisi´on de los n´ umeros racionales a y b. simplifica(a:Racional) devuelve (Racional) • efecto: Devuelve un n´ umero racional que es la simplificaci´on del n´ umero racional a. En la siguiente secci´on incluimos una implementaci´on en Java del TDA Racional.

1.3.2

Especificaciones formales

Utilizaremos para la escritura de especificaciones formales el siguiente esquema: • Tipo: Nombre del TDA. • Sintaxis: Forma de las operaciones. • Sem´ antica: Significado de las operaciones. Para describir la sintaxis de las operaciones asumimos un esquema funcional, sumistrando un nombre de funci´on para cada operaci´on e indicando el tipo de los argumentos y el del resultado: nombre de la funci´ on (tipo de los argumentos) → tipo del resultado

Algoritmos y Estructura de Datos. Implementaciones en Java

30

´ CAP´ıTULO 1. TIPOS DE DATOS ABSTRACTOS Y PROGRAMACION ORIENTADA A OBJETOS

Aunque en la parte de sintaxis de una especificaci´on formal todas las operaciones del TDA se describen como funciones, ´esto no obliga a que en la implementaci´on del TDA todas las operaciones sean funciones, sino que pueden definirse de forma similar como procedimientos, de acuerdo al estilo de programaci´on adoptado por el implementador o a las restricciones del lenguaje de programaci´on. El apartado de sem´antica nos indica el comportamiento de las funciones definidas sobre el TDA. La sem´antica consiste en un conjunto de reglas de tipo algebraico de la forma: nombre de la funci´ on (valores particulares) ⇒ expresi´ on del resultado Debemos tener en cuenta los siguientes aspectos: • No se definen reglas sem´anticas (se consideran axiomas) para ciertas funciones, como son algunas funciones constructoras. • La expresi´on del resultado puede ser recursiva, conteniendo referencias a la misma funci´on o a otras del TDA. • Las expresiones pueden contener referencias a otros tipos que consideramos predefinidos. En particular es importante considerar como predefinido el tipo booleano, con los valores cierto y falso, o el valor predefinido error, para indicar los valores de los argumentos en los que ciertas funciones parciales no est´an definidas. • Cualquier implementaci´on del TDA deber´a cumplir las condiciones impuestas por la sem´antica. • Las reglas han de intentar aplicarse en el orden indicado para la verificaci´on formal de programas. Para facilitar la escritura de las expresiones en la parte de sem´antica, se permite emplear expresiones condicionales, que adoptan la forma: si condici´ on ⇒ valor si cierto | valor si falso La condici´on ser´a una expresi´on que toma un valor booleano. Se considera como predefinida la comparaci´on de igualdad entre valores del mismo tipo, escrita como valor1 = valor2. Otra ampliaci´on de la notaci´on es permitir la definici´on de TDA’s gen´ericos, que se expresan en base a otro u otros tipos sin especificar exactamente cu´ales son. Algoritmos y Estructura de Datos. Implementaciones en Java

´ DE TIPOS DE DATOS ABSTRACTOS 1.3. ESPECIFICACION

31

Ejemplo: El TDA Bolsa A continuaci´on mostramos como ejemplo la especificaci´on formal del TDA Bolsa de acuerdo al modelo de especificaci´on formal descrito anteriormente. Podemos definir el TDA Bolsa (colecci´on de elementos, no ordenada, con repetici´on) mediante la especificaci´on: • Tipo: Bolsa (Elemento) • Sintaxis: bolsavacia → Bolsa poner(Bolsa,Elemento) → Bolsa esvacia(Bolsa) → booleano cuantos(Bolsa,Elemento) → natural • Sem´ antica: ∀b ∈ Bolsa, ∀e,f ∈ Elemento: esvacia(bolsavacia) ⇒ cierto esvacia(poner(b,e)) ⇒ falso cuantos(bolsavacia,e) ⇒ cero cuantos(poner(b,f),e) ⇒ si f=e ⇒ sucesor(cuantos(b,e)) | cuantos(b,e) La definici´on del tipo bolsa se apoya en el tipo predefinido booleano y en el tipo natural que asumimos que se ha definido formalmente con constructores cero y sucesor. Los constructores de los casos del tipo bolsa son bolsavacia y poner. En el ejemplo anterior las funciones introducidas son todas ellas totales, es decir, est´an definidas para todos los valores de sus argumentos. Cuando las funciones a especificar son parciales se deber´an incluir reglas sem´anticas que indiquen que para ciertos valores de los argumentos la funci´on tomar´a el valor predefinido error (por ejemplo, si queremos incluir la funci´on predecesor(natural) → natural en la definici´on del tipo natural, habr´a que a˜ nadir, entre otras, la regla predecesor(cero) ⇒ error). En la siguiente secci´on incluimos la implementaci´on en Java del TDA bolsa. Finalmente haremos los siguientes comentarios relativos a la realizaci´on y uso de especificaciones en general:

Algoritmos y Estructura de Datos. Implementaciones en Java

32

´ CAP´ıTULO 1. TIPOS DE DATOS ABSTRACTOS Y PROGRAMACION ORIENTADA A OBJETOS

• El usuario de una abstracci´on es el m´aximo responsable de que se cumplan los requerimientos de ´esta. Aunque, como hemos visto, el efecto de la abstracci´on no contempla situaciones para las cuales los requerimientos no se cumplen, es, sin embargo, importante prever la posibilidad de errores de software a la hora de implementar una abstracci´on operacional. Una implementaci´on se dice que es robusta si se autoproteje frente a valores inconsistentes de los datos. De acuerdo con las especificaciones, una llamada con argumentos que no cumplan los requerimientos se considera un error. No obstante, dicho error no deber´ıa provocar que el programa aborte, sino que deber´ıa dar lugar a un tratamiento excepcional pero controlado. Una manera de hacer expl´ıcita la previsi´on de errores es a˜ nadir sistem´aticamente a las listas de argumentos de todas las abstracciones operacionales un par´ametro de error en el que se devolver´a indicaci´on de si el resultado es normal o excepcional. Otra forma de llevar a cabo el tratamiento de errores es mediante el manejador de excepciones del que disponen algunos lenguajes de programaci´on, como es el caso de Java, y que ser´a el mecanismo que usaremos a lo largo de este texto. • Una especificaci´on debe ser totalmente independiente de cualquier implementaci´on, incluso del lenguaje de programaci´on bajo el cual recaer´a la implementaci´on. Por esta raz´on, las especificaciones son escritas en un lenguaje de especificaci´on, no en un lenguaje de programaci´on. Existe, pues, cierta informaci´on adicional de cara al usuario de la abstracci´on que le permitir´a usar ´esta en un lenguaje de programaci´on concreto, como puede ser si la operaci´on es funci´on o procedimiento, si los par´ametros son por valor o por referencia o, en su caso, la informaci´on de los par´ametros a˜ nadidos para el tratamiento de errores. Toda esta informaci´on adicional debe proporcionarse al usuario por el programador de la implementaci´on como un complemento de la especificaci´on; los entornos de desarrollo Java usualmente disponen de herramientas para la generaci´on autom´atica de este tipo de documentaci´on. • Hemos asumido que las operaciones de destrucci´on de los casos de un TDA no se especifican. No obstante, si el el lenguaje de programaci´on sobre el que recaiga la implementaci´on del TDA no dispone de mecanismos autom´aticos de destrucci´on, podr´ıa ser necesario la existencia de operaciones de destrucci´on en el conjunto de operaciones del TDA.

Algoritmos y Estructura de Datos. Implementaciones en Java

´ ORIENTADA A OBJETOS 1.4. PROGRAMACION

1.4

33

Programaci´ on Orientada a Objetos

Hasta ahora hemos visto c´omo pod´ıamos utilizar los tipos de datos abstractos para definir nuestras propias estructuras de datos junto con sus operaciones. La programaci´on orientada a objetos es un paradigma de programaci´on que nos permite hacer todo eso y a˜ nade algunas caracter´ısticas m´as, entre ellas la herencia y el polimorfismo, que permiten realizar una programaci´on todav´ıa m´as estructurada y encapsulada. En esta secci´on introduciremos los conceptos m´as importantes relacionados con la programaci´on orientada a objetos, como son los de clase, objeto, propiedad, m´etodo, herencia y polimorfismo, y la forma de utilizarlos mediante el lenguaje de programaci´on Java. La secci´on tiene una doble finalidad: por un lado, estudiar las principales t´ecnicas generales de implementaci´on de TDA’s, en donde distinguiremos entre implementaciones est´aticas y din´amicas, y entre representaciones contiguas y enlazadas, y por otro, estudiar c´omo pueden ser llevadas a cabo esas t´ecnicas mediante un lenguaje de programaci´on orientado a objetos, en concreto Java. El lenguaje Java fue dise˜ nado desde el principio como un lenguaje orientado a objetos. Su integraci´on en el ´ambito de las telecomunicaciones, la caracterizaci´on de lenguaje multiplataforma, y su propio dise˜ no hacen de Java un lenguaje de gran actualidad y relevancia, por lo que hemos decidido utilizarlo en el texto.

1.4.1

Clases y Objetos

Una clase es un tipo de datos definido por el usuario. Dentro de una clase tenemos un conjunto de datos y funciones que operan sobre dichos datos. Las clases son equivalentes a los tipos de datos abstractos. Un objeto es una instancia del tipo definido por su clase. Cuando creamos un nuevo objeto, estamos instanciando la clase. Cada clase existe solamente una vez en un programa, pero pueden haber muchos objetos que son instancias de una misma clase. La creaci´on de un objeto es un proceso de dos fases: declaraci´on e inicializaci´on. Cuando declaramos un objeto, el compilador reserva memoria para un apuntador al objeto cuyo tipo de datos es especificado por su clase. Un apuntador es por tanto una direcci´on de memoria la cual albergar´a un objeto en tiempo de ejecuci´on. Inicializar un objeto supone asignar la cantidad de memoria que necesita dicho objeto. Para inicializar un objeto es necesario llamar al constructor de la clase. Los constructores son funciones que define el programador y sirven para crear nuevas instancias de la clase. Algunos lenguajes orientados a objetos ofrecen un constuctor por defecto que puede utilizarse si no se define ning´ un constructor espec´ıfico. Para destruir un objeto, es necesario liberar la memoria que ´este ocupa, para lo cual puede requerirse llamar al destructor de la

Algoritmos y Estructura de Datos. Implementaciones en Java

34

´ CAP´ıTULO 1. TIPOS DE DATOS ABSTRACTOS Y PROGRAMACION ORIENTADA A OBJETOS Creaci´on del Objeto:

Objeto instanciado

Destrucci´on del Objeto:

Constructor

Destructor

Figura 1.2: Esquema de la vida de un objeto. clase. Sin embargo, en muchos lenguajes, la destrucci´on del objeto se realiza de forma autom´atica. En concreto, Java dispone de un mecanismo propio, llamado Recolector de Basura (Garbage Collector), que se encarga de liberar de forma autom´atica la memoria de aquellos objetos que no se utilicen, por lo que no es necesario ning´ un destructor expl´ıcito. El esquema de la vida de un objeto es, por tanto, de la siguiente forma: En Java, una clase se declara utilizando la palabra clave class de la siguiente forma: class { } y un objeto se declara como: ; Por ejemplo, para declarar una clase Vehiculo, se har´ıa como sigue: class Vehiculo { } y para declarar que miVehiculo es un objeto de la clase Vehiculo: Vehiculo miVehiculo; Para instanciar un objeto en Java tenemos que utilizar la palabra clave new. Por ejemplo, para crear un nuevo objeto de la clase Vehiculo tendr´ıamos que hacer lo siguiente: Vehiculo miVehiculo; miVehiculo = new Vehiculo(); en una sola l´ınea: Vehiculo miVehiculo = new Vehiculo(); siendo el constructor vacio el constructor por defecto que ofrece Java. Algoritmos y Estructura de Datos. Implementaciones en Java

´ ORIENTADA A OBJETOS 1.4. PROGRAMACION

1.4.2

35

Propiedades y M´ etodos

Dentro de una clase se declaran una serie de variables que son las que indican las propiedades particulares de cada objeto. Estas variables se llaman variables miembros o propiedades de la clase. Una propiedad es, por tanto, un campo de datos, que puede ser bien un tipo de datos b´asico, tal como un entero, un real, etc., o bien un objeto de otra clase. Junto con los datos que definen un objeto, tenemos tambi´en una serie de funciones que nos permiten operar con dichos datos. Estas funciones se llaman funciones miembros o m´etodos. Un m´etodo es una funci´on que realiza ciertas operaciones con los datos del objeto. Los constructores vistos anteriormente son m´etodos. Las variables miembros de una clase pueden ser b´asicamente de dos tipos: p´ ublicas y privadas. Las variables privadas pueden ser solamente accedidas desde m´etodos pertenecientes a la misma clase, mientras que las variables p´ ublicas pueden ser accedidas desde m´etodos pertenecientes a otras clases. La utilizaci´on de variables privadas garantiza la encapsulaci´on y estructuraci´on del c´odigo, lo cual supone un c´odigo de mayor calidad. En una clase dise˜ nada de forma adecuada, por tanto, los campos de datos ser´an en su mayor parte privados. Cuando es necesario acceder a campos privados desde fuera de la clase, se definen unos m´etodos de acceso que permiten recuperar el valor de dichos campos o modificar su valor. La utilizaci´on de dichos m´etodos asegura que el acceso a los campos de datos se realiza de forma correcta. Los m´etodos tambi´en pueden ser privados o p´ ublicos. Los m´etodos privados solamente pueden llamarse desde dentro de la misma clase, mientras que los m´etodos p´ ublicos pueden ser llamados desde otras clases. Por u ´ltimo, un m´etodo, o una variable miembro, puede ser declarada est´atica. Esto significa que dicho miembro pertenece a la clase, no a los objetos individuales. Si una variable es est´atica, entonces cuando se cambia el valor de la variable, dicho valor cambia para todos los objetos de la clase. Para acceder a una variable est´atica, tendr´a que hacerse utilizando el nombre de la clase, no el nombre de objetos de la clase. De igual forma, si una variable est´atica es privada, ser´a necesario acceder a trav´es de un m´etodo de acceso, pero dicho m´etodo tendr´a que ser declarado tambi´en est´atico y se llamar´a a dicho m´etodo a trav´es de la clase, no de ning´ un objeto en concreto. En Java, una clase junto con sus datos y m´etodos se puede definir con la siguiente sintaxis: class { private ; public () { } Algoritmos y Estructura de Datos. Implementaciones en Java

36

´ CAP´ıTULO 1. TIPOS DE DATOS ABSTRACTOS Y PROGRAMACION ORIENTADA A OBJETOS

public () { } } En Java, las palabras clave para restringir el acceso a los campos de datos y a los m´etodos dentro de una clase son: • public: accesible desde todos los m´etodos en todos los paquetes (un paquete en Java consiste en un conjunto de clases que se agrupan juntas y est´an relacionadas). • private: accesible s´olo desde m´etodos dentro de la misma clase. • protected: accesible solo desde m´etodos dentro del mismo paquete o a m´etodos pertenecientes a subclases (veremos los que son subclases m´as adelante cuando estudiemos la herencia). Cuando no se establece ninguna palabra clave para restringir el acceso, se supone por defecto que el campo o el m´etodo tienen acceso “package”, es decir, es accesible desde cualquier otra clase en el mismo paquete. Si la clase no pertenece a ning´ un paquete, entonces podemos suponer que son p´ ublicas. Por otro lado, una variable o un m´etodo dentro de una clase tambi´en pueden ser definidas como static. En este caso, el campo de datos o el m´etodo pertenece a la clase, no a una instancia particular de la clase. Utilizando el lenguaje Java, podriamos declarar la clase Vehiculo de la siguiente forma: class Vehiculo { private int numeroRuedas; private double velocidadMaxima; public String nombrePropietario; static private String nombreFabrica = "SEAT"; public Vehiculo(int nRuedas) { if (nRuedas=e.dato); } public boolean menorQue(Object elemento) { if (elemento==null) return false; Elemento e = (Elemento)elemento; return (dato0) { t=m; m=n%m; n=t; } return n; } /** * Devuelve el numerador del n´ umero racional * * @return Devuelve el valor del numerador del n´ umero racional */ public int numerador() {

Algoritmos y Estructura de Datos. Implementaciones en Java

´ DESARROLLO DE LAS PRACTICAS

return num; } /** * Devuelve el denominador del n´ umero racional * * @return Devuelve el valor del denominador del n´ umero racional */ public int denominador() { return den; } /** * Suma dos n´ umeros racionales a + b * * @param a Primer sumando * @param b Segundo sumando * @return El n´ umero racional que es la suma de los anteriores */ static public Racional suma(Racional a, Racional b) { int n = (a.num*b.den)+(b.num*a.den); int d = a.den*b.den; return new Racional(n,d); } /** * Resta dos n´ umeros racionales a - b * * @param a Primer operando de la resta * @param b Segundo operando de la resta * @return El n´ umero racional que es la resta de los anteriores */ static public Racional resta(Racional a, Racional b) { int n = (a.num*b.den)-(b.num*a.den); int d = a.den*b.den; return new Racional(n,d); }

Algoritmos y Estructura de Datos. Implementaciones en Java

73

74

´ DESARROLLO DE LAS PRACTICAS

/** * Multiplica dos n´ umeros racionales a * b * * @param a Primer multiplicando * @param b Segundo multiplicando * @return El n´ umero racional que es la multiplicaci´ on de los anteriores */ static public Racional multiplica(Racional a, Racional b) { int n = a.num*b.num; int d = a.den*b.den; return new Racional(n,d); } /** * Divide dos n´ umeros racionales a / b * * @param a Dividendo * @param b Divisor * @return El n´ umero racional que es la divisi´ on de los anteriores */ static public Racional divide(Racional a, Racional b) { int n = a.num*b.den; int d = a.den*b.num; return new Racional(n,d); } /** * Simplifica un n´ umero racional * * @param a N´ umero racional a simplificar * @return Devuelve el n´ umero racional que es la simplificaci´ on */ static public Racional simplifica(Racional a) { int x = mcd(Math.abs(a.num),Math.abs(a.den)); int n = a.num/x; int d = a.den/x;

Algoritmos y Estructura de Datos. Implementaciones en Java

´ DESARROLLO DE LAS PRACTICAS

75

return new Racional(n,d); } public String toString() { return (num+"/"+den); } public boolean equals(Object o) { Racional r1 = simplifica(this); Racional r2 = simplifica((Racional)o); return ((r1.num==r2.num)&&(r1.den==r2.den)); } public Object clone() { Racional r = new Racional(num,den); return r; } } // fin class Racional VisualCaf´e nos ofrece un asistente para escribir todos los comentarios de la aplicaci´on mediante la opci´on Edit Javadoc Comments, que aparece pulsando el bot´on derecho del rat´on. Cuando ejecutamos javadoc sobre la clase anterior, obtenemos el siguiente fichero de especificaci´on, que es mucho m´as completo. En este caso, la documentaci´on generada es la siguiente: Class Racional Object | +----Racional

public class Racional extends Object Algoritmos y Estructura de Datos. Implementaciones en Java

´ DESARROLLO DE LAS PRACTICAS

76 implements Cloneable Clase que define un n´ umero racional Version: 1.0 Author: Fernando Jimenez, Gracia S´anchez Since: 1999 Constructor Index

• Racional(int, int) Construye un n´ umero racional de la forma numerador / denominador Method Index • clone() • denominador() Devuelve el denominador del n´ umero racional • divide(Racional, Racional) Divide dos n´ umeros racionales a / b • equals(Object) • multiplica(Racional, Racional) Multiplica dos n´ umeros racionales a * b • numerador() Devuelve el numerador del n´ umero racional • resta(Racional, Racional) Resta dos n´ umeros racionales a - b • simplifica(Racional) Simplifica un n´ umero racional • suma(Racional, Racional) Suma dos n´ umeros racionales a + b

Algoritmos y Estructura de Datos. Implementaciones en Java

´ DESARROLLO DE LAS PRACTICAS

• toString() Constructors • Racional public Racional(int n,int d) Construye un n´ umero racional de la forma numerador / denominador Parameters: n - El numerador d - El denominador Methods • clone public java.lang.Object clone() Overrides: clone in class Object • denominador public int denominador() Devuelve el denominador del n´ umero racional Returns: Devuelve el valor del denominador del n´ umero racional • divide public static Racional divide(Racional a, Racional b) Divide dos n´ umeros racionales a / b Parameters: a - Dividendo b - Divisor Returns: El n´ umero racional que es la divisi´on de los anteriores • equals public boolean equals(Object o) Overrides: equals in class Object

Algoritmos y Estructura de Datos. Implementaciones en Java

77

´ DESARROLLO DE LAS PRACTICAS

78 • multiplica

public static Racional multiplica(Racional a, Racional b) Multiplica dos n´ umeros racionales a * b Parameters: a - Primer multiplicando b - Segundo multiplicando Returns: El n´ umero racional que es la multiplicaci´on de los anteriores • numerador public int numerador() Devuelve el numerador del n´ umero racional Returns: Devuelve el valor del numerador del n´ umero racional • resta public static Racional resta(Racional a, Racional b) Resta dos n´ umeros racionales a - b Parameters: a - Primer operando de la resta b - Segundo operando de la resta Returns: El n´ umero racional que es la resta de los anteriores • simplifica public static Racional simplifica(Racional a) Simplifica un n´ umero racional Parameters: a - N´ umero racional a simplificar Returns: Devuelve el n´ umero racional que es la simplificaci´on del anterior • suma public static Racional suma(Racional a, Racional b) Suma dos n´ umeros racionales a + b Parameters: a - Primer sumando

Algoritmos y Estructura de Datos. Implementaciones en Java

´ DESARROLLO DE LAS PRACTICAS

79

b - Segundo sumando Returns: El n´ umero racional que es la suma de los anteriores • toString public java.lang.String toString() Overrides: toString in class Object

La documentaci´on del software es muy importante y ayuda a la reutilizaci´on del mismo. Por lo tanto, siempre resulta aconsejable generar dicha documentaci´on, m´axime cuando javadoc nos ofrece una forma tan sencilla de hacerlo. Es por tanto recomendable ejecutar javadoc en todas nuestras clases y realizar adem´as unos comentarios claros y suficientemente explicativos. En resumen: • Para crear una clase tendremos que hacer lo siguiente: – Establecer los directorios de salida para los ficheros compilados y de documentaci´on mediante la opci´on Projects - Options - Directories - Output files – Crear un fichero fuente miClase.java – Compilar el fichero para obtener el fichero de clase miClase.class – Comprobar que los comentarios de documentaci´on de la clase son suficientes – Ejecutar javadoc para obtener el fichero de documentaci´on miClase.html • Para utilizar una clase en nuestro proyecto tenemos que: – Disponer del fichero de clase laClase.class – Establecer la variable classpath para que encuentre el fichero anterior mediante la opci´on Projects - Options - Directories - Input class files – Utilizar la clase seg´ un la documentaci´on contenida en laClase.html

Algoritmos y Estructura de Datos. Implementaciones en Java

´ EVALUACION

80

E. Evaluaci´on 1.E.1 Ampliar la clase Racional para que implemente las interfaces Comparable y Valuable

1.E.2 Implementar una clase ElementoReal que represente un n´umero real de forma an´aloga a como la clase Elemento representa un n´umero entero. La clase ElementoReal debe implementar, entre otros, los m´etodos equals, toString y tambi´en implementar las interfaces Comparable y Valuable.

1.E.3 Implementar una clase ElementoCaracter que represente un car´acter. Esta clase ¿puede implementar las interfaces Comparable y Valuable? ¿c´omo?

1.E.4 Implementar una clase Circulo que represente un c´ırculo.

1.E.5 Implementar una clase Persona donde se representen los datos relacionados con una persona (nombre, direcci´on, tel´efono). Como en todas las clases anteriores, no olvidar implementar los m´etodos equals y toString. Esta clase ¿podr´ıa implementar la interface Comparable? ¿c´omo? ¿y la interface Valuable?

1.E.6 Realizar una interface para el TDA Bolsa.

1.E.7 Para implementar un TDA en Java, ¿es necesario implementar una interface? ¿en qu´e casos es conveniente?

1.E.8 Realizar una implementaci´on contigua para el TDA Bolsa.

1.E.9 Realizar un programa que utilice la clase Bolsa para construir una bolsa de enteros. ¿Qu´e hace falta cambiar para construir una bolsa de racionales? ¿y una bolsa de personas?

Algoritmos y Estructura de Datos. Implementaciones en Java

´ EVALUACION

81

1.E.10 ¿Es posible realizar un m´etodo que, pas´andole como par´ametro una bolsa, imprima los elementos de dicha bolsa? ¿y un m´etodo que borre un elemento de una bolsa?

1.E.11 ¿Es cierto que las representaciones contiguas son menos eficientes que las representaciones enlazadas?

Algoritmos y Estructura de Datos. Implementaciones en Java

´ NOTAS BIBLIOGRAFICAS

82

F. Notas Bibliogr´aficas La mayor´ıa de los textos de Programaci´on y de Algoritmos y Estructura de Datos incluyen apartados dedicados a los TDA’s as´ı como al estudio de los TDA’s fundamentales que se usan en numerosas aplicaciones. No obstante, podemos apreciar entre ellos distintos enfoques, unos m´as formalistas y te´oricos, y otros m´as pr´acticos. 1. [PEN98] ofrece un enfoque fromalista y te´orico. Tras una buena introducci´on al concepto de TDA y a su importancia en el dise˜ no modular de programas, se describe exhaustivamente un modelo de especificaci´on algebraica para TDA’s con el objetivo principal de la verificaci´on formal de la correcci´on de programas. Los principales TDA’s (tanto simples como contenedores) se especifican mediante dicho modelo de especificaci´on, prestando, quiz´as, menos atenci´on a los aspectos de implementaci´on. 2. En [LIS86] se aprecia tambi´en un marcado car´acter te´orico, si bien se analizan tambi´en aspectos de implementaci´on en lenguaje CLU. Se incluyen modelos de especificaci´on tanto informales como formales, y se introducen conceptos relacionados con los TDA’s como son, entre otros muchos, los conceptos de mutabilidad e inmutabilidad. 3. [COLL87] es un texto m´as orientado a los aspectos de implementaci´on, y los TDA’s se definen mediante un modelo de especificaci´on formal que luego no se utiliza para verificaci´on formal, sino como herramienta para dotar de una mayor precisi´on a las especificaciones de TDA’s. 4. [AHO88] es un texto con mayor componente pr´actica en donde no se establece un modelo de especificaci´on para TDA’s, ni siquiera informal, sino que estos se describen de forma totalmente gen´erica haciendo uso directamente del lenguaje natural. Ahora bien, es un libro muy apropiado a este nivel para tratar los aspectos de implementaci´on. 5. En [HAR89] se utilizan especificaciones formales para los TDA’s y un estilo de programaci´on funcional y recursivo. 6. En [YOU94] se revisa toda la teor´ıa de Programaci´on Orientada a Objetos sin entrar en ning´ un lenguaje concreto.

Algoritmos y Estructura de Datos. Implementaciones en Java

´ NOTAS BIBLIOGRAFICAS

83

7. En [RIE96] se revisa la teor´ıa OO sin ejemplos concretos, pero contiene al final un par de ap´endices con implementaciones de ejemplos muy interesantes en C++. 8. [RUS96] puede servir de iniciaci´on a Java; est´a escrito de una forma muy sencilla para aprender las primeras nociones de Java. 9. [ROW98] hace una revisi´on de todas las estructuras de datos utilizando Java, resultando por tanto un libro muy aconsejable. 10. [MAI99] presenta un enfoque muy similar al que en este texto estamos mostrando, es decir, la asociaci´on clara entre TDA y clase, usando tambi´en Java como lenguaje para la implementaci´on de los principales TDA’s. 11. [WEI99] y [WEI00] son textos de algoritmos y estructuras de datos en Java, en sus versiones ingl´es y castellano respectivamente.

Algoritmos y Estructura de Datos. Implementaciones en Java

Cap´ıtulo 2

Listas Contenidos

• Descripci´on del TDA Lista • Especificaci´on del TDA Lista • Ejemplos de uso • Implementaciones del TDA Lista – Representaciones contiguas – Representaciones enlazadas ∗ Representaci´on con simple enlace ∗ Representaci´on con doble enlace – Comparaci´on de las implementaciones • Otras alternativas en la definici´on del TDA Lista • Modalidades de listas

86

CAP´ıTULO 2. LISTAS

A. Objetivos • Entender el Tipo de Dato Abstracto Lista. • Aprender a utilizar el TDA Lista. • Estudiar diferentes implementaciones del TDA Lista. • Ver diferentes modalidades de listas.

B. Desarrollo

2.1

Descripci´ on del TDA Lista

Una lista es una colecci´on de cero o m´as elementos de un tipo determinado T , de forma que todos los elementos, excepto el primero, tienen un predecesor u ´nico, y todos los elementos, excepto el u ´ltimo, tienen un sucesor u ´nico. As´ı pues, los elementos en una lista est´an ordenados en forma lineal de acuerdo con sus posiciones en la misma. Podemos representar entonces una lista L como una secuencia de n elementos separados por comas, de la siguiente forma: L = (a1 , a2 , . . . , an ) donde n ≥ 0, y ai ∈ T , para i = 1, . . . , n. Al n´ umero n de elementos en la lista se le denomina longitud de la lista. Si n = 0 decimos que L es la lista vac´ıa, y cuando n ≥ 1 entonces se dice que a1 es el primer elemento y que an es el u ´ltimo elemento (si n = 1 entonces el elemento a1 = an es primer y u ´ltimo elemento de la lista simult´aneamente). Para una lista no vac´ıa, el elemento ai ocupa la i-´esima posici´ on de la lista, para i = 1, . . . , n, ai es predecesor de ai+1 , para i = 1, . . . , n − 1, y ai es sucesor de ai−1 , para i = 2, . . . , n. Una definici´on recursiva de las listas bastante habitual es la siguiente Una lista L es un conjunto de elementos del mismo tipo que • O bien es vac´ıo, en cuyo caso se denomina lista vac´ıa.

Algoritmos y Estructura de Datos. Implementaciones en Java

´ DEL TDA LISTA 2.1. DESCRIPCION

87

• O bien puede distinguirse un elemento, llamado cabeza, y el resto de los elementos constituyen una lista L0 , denominada resto de la lista original. Una propiedad importante con la que se caracterizan las listas es que su longitud puede aumentar o disminuir seg´ un se requiera. Es m´as, podemos insertar o eliminar elementos en cualquier posici´on de una lista. As´ı pues, dada una lista L de longitud n > 0, podemos eliminar cualquier elemento ai de la lista, para i = 1, . . . , n, para lo cual requeriremos su posici´on. N´otese por otra parte que, para una lista L de longitud n ≥ 0, podemos realizar inserciones en n + 1 posiciones diferentes de ´esta (si n = 0 tenemos una u ´nica posibilidad de inserci´on, si n = 1 podremos insertar antes de a1 o despu´es de a1 , si n = 2 podremos insertar antes de a1 , entre a1 y a2 , o despu´es de a2 , etc.). Nosotros asumiremos aqu´ı que, dada la posici´on de un elemento ai de una lista L, la inserci´on de un nuevo elemento en dicha posici´on provoca que el nuevo elemento se sit´ ue como predecesor del elemento ai . Ya que en una lista L = (a1 , a2 , . . . , an ) disponemos de n posiciones, podemos postular la existencia de una posici´on ficticia adicional (la cual no se corresponde con la posici´on de ning´ un elemento en la lista) que nos permita insertar elementos despu´es del u ´ltimo. Denominaremos a esta posici´on ficticia la posici´on fin de la lista. La posici´on fin representa la u ´nica posici´on existente en una lista vac´ıa, y en el orden establecido para las posiciones aparece como la siguiente posici´on a la posici´on del u ´ltimo elemento en una lista L de longitud n > 0. La posici´on fin nos servir´a por tanto para poder realizar todas las inserciones posibles en una lista, y podremos utilizarla tambi´en como una “marca” que nos indique cu´ando hemos recorrido todos los elementos de una lista, como veremos en las secciones siguientes. El siguiente paso en la descripci´on del TDA Lista es asociarle un conjunto de operaciones. Esta tarea, como ocurre en la mayor´ıa de los TDA, usualmente depende de la aplicaci´on en la cual se utilize el TDA Lista. Nosotros buscaremos un conjunto completo de operaciones b´asicas, de forma que pueda usarse en cualquier tipo de aplicaci´on, y que permita crear de forma eficiente nuevas operaciones, espec´ıficas para la aplicaci´on concreta, a partir de dicho conjunto de operaciones base. A continuaci´on presentamos un conjunto representativo de operaciones sobre listas y una descripci´on general de cada una de ellas. Dicho conjunto se ha desglosado en los siguientes cuatro subconjuntos diferentes, que atienden al tipo de operaci´on: operaciones de creaci´ on y destrucci´ on, operaciones de posicionamiento, operaciones de consulta y operaciones de modificaci´ on. En este conjunto de operaciones podemos observar tambi´en tres tipos de datos diferenciados el de los casos del TDA Lista, el Algoritmos y Estructura de Datos. Implementaciones en Java

88

CAP´ıTULO 2. LISTAS

de las posiciones de los elementos de las listas, y el de los elementos de las listas. El tipo de datos de las posiciones nos permitir´a, por un lado, acceder a cualquier elemento de la lista (para insertar, suprimir, modificar o recuperar), y por otro, la creaci´on de m´ ultiples instancias de dicho tipo de datos, lo que facilita el dise˜ no de nuevas operaciones sobre listas. Aunque, cuando hemos descrito el modelo abstracto de datos asoci´abamos ´ındices enteros a las posiciones para establecer el orden de los elementos con respecto al de sus posiciones en la lista, en la pr´actica esto no tiene por qu´e ser as´ı, y el tipo de datos de las posiciones puede variar seg´ un la implementaci´on, como veremos en las siguientes secciones. Operaci´ on de construcci´ on • CREA. Esta operaci´on crea una lista vac´ıa. Tras su ejecuci´on, existe una nueva lista, y debe invocarse antes de realizar cualquier otra operaci´on sobre la misma. Es importante asegurarse de que la lista creada no exista antes de su creaci´on, ya que provocar´ıa la p´erdida de los elementos contenidos en ella.

Operaciones de posicionamiento • FIN. Esta operaci´on devuelve la posici´on fin de una lista existente. La lista puede contener elementos o bien ser la lista vac´ıa. • PRIMERO. Esta operaci´on devuelve la posici´on que ocupa el primer elemento de una lista existente. Es por tanto necesario que la lista contenga al menos un elemento. • SIGUIENTE. Dada la posici´on que ocupa un elemento en una lista existente, esta operaci´on devuelve la posici´on del elemento sucesor en la lista. Si la posici´on dada es la del u ´ltimo elemento de la lista, la operaci´on devuelve la posici´on fin de la lista. • ANTERIOR. Dada la posici´on que ocupa un elemento en una lista existente (distinta de la posici´on del primer elemento en la lista), esta operaci´on devuelve la posici´on que ocupa el elemento predecesor en la lista. Si la posici´on es la posici´on fin de la lista, entonces la operaci´on devuelve la posici´on del u ´ltimo elemento de la lista.

Algoritmos y Estructura de Datos. Implementaciones en Java

´ DEL TDA LISTA 2.2. ESPECIFICACION

89

Operaciones de consulta • VAC´IA. Dada una lista existente, esta operaci´on devuelve un valor cierto si la lista es vac´ıa, y falso en caso contrario. • RECUPERA. Dada la posici´on que ocupa un elemento en una lista existente no vac´ıa, este operaci´on devuelve dicho elemento. • LONGITUD. Esta operaci´on devuelve la longitud de una lista existente.

Operaciones de modificaci´ on • INSERTA. Dada la posici´on de un elemento en una lista existente, esta operaci´on inserta un nuevo elemento en la lista como predecesor del elemento que ocupa dicha posici´on. Si la posici´on es la posici´on fin de la lista, entonces el elemento pasa a ser el u ´ltimo elemento de la lista tras la operaci´on de inserci´on. • SUPRIME. Dada la posici´on de un elemento en una lista existente, esta operaci´on elimina dicho elemento de la lista. • MODIFICA. Dada la posici´on de un elemento en una lista existente, esta operaci´on modifica dicho elemento, cambi´andolo por uno nuevo. En esta descripci´on general faltan a´ un por concretar aspectos sint´acticos y sem´anticos relevantes para los implementadores y usuarios del TDA, que mostramos a continuaci´on mediante su especificaci´on.

2.2

Especificaci´ on del TDA Lista

Definiremos el TDA Lista a trav´es de su especificaci´ on, para lo cual, como una primera aproximaci´on, usaremos un modelo de especificaci´on informal. Como ya se coment´o, las especificaciones informales pueden no ser precisas, pero son, en general, m´as f´aciles de leer y escribir que las especificaciones formales, pudiendo ser lo suficientemente informativas como para que sus usuarios las entiendan sin dificultades, por lo que pueden resultar apropiadas en alumnos que est´en inici´andose en programaci´on. Por otro lado, definiremos el TDA Lista como mutable, utilizando el tipo de datos de las posiciones de los elementos en la definici´on del TDA Lista, debido al valor pedag´ogico Algoritmos y Estructura de Datos. Implementaciones en Java

90

CAP´ıTULO 2. LISTAS

que ofrece esta definici´on a la hora de llevar a cabo las distintas implementaciones. En otra secci´on de este cap´ıtulo veremos otra definici´on del TDA Lista como un TDA inmutable en donde no interviene el tipo de datos de las posiciones de los elementos en la lista. A continuaci´on mostramos la especificaci´on informal del TDA Lista. En ´esta, L es una lista de elementos de un tipo de datos Elemento, E es un elemento de ese tipo, y P es del tipo de datos de las posiciones de los elementos de la lista, al que denominamos Posicion. Especificaci´ on informal del TDA Lista Lista = TDA con operaciones crea, fin, primero, siguiente, anterior, vacia, recupera, longitud, inserta, suprime, modifica. ´ DESCRIPCION: Los valores del TDA Lista son listas de elementos del tipo Elemento. Las posiciones de los elementos de la lista y la posici´on fin de la lista son del tipo Posicion. Las listas son mutables: inserta, suprime y modifica a˜ naden, eliminan y modifican elementos en la lista respectivamente. OPERACIONES: crea() devuelve (L:Lista) • efecto: Devuelve la lista vac´ıa L. fin(L:Lista) devuelve (Posicion) • efecto: Devuelve la posici´on fin de la lista L. primero(L:Lista) devuelve (Posicion) • requerimientos: La lista L es no vac´ıa. • efecto: Devuelve la posici´on del primer elemento de la lista L. siguiente(L:Lista; P:Posicion) devuelve (Posicion) Algoritmos y Estructura de Datos. Implementaciones en Java

´ DEL TDA LISTA 2.2. ESPECIFICACION

91

• requerimientos: La lista L es no vac´ıa. P6=fin(L). • efecto: Devuelve la posici´on que ocupa el elemento sucesor del elemento que ocupa la posici´on P en la lista L. Si P es la posici´on que ocupa el u ´ltimo elemento de la lista L, devuelve la posici´on fin de la lista. anterior(L:Lista; P:Posicion) devuelve (Posicion) • requerimientos: La lista L es no vac´ıa. P6=primero(L). • efecto: Devuelve la posici´on que ocupa el elemento predecesor del elemento que ocupa la posici´on P en la lista L. Si P es la posici´on fin de la lista L, devuelve la posici´on del u ´ltimo elemento de la lista. vacia(L:Lista) devuelve (booleano) • efecto: Devuelve cierto si L es la lista vac´ıa, y falso en caso contrario. recupera(L:Lista; P:Posicion) devuelve (E:Elemento) • requerimientos: La lista L es no vac´ıa. P6=fin(L). • efecto: Devuelve en E el elemento que ocupa la posici´on P en la lista L. longitud(L:Lista) devuelve (entero) • efecto: Devuelve la longitud de la lista L. inserta(L:Lista; P:Posicion; E:Elemento) • modifica: L. • efecto: Inserta el elemento E en la lista L como predecesor del elemento que ocupa la posici´on P en la lista. Si P es la posici´on fin de la lista L entonces el elemento E pasa a ser el u ´ltimo elemento de la lista tras la operaci´on de inserci´on. El valor de P, as´ı como el de cualquier otro caso o instancia del tipo de datos posicion existente antes de la operaci´on de inserci´on, quedan indefinidos tras ejecutarse la operaci´on. suprime(L:Lista; P:Posicion) • requerimientos: La lista L es no vac´ıa. P6=fin(L). Algoritmos y Estructura de Datos. Implementaciones en Java

92

CAP´ıTULO 2. LISTAS

• modifica: L. • efecto: Elimina de la lista L el elemento que ocupa la posici´on P. El valor de P, as´ı como el de cualquier otro caso o instancia del tipo de datos posicion existente antes de la operaci´on de eliminaci´on, quedan indefinidos tras ejecutarse la operaci´on. modifica(L:Lista; P:Posicion; E:Elemento) • requerimientos: La lista L es no vac´ıa. P6=fin(L). • modifica: L. • efecto: Modifica el elemento que ocupa la posici´on P de la lista L, cambi´andolo por el nuevo elemento E. La interface Java del TDA Lista de acuerdo a esta especificaci´on puede definirse de la siguiente forma: package listaInterface; import listaException.*; public interface Lista { public Object fin(); public Object primero() throws ListaVaciaException; public Object siguiente(Object posicion) throws ListaVaciaException, FinPosicionException; public Object anterior(Object posicion) throws ListaVaciaException, PrimeraPosicionException; public boolean vacia(); public Object recupera(Object posicion) throws ListaVaciaException, FinPosicionException; public int longitud(); public void inserta(Object posicion, Object elemento); public void suprime(Object posicion) throws ListaVaciaException, FinPosicionException ; public void modifica(Object posicion, Object elemento) throws ListaVaciaException, FinPosicionException; } // fin interface Lista Podemos observar los siguientes puntos relativos a esta interface: Algoritmos y Estructura de Datos. Implementaciones en Java

´ DEL TDA LISTA 2.2. ESPECIFICACION

93

• No se ha declarado el constructor; esto es debido a que en las interfaces no se pueden declarar los constructores; ´estos se declaran y se definen posteriormente en las implementaciones de la clase. • Las posiciones son de la clase Object; esto nos permite que dicho tipo sea gen´erico y as´ı sea posible, en cada implementaci´on de la clase, definir su propia clase Posicion. • Los elementos son de la clase Object; esto nos permite que las listas puedan contener elementos de cualquier clase gen´erica que definamos posteriormente. • La interface se ha definido dentro del paquete listaInterface • Se han definido una serie de excepciones para realizar el tratamiento de errores, en concreto, las excepciones son de la clase ListaVaciaException, PrimerElementoException y UltimoElementoException. Todas estas excepciones forman el paquete listaException y son subclases de una excepci´on gen´erica de listas de la clase ListaException que es a su vez subclase de la clase gen´erica de excepciones Exception. Su definici´on es como sigue: package listaException; public class ListaException extends Exception { public ListaException() { super(); } public ListaException(String s) { super(s); } } package listaException; public class FinPosicionException extends ListaException { public FinPosicionException() { super(); } public FinPosicionException(String s) { super(s); } } package listaException; public class PrimeraPosicionException extends ListaException { public PrimeraPosicionException() { super(); } public PrimeraPosicionException(String s) { super(s); } } package listaException; public class ListaVaciaException extends ListaException { public ListaVaciaException() { super(); } public ListaVaciaException(String s) { super(s); } } Algoritmos y Estructura de Datos. Implementaciones en Java

94

2.3

CAP´ıTULO 2. LISTAS

Ejemplos de uso

Antes de pasar a estudiar algunas de las implementaciones de listas m´as importantes, mostraremos algunos ejemplos para su manejo. Podemos hacer esto ya que estamos contemplando las listas como pertenecientes a un TDA y, por tanto quedan separados el modelo abstracto de datos frente a su implementaci´on, por lo que, conocida la especificaci´on del TDA, podremos hacer uso de la abstracci´on sin necesidad de conocer los detalles de la implementaci´on. Mostramos a continuaci´on varios ejemplos, en Java, de operaciones b´asicas sobre listas. Estas operaciones consisten en la b´ usqueda en una lista de un elemento dado, en la ordenaci´on de una lista, y en la impresi´on de los elementos de una lista. import listaInterface.*; import listaException.*; public class ListaUtil { static public Object buscar(Lista lista, Object elemento) { if (lista.vacia()) return null; try { for(Object p = lista.primero(); !p.equals(lista.fin()); p = lista.siguiente(p)) { Object e = lista.recupera(p); if (e.equals(elemento)) return p; } return null; } catch (ListaException e) { System.err.println("Error en el manejo de listas: "+e); return null; } } // fin buscar() static public void ordenar(Lista lista) { try { Object p,q; int n=lista.longitud(); p=lista.fin(); for(int i=0; ii; j--) { Algoritmos y Estructura de Datos. Implementaciones en Java

2.3. EJEMPLOS DE USO

95

Comparable e1=(Comparable)lista.recupera(p); q=lista.anterior(q); Comparable e2=(Comparable)lista.recupera(q); if (e2.mayorQue(e1)) { lista.modifica(p,e2); lista.modifica(q,e1); } } } } catch (ListaException e) { System.err.println("Error en el manejo de listas: "+e); } } // fin ordenar() static public void imprimir(Lista lista) { if (lista.vacia()) { System.out.println(); return; } try { for(Object p = lista.primero(); !p.equals(lista.fin()); p = lista.siguiente(p)) { Object e = lista.recupera(p); System.out.print(e+" "); } System.out.println(); } catch (ListaException e) { System.err.println("Error en el manejo de listas: "+e); } } // fin imprimir() } // fin class ListaUtil En la implementaci´on anterior se pueden destacar los siguientes puntos: • Para comparar posiciones de la lista, que son de tipo gen´erico Object, se utiliza el m´etodo equals. • Los m´etodos buscar e imprimir suponen que los elementos de la lista son de la clase gen´erica Object y utilizan los m´etodos equals y toString para comparar e imprimir los elementos respectivamente. • El m´etodo ordenar necesita realizar la comparaci´on mayorQue entre objetos que no est´a definida en la clase Object, por tanto, ya no puede utilizar esta Algoritmos y Estructura de Datos. Implementaciones en Java

96

CAP´ıTULO 2. LISTAS

clase gen´erica; sin embargo, dicho m´etodo est´a declarada dentro de la interface Comparable por lo que se puede generalizar a todos los objetos que implementen dicha interface. • N´otese que hemos empleado dos estructuras de control diferentes para recorrer la lista. En el primer tipo de bucle, se sabe el n´ umero de elementos n que se deben recorrer, como ocurre con el m´etodo ordenar; dicho n´ umero n lo sabemos gracias al m´etodo longitud. Con el segundo tipo de bucle se establece como condici´on de terminaci´on de recorrido que la posici´on actual alcance la posici´on fin de la lista, por ejemplo, en el caso de los m´etodos buscar e imprimir lo cual nos permite hacer un seguimiento de las posiciones que vamos recorriendo. Podemos destacar c´omo en el m´etodo buscar es posible terminar el bucle si se cumple alguna otra condici´on (en este caso, que se encuentre el elemento buscado). No obstante, el uso de una estructura de control u otra queda normalmente establecido por el programador de acuerdo a su estilo. • Una tarea muy importante que debe llevar a cabo el usuario de un TDA es la comprobaci´on de que se cumplen los requerimientos impuestos sobre las operaciones del TDA. En los m´etodos buscar e imprimir, debemos hacer distinci´on entre cuando la lista esta vac´ıa y cuando contiene alg´ un elemento, ya que no est´a definida la posici´on del primer elemento cuando la lista est´a vac´ıa. En el m´etodo ordenar, el bucle externo se ejecutar´a u ´nicamente cuando la lista contenga dos o m´as elementos, por lo que se cumplen los requerimientos del m´etodo anterior. Por otra parte, se garantiza que las posiciones usadas para recuperar elementos de la lista son posiciones de elementos de la lista, ya que se itera desde la posici´on del primer elemento hacia los elementos sucesores utilizando para ello el m´etodo siguiente, en los m´etodos buscar e imprimir, y desde la posici´on del u ´ltimo elemento hacia los elementos predecesores utilizando el m´etodo anterior, en el m´etodo ordenar. N´otese que para que el algoritmo de ordenaci´on se realice en un O(n2 ), se requiere un O(1) en las todas las operaciones sobre listas involucradas.

2.4

Implementaciones del TDA Lista

En esta secci´on presentamos algunos mecanismos de implementaci´on que pueden utilizarse para el TDA Lista. Usaremos representaciones contiguas y representaciones enlazadas. Analizaremos el uso de arrays para llevar a cabo las representaciones contiguas. Para las representaciones enlazadas, analizaremos dos modalidades, con Algoritmos y Estructura de Datos. Implementaciones en Java

2.4. IMPLEMENTACIONES DEL TDA LISTA

97

simple enlace y con doble enlace. Para cada implementaci´on se analizan los requerimientos de memoria y el tiempo de ejecuci´on de las operaciones, indic´andose bajo qu´e condiciones resulta m´as apropiada (en t´erminos de eficiencia) cada una de ellas en comparaci´on con las restantes. Para las implementaciones del TDA Lista en un lenguaje de programaci´on concreto usaremos Java.

2.4.1

Representaciones contiguas

La forma m´as usual de implementar el TDA Lista con representaci´on contigua es mediante el uso de un vector o array unidimensional. De esta forma los sucesivos elementos de la lista se almacenan en posiciones contiguas del vector. Una de las grandes ventajas que caracteriza a esta implementaci´on es que las posiciones de los elementos en la lista pueden representarse de una forma sencilla a trav´es de los ´ındices del array. La posici´on que ocupa un elemento ai de una lista viene representada mediante el ´ındice i del array, tal como muestra la figura 2.1. La definici´on b´asica en Java de la clase Lista con representaci´on contigua, as´ı como la clase Posicion, puede ser la siguiente: class Posicion { int posicion; } // fin class Posicion class Lista { Object elementos[]; int longitud; static int max=100; } // fin class Lista La clase Lista posee dos campos elementos y longitud. El campo elementos es un array de objetos de la clase gen´erica Object. Desde este campo podremos acceder a todos los elementos del array. El campo longitud representa la longitud de la lista, y resulta u ´til para obtener de forma eficiente la posici´on fin de lista o la longitud de ´esta. La clase Posicion contiene un campo entero que indica el ´ındice en el array del elemento que ocupa esa posici´on. La representaci´on contigua presenta algunos inconvenientes. El primer problema que nos encontramos es elegir el tama˜ no m´aximo de la memoria asignada para la lista, ya que tama˜ nos grandes suponen un desperdicio de memoria cuando las listas representadas son de peque˜ na longitud, y tama˜ nos peque˜ nos impiden la representaAlgoritmos y Estructura de Datos. Implementaciones en Java

98

CAP´ıTULO 2. LISTAS

Indices del array

0 1 Campo elementos

.. .

a1 a2 .. .

.. .

an .. .

max-1

−

n-1

n

Campo longitud

Lista

Vac´ıo

Longitud de la lista

Figura 2.1: Una lista L = (a1 , a2 , . . . , an ) con representaci´on contigua mediante un array. ci´on de listas de longitud superior. Segundo, las operaciones de inserci´on y eliminaci´on requieren una reubicaci´on de elementos. Por tanto, bajo la representaci´on contigua las operaciones de inserci´on y eliminaci´on consumir´an un tiempo de ejecuci´on proporcional a la longitud de la lista. A continuaci´on comentamos las implicaciones de esta representaci´on en la implementaci´on de las operaciones del TDA de acuerdo a la especificaci´on dada en la secci´on 2.2, as´ı como en el tiempo de ejecuci´on T (n) de las operaciones para el peor caso en notaci´on asint´otica O. Operaci´ on de construcci´ on. La operaci´on de construcci´on Lista() se implementa de forma sencilla bajo la representaci´on contigua, con tiempos de ejecuci´on constantes O(1). Una vez que hemos asignado din´amicamente la memoria para el array que contiene los elementos de la lista (con la operaci´on new, representaremos la lista vac´ıa asignando el valor 0 al campo longitud. Operaciones de posicionamiento.

Algoritmos y Estructura de Datos. Implementaciones en Java

2.4. IMPLEMENTACIONES DEL TDA LISTA

99

Como ya se ha comentado, las posiciones de los elementos en la lista se representan bajo esta implementaci´on a trav´es de enteros que representan el ´ındice de los elementos almacenados en el array. Por tanto, la posici´on del primer elemento de la lista se representa de forma constante mediante un objeto de la clase Posicion que contenga el valor entero 0 en el campo posicion. Las posiciones de los elementos sucesor y predecesor de un elemento determinado se obtienen f´acilmente a partir de la posici´on de dicho elemento mediante un sencillo c´alculo aritm´etico de incremento o decremento unidad respectivamente. La posici´on fin de lista se obtiene tambi´en f´acilmente asignando a la posici´on el valor de la longitud de la lista. De esta forma, todas las operaciones de posicionamiento que estamos considerando consumen bajo esta implementaci´on un tiempo de ejecuci´on constante O(1). Operaciones de consulta. Las tres operaciones de consulta que hemos considerado (vacia, recupera y longitud) se implementan de forma sencilla bajo esta representaci´on, consumiendo todas un tiempo de ejecuci´on constante O(1). La operaci´on vacia devuelve true si el campo longitud es 0, y false en caso contrario. La operaci´on recupera accede al array mediante el valor entero representado en la posicion para devolver el elemento contenido. La operaci´on longitud devuelve el valor contenido en el campo longitud. Operaciones de modificaci´ on. El mayor inconveniente de la representaci´on contigua es que insertar o eliminar un elemento en la lista obliga a desplazar una posici´on a los elementos que siguen en la lista al elemento insertado o eliminado, para conceder espacio o para llenar el hueco vac´ıo respectivamente (excepto si la inserci´on se hace al final de la lista o se elimina el u ´ltimo elemento de la lista). Por tanto, bajo esta representaci´on las operaciones inserta y suprime requieren un tiempo de ejecuci´on O(n), es decir, proporcional a la longitud de la lista. Evidentemente, el campo longitud debe incrementarse o decrementarse seg´ un sea la operaci´on de inserci´on o de eliminaci´on. La operaci´on modifica se realiza en un tiempo de ejecuci´on constante O(1), ya que se accede directamente al array mediante el ´ındice representado en la posici´on para modificar el valor antiguo por el nuevo. Una implementaci´on completa en Java del TDA Lista con representaci´on contigua teniendo en cuenta las consideraciones anteriores puede ser la siguiente package listaContigua; Algoritmos y Estructura de Datos. Implementaciones en Java

100

CAP´ıTULO 2. LISTAS

class Posicion { protected int posicion; public boolean equals(Object o) { if (o==null) return false; Posicion p = (Posicion)o; return (p.posicion==posicion); } } // fin class Posicion package listaContigua; import listaException.*; public class Lista implements listaInterface.Lista { private Object elementos[]; private int longitud; private static int max=100; public Lista() { elementos = new Object[max]; longitud = 0; } public Object fin() { Posicion p = new Posicion(); p.posicion = longitud; return p; } public Object primero() throws ListaVaciaException { if (vacia()) throw new ListaVaciaException(); Posicion p = new Posicion(); p.posicion = 0; return p; } public Object siguiente(Object posicion) throws ListaVaciaException, FinPosicionException { Posicion p = (Posicion)posicion; if (vacia()) throw new ListaVaciaException(); if (p.posicion==longitud) throw new FinPosicionException(); Posicion q = new Posicion(); q.posicion = p.posicion+1;

Algoritmos y Estructura de Datos. Implementaciones en Java

2.4. IMPLEMENTACIONES DEL TDA LISTA

101

return q; } public Object anterior(Object posicion) throws ListaVaciaException, PrimeraPosicionException { Posicion p = (Posicion)posicion; if (vacia()) throw new ListaVaciaException(); if (p.posicion==0) throw new PrimeraPosicionException(); Posicion q = new Posicion(); q.posicion = p.posicion-1; return q; } public boolean vacia() { return (longitud==0); } public Object recupera(Object posicion) throws ListaVaciaException, FinPosicionException { Posicion p = (Posicion)posicion; if (vacia()) throw new ListaVaciaException(); if (p.posicion==longitud) throw new FinPosicionException(); return elementos[p.posicion]; } public int longitud() { return longitud; } public void inserta(Object posicion, Object elemento) { Posicion p = (Posicion)posicion; for(int i=longitud;i>p.posicion;i--) { elementos[i] = elementos[i-1]; } elementos[p.posicion] = elemento; longitud++; } public void suprime(Object posicion) throws ListaVaciaException, FinPosicionException { Posicion p = (Posicion)posicion; if (vacia()) throw new ListaVaciaException(); if (p.posicion==longitud) throw new FinPosicionException();

Algoritmos y Estructura de Datos. Implementaciones en Java

102

CAP´ıTULO 2. LISTAS

for(int i=p.posicion;ie.dato); } public boolean mayorIgualQue(Object elemento) { Elemento e = (Elemento)elemento; return (dato>=e.dato); } public boolean menorQue(Object elemento) { Elemento e = (Elemento)elemento; return (datolimite) { multa = valorMulta; System.out.println("Multazo"); } else { multa = 0; System.out.println("Buen conductor"); }

A.4.2

Sucesivos else-if

Cuando tenemos que considerar m´as de dos posibilidades, una opci´on es utilizar else-if sucesivos. El esquema es como sigue: if (condicion) instrucci´on; else if (condicion) instrucci´on; else if (condicion) instrucci´on; .... else instrucci´on; Ejemplo: if (nota>=9) calificacion=’SB’; else if (nota>=7) calificacion=’N’; else if (nota>=5) calificacion=’A’; else calificacion=’S’;

A.4.3

La instrucci´ on switch

Utilizando else if sucesivos se pueden tener en cuenta varias condiciones. Sin embargo, en muchas ocasiones esto no resulta muy eficiente, por lo que Java dispone de Algoritmos y Estructura de Datos. Implementaciones en Java

´ ´ A JAVA APENDICE A. INTRODUCCION

280

lo que se llama selecci´ on con claves por medio de la instrucci´on switch. El modelo de la instrucci´on switch es: switch (expresion) { case valor: instrucci´on; break; case valor: instrucci´on; break; .... default: instrucci´on; break; } La instrucci´on switch toma el valor de la expresi´on y, empezando con el primer valor, intenta encontrar una correspondencia. Si se encuentra una correspondencia, se ejecuta la instrucci´on asociada y el break hace que el control pase al final de la instrucci´on switch. La palabra clave default (caso por omisi´on) captura todos los valores que no han sido mencionados. La utilizaci´on de break y default no es obligatoria, pero su utilizaci´on suele considerarse conveniente. La expresi´on del switch debe producir un valor que sea un entero o un car´acter. Los valores son expresiones del mismo tipo que la expresi´on del switch y puede haber m´as de un valor para una instrucci´on dada. Sin un break, el control pasa al siguiente caso. Esto puede ser u ´til en algunos casos, como se muestra en el siguiente ejemplo: switch(nota) { case 10: case 9: calificacion = ’SB’; break; case 8: case 7: calificacion = ’N’; break; case 6: case 5: calificacion = ’A’; break; default: calificacion = ’S’; break; } Como siempre, la instrucci´on mencionada despu´es de cada caso puede ser una instrucci´on compuesta e incluir varias instrucciones. En este caso, el bloque de instrucciones deber´a tener llaves. Por ejemplo: switch(nota) { case 10: case 9: { calificacion = ’SB’; Algoritmos y Estructura de Datos. Implementaciones en Java

A.4. CONTROL DEL FLUJO

281

System.out.println(califacion); }; break; case 8: case 7: calificacion = ’N’; break; case 6: case 5: calificacion = ’A’; break; default: calificacion = ’S’; break; }

A.4.4

Repetici´ on con bucles for

Un bucle for Java b´asico aparece en el siguiente modelo: for(inicio; prueba; actualizaci´on) { cuerpo del bucle for } El for, los par´entesis y las llaves forman la estructura obligatoria del bucle. La parte de inicio introduce una o m´as variables de bucle que se prueban y actualizan. Si hay m´as de una variable de bucle, sus instrucciones de inicio se separan con comas. Normalmente, s´olo hay una variable de bucle. Las variables de bucle deben ser n´ umeros y, por convenci´on, suelen ser enteros. Es posible utilizar un n´ umero real como variable de bucle, pero se considera un mal h´abito. La raz´on es que una comparaci´on sobre los n´ umeros reales es inexacta en los l´ımites y se podr´ıa ejecutar el bucle una vez m´as o menos de las esperadas. La prueba es una comparaci´on que proporciona la condici´on para que termine el bucle, basada en el valor actual de las variables de bucle. La actualizaci´on consta de asignaciones para cambiar los valores de las variables de bucle en cada vuelta del bucle. El cuerpo del bucle consta de instrucciones. Si hay una sola instrucci´on, se pueden omitir las llaves. Un ejemplo de bucle for sencillo ser´ıa el siguiente: for(int i=0; i