Estructura De Datos 376b3d

<métodos6> public static void main (String [ ] args) {

Declaración del programa principal Inicio del programa principal

<cuerpo del programa principal> } }

Fin del programa principal. Fin de la clase.

Tabla 1.2. Estructura general de un programa en Java. La sintaxis del lenguaje Java es de formato libre7. Para identificar sus partes se utilizan delimitadores. El delimitador más importante es el punto y coma (;), que se utiliza como fin de instrucción. Así mismo las llaves ({ }), se utilizan para indicar el inicio y final

5

Este esquema se ampliará en el punto de Programación modular (1.3) Devuelve/n uno o ningún (void) valor/es. En Java no existe la posibilidad de devolver varios valores. 7 La otra alternativa (utilizada por lenguajes tales como COBOL o FORTRAN) se basa en considerar líneas de código de una longitud determinada estructuradas en campos, cada uno de los cuales tiene un significado predeterminado. 6

6 INTRODUCCIÓN A LA PROGRAMACIÓN

ESTRUCTURAS DE DATOS

de bloques de instrucciones o del programa. Estos (u otros) delimitadores pueden tener un significado particular en diferentes contextos. Generalmente una aplicación se desarrolla en varios ficheros, que se agrupan en packages, que son librerías de clases. Cada uno de los ficheros que la componen debe tener la extensión .java, y la aplicación se ejecutará por medio de la clase que contenga la función main. 1.2.2. Nomenclatura habitual en Java. Los nombres en Java son sensibles a las mayúsculas y las minúsculas (por ejemplo, cadena sería una variable distinta de Cadena). Habitualmente en Java se escribe con minúsculas, con las siguientes excepciones: o Cuando un nombre consta de varias palabras, se escriben seguidas, comenzando en minúsculas, excepto la primera letra de cada palabra a partir de la segunda (por ejemplo presuntoDivisor, datoMayor, etc.). o Los nombres de las clases e interfaces empiezan con mayúscula (por ejemplo Pila, Lista, Arbol). o Los nombres de objetos, variables y métodos empiezan por minúscula (por ejemplo buscarMayor, maximaDiferencia, etc.). o Los nombres de las constantes (o variables finales) se escriben en mayúsculas (por ejemplo PI). 1.2.3. Los datos. Como ya se ha indicado, los datos son los sujetos del tratamiento. Los datos, en un programa se pueden presentar en tres modalidades: o En forma literal. Es decir, indicando de forma explícita el propio dato. Por ejemplo, la cadena de caracteres “Hola EUI” en el ejemplo anterior. o Mediante un identificador de constante. Si se ha dado un nombre simbólico al valor de un dato (por ejemplo: PI = 3.14), el programa puede hacer referencia a él mediante el identificador asociado. o Mediante un identificador de variable. Se trata de un caso parecido al de constantes, con la importante diferencia que el valor asociado al identificador de la variable (en adelante, simplemente, variable) puede cambiar durante la ejecución del programa.


INTRODUCCIÓN A LA PROGRAMACIÓN 7

1.2.3.1. Tipos de datos. El lenguaje Java reconoce de forma predefinida los siguientes tipos8 de datos: Numéricos: o Enteros (int). En el rango, aproximadamente, ± 2*109. Además existen otros tipos de datos enteros: byte, short y long. o Racionales o fraccionarios (float). Aproximadamente en el rango ± 3.4*1038. La parte real y la fraccionaria se separan mediante un punto (.). También se pueden utilizar números reales con mayor precisión por medio del tipo double (aproximadamente en el rango ± 1.8*10308). Lógicos (boolean). Se refieren a los valores utilizados en el Álgebra de Boole (verdadero: true o falso: false). Carácter (char). Se utiliza para representar todos los caracteres del estándar Unicode (que incluye el ASCII). Cadena de caracteres (String). Este tipo de datos consiste en una secuencia de caracteres (por ejemplo “El cielo está enladrillado”). 1.2.3.2. Tratamiento de datos. 1.2.3.2.1. Operaciones. Una operación es un proceso que actúa sobre dos datos (operandos) y produce, en consecuencia, un resultado. Se identifica mediante un símbolo (o palabra reservada) denominado operador. Excepcionalmente se pueden presentar operaciones (unarias) que implican un solo operando y/u operaciones con datos de diferentes tipos9. Normalmente (pero no siempre) se utilizan dos operandos del mismo tipo que, además, es el tipo del resultado. Como consecuencia de la naturaleza (tipo) de un dato, tendrá sentido realizar cierto tipo de operaciones con él. La tabla siguiente muestra las más habituales:

8

El concepto tipo de datos se asocia implícitamente al los datos elementales (simples). Más adelante (apartado 1.4) se contemplará la posibilidad de agrupar datos simples en unidades de orden superior para dar lugar a diferentes estructuras de datos. 9 Las “operaciones” con más de dos operandos las consideramos dentro del epígrafe de expresiones.



Tipo

Operación

Operador

Entero (int)

Suma Resta Multiplicación Cociente Resto Suma Resta Multiplicación División Negación Unión (or) Intersección (and) No existen Concatenación

+ * / % + * / ! || &&

Ejemplo Operación 3+5 1-3 2 * (-5) 7/3 7%3 1,23 + 8,77 1,23 - 8,77 -3,2 * 4,6 3,2 / (-4,6) ! true true || false true && false

+

“Hola” + “ Antonio”

Real (float)

Lógico (boolean)

Carácter (char) Cadena (String)

Resultado 8 -2 -10 2 1 10,0 -7,54 -14,72 -0,6956 false true false 10

“Hola Antonio”

Tabla 1.3. Operaciones básicas. Operaciones de relación. Se trata de un tipo especial de peraciones en donde los operandos son del mismo tipo y el resultado es de tipo lógico (boolean). Su interpretación es ligeramente distinta en función del tipo de operandos. 11

Operador > < == >= <= !=

Tipos numéricos (int o float) Significado Ejemplo Mayor que 7>3 Menor que 7<3 Igual a 7 == 3 Mayor o igual que 3 >= 3 Menor o igual que (-3) <= 3 Distinto de 3 != 3

Result. true false false true true false

Tipo carácter (char) Significado Ejemplo Posterior a “a” > “z” Anterior a “P” < “p” Igual a “a” == “A” Posterior o igual a “z” >= “m” Anterior o igual a “M” <= “N” Distinto de “p” !=“P”

Result. false 12 true false true true true

Tabla 1.4. Operaciones de relación. 1.2.3.2.2. Funciones estándar y “complementos”. En términos generales se define una función como un tratamiento que se realiza sobre ninguno, uno o varios operandos (argumentos) y produce (devuelve) un resultado. Los lenguajes de programación incluyen un conjunto más o menos amplio de funciones13 que se identifican como palabras reservadas (forman parte del lenguaje) y

10

Obsérvese que la cadena (String) “ Antonio” incluye un espacio en blanco a su izquierda. Excepto de tipo lógico (boolean) en donde no tiene sentido. 12 Los códigos Unicode de las letras mayúsculas son más bajos que los de las minúsculas. 13 La diversidad de oferta de funciones “integradas” en el lenguaje es muy dispar, no solo entre diferentes lenguajes sino, también, para un mismo lenguaje, entre diferentes desarrolladores de traductores. Para su eficiente utilización se insta encarecidamente a utilizar el manual del fabricante. En este sentido su empleo debe entenderse como “manejo de catálogo”, dado que la aportación conceptual es escasa. 11



deben emplearse siguiendo la sintaxis adecuada: <nombre de la función> (<arg1>, <arg2>, … <argN>). Algunas funciones están disponibles como parte integrante del propio lenguaje en tanto que otras no forman parte del lenguaje. En el caso de Java, las correspondientes funciones (métodos) están declaradas y definidas en componentes (en Java, paquetes o packages) que, en su conjunto, configuran una biblioteca, almacenadas en uno o varios directorios14. Ejemplos: Algunos de los métodos de la clase MATH son: o Valor absoluto. (abs). Su sintaxis es abs ( ). Devuelve un número (integer o real, según proceda, positivo). Ejemplos: 

abs(-3.25) devuelve el valor 3.25.



abs(77) devuelve el valor 77.

o Número aleatorio (random). No utiliza argumentos. Devuelve un número racional (real) en el rango 0 < n < 1. Ejemplo: random puede devolver 0,67635… o Redondeo (round), Devuelve el entero más cercano al argumento. La clase String tiene entre otros los siguientes métodos: o length () devuelve la longitud de una cadena (). o toLowerCase () devuelve una cadena con todas las letras en minúsculas, o toUpperCase () devuelve una cadena con todas las letras en mayúsculas o subString (int, int), devuelve un subString extraído de otro. La clase Integer (es un wrapper del tipo primitivo int: los wrappers se utilizan para poder utilizar métodos como conversión de cadenas de caracteres a enteros y viceversa), tiene entre otros los siguientes métodos: o parseInt (String) convierte una cadena a un número entero, o toString () convierte un número entero a una cadena, o MAX_VALUE, MIN_VALUE, constantes predefinidas que devuelven el valor mayor y menor de un entero. Finalmente, usted también puede desarrollar sus propias librerías (packages), almacenarlas en el directorio que considere oportuno, indicarle dicha ubicación al compilador y utilizar las correspondientes operaciones (Ver Tema 2 “Tipos Abstractos de Datos”).

14

Además de las componentes (clases) proporcionadas por el “fabricante” (en este caso Eclipse) el programador puede incorporar otras de desarrollo propio (ver tema 2: “Tipos Abstractos de Datos”) o adquiridas a terceros.



1.2.3.2.3. Expresiones. Una expresión es una combinación (coherente) de datos (literales, constantes y/o variables), operaciones y funciones, enlazados entre sí por medio de operadores. Como consecuencia de evaluar una expresión, siguiendo las reglas correspondientes, se obtiene un resultado de tipo acorde con la naturaleza de la expresión. 1.2.4. Sentencias. Las sentencias son construcciones sintácticas que indican al ordenador qué operaciones debe realizar y, normalmente, con qué datos. Materializan la “parte operativa” de un programa que implementa el algoritmo (definición de Wirth, 1985) que se deberá ejecutar15. Dicha parte constituye un bloque delimitado por { y }. Se describe a continuación, la sintaxis de las sentencia de Java, agrupadas en función de su naturaleza. 1.2.4.1. Asignación. Permite, como su propio nombre indica, asignar un valor a una variable (ver 1.2.2) definida en la parte declarativa. Su sintaxis es: 16

<nombreVariable> = <expresión >;

Ejemplo (HolaEui2.Java): //Ejemplo de asignacion a variables. public class HolaEui2 { public static void main (String [ ] args) { String cadena = "Hola EUI"; System.out.println (cadena); } }

1.2.4.2. Entrada y salida17. Para realizar la entrada y salida de datos se utiliza la clase Java.io. La entrada estándar es System.in y la salida estándar es System.out. Para realizar la entrada/salida se utilizan flujos de datos (streams). Un stream es una conexión entre el programa y la fuente o destino de los datos. Las sentencias principales son readline (entrada) y print o println (salida). La sentencia print, cuya sintaxis básica es: System.out.print (<expresión>);

15

Con excepción de comentarios y “Directivas de compilación”. Consultar el manual del compilador. Ver epígrafe Expresiones. 17 Hacen referencia a los dispositivos configurados por defecto (el teclado y la pantalla). 16



Hace que se muestre en la pantalla (System.out representa la salida estándar, es decir, la pantalla) el resultado de evaluar la <expresión> utilizada como argumento. Dicho argumento debe ser un String, que puede estar formado por la concatenación (con +) de varias cadenas de caracteres diferentes. Si se incluye un número o valor lógico dentro de la expresión, se convertirá automáticamente a un String (por medio de los wrappers: las clases Integer, Float, Boolean etc.). Si en vez de utilizar print, utilizamos println, se incluirá un salto de línea después de <expresión>. La sentencia readline, cuya sintaxis básica es: BufferedReader linea = new BufferedReader (new InputStreamReader (System.in)); String cadena; ….

cadena = linea.readLine(); ….

implica la realización de la siguiente secuencia de acciones: En las dos primeras líneas, se declaran los objetos linea del tipo BufferedReader y cadena de tipo String. El escribe los caracteres correspondientes y finaliza pulsando la tecla “Intro”. Se utiliza el método readLine sobre el objeto linea, y se almacena en cadena. Se continúa con la ejecución del programa. Para leer otros datos que no sean de tipo String, habría que utilizar una sintaxis similar a la siguiente: BufferedReader linea = new BufferedReader (new InputStreamReader (System.in)); int n; ….

n = Integer.parseInt (linea.readLine()); ….

que implica la realización de la siguiente secuencia de acciones: En la primera línea, se declara el objeto linea del tipo BufferedReader. El escribe los datos correspondientes y finaliza pulsando la tecla “Intro”. Se utiliza el método readline sobre el objeto linea, y como se espera la introducción de un dato de tipo int, se convierte la línea leída (de tipo String), al tipo entero mediante el método parseInt de la clase Integer. Se continúa con la ejecución del programa. A continuación se muestra un ejemplo (HolaEui3.Java) que contempla la mayoría de consideraciones explicadas hasta el momento.



import java.io.*; //Ejemplo de sentencias de entrada/salida. public class HolaEui3 { public static void main(String [] args) throws NumberFormatException,IOException{ String cadena, cadena2; int edad, año = 2010; BufferedReader linea=new BufferedReader (new InputStreamReader (System.in)); System.out.println ("Hola, ¿como te llamas? "); cadena = linea.readLine(); System.out.println ("Encantado de conocerte, " + cadena); System.out.println ("Cuantos años tienes? "); edad = Integer.parseInt (linea.readLine()); edad = edad+3; año = año+3; cadena2 = cadena+", en algun momento de "+año+" tendrás "+edad+" años"; System.out.println (cadena2); System.out.println (cadena); } }

La figura siguiente (consola de eclipse) muestra un posible resultado de su ejecución.

Figura 1.4. Ejecución del ejemplo HolaEui3.pas. 1.2.4.3. Control de flujo. En los ejemplos anteriores se ha mostrado una de las tres estructuras consideradas en el enfoque (paradigma) de programación estructurada: la secuencia. El ordenador ejecuta (salvo imprevistos) una sentencia tras otra. Las dos estructuras restantes suponen una ejecución no lineal del conjunto de sentencias respecto al orden en que aparecen escritas en el programa. Son las estructuras alternativa y repetitiva (o iteración).



1.2.4.3.1. Estructura alternativa. Lo que se ejecute dependerá del resultado de evaluar una operación de relación ( ). Alternativa simple (if..else). En su modalidad más sencilla la estructura alternativa se regula mediante la sentencia if, cuya sintaxis18 es: if ( ) { ; } else { ; }

Ejemplo: El siguiente programa informa al de la paridad de un número entero introducido por el teclado. import java.io.*; //Ejemplo de alternativa simple. public class PruebaIf { public static void main (String [] args) throws NumberFormatException, IOException { int dato; BufferedReader linea=new BufferedReader (new InputStreamReader (System.in)); System.out.print("Numero: "); dato = Integer.parseInt (linea.readLine()); if ((dato % 2) == 0) System.out.println (" es par"); else System.out.println (" es impar"); } }

Operador condicional El operador condicional ?: se puede usar como abreviatura de la sentencia if, cuya sintaxis es: expresionCondicional ? expresionSI : expresionNO;

Primero se evalúa expresionCondicional. Si es true, se devuelve expresionSI, en caso contrario se devuelve expresionNO. Por ejemplo, si queremos guardar el valor menor entre x e y en la variable minimo podríamos hacer: minimo = x <= y ? x : y;

18

Se consideran los siguientes casos particulares: puede ser una única sentencia, y no harían falta las llaves ({ y }). Se puede omitir else: el ordenador no realizaría ninguna acción y ejecutaría la siguiente sentencia.



Alternativa múltiple (switch). La ejecución del programa continúa por una de entre varias opciones en función del resultado de evaluar una variable (de tipo char o int). Para utilizar esta estructura se utiliza la sentencia switch, cuya sintaxis general es: switch ( ) { case : break; ………. case : ; break; default break; }

Ejemplo: El programa siguiente espera recibir desde el teclado un dígito, entre 1 y 7, correspondiente al ordinal del día de la semana (lunes a domingo) y mostrará por la pantalla el literal del día asociado o un mensaje de error si el código no es válido. import java.io.*; //Ejemplo de alternativa multiple. public class PruebaSwitch { public static void main (String [ ] args) throws NumberFormatException, IOException { BufferedReader linea = new BufferedReader (new InputStreamReader (System.in)); System.out.print ("Opcion: "); int opc = Integer.parseInt (linea.readLine ()); switch (opc) { case 1: System.out.println ("lunes"); break; case 2: System.out.println ("martes"); break; case 3: System.out.println ("miercoles"); break; case 4: System.out.println ("jueves"); break; case 5: System.out.println ("viernes"); break; case 6: System.out.println ("sabado"); break; case 7: System.out.println ("domingo"); break; default: System.out.println ("opcion no valida"); break; } } }



1.2.4.3.2. Estructura iterativa. Consiste en realizar la ejecución de un bloque de código varias veces. Las modalidades que se explican a continuación dependen de la forma en que se realiza el control del número de repeticiones. Estructura iterativa controlada por contador (for). Se utiliza una variable entera que actúa como contador. La sentencia indica el valor inicial del contador, hasta cuando se debe realizar el bucle, así como la cuantía en que se incrementa (o decrementa) el contador. Su sintaxis es: for ( ; ; ) { }

Ejemplo: El siguiente programa muestra por la pantalla el valor de los cuadrados de 5 números introducidos por el teclado. import java.io.*; //Ejemplo de bucle for. public class PruebaFor { public static void main(String[] args) throws NumberFormatException,IOException{ int i, dato, cuadrado; BufferedReader linea = new BufferedReader (new InputStreamReader (System.in)); for (i = 1; i <= 5; i ++) { System.out.print ("Numero: "); dato = Integer.parseInt (linea.readLine ()); cuadrado = dato * dato; System.out.println ("El cuadrado de " + dato + " es: " + cuadrado); } } }

Estructura iterativa controlada por condición. En los casos siguientes la repetición, o no, de la ejecución de un bloque de código es consecuencia del resultado de evaluar una expresión booleana ( ). o Estructura mientras (while). Se utiliza la sentencia while, cuya sintaxis es: while ( ) { }

La evaluación de la es previa19 a la ejecución del bloque de código que se repite.

19

En consecuencia, podría ser que el bloque de código pudiera no ejecutarse ninguna vez.



Ejemplo: El siguiente programa ejecuta reiteradamente el ejemplo de los días de la semana, salvo que el teclee „0‟ como opción20. import java.io.*; //Ejemplo de bucle while. public class PruebaWhile { public static void main (String [] args) throws NumberFormatException, IOException { int opc; BufferedReader linea = new BufferedReader (new InputStreamReader (System.in)); System.out.print ("Opción: "); opc = Integer.parseInt (linea.readLine()); while (opc != 0) { switch (opc) { case 1: System.out.println ("lunes"); break; case 2: System.out.println ("martes"); break; case 3: System.out.println ("miercoles"); break; case 4: System.out.println ("jueves"); break; case 5: System.out.println ("viernes"); break; case 6: System.out.println ("sabado"); break; case 7: System.out.println ("domingo"); break; default: System.out.println ("opción no valida"); break; } System.out.print ("Opción: "); opc = Integer.parseInt (linea.readLine ()); } } }

o Estructura Repetir mientras (do … while). Se utiliza la sentencia do ... while, cuya sintaxis es: do while

( );

La evaluación de la es posterior21 a la ejecución del bloque de código que se repite.

20 21

Pruebe a ejecutarlo introduciendo la primera vez la opción 0. En consecuencia, la ejecución del bloque tiene lugar, al menos, una vez.



Ejemplo: El programa siguiente constituye una variante del ejemplo anterior en el que el bloque de código se ejecuta una vez y volverá a repetirse reiteradamente, o no, hasta que el teclee „0‟ como opción22. import java.io.*; //Ejemplo de bucle do ... while. public class PruebaDoWhile { public static void main (String [] args) throws NumberFormatException, IOException { int opc = 7; BufferedReader linea=new BufferedReader (new InputStreamReader (System.in)); System.out.println("Empezamos en domingo"); do { switch (opc) { case 1: System.out.println ("lunes"); break; case 2: System.out.println ("martes"); break; case 3: System.out.println ("miercoles"); break; case 4: System.out.println ("jueves"); break; case 5: System.out.println ("viernes"); break; case 6: System.out.println ("sabado"); break; case 7: System.out.println ("domingo"); break; default: System.out.println ("opción no valida"); break; }; System.out.print ("Opción: "); opc = Integer.parseInt (linea.readLine ()); } while (opc != 0); } }

22

Pruebe a ejecutarlo introduciendo la primera vez la opción 0.



1.3. PROGRAMACIÓN MODULAR. SUBPROGRAMAS. 1.3.1. Reflexión previa. Cualquier producto de Ingeniería (desde un barco hasta una central nuclear, pasando por una catedral) se concibe como un sistema complejo constituido por un conjunto de subsistemas más sencillos, y así sucesivamente hasta acabar en piezas indivisibles. El plantearse las cosas de esta manera permite que un conjunto de profesionales especializados pueda realizar la obra, con unos costes y tiempos razonables, y que, una vez finalizada, se puedan acometer con eficiencia las inevitables tareas de actualización y conservación. Inexplicablemente, con demasiada frecuencia, nos cuesta transmitir a algunos alumnos que la filosofía expuesta es (como no podía ser de otra manera), también, aplicable a las obras producidas mediante la Ingeniería del Software. Sostienen que como, de momento, las aplicaciones que desarrollan en sus actividades prácticas no son de gran volumen, se acaba antes “programando de un tirón” y que el día que les toque trabajar en un proyecto de centenares de millares de líneas de código ya cambiarán de actitud, etc. Evidentemente, cada cual es libre de equivocarse voluntariamente siempre que así lo desee. 1.3.2. Tecnología para la programación modular. Cuando hemos hablado antes de programación modular lo hemos hecho desde una perspectiva de “disciplina mental”. Por supuesto que la tecnología proporciona un importante conjunto de facilidades para dar soporte a tales concepciones. Aunque su explicación pormenorizada queda fuera de los objetivos y alcance de este curso, citaremos, simplemente, a grandes rasgos las principales variantes: Módulos externos. La fuente de procedencia de tales módulos es diversa: construidos previamente por el propio programador (o su empresa), incluidos en el propio entorno de programación (paquetes o packages en el caso del entorno de programación de Java utilizado en el curso) o adquiridos a terceros23. El programador de aplicaciones, para utilizar dichos módulos deberá únicamente incorporarlos, indicar al compilador, dónde está/n ubicado/s y saber de que funcionalidades dispone y que sintaxis hay que emplear.

23

Internet es una fuente casi inagotable donde obtener este tipo de recursos.



Módulos desarrollados por el propio programador almacenados como ficheros independientes de la aplicación principal. A todos los efectos su funcionamiento es análogo al caso de los módulos externos24. Módulos desarrollados por el propio programador y almacenados junto con la aplicación principal25 en un único fichero. Existen varias alternativas tecnológicas a la hora de gestionar la memoria del ordenador cuando ejecuta una aplicación concebida en forma modular. La más sencilla es la que aparece ilustrada en la figura siguiente. Memoria libre Zona de datos

Zona de algoritmo

Subprograma (módulo) Zona de datos

>

---------------------

---------------------

Programa principal

Figura 1.5. Gestión de la memoria en programas modulares-. Este tipo de gestión de memoria se denomina estática26 porque durante todo el tiempo de ejecución tanto el programa principal como la totalidad de módulos están cargados en memoria, alojados en espacios independientes. A su vez, cada uno de los espacios se subdivide en otros dos: zona de datos y zona de algoritmo (la parte de código -previamente traducido a lenguaje de máquina-). La ejecución del conjunto tiene lugar a partir de la primera instrucción del programa principal. Cuando se llega a una se suspende y se pasa al contexto del

24

La mayoría de entornos de programación modernos contemplan el concepto de proyecto en donde se indica el conjunto de módulos que configuran el sistema y sus ubicaciones. En el curso, dado su carácter básico, no utilizaremos esta posibilidad. 25 Se entiende por aplicación principal a la parte de código (generalmente poco extensa) que utiliza (llama o invoca) los diferentes módulos funcionales. 26 Las alternativas más evolucionadas son de naturaleza dinámica: el bloque correspondiente al programa principal está permanentemente en memoria mientras que los subprogramas se cargan cuando se necesitan y al finalizar su ejecución se libera la memoria ocupada. No obstante esta técnica es la única posible cuando se utiliza el tratamiento recursivo (ver apartado 1.2.5.5)



subprograma, hasta que finalice su ejecución, a partir de entonces se reanuda la ejecución del programa principal en el punto en que quedó suspendida. 1.3.3. Mecanismos para el paso de información27. Cuando un programa llama a un módulo deberá utilizar un nombre que lo identifique y, además, “pasarle” los datos que necesite. El conjunto de estos datos se denomina genéricamente parámetros o argumentos y se expresa mediante las correspondientes variables y su tipo. Existen dos modalidades de paso de argumentos: Por valor. La variable del subprograma recibe inicialmente una copia del valor almacenado, en el momento de producirse la llamada, en el módulo principal. Durante su ejecución (del subprograma) podrá modificarlo pero una vez que finalice, el programa principal conserva intacto su valor. En Java todos los tipos primitivos (números enteros, reales, caracteres y booleanos) se pasan siempre por valor. Por referencia. En este caso no existe tal variable en el ámbito del subprograma. El mecanismo consiste en que el módulo principal permite al subprograma actuar sobre sus propias variables. En consecuencia, cualquier modificación que se realice en una variable pasada por referencia tendrá efecto en el contexto del programa (módulo) principal. En Java todos los datos que no sean de un tipo primitivo se pasan por valor, pero al ser referencias, los datos en sí pueden cambiar (pero no la posición de memoria en la que están guardados). Además hay que considerar los siguientes aspectos: Un subprograma puede declarar sus propias variables locales28. Es posible, pero no recomendable29 (salvo contadas excepciones), declarar una variable como accesible para el programa principal y la totalidad de los subprogramas30. Este tipo de variables se denominan globales31.

27

Lo que se explica en el apartado debe entenderse con carácter general. El lenguaje Java solo ite el paso de argumentos por valor. Esta afirmación es extensiva al caso de que el argumento sea un objeto (por ejemplo, un vector) dado que lo que se pasa como argumento por valor es un puntero (referencia) a dicho objeto que no puede ser modificado por el módulo subordinado (aunque sí el propio objeto). 28 No hay ningún inconveniente en que dos variables locales de módulos diferentes tengan el mismo nombre. 29 Una modificación de una variable global realizada por un módulo afectará al resto. 30

En este caso si habría ambigüedad en caso de coincidencia de nombres de una variable local y otra global. Esto no supone ningún error de compilación y la ejecución podría producir resultados no esperados (ni deseados). 31 No tiene sentido pasar como argumentos variables globales. Ya están accesibles desde todos los módulos.



Que el programa “funcione” (correctness) es una condición necesaria, pero no suficiente. Existen otros criterios: eficiencia, seguridad, fiabilidad, mantenibilidad, legibilidad, productividad, posibilidad de desarrollo en equipo, etc. En la Ingeniería del Software, debe prestarse atención especial al uso correcto y eficiente de los datos (la información) tanto o más que al código (algoritmo). A continuación se indican algunas recomendaciones en este sentido. Protección de la información: evitar el uso de variables globales. Eficiencia: no pasar más argumentos que los estrictamente imprescindibles. Productividad / mantenibilidad: dotar a los subprogramas de la mayor autonomía posible (no pasar argumentos que se puedan obtener en el contexto del propio subprograma).

1.3.4. Aplicación al lenguaje Java. Lo que en otros lenguajes se llama función o procedimiento, en Java se llama método. La cabecera de un método consiste en un nombre, una lista de parámetros (que puede ser vacía), y el tipo de resultado (si no devuelve resultado, el método será de tipo void). La sintaxis (cabecera o prototipo) en Java es: <nombre del método> (<lista de argumentos>)

Siendo la sintaxis de <lista de argumentos> la siguiente: <argumento1>, <argumento2>, ...

Los nombres de los argumentos son formales. No tienen por qué coincidir con los nombres reales de las variables utilizadas en la llamada al método32. El compilador solo verifica que las listas de argumentos empleadas en la llamada (reales) y en la cabecera (formales) coinciden en número, tipo y orden. Las sintaxis de las llamadas es similar a la de las cabeceras, si bien en este caso se utiliza una versión “reducida” de la <lista de argumentos> en la que solo aparecen sus nombres (reales), separados por comas. El método está delimitado por las llaves de inicio y fin de bloque ({ y }), y a continuación aparece la declaración de variables locales del subprograma y el algoritmo. Los métodos que no sean de tipo void deben acabar con la siguiente sentencia: return ;

(siendo el nombre de una variable local en donde se recoge el resultado generado por el método). De esta forma el método “devuelve” el resultado generado al módulo de llamada. Si el método es de tipo void, se puede prescindir de la instrucción return, o utilizarla sin ninguna variable asociada (return;).

32

El hacerlo así permite que los subprogramas sean reutilizables.



Dado que el lenguaje Java solo ite el paso de argumentos por valor no es posible que el modulo subordinado modifique una variable del módulo de llamada (salvo que se trate del valor devuelto por el método). En tales situaciones optamos por crear una clase estática que declare dicha variable como global de la clase (lo que no contraviene la recomendación general de no utilizar variables globales)33 por lo que carecería de sentido pasarla como argumento. Como consecuencia de la utilización de la técnica de subprogramación, el esquema de estructura general de un programa en Java visto en la sección 1.2.1 queda ampliado tal como se muestra a continuación. Sintaxis import <nombre> public class <nombre de la clase general> {

Semántica Llamada a una (o varias) componente(s) de la “biblioteca”. Nombre de la clase general (obligatorio) Principio de la clase.

<nombre del método1> (<lista de argumentos>) { .... return [ ]; } <nombre del método1> (<lista de argumentos>)

Cabecera del método 1 Inicio del método 1 sentencias del método 1

fin del método 1 Cabecera del método 2 Inicio del método 2

{ ....

sentencias del método 2

return [ ];

fin del método 2

...... public static void main (String [ ] args) {

Declaración del programa principal Inicio del programa principal

sentencias del programa principal } }

Fin del programa principal. Fin de la clase.

Tabla 1.5. Estructura de un programa en Java.

33

Algunos programadores optan por la alternativa de declarar dicha variable como vector (objeto) y pasar el puntero (referencia) correspondiente como argumento (por valor).



1.3.4.1. Ejemplo. El siguiente programa pide al una serie de cinco números enteros y muestra por la pantalla dos de sus estadísticas: valor medio y rango. import java.io.*; public class PruebaMetodos { static float media (int dato1, int dato2, int dato3, int dato4, int dato5) { float resul; resul = (dato1 + dato2 + dato3 + dato4 + dato5) / 5; return resul; } static int max (int dato1, int dato2, int dato3, int dato4, int dato5) { int resul; resul=dato1; if (dato2 > resul) resul = dato2; if (dato3 > resul) resul = dato3; if (dato4 > resul) resul = dato4; if (dato5 > resul) resul = dato5; return resul; } static int min (int dato1, int dato2, int dato3, int dato4, int dato5) { int resul; resul = dato1; if (dato2 < resul) resul = dato2; if (dato3 < resul) resul = dato3; if (dato4 < resul) resul = dato4; if (dato5 < resul) resul = dato5; return resul; } public static void main(String[] args) throws NumberFormatException,IOException{ int d1, d2, d3, d4, d5, rango; float media; BufferedReader linea = new BufferedReader(new InputStreamReader(System.in)); System.out.println ("Introduce cinco números enteros: "); d1 = Integer.parseInt (linea.readLine ()); d2 = Integer.parseInt (linea.readLine ()); d3 = Integer.parseInt (linea.readLine ()); d4 = Integer.parseInt (linea.readLine ()); d5 = Integer.parseInt (linea.readLine ()); media = media (d1, d2, d3, d4, d5); System.out.println("El valor medio es: " + media); rango = max (d1, d2, d3, d4, d5) - min (d1, d2, d3, d4, d5); System.out.println ("y el rango: " + rango); } }



1.3.5. Recursividad. 1.3.5.1. Concepto. Se define objeto recursivo como: “aquel que forma parte de sí mismo o que forma parte de su propia definición”. La recursividad es un concepto matemático que permite formular definiciones como, por ejemplo, la de número natural: o El 1 es un número natural. o El siguiente de un número natural es un número natural. Otro ejemplo sería la definición de factorial de número natural: o 0! = 1; o N > 0, N! = N * (N-1)! 1.3.5.2. Aplicación del concepto de recursividad en programación. Los ejemplos anteriores se pueden implementar mediante programas informáticos que proporcionan un método sencillo, útil y potente de resolución de infinidad de problemas. De hecho, hay algunos cuya solución no recursiva sería de elevada complejidad y escasa eficiencia34. Frente a las ventajas indicadas (robustez y legibilidad) de la recursividad frente al tratamiento iterativo se contrapone el inconveniente del mayor consumo de memoria, por las razones que se explican a continuación. La recursividad en programación se obtiene mediante subprogramas que se llaman a sí mismos (es decir, una de las sentencias del cuerpo del subprograma coincide con el nombre del mismo), no obstante sería más correcto decir que llama a otra copia (instancia) del mismo, esa copia a otra nueva y así sucesivamente hasta que se alcanza una condición denominada de terminación o de parada. Una vez que se alcanza la condición de terminación, en la instancia n-ésima se retorna (como en todo subprograma) al punto del modulo de llamada de la instancia previa desde donde ésta se realizó, y así sucesivamente, teniendo lugar una fase de “vuelta” por las instancias anteriores, hasta llegar al punto del programa principal en que se produjo la llamada al subprograma recursivo. La implementación en ordenador de algoritmos recursivos requiere una tecnología dinámica, diferente a la estática (explicada en el apartado 1.3.2), dado que no se sabe, a priori, cuantas instancias se van a necesitar. Durante la fase de “ida” se cargan en la memoria nuevas copias del subprograma35 hasta alcanzar la terminación (fase de

34

Un ejemplo en este sentido sería el clásico algoritmo denominado “Torres de Hanoi”. En caso de un número elevado de llamadas recursivas es posible quedarse sin espacio libre en memoria y se produce un error en tiempo de ejecución (StackOverflowError). 35



“transición”). Por el contrario, durante la fase de “vuelta” se “libera” la memoria correspondiente a cada instancia a medida que finaliza su ejecución (ejecuta el código de retorno). En el ejemplo siguiente el programa principal llama a un método recursivo que devuelve el factorial de un número natural introducido por el teclado. import java.io.*; public class PruebaRecursividad { static int factorial (int dato) { int resul = 1; if (dato > 0) resul = dato * factorial (dato - 1); return resul; } public static void main(String[] args) throws NumberFormatException,IOException{ int d, f; BufferedReader linea = new BufferedReader (new InputStreamReader(System.in)); System.out.print("Introduzca el dato: "); d = Integer.parseInt (linea.readLine ()); if (d >= 0) { f = factorial(d); System.out.println("El factorial de " + d + " es: " + f); } else System.out.println("No existe el factorial de un número negativo"); } }

Explicación: El programa principal llama al subprograma factorial y le pasa como argumento la variable d. Cuando éste termine de ejecutarse, el programa de llamada dispondrá de un resultado que podrá mostrar por la pantalla. El subprograma factorial es recursivo. o

Su condición de terminación es dato == 0. En la instancia en que se alcance36 (“transición”) devolverá el valor 1.

o

Durante la fase de “ida”, la ejecución de cada instancia consiste en multiplicar el valor del argumento recibido desde la instancia anterior (salvo la primera, que lo recibe directamente del programa principal) por el factorial del número anterior (factorial(N-1)). La ejecución de esa instancia queda suspendida hasta que se le devuelva el valor solicitado.

o

En la fase de “vuelta” cada instancia:  Multiplica el valor devuelto por la instancia siguiente por el que, en su momento de la fase de “ida”, recibió como argumento,

36

Su número de orden será uno más que el dato cuyo factorial se quiere calcular.



 almacena el resultado en la variable local resul,  devuelve el contenido de resul a la instancia anterior (sentencia factorial = resul) y  termina su ejecución con „}‟ (Se libera la memoria correspondiente). o

Observe que la palabra dato tiene dos significados en el código del subprograma recursivo:  En la llamada factorial (dato-1) se trata de una variable real. Lo que se pasa como argumento es el valor actual decrementado en una unidad.  En la declaración del subprograma static int factorial (int dato) es una variable formal, debe interpretarse como: “lo que se reciba”.

1.3.5.3. Consideraciones complementarias. Terminación anticipada. La condición de terminación la entendemos como “pesimista” en el sentido de se alcanza cuando se han invocado todas las instancias posibles. No obstante en determinadas circunstancias se puede producir37 una terminación anticipada. En tal caso lo que se debe “hacer” es no realizar nuevas llamadas recursivas. Utilización de módulos de llamada En determinadas ocasiones, el subprograma recursivo requiere el uso de argumentos adicionales, difíciles de imaginar desde el programa principal. En estos casos la solución recomendada es utilizar un subprograma no recursivo (que es el que se llama desde el módulo principal) encargado de “preparar” los argumentos adicionales necesarios y, a continuación, llamar al subprograma recursivo. Momentos de realización del proceso e implicación en la modalidad del paso de argumentos. La ejecución de la lógica del algoritmo puede realizarse en cualquiera de las fases del tratamiento recursivo (“ida”, “transición” o vuelta”) o distribuido en varias de ellas. Recursividad indirecta. Si tenemos dos subprogramas A y B, se utiliza la recursividad indirecta cuando el subprograma A contiene una referencia al subprograma B, y a su vez el subprograma B contiene una referencia al A, como se puede ver en el siguiente esquema: static void A () { <sentencia 1>; <sentencia 2>; B (); ... <sentencia n>; }

37

static void B () { <sentencia 1>; ... A (); ...... <sentencia m>; }

En algunos casos la terminación anticipada es necesaria para el correcto funcionamiento del programa mientras que en otros, aunque el “programa funcione” se debe usar por consideraciones de eficiencia.



1.3.5.4. Ejemplos. Ejemplo 1. (Utilización de un módulo de llamada). El programa que se muestra a continuación utiliza un método que obtiene la suma de los divisores de un número natural. Por ejemplo: la suma de los divisores de 40 (2, 4, 5, 8, 10, 20) es 49. import java.io.*; public class Recursividad1 { static int sumaDivisores (int dato, int presuntoDivisor) { int resul = 0; if ((presuntoDivisor*2) <= dato) { resul = sumaDivisores (dato, presuntoDivisor+1); if ((dato % presuntoDivisor) == 0) resul = resul + presuntoDivisor; } return resul; } static int sumaDivisores (int dato) { return sumaDivisores (dato, 2); } public static void main(String[] args) throws NumberFormatException,IOException{ int d, suma; BufferedReader linea = new BufferedReader (new InputStreamReader(System.in)); do { System.out.print ("Introduzca un número mayor que cero: "); d = Integer.parseInt (linea.readLine ()); } while (d <= 0); suma = sumaDivisores (d); System.out.print ("La suma de los divisores de " + d + " es " + suma); } }

El diseñador del programa principal no tiene por qué saber que se necesitan otros argumentos adicionales al dato (d), sin embargo, el subprograma recursivo realmente necesita otro argumento (presuntoDivisor, de tipo entero), para probar recursivamente desde 2 hasta d/2 y controlar la terminación (“pesimista”). Ejemplo 2. (Terminación anticipada). El siguiente ejemplo consiste en una función booleana (esPrim) que indica si un número (d) que se introduce desde el teclado es primo (true) o no (false). La condición de terminación “pesimista” es d >

dato

.

En cada instancia, (fase de “ida”) se prueba si presuntoDivisor es divisor de dato. En caso afirmativo dato no es primo y se produce terminación anticipada con resultado false, en caso contrario se realiza una llamada recursiva incrementando una unidad el argumento presuntoDivisor. Si se llega a alcanzar la condición de terminación “pesimista” significa que el número (d) es primo y la función devuelve true.



A continuación se muestra una posible implementación. import java.io.*; public class Recursividad2 { static boolean esPrim (int dato, int presuntoDivisor) { boolean resul; if ((presuntoDivisor*presuntoDivisor) <= dato) if ((dato % presuntoDivisor) != 0) resul = esPrim (dato, presuntoDivisor+1); else resul = false; else resul = true; return resul; } static boolean esPrimo (int dato) { boolean resul; resul = esPrim (dato, 2); return resul; } public static void main(String[] args) throws NumberFormatException,IOException{ int d; BufferedReader linea = new BufferedReader (new InputStreamReader(System.in)); do { System.out.print("Introduzca un número mayor que cero: "); d = Integer.parseInt (linea.readLine()); } while (d <= 0); if (esPrimo(d)) System.out.println(d + " es primo"); else System.out.println (d + " no es primo"); } }

Ejemplo 3. (Proceso en la fase de “vuelta”). En el siguiente ejemplo se desarrolla un método que devuelve: o La suma de la primera mitad (los más pequeños) de los factores primos de un número (d). si el número total de factores primos es par. Por ejemplo, el número 420 tiene un número par (4) de factores primos (2, 3, 5, 7). El método devolverá 5 (2+3). o La suma de la segunda mitad (los más grandes) de los factores primos de un número (d), si el número total de factores primos es impar. Por ejemplo, el número 2310 tiene un número impar (5) de factores primos (2. 3, 5, 7, 11). La función devolverá 18 (7+11). Para poder comprobar a la vuelta el número de factores primos, sería necesario pasar la variable que represente el número de factores por referencia. Como el valor es entero, y en Java no es posible pasar tipos primitivos por referencia, crearemos una clase (Suma), dentro de la cual se utiliza la variable miembro numeroFactores (global dentro de dicha clase, pero no accesible al resto de métodos). En la llamada al método sumaPrimosCondicionada desde el programa principal, es necesario indicar que pertenece a la clase Suma (haciendo la llamada: Suma.sumaPrimosCondicionada (d)). A continuación se muestra el código.



import java.io.*; public class Recursividad3 { static boolean esPrim (int dato, int presuntoDivisor) { boolean resul; if ((presuntoDivisor*presuntoDivisor) <= dato) if ((dato % presuntoDivisor) != 0) resul = esPrim (dato, presuntoDivisor+1); else resul = false; else resul = true; return resul; } public static class Suma { static int numeroFactores = 0; //variable global de la clase Suma static int sumaPrimos (int dato, int presuntoPrimo) { int resul, orden; if ((presuntoPrimo * 2) <= dato) if ((dato % presuntoPrimo) == 0) if (esPrim (presuntoPrimo, 2)) { numeroFactores= numeroFactores + 1; orden = numeroFactores; resul = sumaPrimos(dato, presuntoPrimo + 1); if ((numeroFactores% 2) == 0) { if (orden <= (numeroFactores / 2)) resul = resul + presuntoPrimo; } else { if (orden > ((numeroFactores / 2) + 1)) resul = resul + presuntoPrimo; } } else resul = sumaPrimos (dato, presuntoPrimo + 1); else resul = sumaPrimos (dato, presuntoPrimo + 1); else resul = 0; return resul; } static int sumaPrimosCondicionada (int dato) { int resul; resul = sumaPrimos (dato, 2); return resul; } } public static void main(String[] args) throws NumberFormatException,IOException{ int d, suma; BufferedReader linea = new BufferedReader (new InputStreamReader(System.in)); do { System.out.print("Introduzca un número mayor que cero: "); d = Integer.parseInt (linea.readLine()); } while (d <= 0); suma = Suma.sumaPrimosCondicionada (d); System.out.println ("El resultado es: " + suma); } }

En este caso, el proceso no puede realizarse completamente durante la fase de “ida”, dado que hasta la “transición” no se conocerá el número total de factores



primos, por lo que no se sabe qué hay que sumar. La parte de proceso que se realiza en ella consiste en: o Identificar si un número (argumento presuntoPrimo, pasado por valor) es primo y factor de d.  En caso negativo se realiza una nueva llamada recursiva con presuntoPrimo+1.  En caso afirmativo: Se contabiliza en la variable numeroFactores global dentro de la clase Suma, inicializado a 0 (pues se utilizará su valor final en la fase de “vuelta”). Se “toma nota” del número de orden (orden) del factor primo encontrado (variable local que recoge el valor actual de numeroFactores)38. NOTA IMPORTANTE: Evitar el error de “intentar” pasar a la siguiente instancia el valor de una variable local.

El proceso de la fase de “vuelta” está condicionado por el lugar desde el que se hizo la llamada recursiva: o Si se hizo en una instancia correspondiente a un valor de presuntoPrimo que no era factor primo, simplemente se retorna el valor recibido desde la instancia siguiente hacia la anterior39. o

En caso contrario:  Se recibe el valor devuelto por el método desde la instancia siguiente (resul).  Si el valor de orden se encuentra dentro del rango adecuado (primeros o últimos, según proceda) se suma al valor de resul el de presuntoPrimo.  Se devuelve el resultado a la instancia anterior.

38

En las instancias correspondientes a valores de presuntoPrimo que no son factores primos el valor de la variable orden es aleatorio 39 Vamos “marcha atrás”.



Ejemplo 4. (Recursividad indirecta). En el siguiente ejemplo, se desarrollan los métodos esPar y esImpar que utilizan la recursividad indirecta para indicar si el número que se recoge del teclado es par o impar. import java.io.*; public class RecursividadIndirecta { static boolean esPar (int n) { boolean resul = true; if (n != 0) resul = esImpar (n - 1); return resul; } static boolean esImpar (int n) { boolean resul = false; if (n != 0) resul = esPar (n - 1); return resul; } public static void main (String [ ] args) throws IOException { int n; boolean esPar; BufferedReader linea = new BufferedReader (new InputStreamReader (System.in)); System.out.print ("Escriba un número para saber si es par o impar: "); n = Integer.parseInt (linea.readLine ()); esPar = esPar (n); if (esPar) System.out.println ("El número " + n + " es par"); else System.out.println ("El número " + n + " es impar"); }



1.4. ESTRUCTURAS DE DATOS. Una estructura de datos es una agrupación de éstos que se trata como una unidad en su conjunto. Se construyen a partir de los tipos de datos simples, vistos en la sección 1.2.3.1. Las estructuras de datos pueden ser homogéneas (todos los datos son del mismo tipo) o heterogéneas (constituidas por datos de tipos diferentes). Las estructuras de datos homogéneas más representativas son los vectores, las tablas y, en general, las matrices n-dimensionales. El ejemplo más representativo de estructuras de datos heterogéneas son los registros Desde otro punto de vista puede hablarse de estructuras de datos estáticas y dinámicas. Una estructura estática se caracteriza porque su tamaño es conocido a priori (antes de la ejecución del programa). En consecuencia, en el código del programa se declaran variables de tipo estático y en la compilación se reserva en memoria el espacio necesario para ellas. Por el contrario, las estructuras de datos dinámicas no tienen un tamaño predefinido y la memoria utilizada para almacenarlas se reserva o libera, en tiempo de ejecución, según se requiera. 1.4.1. Estructuras de datos dinámicas Se dice que una estructura de datos es dinámica cuando inicialmente (en el momento de la compilación) no tiene espacio asignado para almacenar información. Durante la ejecución del programa el sistema (en tiempo de ejecución, run time) asigna y libera espacio en memoria, en función de las necesidades. Los temas 3 (Listas), 4 (Árboles) y 5 (Grafos) describen distintos tipos de Estructuras de Datos Dinámicas. En algunos lenguajes de programación, para permitir la implementación de estructuras de datos dinámicas es necesario un tipo de datos especial, denominado puntero (pointer). El concepto de puntero (pointer) hace referencia a una variable cuyo contenido es la dirección de otra variable (nodo) que realmente contiene el propio dato que se emplea en el programa40.

40

Este concepto toma su e físico en el mecanismo de direccionamiento indirecto tal como se maneja en los lenguajes de bajo nivel.



La figura 1.6. muestra un modelo de funcionamiento.

Variable de trabajo (apuntada por puntero)

puntero

Memoria dinámica

Memoria estática

Figura 1.6. Punteros y variables de trabajo. El interés del uso de punteros en lenguajes de programación de alto nivel reside en que constituyen la base para la generación de estructuras de datos dinámicas. Esto es, que a lo largo de la ejecución de un programa, y como consecuencia de las sucesivas operaciones de inserción y eliminación, el sistema en tiempo de ejecución (run time) reserva y libera respectivamente unidades (nodos) de una región de memoria destinada a uso dinámico (a diferencia de la que se reserva en el momento de la compilación que contiene el código máquina y el espacio requerido por las variables estáticas). Este espacio (estático) se mantiene inalterado durante toda la ejecución del programa. La utilización de esta posibilidad requiere que el lenguaje de programación disponga de operaciones que soliciten (de forma transparente al programador) espacio en la memoria dinámica para crear nuevos nodos, así como la contraria, para liberar espacio correspondiente a nodos que ya no se necesitan y poder disponer, en consecuencia, de dicho espacio para uso posterior. En Java se utiliza la sintaxis: = new ;

para crear un nodo

La variable puntero (en Java se denominan referencias), se almacena en la memoria estática y su tamaño es fijo. No así los nodos que pueden ser de diferente naturaleza. Es decir que en la declaración de un nodo debe hacerse referencia al tipo de dato al que apunta para que cuando se cree un nodo se reserve con el tamaño necesario. Por ejemplo, al ejecutar el código en Java: char [ ] puntVector = new char [100];

se declara una variable (puntVector) de tal forma que, al realizar la operación new se reserve el espacio necesario para almacenar un vector de 100 caracteres. Además de la operación ya indicada de reserva (new), las referencias iten las siguientes operaciones:



○

Asignación: = . La referencia se copia en , o dicho en otros términos: deja de apuntar al nodo a que apuntaba previamente para pasar a apuntar al nodo apuntado por . Una vez ejecutada la operación ambos punteros apuntan al mismo nodo41.

○

Comparación: == . Devuelve un valor booleano en función de que ambas referencias sean iguales o no, o dicho en otros términos: que apunten o no al mismo nodo.

Aunque, como se ha indicado, una variable de tipo puntero apunta a una zona de memoria (nodo) existe una situación excepcional consistente en no apuntar a ninguno. En Java se utiliza para esto la constante null. Sobre las variables referencia, se realizan las operaciones propias del tipo de datos a que pertenezcan.

41

Este tipo de operaciones deberá hacerse con especial cuidado pues, si no se han tomado previamente las precauciones oportunas, podría perderse la información almacenada en el nodo inicialmente apuntado por (se perderá si no tenemos otra referencia a esa información)



1.4.2. Estructuras de datos estáticas. Una estructura estática se caracteriza porque su tamaño es conocido a priori (antes de la ejecución del programa). En consecuencia, en el código del programa se declaran variables de tipo estático y en la compilación se reserva en memoria el espacio necesario para ellas. 1.4.2.1. Estructuras de datos homogéneas. En las estructuras de datos homogéneas todos los datos son del mismo tipo. Como ejemplo veremos los vectores, las tablas y, en general, las matrices n-dimensionales. 1.4.2.1.1. Unidimensionales (vectores). El caso más sencillo es el vector, que se define como un conjunto de elementos, cada uno de los cuales puede identificarse mediante su posición relativa (índice42). La figura muestra un ejemplo de vector de 5 números enteros. 0

1

2

3

4

20

40

60

80

100

Tabla 1.6. Vector de números enteros. El lenguaje Java permite utilizar este tipo de estructuras utilizando la sintaxis43:

Declaración de variables de tipo vector: [] <nombre de la variable>;

Por ejemplo, la línea:

int [] vector1;

Declara una variable llamada vector1 que es un vector de enteros inicialmente vacío. Para indicar el tamaño del vector, se puede hacer directamente en la propia línea de declaración: Int [] vector1 = new int [5];

//declara un vector de 5 elementos de tipo entero.

: o Al conjunto. Por ejemplo asignar un vector a otro del mismo tipo: vector2 = vector1.

En realidad esta instrucción no copia el contenido de vector1 en vector2, sino que hace que vector2 apunte a la misma posición de memoria en la que está el vector1. o A un elemento del vector: [<índice>];

42

En Java el índice es numérico y siempre comienza en 0. Se describen solamente las operaciones básicas. El manejo de este tipo de estructuras ite una gran flexibilidad. Consultar el manual del lenguaje para mayor información. 43



Con lo que se podrá realizar cualquier operación acorde con el tipo del elemento correspondiente. Por ejemplo, si datos es un vector de números enteros podríamos hacer: datos [3] = datos [3] * 2;

Ejemplo. A continuación se retoma el ejemplo expuesto en el apartado 1.3.4.1 (valores medio y rango de un conjunto de 5 números enteros) utilizando un vector. import java.io.*; public class PruebaVectores { static float media (int [ ] dato) { float resul = 0; int i; for (i = 0; i < 5; i ++) resul = resul + dato [i]; resul = resul / i; return resul; } static int max (int [] dato) { int resul,i; resul = dato[0]; for (i = 1; i<5; i++) if (dato[i] > resul) resul = dato[i]; return resul; } static int min (int [] dato) { int resul,i; resul = dato[0]; for (i = 1; i < 5; i ++) if (dato [i] < resul) resul = dato [i]; return resul; } public static void main(String [] args)throws NumberFormatException,IOException{ int [ ] d = new int [5]; int i, rango; float media; BufferedReader linea = new BufferedReader(new InputStreamReader(System.in)); System.out.println ("Introduce cinco números enteros: "); for (i = 0; i < 5; i ++) d[i] = Integer.parseInt (linea.readLine ()); media = media (d); System.out.println ("El valor medio es: " + media); rango = max (d) - min (d); System.out.println ("y el rango: " + rango); } }



1.4.2.1.2. Bidimensionales (matrices). Una matriz es una estructura de dos dimensiones: horizontal (filas) y vertical (columnas), que contiene elementos del mismo tipo. Se puede hacer referencia a cada uno de los elementos (celdas) mediante un índice de fila y otro de columna. Por ejemplo, la tabla siguiente (temperaturas) muestra las temperaturas máxima y mínima a lo largo de una semana (las filas indican el día de la semana y las columnas las temperaturas mínima y máxima, respectivamente. Por ejemplo, la temperatura mínima del 4º día es: temperaturas (3, 0) = 5 grados). temperaturas

0

1

0

7 8 6 5 7 6 5

15 17 13 14 14 16 13

1 2 3 4 5 6

Tabla 1.7. Temperaturas a lo largo de una semana Los lenguajes de programación permiten utilizar este tipo de estructuras. Para ésto en Java se emplea la siguiente sintaxis: Declaración de variables de tipo matriz: < tipo de datos de los elementos > [ ] [ ] <nombre de la variable>;

Ejemplo: int [ ] [ ] temperaturas; : o Al conjunto. Por ejemplo asignar una matriz a otra del mismo tipo: matriz2 = matriz1.

Como en el caso de los vectores, esta instrucción no copia el contenido de matriz1 en matriz2, sino que hace que matriz2 apunte a la misma posición de memoria que matriz1. o A un elemento de la matriz: [<índice1>] [<índice2>];

(Con lo que se podrá realizar cualquier operación acorde con el tipo del elemento correspondiente). Por ejemplo: temperaturas [3] [1] = temperaturas [3] [1] + 2; Ejemplo. El siguiente código permite encontrar la temperatura mínima de la semana y el día en que se produjo la máxima diferencia (en caso de coincidencia de varias se muestra el primero de ellos). En el ejemplo anterior los resultados serían: Temperatura mínima: 5 grados. Día de máxima diferencia de temperaturas: 5 (10 grados).



import java.io.*; public class PruebaMatrices { static BufferedReader linea=new BufferedReader(new InputStreamReader(System.in)); public static void leerMatriz (int [][] temperaturas) throws NumberFormatException, IOException{ int i,j; for (i = 0;i < 7; i ++) for (j = 0; j < 2; j ++) { System.out.println ("Valor dia: " + i + " extremo: " + j + ": "); temperaturas [i] [j] = Integer.parseInt (linea.readLine ()); } } public static int min (int [][] temperaturas) { int resul, i; resul = temperaturas [0] [0]; for (i = 1; i < 7; i++) if (temperaturas [i] [0] < resul) resul = temperaturas [i] [0]; return resul; } public static int maxDif (int [] [] temperaturas) { int resul, i, dif; resul = 0; dif = temperaturas [0][1]- temperaturas [0][0]; for (i = 1; i < 7; i++) { if (temperaturas [i][1] - temperaturas [i][0] > dif) { dif = temperaturas [i][1] - temperaturas [i][0]; resul = i; } } return resul; } public static void main(String[] args) throws NumberFormatException, IOException{ int [][] temperaturas = new int [7][2]; int minimaTemperatura, diferenciaTemperaturas; leerMatriz (temperaturas); minimaTemperatura = min (temperaturas); diferenciaTemperaturas = maxDif (temperaturas); System.out.println ("Resultados:"); System.out.println ("Temperatura minima: " + minimaTemperatura); System.out.println ("Dia extremo: " + diferenciaTemperaturas); } }



1.4.2.1.3. N-dimensionales. Por extensión, lo explicado para una y dos dimensiones se puede aplicar al caso de matrices N-dimensionales. 1.4.2.2. Estructuras de datos heterogéneas. Como ya se ha indicado, están constituidas por un conjunto de tipos de datos (ya sean datos simples u otras estructuras de datos) de diferente naturaleza. La forma básica de estructura de datos heterogénea es el registro cuyos elementos se llaman campos (o atributos)44. Por ejemplo, la figura siguiente muestra un registro (alumno) cuyos campos son: el número de matrícula (numeroMatricula), apellidos (apellidos), nombre (nombre), dirección de correo electrónico (eMail), año de nacimiento (anio) y calificación (calificacion).

alumno

numeroMatricula

apellidos

nombre

eMail

año

calificacion

bc2658

Sánchez Arellano

Estela

[email protected]

1987

6.75

Tabla 1.8. Registro alumno Para manejar este tipo de estructuras en Java45, se construye una clase dentro de la cual se definen los datos que van a formar parte de la estructura, así como uno o varios constructores, como se puede ver en el siguiente ejemplo (correspondiente a la figura): class RegistroAlumno { public public public public public public

String numeroMatricula; String apellidos; String nombre; String eMail; int año; float calificacion;

public RegistroAlumno (){ numeroMatricula= null; apellidos = null; nombre = null; eMail= null; año = 1980; calificacion = 0; }

44

Con frecuencia uno de los campos (o combinación de ellos) se utiliza como identificativo del registro. A dicho campo (o conjunto) se le denomina clave (key). 45 Existen otras operaciones. Consultar el manual del lenguaje.



: o Al conjunto. Por ejemplo apuntar con una variable de tipo registro mismo sitio que apunta otra del mismo tipo: variable2_RegistroAlumno = variable1_RegistroAlumno;

o A un campo del registro: . ;

Con lo que se podrá realizar cualquier operación acorde con el tipo del elemento correspondiente. Por ejemplo: alumno.eMail = “ [email protected]”; Normalmente, el trabajo con un registro (o con un conjunto pequeño de variables independientes de tipo registro) ofrece “poco juego”. Lo habitual es utilizar una “colección” de registros estructurados en un vector, o mucho mejor, almacenarlos, como un “fichero” en un dispositivo de almacenamiento externo (típicamente disco). La utilización de ficheros en dispositivos de almacenamiento externos se explica en el apartado 1.5. A continuación se muestra un ejemplo que utiliza un vector de registros del tipo anterior cuyo modelo se ilustra gráficamente en la figura siguiente: 0 1 2 3 4 5

numeroMatricula

apellidos

nombre

eMail

año

calificacion

aa1253 ax0074 mj7726 lp1523 bc2658 gb1305

Arias González García Sacedón López Medina Ramírez Heredia Sánchez Arellano Yuste Peláez

Felipe Manuel Margarita Jorge Estela Juan

[email protected] [email protected] [email protected] [email protected] [email protected] [email protected]

1988 1985 1990 1998 1989 1990

3.50 8.35 7,70 4,50 6.75 5,50

Tabla 1.9. Vector de registros. El programa que se muestra a continuación se ha incluido en dos ficheros (clases) que forman parte del mismo paquete (package): RegistroAlumno, que contiene el constructor del registro (construye un registro vacío), así como los métodos aCadena, que devuelve el contenido del registro en un String, y cargarRegistro, que introduce los datos recogidos por teclado en un registro. PruebaRegistro, en el que aparece el programa principal e incluye dos métodos, cargarTabla, que permite cargar la estructura en la memoria central y mediaCalif, que utiliza la estructura anterior para calcular la calificación media. Primero se muestra la clase RegistroAlumno:



Import java.io.*; class RegistroAlumno { public RegistroAlumno () { numeroMatricula= null; apellidos = null; nombre = null; eMail= null; año = 1980; calificacion = 0; } public String aCadena () { return numeroMatricula + " " + apellidos + " " + nombre + " " + eMail + " " + año + " " + calificacion; } public String numeroMatricula; public String apellidos; public String nombre; public String eMail; public int año; public float calificacion; public void cargarRegistro () throws IOException { BufferedReader linea = new BufferedReader (new InputStreamReader (System.in)); System.out.println ("Numero de matricula: "); numeroMatricula = new String (linea.readLine ()); System.out.println ("Apellidos: "); apellidos = new String (linea.readLine ()); System.out.println ("Nombre: "); nombre = new String (linea.readLine ()); System.out.println ("Correo electronico: "); eMail = new String (linea.readLine ()); System.out.println ("Año de nacimiento: "); año = Integer.parseInt (linea.readLine()); System.out.println ("Calificación: "); calificacion = Float.parseFloat (linea.readLine()); System.out.println (this.aCadena ()); } }

Como se ha visto en el apartado 1.2.4., los métodos aCadena y cargarRegistro son métodos de objeto (sin modificador static), y para utilizarlos desde fuera de la clase tendrá que hacerse de la forma <nombreVariable>.<nombreMétodo>. Para poder utilizar los métodos de objeto, es necesario que previamente hayamos utilizado el constructor del objeto sobre la variable correspondiente, como hacemos con las instrucciones: for (i = 0; i < 6;i++) alumnos [i]= new RegistroAlumno ();

A continuación aparece la clase PruebaRegistro, donde se incluye el programa principal:



import java.io.*; public class PruebaRegistro { static void cargarTabla (RegistroAlumno [ ] alumnos) throws IOException { int i; for (i = 0; i < 6; i++) { System.out.println ("Datos del alumno N: "+ i); alumnos [i].cargarRegistro (); } } static float mediaCalif (RegistroAlumno [ ] alumnos) { float resul = 0; int i; for (i = 0; i < 6; i++) { System.out.println(alumnos [i].aCadena ()); resul = resul + alumnos [i].calificacion; } return resul/6; } public static void main (String [ ] args) throws IOException { RegistroAlumno [ ] alumnos = new RegistroAlumno [6]; float media; int i; for (i = 0; i < 6; i++) alumnos [i]= new RegistroAlumno (); cargarTabla (alumnos); media = mediaCalif (alumnos); System.out.println ("La media de las calificaciones es: " + media); } }



1.5. UTILIZACIÓN DE DISPOSITIVOS DE ALMACENAMIENTO EXTERNO. Con frecuencia las aplicaciones informáticas trabajan sobre datos almacenados de forma estable en dispositivos de almacenamiento (típicamente discos magnéticos). Una primera vez el crea un “fichero” (file) y lo “guarda” en un disco. Posteriormente podrá utilizar dicho fichero, consultar y modificar los datos, así como añadir nuevos o eliminar alguno/s de los actuales. La utilización de ficheros en disco es muy amplia y va más allá de los objetivos de este curso. Simplemente indicar que los ficheros están constituidos por un conjunto de registros que definen las características de cada uno de los elementos (“fichas”) del fichero46. Otro aspecto a considerar es cómo organizar las “fichas” dentro del dispositivo (fichero). Con soportes tradicionales la forma de organización es única (por ejemplo, alfabética) y secuencial (una ficha tras otra, en el orden predefinido). La Informática ha heredado esta idea aunque permite otras modalidades de organización y modos de adicionales a los puramente únicos y secuenciales. 1.5.1. Ficheros de texto. En un fichero de texto, cada una de sus “fichas” consiste en una cadena de caracteres de longitud variable (líneas de texto). Las “fichas” se almacenan una tras otra sin mantener ningún criterio de orden entre sí. Por ejemplo (marsell.txt): Allons enfants de la Patrie, Le jour de gloire est arrivé! Contre nous de la tyrannie, L'étendard sanglant est levé,(bis) Entendez-vous dans le campagnes, Mugir ces féroces soldats? Ils viennent jusque dans nos bras, Égorger nos fils, nos compagnes!

Entre cada una de las líneas existen “códigos invisibles” cuyo efecto es hacer saltar al inicio de la línea siguiente. Estos códigos se generan automáticamente al pulsar la tecla “Intro”. Así mismo, para indicar el final del fichero de texto, el deberá haber pulsado la tecla de función “F6”. La figura siguiente muestra el código ASCII correspondiente al ejemplo.

46

Este concepto está heredado de los antiguos “ficheros” (o archivadores) que contenían “fichas” (de papel) cada una de las cuales representaba una información unitaria: ficheros de películas, personas, asignaturas….



Pareja de códigos (ocultos): Salto de línea (LF): „X‟=0A; dec=10 Retorno de “carro” (CR): „X‟=0D; dec=13

Figura 1.7. Códigos de fin de línea y retorno de carro en un fichero de texto. La figura siguiente muestra, a título de ejemplo, un programa que crea un fichero (archivo.txt)47 e introduce en él dos líneas de texto (procedentes del teclado y recogidas, sucesivamente, en la variable, de tipo String, lineaLeida). Una vez finalizado el proceso el fichero deberá “cerrarse” para permitir posteriores usos del mismo.

import java.io.*; public class prueba_fichero_texto { lineaLeida

Marse.txt

public static void main(String[] args) throws IOException { FileWriter fich_s = new FileWriter ("archivo.txt"); BufferedWriter bw = new BufferedWriter (fich_s); PrintWriter salida = new PrintWriter (bw); BufferedReader linea = new BufferedReader (new InputStreamReader(System.in)); String lineaLeida; System.out.println ("Escriba la primera linea: "); lineaLeida = new String (linea.readLine()); salida.println (lineaLeida); System.out.println ("Escriba la segunda linea: "); lineaLeida = new String (linea.readLine()); salida.println (lineaLeida); salida.close(); } }

Figura 1.8. Funcionamiento del programa

47

La ruta, nombre y extensión del fichero se eligen libremente (con las restricciones propias del sistema operativo). En el ejemplo se han utilizado: Ruta: (por omisión) la misma que el programa. Nombre: archivo. Extensión txt (para poder visualizarlo mediante el bloc de notas –notepad- de Windows).



import java.io.*; public class PruebaFicheroSalida { public static void main (String [ ] args) throws IOException { FileWriter fich_s = new FileWriter ("archivo.txt"); BufferedWriter bw = new BufferedWriter (fich_s); PrintWriter salida = new PrintWriter (bw); BufferedReader linea = new BufferedReader (new InputStreamReader(System.in)); String lineaLeida; System.out.println ("Escriba la primera lineaLeida = new String (linea.readLine salida.println (lineaLeida); System.out.println ("Escriba la segunda lineaLeida = new String (linea.readLine salida.println (lineaLeida); salida.close ();

linea: "); ()); linea: "); ());

} }

La figura siguiente ilustra un ejemplo de posible resultado de la ejecución del programa anterior.

Figura 1.9. Resultado de la ejecución del programa



1.5.1.1. Principales consideraciones semánticas. El programador no es consciente del fichero físico con que está trabajando. Se crea un nombre simbólico (por ejemplo fich_s), y sobre él se realizan todas las operaciones48. Sólo existe una excepción, la sentencia: FileWriter fich_s = new FileWriter ("archivo.txt");

establece una vinculación entre el nombre físico del fichero y el nombre lógico. Se utiliza una variable de tipo String (en el ejemplo: lineaLeida) como “puente” entre la memoria del ordenador y el dispositivo de almacenamiento (disco). Según sea el sentido de la transferencia se puede hablar de lectura: disco → memoria (readline) o de escritura memoria → disco (println). Hay que preparar el fichero en disco para utilizarlo (apertura) y dejarlo disponible para posteriores usos (cierre). 1.5.1.2. Sintaxis de las principales operaciones relacionadas con los ficheros de texto49. (Asignación y apertura) y declaración de variables: o Crear un nuevo fichero y destruir, en su caso, un fichero previo. Posteriormente se podrá escribir en él: FileWriter <nombre lógico> = new FileWriter (<nombre físico>); BufferedWriter = new BufferedWriter (<nombre lógico>); PrintWriter = new PrintWriter ( );

o Preparar un fichero (que debe existir previamente) para poder leer posteriormente su contenido: FileReader <nombre lógico> = new FileReader (<nombre físico>); BufferedReader = new BufferedReader (<nombre lógico>);

o Escribir en un fichero (previamente creado) nuevas líneas de texto a partir de la última: FileWriter <nombre lógico> = new FileWriter (<nombre físico>,true);

Proceso: o Leer (transferir a la variable correspondiente) el contenido de una línea del fichero y prepararse para la siguiente. = .readline();

o Escribir (transferir) el contenido de una línea (<expresión tipo String>) al fichero y prepararse para la siguiente: .println = <expresión tipo String>;

48

Dicho fichero estará gestionado por el sistema operativo. Con frecuencia se cambia de ubicación los ficheros (físicos) y de no seguir esta filosofía, esto implicaría re-escribir parte del código cada vez que un fichero cambiase de ubicación. 49 Para mayor información consultar el manual de programación.



Terminación: o Dejar el fichero preparado para usos posteriores: .close ();

Por ejemplo, si queremos leer un fichero hasta llegar al final lo podemos hacer utilizando lo siguiente: import java.io.*; public class PruebaFicheroEntrada { public static void main (String [ ] args) throws IOException { String lineaLeida; FileReader fichLeido = new FileReader ("archivo.txt"); BufferedReader entrada = new BufferedReader (fichLeido); System.out.println ("Contenido del fichero: "); while ((lineaLeida = entrada.readLine ()) != null) System.out.println (lineaLeida); entrada.close (); } }

1.5.2. Ficheros binarios. En un fichero binario, las “fichas” son elementos de tipo registro50. En consecuencia (entre otras) no se puede visualizar su contenido con un visor de texto del sistema operativo (por ejemplo, el bloc de notas de Windows). Para poder guardar objetos (por ejemplo, del tipo RegistroAlumno visto en apartados anteriores) en un fichero hay que hacerlos “serializables”. Mediante la serialización, un objeto se convierte en una secuencia de bytes con la que se puede reconstruir posteriormente manteniendo el valor de sus variables. Esto permite guardar un objeto en un archivo o mandarlo por red. Una clase se serializa añadiendo en su definición: implements Serializable

Para poder leer y escribir objetos que se han declarado como serializables se utilizan las clases ObjectInputStream y ObjectOutputStream, que cuentan con los métodos writeObject() y readObject(). Para escribir un objeto en un fichero se utilizará: ObjectOutputStream = new ObjectOutputStream (new FileOutputStream("<nombre fichero>")); .writeObject ( );

50

Ver apartado 1.4.2 “Estructuras de datos heterogéneas”.



Mientras que las instrucciones utilizadas para leerlos después serían: ObjectInputStream = new ObjectInputStream (new FileInputStream ("<nombre fichero>")); = ( ) .readObject ();

Cuando se ha terminado de leer o escribir el fichero correspondiente es necesario cerrar el fichero con: <nombre fichero>.close()

El siguiente ejemplo es una variante del programa de gestión de alumnos visto en el apartado 1.4.2.2. Sus características más importantes son51: Concepción modular: un programa principal y un conjunto de subprogramas. No se utilizan variables globales. El programa principal: o Prepara el fichero en disco: String nombre; BufferedReader linea = new BufferedReader (new InputStreamReader(System.in)); System.out.println ("Introducir nombre del fichero: "); nombre = new String (linea.readLine());

o Su lógica se basa en un planteamiento de “tipo menú”: 

Llama al módulo que realiza la interfaz de : menu (sin argumentos)



Recibe (variable op) la opción seleccionada, la analiza (mediante una estructura case) e invoca al módulo correspondiente: crearFichero (fichero). cargarTabla (alumnos, fichero) mediaCalif (alumnos)

o Utiliza el menor conjunto posible de información (variables). Obsérvese que el programa principal no necesita para nada utilizar registros correspondientes a alumnos individuales (tipo RegistroAlumno). El procedimiento menu. Es autónomo (no necesita recibir ni devolver argumentos). La función mediaCalif (alumnos). El único argumento que necesita es una tabla de registros de alumnos (RegistroAlumno []). El procedimiento cargarTabla (alumnos, fichero). Utiliza como información de entrada un fichero y genera en memoria (alumnos) una estructura RegistroAlumno 51

Por simplicidad no se han considerado situaciones excepcionales (“por excepción”). Por ejemplo: No tiene sentido utilizar la opción [2]: “Cargar tabla de registros”, si no existe el fichero en disco. Tampoco lo tiene utilizar la opción [3]: “Calcular calificación media”, si no se ha ejecutado (con éxito) previamente la opción [2].



[] que quedará a disposición del programa principal. Se encarga de abrir, en modo lectura, el fichero y cerrarlo al finalizar. El procedimiento crearFichero (fichero). Genera un fichero binario en disco a partir de los datos introducidos por el desde el teclado. Abre el fichero en modo escritura y lo cierra al terminar. El siguiente esquema muestra gráficamente la arquitectura de la aplicación.

Inicio

menu

Módulo principal

Fin

crearFichero

cargarTabla

op

mediaCalif

Figura 1.10. Arquitectura del programa ejemplo. El código del ejemplo sería: import java.io.*; public class PruebaFichES { static void crearFichero (RegistroAlumno [ ] alumnos, String nombref) throws IOException { int i; FileOutputStream fich = new FileOutputStream (nombref); ObjectOutputStream objEscrito = new ObjectOutputStream (fich); for (i = 0; i < 6; i++) { alumnos [i] = new RegistroAlumno(); System.out.println ("Datos del alumno N: "+ i); alumnos [i].cargarRegistro (); objEscrito.writeObject (alumnos [i]); } fich.close (); } static void cargarTabla (RegistroAlumno [ ] alumnos, String nombref) throws IOException, ClassNotFoundException { int i; FileInputStream fich =new FileInputStream (nombref); ObjectInputStream objLeido = new ObjectInputStream (fich); for (i = 0; i < 6; i++) { alumnos [i] = (RegistroAlumno) objLeido.readObject (); System.out.println ("Datos del alumno N: " + i); System.out.println(alumnos [i].aCadena ()); } fich.close (); }



static float mediaCalif (RegistroAlumno [ ] alumnos) { float resul; int i; resul = 0; for (i = 0; i < 6; i++) { System.out.println (alumnos [i].aCadena ()); resul = resul + alumnos [i].calificacion;} return resul/6; } static void menu () { System.out.println System.out.println System.out.println System.out.println System.out.println System.out.println }

("OPCIONES:"); ("Opcion 1: Crear fichero."); ("Opcion 2: Cargar tabla de registros."); ("Opcion 3: Calcular calificacion media."); ("Opcion 0: Salir."); ("\n Introduzca opcion: ");

public static void main (String[] args) throws IOException, ClassNotFoundException { RegistroAlumno [ ] alumnos = new RegistroAlumno [6]; float media; int op; String nombre; BufferedReader linea = new BufferedReader (new InputStreamReader(System.in)); System.out.println ("Introducir nombre del fichero: "); nombre = new String (linea.readLine ()); menu(); op = Integer.parseInt (linea.readLine ()); while (op != 0) { switch (op) { case 1: crearFichero (alumnos,nombre); break; case 2: cargarTabla (alumnos, nombre); break; case 3: media = mediaCalif (alumnos); System.out.println ("La media de las calificaciones es: "+media); break; default: System.out.println("opción no valida"); break; } menu (); op = Integer.parseInt (linea.readLine ()); } System.out.println ("Adios"); } }



TEMA 1. ....................................................................................................................... 1 1.1.

Conceptos básicos. ......................................................................................... 1

1.1.1.

Características específicas del lenguaje Java. ........................................ 3

1.1.2.

Entorno de programación (IDE). ............................................................ 4

1.2.

Sintaxis del lenguaje Java............................................................................... 5

1.2.1.

Estructura de un programa en Java......................................................... 5

1.2.2.

Nomenclatura habitual en Java............................................................... 6

1.2.3.

Los datos................................................................................................. 6

1.2.4.

Sentencias. ............................................................................................ 10

1.3.

Programación modular. Subprogramas. ....................................................... 18

1.3.1.

Reflexión previa. .................................................................................. 18

1.3.2.

Tecnología para la programación modular. .......................................... 18

1.3.3.

Mecanismos para el paso de información. ........................................... 20

1.3.4.

Aplicación al lenguaje Java. ................................................................. 21

1.3.5.

Recursividad. ........................................................................................ 24

1.4.

Estructuras de datos. ..................................................................................... 32

1.4.1.

Estructuras de datos dinámicas............................................................. 32

1.4.2.

Estructuras de datos estáticas. .............................................................. 35

1.5.

Utilización de dispositivos de almacenamiento externo. ............................. 43

1.5.1.

Ficheros de texto. ................................................................................. 43

1.5.2.

Ficheros binarios. ................................................................................. 47


TIPOS ABSTRACTOS DE DATOS 51

TEMA 2

Tipos Abstractos de Datos. 2.1. CONCEPTO Como se vio en el apartado 1.4, se entiende por Estructura de Datos una agrupación de datos, simples o compuestos, del mismo o diferente tipo, que constituyen una entidad en su conjunto (por ejemplo un vector o un registro). Evolucionando en el concepto de estructura de datos aparece el de Tipo Abstracto de Datos (TAD) que obedece a la técnica de abstracción de datos y sienta las bases para una adecuada compresión de la Programación Orientada a Objetos. Una definición de TAD u Objeto sería: El conjunto constituido por la estructura de datos y las operaciones asociadas a la misma que permite modelar el comportamiento de una entidad real. Se trata de construir entidades (TAD’s, Objetos, etc.) que puedan ser posteriormente utilizadas por otros. Sus principales características son: Ocultamiento. El TAD tiene un comportamiento de “caja negra” dado que quien lo usa sabe qué puede hacer pero no cómo lo hace.

52 TIPOS ABSTRACTOS DE DATOS


Encapsulamiento (y, en consecuencia, Protección). El de TAD’s no tiene y, por tanto, no puede modificar sus características. No obstante, puede partir de él para construir otros TAD’s1 Compilación separada: El resultado de la compilación del TAD se pone a disposición de los s en forma de unidades que pueden utilizarse como si estuvieran predefinidas en el lenguaje de programación. El objetivo de emplear este tipo de mecanismos obedece a criterios de productividad en la Ingeniería del Software. De forma simplificada se trata de clasificar a los profesionales de la construcción de Software en dos categorías: Constructores (y distribuidores) de TAD’s. Utilizadores de TAD’s hechos por otros. El de un TAD sabe de su comportamiento a partir de las especificaciones tanto semánticas como sintácticas que le habrán sido proporcionadas por el creador del mismo. Veamos, a partir de unos sencillos ejemplos, la forma de usar TAD’s (queda pendiente cómo construirlos: se verá en los temas posteriores). Se trata de dos tipos abstractos de datos: Pilas y Colas que constituyen fenómenos observables con mucha frecuencia en el mundo real.

1

Esta idea permite introducir el segundo concepto más representativo de la Programación Orientada a Objetos: la HERENCIA



2.2. TAD PILA DE NÚMEROS ENTEROS. 2.2.1. Concepto. Una pila es una agrupación de elementos de determinada naturaleza o tipo (datos de personas, números, procesos informáticos, automóviles, etc.) entre los que existe definida una relación de orden (estructura de datos). En función del tiempo, algunos elementos de dicha naturaleza pueden llegar a la pila o salir de ella (operaciones / acciones). En consecuencia el estado de la pila varía. Una pila presenta el comportamiento LIFO (Last Input First Output) y el criterio de ordenación se establece en sentido inverso al orden de llegada. Así pues, el último elemento que llegó al conjunto será el primero en salir del mismo, y así sucesivamente. 2.2.2. Modelo gráfico Podríamos representar gráficamente una pila según aparece en la figura 2.1: una estructura de datos vertical, en la que los elementos se insertan y extraen por la parte superior. desapilar

apilar 5 4 1 7 2

cima

fondo

Figura 2.1. Modelo gráfico de Pila 2.2.3. Especificaciones A continuación se describen las operaciones que vamos a poder realizar sobre el TAD pila de enteros. Para ello, utilizaremos dos tipos de especificaciones: o Especificaciones sintácticas. Hacen referencia a los aspectos sintácticos de las distintas operaciones asociadas al TAD: nombre de la operación, parámetros, resultado devuelto por la operación, tipo de dicho resultado, etc. o Especificaciones semánticas. Indican el efecto producido por la operación, es decir, la definen desde el punto de vista de lo que hace. En la Tabla 2.1., se definen las especificaciones semánticas y sintácticas del TAD pila de enteros. Cuando se desee utilizar el tad pila en un programa, habrá que poner la siguiente sentencia en la primera línea del programa, después de la cabecera (o bien utilizarlo dentro del mismo paquete –package tadPila–): import tadPila.*;


Operación 2 apilar

desapilar

3

pilaVacia

leerPila imprimirPila numElemPila cima decapitar eliminarPila

4

Especificación semántica Método que entrega un elemento (x) para que quede incorporado en la cima de la pila. Método que elimina el elemento que ocupa la cima de la pila y devuelve como resultado dicho elemento. Método que al ejecutarse devuelve true si la pila está vacía (no tiene elementos), y false en caso contrario. Método que se utiliza para realizar la carga inicial de elementos de la pila. Método que muestra en la pantalla el contenido de la pila. Método que devuelve el número de elementos de la pila. Método que devuelve la cima de la pila (sin alterarla). Método que elimina el elemento de la cima de la pila. Método que recibe una pila (que puede tener elementos o no) y la devuelve vacía.


Especificación sintáctica void apilar (int x)

int desapilar () throws PilaVacia

boolean pilaVacia ()

void leerPila () throws NumberFormatException, IOException void imprimirPila () int numElemPila () int cima () throws PilaVacia void decapitar ()throws PilaVacia void eliminarPila ()

Tabla 2.1. Especificaciones semánticas y sintácticas del TAD Pila de enteros. 2.2.4. Interfaz del TAD Pila. El interfaz Pila define los métodos de objeto que utilizaremos con la clase TadPila: import java.io.*; public interface Pila { boolean pilaVacia (); void eliminarPila (); int cima () throws PilaVacia; void apilar (int x); int desapilar () throws PilaVacia; void decapitar () throws PilaVacia; void imprimirPila (); void leerPila () throws NumberFormatException, IOException; int numElemPila (); }

2

Se puede producir una situación de excepción cuando el número de elementos de la pila supere determinado valor (lógicamente no podrán ser infinitos). Dicha situación se manifestará al intentar ejecutar la operación de apilar sobre una pila en dicho estado. 3 Se produce una excepción (PilaVacia) si se intenta desapilar de una pila vacía. Lo mismo ocurre con las operaciones cima y decapitar. 4 Puede resultar innecesario y forzado en Java, pero queremos transmitir la idea de la obligación de crear y destruir los objetos cuando se trabaje en Programación Orientada a Objetos.



2.2.5. Prueba del TAD pila. 2.2.5.1. Condiciones normales. En el siguiente algoritmo se va a realizar una verificación del funcionamiento elemental (sin situaciones de excepción) del TAD Pila. Primero se inicializa la pila, a continuación se introducen varios elementos en la misma, y por último se sacan dos de los datos, escribiendo los elementos desapilados en la pantalla. public class PruebaPila1 { public static void main (String[] args) throws PilaVacia { Pila p = new TadPila (); int x; p.apilar (1); p.apilar (2); p.apilar (3); p.apilar (11); p.apilar (15); x = p.desapilar (); System.out.println ("x = " + x); x = p.desapilar (); System.out.println ("x = " + x); p.eliminarPila (); } }

2.2.5.2. Situaciones de excepción. A continuación se muestra un ejemplo mediante el cual podemos verificar el funcionamiento del TAD frente a situaciones de excepción: introducimos una serie de elementos en la pila, y luego intentamos desapilar uno más de los que tenía la pila originalmente. public class PruebaPila2 { public static void main(String[] args) throws PilaVacia { Pila pila1 = new TadPila (); int i, j; System.out.println (); for (i = 1; i < 10; i++) pila1.apilar (i); j = pila1.desapilar (); for (i = 1; i < 10; i++) j = pila1.desapilar (); pila1.eliminarPila (); } }



2.2.6. Algoritmos básicos con pilas. En los siguientes apartados se desarrollan algunos ejemplos elementales que hacen uso del TAD pila siguiendo las especificaciones indicadas en el apartado anterior. En general se tendrán en cuenta las siguientes consideraciones: La pila es una estructura muy adecuada para el tratamiento recursivo por lo que se insta a su empleo. Con frecuencia las especificaciones de los enunciados fuerzan a ello tanto por indicación expresa como por la exigencia del cumplimiento simultáneo de las condiciones de realizar un único recorrido (no desapilar/apilar cada elemento más de una vez) y no utilizar estructuras de datos auxiliares. Así pues, en general el tratamiento de pilas se hará siguiendo la mecánica desapilar – llamada recursiva – apilar. El proceso de los elementos de la pila se realizará, según los casos, a la “ida”, a la “vuelta”, o parcialmente en ambas fases. La condición de terminación “pesimista” supone el cumplimiento (true) de la condición pila.pilaVacia (). La terminación anticipada se ejecuta de forma implícita no realizando llamadas posteriores cuando se cumpla determinada circunstancia. En este caso se deberá prestar atención especial al tratamiento del último elemento desapilado (si se desea volver a apilarlo o no). El resto de elementos de la pila (desde el actual hasta el fondo) permanece inalterado. 2.2.6.1. Sin terminación anticipada. 2.2.6.1.1. Escribir el contenido de una pila en pantalla. Se muestra un método (escribirPila) que consiste en vaciar la pila (desapilar) durante la fase de “ida”. A continuación, se escribe en la pantalla el elemento desapilado y se hace una llamada recursiva. A la vuelta de la recursividad, se deberán apilar los sucesivos valores almacenados localmente en las diferentes instancias de la variable elem (local). El único argumento que necesita el método es la propia pila. A continuación se muestra el algoritmo. static void escribirPila (Pila pila) throws PilaVacia { int elem; if (!pila.pilaVacia ()) { elem = pila.desapilar (); System.out.println (elem); escribirPila (pila); pila.apilar (elem); } }



2.2.6.1.2. Contar los elementos de una pila. Se muestra un método que consiste en vaciar la pila (desapilar) durante la fase de “ida”. En cada llamada se incrementa en una unidad el resultado de la variable local (resul) que, en cada paso de la fase de “vuelta”, se devuelve como resultado del método. Así mismo se deberán apilar los sucesivos valores almacenados localmente en las diferentes instancias de la variable elem (local). No existe finalización anticipada y la inicialización se produce en el momento de transición del proceso recursivo (al alcanzar la condición de terminación, cuando la pila esté vacía). El único argumento que necesita el método es la propia pila. A continuación se muestra el algoritmo. static int contarPila (Pila pila) throws PilaVacia { int elem, resul; if (! pila.pilaVacia ()) { elem = pila.desapilar (); resul = 1 + contarPila(pila); pila.apilar (elem); } else resul = 0; return resul; }

2.2.6.1.3. Obtener el duplicado de una pila. Se trata de obtener un duplicado de la pila que se pasa como argumento. En consecuencia el algoritmo necesitará dos argumentos: la pila origen (pilaO) y la pila destino (pilaD). En este caso tampoco existe la posibilidad de terminación anticipada sino que seguiremos procesando los datos hasta que se cumpla la condición pilaO.pilaVacia (). La construcción del duplicado de la pila (pilaD) se consigue apilando en ella a la vez que se reconstruye la original (en la fase de “vuelta”). A continuación se muestra el algoritmo. static void copiarPila (Pila pilaO, Pila pilaD) throws PilaVacia { int elem; if (! pilaO.pilaVacia ()) { elem = pilaO.desapilar (); copiarPila (pilaO, pilaD); pilaO.apilar (elem); pilaD.apilar (elem); } }

Si se deseara obtener un resultado en orden inverso al inicial apilaríamos en la pila destino (pilaD) en la fase de “ida”, utilizando el siguiente algoritmo:



static void copiarPilaI (Pila pilaO, Pila pilaD) throws PilaVacia { int elem; if (! pilaO.pilaVacia ()) { elem = pilaO.desapilar (); pilaD.apilar (elem); copiarPilaI (pilaO, pilaD); pilaO.apilar (elem); } }

2.2.6.1.4. Sumergir un elemento en una pila. Este ejemplo, permite implementar una operación contraria a la naturaleza de la pila. Consiste en un método que introduce un dato en el fondo de la pila. Para poder colocar un elemento en el fondo de la pila, se procede a vaciar la pila, y en el momento que esté vacía se apila el dato (transición entre las fases de “ida” y de “vuelta”). static void sumergir (Pila pila, int dato) throws PilaVacia { int elem; if (!pila.pilaVacia ()) { elem = pila.desapilar (); sumergir (pila, dato); pila.apilar (elem); } else pila.apilar (dato); }

2.2.6.1.5. Invertir los elementos de una pila. Dada una pila de números enteros, vamos a implementar un método que la devuelva con su contenido invertido. Para ello, utilizaremos el método sumergir que hemos visto en el apartado anterior: el método invertir consistirá en desapilar un elemento, llamar recursivamente, y a la vuelta de la recursividad, en vez de apilar el elemento en la pila, lo sumergiremos en el fondo de la misma. Nótese que al utilizar dos métodos recursivos, cada uno de los elementos de la pila se desapilará y apilará más de una vez. static void invertir (Pila pila) throws PilaVacia { int elem; if (!pila.pilaVacia ()) { elem = pila.desapilar (); invertir (pila); sumergir (pila, elem); } }



2.2.6.2. Terminación anticipada. Como ya se ha indicado en algunos casos no será necesario que se alcance la condición de parada en la ejecución del programa (cuando se cumpla determinada circunstancia). Para ello basta con que el algoritmo no ejecute una nueva llamada recursiva, no requiriéndose el empleo de variables de control ni ninguna lógica complementaria. 2.2.6.2.1. Obtener el elemento del fondo de una pila. Este ejemplo permite implementar una operación contraria a la naturaleza de la pila (ya que debemos llegar a vaciarla para localizar el último elemento). En el siguiente método se muestra una posible solución que permite identificar, en la fase de “ida”, cuál es el elemento del fondo. Cada vez que desapilamos un elemento, verificamos si siguen quedando elementos. En caso afirmativo, hacemos una nueva llamada recursiva y a la “vuelta” apilamos el elemento desapilado. Cuando la pila se ha quedado vacía, acabamos de desapilar el último elemento: guardamos en la variable dato el último elemento de la pila (elem), y no hacemos más llamadas recursivas. En el caso de que la pila estuviese originalmente vacía devolveríamos un mensaje de error (y como resultado de error devolveríamos -9999). public static int desfondar (Pila p) throws PilaVacia { int elem, dato; if (!p.pilaVacia ()) { elem = p.desapilar (); if (!p.pilaVacia ()) { dato = desfondar(p); p.apilar (elem); } else dato = elem; } else { System.out.println ("error, la pila está vacía"); dato = -9999; } return dato; }



2.2.6.2.2. Comprobar si un elemento pertenece a una pila. El siguiente ejemplo muestra un método (esta) que devuelve un valor booleano dependiendo de que durante el transcurso de exploración de la pila encuentre o no un valor (dato) que se pasa como argumento. En esencia el algoritmo consiste en vaciar la pila (condición pesimista) verificando en cada llamada si el elemento desapilado coincide con el dato. En caso negativo se genera una nueva llamada recursiva, pero en caso afirmativo se prepara el valor a devolver por el método (resul = true) y no se realiza una nueva llamada recursiva. Si se llega a vaciar la pila, se entenderá que el elemento buscado no existe y, en consecuencia, el método devolverá el valor false. static boolean esta (Pila pila, int dato) throws PilaVacia { int elem; boolean resul; if (!pila.pilaVacia ()) { elem = pila.desapilar (); if (elem == dato) resul = true; else resul = esta (pila, dato); pila.apilar (elem); } else resul= false; return resul; }

2.2.6.3. Mezclar dos pilas. La dificultad principal de este tipo de procesos se deriva de la naturaleza “destructiva” de la operación de “lectura” (para conocer el elemento de la cima de una pila hay que “quitarlo” de ella –desapilar-). Esto implica que, en un tratamiento recursivo, es posible que algún valor desapilado de alguna de las pilas en instancias anteriores esté durante algún tiempo “pendiente” de ser procesado. El método, con carácter general, consiste en realizar un tratamiento recursivo cuya estructura es la siguiente: Fase de ida: Se desapilará de una de las dos pilas o de ambas. Se realiza el tratamiento específico. Dicho tratamiento deberá incluir el mecanismo de informar a la siguiente instancia, mediante los argumentos apropiados, de qué pila o pilas deberá desapilarse, así como los elementos desapilados en la propia instancia o en alguna instancia anterior (y propagados como argumento en el proceso recursivo),



(elem1, elem2)5. Para ello se utilizan los argumentos booleanos apilar1 y apilar2. Su interpretación es: un valor true indica que el elemento (elem1|2) aún no se ha tratado, por lo que queda pendiente de apilar en la fase de vuelta (y, en su caso, de tratar) y no deberá desapilarse de la pila correspondiente en la siguiente instancia. Se realiza una llamada recursiva con los argumentos actualizados durante el tratamiento anterior. Se escribe el código que deberá ejecutarse la fase de “vuelta” correspondiente a la instancia actual que, entre otros posibles aspectos, deberá ocuparse de (re)apilar los elementos desapilados en dicha instancia. Consideración inicial: Los argumentos apilar1 y apilar2 deben inicializarse a false (no hay ningún elemento pendiente por tratar). Los valores iniciales de elem1 y elem2 no tienen relevancia. Condición de terminación: Obsérvese que el hecho de recibir una pila vacía es una condición necesaria para dar por finalizado su tratamiento, pero no suficiente. Es posible que el elemento del fondo de una pila se haya desapilado en instancias anteriores, por lo que la pila se propaga vacía pero aun no se ha tratado su último elemento. Así pues una pila se mantiene “vigente” en el proceso recursivo si: !pila1|2.pilaVacia () || apilar1|2

Para facilitar la legibilidad usaremos las variables locales booleanas6 pend1|2 = (!pila1|2.pilaVacia () || apilar1|2)

La cabecera del módulo deberá usar como argumentos: o pila1 y pila2, de tipo Pila,; o apilar1 y apilar2, de tipo boolean o elem1 y elem2 de tipo int Fase de transición: Para saber cuándo debemos parar de hacer llamadas recursivas, tenemos dos casos posibles: La naturaleza del tratamiento es tal que el proceso finaliza cuando se acaba con el tratamiento de una de las pilas (intersección o modalidad AND). El tratamiento recursivo se mantiene si (pend1 && pend2) == true (ambas pilas están pendientes de

5

En este caso elem1, elem2 no se utilizan como variables locales tal como se hace en el caso de tratamientos con una sola pila). 6 Entendidas como “pendiente”.



tratar). Se deberán apilar (y, en su caso, procesar) los elementos pendientes desapilados en instancias anteriores (identificados mediante la condición apilar1|2 == true). La fase de “transición” finaliza y se inicia la de “vuelta”. (Un posible ejemplo sería: obtener una pila con los elementos comunes de otras dos). Para que el tratamiento acabe es necesario procesar ambas pilas (unión o modalidad OR). (Por ejemplo, si se desea obtener una pila con los elementos de otras dos). En este caso: o Si una pila está procesada (pend1|2 == false) y la otra no (pend2|1 == true):  Se (re)apila, si procede, el elemento desapilado de la pila pendiente de procesar (apilar2|1) y se realiza, si procede, el tratamiento oportuno con dicho elemento (elem2|1).  Se invoca a un (nuevo) tratamiento recursivo que opera únicamente sobre la pila pendiente de procesar. o Si ambas pilas están procesadas por completo (pend1 == false y pend2 == false), el proceso de “transición” finaliza y se inicia la fase de vuelta. Fase de vuelta: Desde las correspondientes instancias se realiza el tratamiento adecuado que deberá contemplar, normalmente, la restitución (apilar) de los valores desapilados en la fase de ida. 2.2.6.3.1. Ejemplo1. Realizar la intersección de dos pilas. Dadas dos pilas (pila1 y pila2) ordenadas ascendentemente desde la cima hacia el fondo (sin elementos repetidos en cada una de las pilas), se desea obtener una nueva pila (pila3), también ordenada ascendentemente y sin elementos repetidos, con los elementos comunes de ambas. Aplicando a este caso el tratamiento genérico, se trata de: Fase de “ida”. Desapilar si procede (en función del valor de los argumentos apilar1 y apilar2. Existen los siguientes casos: o elem1 > elem2. Habrá que (re)apilar elem2 en pila2 en la fase de vuelta. La llamada recursiva se hace con apilar1 = true y apilar2 = false. o

elem1 < elem2. Tendremos que (re)apilar elem1 en pila1 en la fase de vuelta. La llamada recursiva se hace con apilar1 = false y apilar2 = true.

o elem1 == elem2. En la fase de vuelta se puede apilar cualquiera de los dos elementos (sólo una vez) en pila3, y reapilar en pila1 y pila2. La llamada recursiva se hace con apilar1 = false y apilar2 = false. Condición de terminación. El proceso finaliza cuando se acaba con el tratamiento de una de las pilas (pend1 && pend2) == false.



Fase de “transición”: Si queda algún elemento pendiente en alguna de las pilas (apilar1 == true o apilar2 == true), habrá que apilarlo en la pila que corresponda. Las siguientes figuras muestran un ejemplo. apilar1 false ep1 ?

2 4 77 pila1

apilar2 false ep2 ?

1 2 3 4 5 6 7 pila2

pila3

Figura 2.2. Situación de partida. apilar1 indif ep1 indif

2 4 77 pila1

apilar2 indif ep2 indif

Figura 2.3. Situación final A continuación aparece el código.

1 2 3 4 5 6 7 pila2

2 4 pila3



static void mezclarPilaAND (Pila pila1, Pila pila2, Pila pila3, boolean apilar1, boolean apilar2, int elem1, int elem2) throws PilaVacia { boolean pend1, pend2; pend1 = !pila1.pilaVacia () || apilar1; pend2 = !pila2.pilaVacia () || apilar2; if (pend1 && pend2) { if (!apilar1) elem1 = pila1.desapilar (); if (!apilar2) elem2 = pila2.desapilar (); if (elem1 < elem2) { mezclarPilaAND (pila1,pila2,pila3,false,true,elem1,elem2); pila1.apilar (elem1); } else if (elem2 < elem1) { mezclarPilaAND (pila1,pila2,pila3,true,false,elem1,elem2); pila2.apilar (elem2); } else { mezclarPilaAND (pila1,pila2,pila3,false,false,elem1,elem2); pila1.apilar (elem1); pila2.apilar (elem2); pila3.apilar (elem1); } } else if (apilar1) pila1.apilar (elem1); else if (apilar2) pila2.apilar (elem2); }



2.2.6.3.2. Ejemplo 2. Realizar la unión de dos pilas. Dadas dos pilas (pila1 y pila2) ordenadas ascendentemente desde la cima hacia el fondo (sin elementos repetidos en cada una de las pilas), se desea obtener una nueva pila (pila3), también ordenada ascendentemente y sin elementos repetidos, con los elementos de ambas. Aplicando a este caso el tratamiento genérico, se trata de: Fase de “ida”. Desapilar si procede (en función del valor de los argumentos apilar1 y apilar2. Se pueden dar los siguientes casos: o elem1 > elem2. Habrá que apilar elem2 en pila3 (y reapilar en pila2) en la fase de vuelta. La llamada recursiva se hace con apilar1 = true y apilar2 = false. o

elem1 < elem2. Tendremos que apilar elem1 en pila3 (y reapilar en pila1) en la fase de vuelta. La llamada recursiva se hace con apilar1 = false y apilar2 = true.

o elem1 == elem2. En la fase de vuelta se puede apilar cualquiera de los dos elementos (solo una vez) en pila3, y reapilar en pila1 y pila2. La llamada recursiva se hace con apilar1 = false y apilar2 = false. Condición de terminación. Para que el tratamiento acabe es necesario procesar ambas pilas (pend1 || pend2) == false Fase de “transición” o Si se ha “terminado” con pila1 (pend1 == true) y no con pila2 (pend2 == false).  Se aplical método copiarPila con efectos sobre el estado actual de pila2.  Se restaura, si procede, el último valor desapilado de pila1.  Se inicia la fase de “vuelta” o Si se ha “terminado” con pila2 (pend2 == true) y no con pila1 (pend1= = false).  Se aplica el método copiarPila con efectos sobre el estado actual de pila1.  Se restaura, si procede, el último valor desapilado de pila2.  Se inicia la fase de “vuelta”. o Si se ha “terminado” con ambas pilas (pend1 == false y pend2 == false).  Se inicia la fase de vuelta. Las siguientes figuras muestran un ejemplo:


apilar1 false ep1 ?


2 4 77 pila1

apilar2 false ep2 ?

1 2 3 4 5 6 7 pila2 pila3

Figura 2.4. Situación de partida. apilar1 indif ep1 indif

2 4 77 pila1

apilar2 indif ep2 indif

Figura 2.5. Situación final A continuación se muestra el código.

1 2 3 4 5 6 7 pila2

1 2 3 4 5 6 7 77 pila3



static void copiarPila (Pila pilaO, Pila pilaD) throws PilaVacia

{

int elem; if (! pilaO.pilaVacia ()) { elem = pilaO.desapilar (); copiarPila (pilaO, pilaD); pilaO.apilar (elem); pilaD.apilar (elem); } } static void mezclarPilaOR (Pila pila1, Pila pila2, Pila pila3, boolean apilar1, boolean apilar2, int elem1, int elem2) throws PilaVacia { boolean pend1, pend2; pend1 = !pila1.pilaVacia () || apilar1; pend2 = !pila2.pilaVacia () || apilar2; if (pend1 && pend2) { if (!apilar1) elem1 = pila1.desapilar (); if (!apilar2) elem2 = pila2.desapilar (); if (elem1 < elem2) { mezclarPilaOR (pila1, pila2, pila3, false, true, elem1, elem2); pila1.apilar (elem1); pila3.apilar (elem1); } else if (elem2 < elem1) { mezclarPilaOR (pila1,pila2,pila3,true,false,elem1,elem2); pila2.apilar (elem2); pila3.apilar (elem2); } else { mezclarPilaOR (pila1,pila2,pila3,false,false,elem1,elem2); pila1.apilar (elem1); pila2.apilar (elem2); pila3.apilar (elem1); } } else if (pend1 && !pend2) { copiarPila (pila1, pila3); if (apilar1) { pila1.apilar (elem1); pila3.apilar (elem1); } } else if (pend2 && !pend1) { copiarPila (pila2, pila3); if (apilar2) { pila2.apilar (elem2); pila3.apilar (elem2); } } }



2.2.6.4. Mezcla de pilas con terminación anticipada. Dadas dos pilas (pila1 y pila2) ordenadas ascendentemente desde la cima hacia el fondo (sin elementos repetidos en cada una de las pilas), se desea realizar un método booleano que indique si los elementos de pila2 están contenidos en pila1 o no. Esta situación se puede resolver a partir de la consideración de mezcla de pilas en la modalidad AND (termina cuando se ha procesado por completo cualquiera de las pilas). En este caso se produce una situación de terminación anticipada cuando, en su caso, aparece por primera vez un elemento de pila2 que no está en pila1 (elem1 > elem2). El proceso debe terminar y el método devuelve false. En caso contrario (terminación “pesimista”) pueden darse las siguientes circunstancias: Se ha procesado completa pila1 (pend1 == false) pero pila2 no (pend2 == true). Aún quedan elementos en pila2 por tanto no cumple la condición de “estar contenida” en pila1, y en consecuencia el resultado será false. Se ha procesado pila2 completa (pend2 == false) y pero no pila1 (pend1 == true). Por tanto, pila2 estará contenida en pila1; y en consecuencia el resultado será true. Se ha conseguido llegar a la terminación “pesimista” (se han procesado completamente ambas pilas: pend1 == false y pend2 == false). Por lo tanto, pila2 está contenida en pila1 y el método devolverá el valor true. Aplicando a este caso el tratamiento genérico, se trata de: Fase de “ida”. Desapilar si procede (en función del valor de los argumentos apilar1 y apilar2). Se pueden dar los siguientes casos: o elem1 > elem2. Hay que reapilar elem2 en pila2 en la fase de vuelta. Es imposible que la pila2 se encuentre contenida en la pila1, por lo que habrá que devolver false como resultado. o

elem1 < elem2. Hay que reapilar elem1 en pila1 en la fase de vuelta. La llamada recursiva se hace con apilar1 = false y apilar2 = true.

o elem1 == elem2. En la fase de vuelta se reapilan los dos elementos en pila1 y pila2. La llamada recursiva se hace con apilar1 = false y apilar2 = false. Condición de terminación. El proceso finaliza cuando se acaba con el tratamiento de una de las pilas (pend1 && pend2) == false. Fase de “transición” o Si queda algún elemento pendiente de tratar en alguna de las pilas (apilar1 == true o apilar2 == true), habrá que apilarlo en la pila que corresponda y asignar el resultado correspondiente al método.



El código se muestra a continuación: static boolean contenida (Pila pila1, Pila pila2, boolean apilar1, boolean apilar2, int elem1, int elem2) throws PilaVacia { boolean pend1, pend2, resul; pend1 = !pila1.pilaVacia () || apilar1; pend2 = !pila2.pilaVacia () || apilar2; if (pend1 && pend2) { if (!apilar1) elem1 = pila1.desapilar (); if (!apilar2) elem2 = pila2.desapilar (); if (elem1 < elem2) { resul = contenida (pila1, pila2, false, true, elem1, elem2); pila1.apilar (elem1); } else if (elem2 < elem1) { resul = false; pila2.apilar (elem2); pila1.apilar (elem1); } else{ resul = contenida (pila1,pila2,false,false,elem1,elem2); pila1.apilar (elem1); pila2.apilar (elem2); } } else if (apilar1) { resul = true; pila1.apilar (elem1); } else if (apilar2) { resul = false; pila2.apilar (elem2); } else resul = true; return resul; }



2.3. 2.4.2.3. TAD COLA DE NÚMEROS ENTEROS. 2.4.1.2.3.1. Concepto. Una cola es una agrupación de elementos de determinada naturaleza o tipo (datos de personas, números, procesos informáticos, automóviles, etc.) entre los que existe definida una relación de orden (estructura de datos). En función del tiempo, algunos elementos pueden llegar a la cola o salir de ella (operaciones / acciones). En consecuencia el estado de la cola varía. Una cola presenta comportamiento FIFO (First Input First Output) y se respeta como criterio de ordenación el momento de la llegada: el primer elemento de la cola, será el que primero llegó a ella y, en consecuencia, el primero que saldrá, y así sucesivamente. 2.4.2.2.3.2. Modelo gráfico. Podríamos representar gráficamente una cola según aparece en la Figura 2.6: una estructura de datos horizontal, en la que los elementos se insertan por el extremo derecho, y se extraen por la parte izquierda. desencolar

principio fin 5 1 4 3 2 7 9 6 8

encolar

Figura 2.6. Modelo gráfico de Cola 2.4.3.2.3.3. Especificaciones En la Tabla 2.2., que aparece en la página siguiente, se definen las especificaciones semánticas y sintácticas del TAD cola de enteros. Utiliza el tipo de datos TadCola (cola de números enteros). Cuando se desee utilizar el tad cola, habrá que poner la siguiente sentencia en la primera línea del programa, después de la cabecera (o bien utilizarlo dentro del mismo paquete –package tadCola–): import tadCola.*;


Operación 7 encolar desencolar

8

colaVacia

leerCola imprimirCola

invertirCola numElemCola primero quitarPrimero eliminarCola

Especificación semántica Método que entrega un elemento (x) para que quede incorporado al final de la cola. Método que elimina el elemento de la cola que ocupa el primer lugar, devolviéndolo como resultado. Método que al ejecutarse devuelve true si la cola está vacía, y false en caso contrario. Método mediante el que se produce la carga inicial de elementos de la cola. Método que muestra en el dispositivo de salida (pantalla) el contenido actual de la cola. Método que devuelve la cola con sus elementos invertidos Método que devuelve el número de elementos de la cola. Método que devuelve el primer elemento de la cola sin desencolarlo. Método que elimina el primer elemento de la cola. Método que recibe una cola (que puede tener elementos o no) y la devuelve vacía.


Especificación sintáctica void encolar (int x) int desencolar () throws ColaVacia

boolean colaVacia ()

void leerCola () throws NumberFormatException, IOException void imprimirCola ()

void invertirCola () throws ColaVacia int numElemCola () int primero () throws ColaVacia void quitarPrimero () throws ColaVacia void eliminarCola ()

Tabla 2.2. Especificaciones semánticas y sintácticas del TAD Cola de enteros. 2.4.4.2.3.4. Interfaz del TAD Cola. import java.io.IOException; public interface Cola { boolean colaVacia (); void eliminarCola (); int primero () throws ColaVacia; void encolar (int x); int desencolar () throws ColaVacia; void quitarPrimero () throws ColaVacia; void mostrarEstadoCola (); void imprimirCola (); void leerCola () throws NumberFormatException, IOException; int numElemCola (); void invertirCola () throws ColaVacia; }

7

Se puede producir una situación de excepción cuando el número de elementos de la cola supere determinado valor (lógicamente no podrán ser infinitos) y se intente encolar sobre una cola en dicho estado. 8 Se produce una excepción (ColaVacia) si se intenta desencolar de una cola vacía. Lo mismo ocurre con las operaciones primero y quitarPrimero.



2.4.5.2.3.5. Prueba del TAD Cola. 2.4.5.1.2.3.5.1.

Condiciones normales.

El siguiente algoritmo simplemente se trata de introducir y extraer elementos de la cola sin provocar situaciones de excepción. public class PruebaCola1 { public static void main (String [ ] args) throws ColaVacia { Cola cola1 = new TadCola (); int Elem; cola1.encolar (8); cola1.encolar (7); cola1.encolar (9); cola1.encolar (11); Elem = cola1.desencolar (); Elem = cola1.desencolar (); System.out.println ("Acaba de salir el numero "+Elem); cola1.eliminarCola (); } }

2.4.5.2.2.3.5.2.

Situaciones de excepción.

En el siguiente ejemplo se verifica el funcionamiento del TAD frente a situaciones de excepción. public class PruebaCola2 { public static void main (String [ ] args) throws ColaVacia { Cola cola1 = new TadCola (); int i, j; for (i = 1; i < 10; i++) cola1.encolar (i); j = cola1.desencolar (); System.out.println ("Hemos sacado " + j); for (i = 1; i < 10; i++) { j = cola1.desencolar (); System.out.println("Hemos sacado " + j); } cola1.eliminarCola (); } }



2.4.6.2.3.6. Algoritmos básicos con colas. La filosofía general para la solución para el tratamiento de pilas, mediante técnicas recursivas, basada en un esquema de desapilar – llamada recursiva – apilar con una condición de finalización vinculada a la situación de estructura vacía no dará en general buenos resultados con colas, dado que devolvería la estructura con sus elementos cambiados de orden respecto a la situación inicial (devolverá la cola invertida). Tampoco sería válido un planteamiento del tipo de desencolar – encolar – llamada recursiva, pues nunca se alcanzaría la condición de finalización. En consecuencia para basarse en la primera idea resultará, casi siempre, necesario ejecutar un proceso complementario de invertir los elementos de la cola (como alternativa podría usarse una estructura de datos auxiliar). El proceso se simplifica notablemente si se conoce a priori el número inicial de elementos de la cola pues a partir de este valor se podría utilizar la segunda idea utilizando como condición de finalización el valor de una variable, inicialmente con el valor del número de elementos de la cola, que se decrementaría con cada llamada al algoritmo. También podría procederse en este caso a un tratamiento iterativo. 2.4.6.1.2.3.6.1.

Invertir el orden de los elementos de una cola.

Si deseamos invertir una cola, y suponiendo que no se conoce el número de elementos que contiene, ni tenemos invertirCola entre las operaciones del TAD, se propone una solución recursiva, acorde con la tendencia a invertirla que produce este tipo de tratamiento. static void invertir (Cola cola) throws ColaVacia { int elem; if (!cola.colaVacia ()) { elem = cola.desencolar (); invertir (cola); cola.encolar (elem); } }

2.4.6.2.2.3.6.2.

Contar los elementos de una cola.

Si hay que hacer un método que cuente los elementos de una cola, evidentemente no se conoce a priori el número de elementos. La única posibilidad para realizar el método es un tratamiento recursivo que, aunque cuente correctamente el número de elementos de la cola, los devolvería en el orden contrario al inicial. Se necesita, pues, una ejecución (antes o después) del método visto en el apartado anterior (invertir) fuera del tratamiento recursivo.



static void invertir (Cola cola) throws ColaVacia { int elem; if (!cola.colaVacia ()) { elem = cola.desencolar (); invertir (cola); cola.encolar (elem); } } static int contarCola (Cola cola) throws ColaVacia { int elem, resul; if (! cola.colaVacia ()) { elem = cola.desencolar (); resul = 1 + contarCola (cola); cola.encolar (elem); } else resul = 0; return resul; } static int cuentaCola (Cola cola) throws ColaVacia { invertir (cola); return contarCola (cola); }

2.4.6.3.2.3.6.3.

Obtención una cola a partir de otra.

Siempre que vayamos a trabajar con colas, tenemos tres formas posibles de hacerlo: Si no conocemos el número de elementos de la cola, necesariamente tendremos que realizar un tratamiento recursivo siguiendo el esquema desencolar–tratamiento recursivo–encolar. El problema que tenemos es el que ya se ha planteado previamente: este tratamiento deja la cola invertida. Por lo tanto, posteriormente habrá que invertir la cola resultante. Cuando conocemos el número de elementos de la cola, podemos optar entre las dos siguientes posibilidades: ○

Hacer un tratamiento recursivo, utilizando el número de elementos de la cola para fijar la condición de parada de la recursividad. Tendremos que realizar el tratamiento desencolar–encolar antes de la recursividad.

○

Realizar un tratamiento iterativo, por medio de un bucle for.

Utilizando cualquiera de estos dos métodos, los elementos de la cola se quedarán en el mismo orden inicial. Como ejemplo, en los siguientes subapartados se realiza la copia de una cola sobre otra siguiendo los tres métodos propuestos.



2.4.6.3.1.2.3.6.3.1. Sin conocer el número de elementos. Necesariamente deberá realizarse mediante un tratamiento recursivo que devolverá la cola original (ColaO) con sus elementos en orden contrario respecto al inicial. Para restaurarlo se ejecutará una llamada (no recursiva) al método invertir. static void copiar (Cola colaO, Cola colaD) throws ColaVacia { int elem; if (!colaO.colaVacia ()) { elem = colaO.desencolar(); colaD.encolar (elem); copiar (colaO, colaD); colaO.encolar (elem); } } static void copiaRecursiva1 (Cola colaO, Cola colaD) throws ColaVacia { copiar (colaO,colaD); invertir (colaO); }

Si lo que se desea es obtener una cola (ColaD) ordenada de forma inversa a la original (ColaO) bastará con encolar en la fase de “vuelta”. static void copiarInvertido (Cola colaO, Cola colaD) throws ColaVacia { int elem; if (!colaO.colaVacia ()) { elem = colaO.desencolar(); copiarInvertido (colaO, colaD); colaD.encolar (elem); colaO.encolar (elem); } } static void copiaRecursivaInvertida (Cola colaO, Cola colaD) throws ColaVacia { copiarInvertido (colaO, colaD); colaO.invertirCola (); }

2.4.6.3.2.2.3.6.3.2. Conociendo el número de elementos. Técnica recursiva. Como ya se ha indicado, es necesario utilizar como condición de parada el valor del argumento n (número de elementos de la cola) que se decrementa en una unidad en cada llamada. static void copiaRecursiva2 (Cola colaO, Cola colaD, int n) throws ColaVacia { int elem; if (n > 0) { elem = colaO.desencolar(); colaD.encolar (elem); colaO.encolar (elem); copiaRecursiva2 (colaO, colaD, n-1); } }



Análogamente al caso anterior, para obtener un duplicado con los elementos invertidos se utilizaría la variante siguiente. static void copiaRecursiva2Invertida (Cola colaO, Cola colaD, int n) throws ColaVacia { int elem;

}

if (n > 0) { elem = colaO.desencolar (); colaO.encolar (elem); copiaRecursiva2Invertida (colaO, colaD, n-1); colaD.encolar (elem); }

2.4.6.3.3.2.3.6.3.3. Conociendo el número de elementos. Técnica iterativa. De forma similar se utiliza la variable N (número de elementos de la cola) como condición de fin de un bucle for. static void copiaIterativa (Cola colaO, Cola colaD) throws ColaVacia { int elem, i, n;

}

n = colaO.numElemCola (); for (i = 1; i <= n; i++) { elem = colaO.desencolar (); colaD.encolar (elem); colaO.encolar (elem); }

Si lo que se pretende es obtener la cola resultante (colaD) con sus elementos en orden contrario al inicial (colaO) sería necesario invertir posteriormente el resultado (ejecución del método invertir) una vez ejecutado el tratamiento iterativo. static void copiaIterativaInvertida (Cola colaO, Cola colaD) throws ColaVacia { int elem, i, n; n = colaO.numElemCola (); for (i = 1; i <= n; i++) { elem = colaO.desencolar (); colaD.encolar (elem); colaO.encolar (elem); } colaD.invertirCola (); }


2.4.6.4.2.3.6.4.


Insertar un elemento al principio de una cola.

Se trata de introducir en la cola un dato, pasado como argumento, que no se ubicará al final de la misma (tal como resultaría como consecuencia de ejecutar la operación encolar (cola, dato)), sino al principio de la misma. La Figura 2.8 muestra como ejemplo el resultado de ejecutar el algoritmo introduciendo el dato 77 en la cola cuya situación inicial es la representada en la Figura 2.7.

2

4

6

Figura 2.7. Situación inicial de la cola. 77

2

4

6

Figura 2.8. Resultado después de introducir el 77. Se resolverá de manera iterativa (conociendo el número de elementos). Para ello, la inserción inicial del dato al final de la cola se produce con anterioridad a la ejecución de la iteración (pero una vez contado el número de elementos que tiene la cola original). Se propone al alumno la realización del mismo ejemplo siguiendo los otros dos métodos propuestos. static void insertarPrincipioIterativo (Cola cola, int dato) throws ColaVacia { int elem, i, n; n = cola.numElemCola (); cola.encolar (dato); for (i = 1; i <= n; i++) { elem = cola.desencolar(); cola.encolar (elem); } }

2.4.6.5.2.3.6.5.

Terminación anticipada.

Como ya se ha indicado, en algunos casos no será necesario que en la ejecución del programa se procese toda la estructura produciendo, en consecuencia, una terminación anticipada. La solución depende de la técnica empleada: iterativa o recursiva si se conoce el número de elementos o, necesariamente recursiva si no se conoce. En cualquier caso deberá asegurarse que la estructura se devuelve en el orden correcto, lo que implica que todos los elementos deberán ser desencolados y encolados (además, cuando no se conoce el número de elementos, deberán invertirse tanto la cola completa como la parte de ella que no se haya tratado en el momento de la terminación anticipada). Pese a ello la terminación anticipada tiene interés en general, dado que se evitan copias innecesarias en la memoria en la fase de “ida” y en particular cuando dicho tratamiento resulte complejo.



A continuación se muestran ejemplos de un método (esta) que devuelve un valor booleano dependiendo de que durante el transcurso de exploración de la cola encuentre o no un valor (dato) que se pasa como argumento. Por último, se ve un método que permite obtener el elemento final de una cola. 2.4.6.5.1.2.3.6.5.1. Verificar si hay un elemento sin conocer el número de elementos. En esencia el algoritmo consiste en vaciar la cola (condición pesimista) verificando en cada llamada si el elemento desencolado coincide con el dato. En caso negativo se genera una nueva llamada recursiva pero en caso afirmativo se prepara el valor a devolver por el método (resul=true) y no se realiza una nueva llamada recursiva. Deberá asegurarse que se devuelve a la cola el último elemento desencolado. Si se alcanza la condición de terminación se entenderá que el elemento buscado no existe y, en consecuencia, el método devolverá el valor false. Un problema adicional es que el tratamiento recursivo produce el desorden parcial de los elementos de la cola. Es decir, en caso de que se produzca terminación anticipada la cola tendería a quedar con el siguiente aspecto: o El bloque de elementos previo al dato encontrado quedaría al final de la cola y con sus elementos en orden inverso. o El bloque de elementos posterior al dato encontrado quedaría al principio de la cola y con sus elementos en el orden inicial. o El dato buscado estaría situado entre ambos bloques. Por ejemplo, si en la cola indicada en la Figura 2.9 se busca el elemento de valor 12, el método devolvería correctamente el valor true pero dejaría sus elementos en la situación de la Figura 2.10. 2

4

6

8

10

12

14

16

18

20

Figura 2.9. Situación inicial de la cola. Se busca el valor 12. 14

16

18

20

12

10

8

6

4

2

Figura 2.10. Valor 12 encontrado. Situación actual de los elementos de la cola. Por lo tanto, para evitar este problema, se deberá utilizar un método externo (previo o posterior) de inversión de la cola inicial así como otra inversión de lo que queda de la cola una vez encontrado el dato (antes de volver a encolarlo). A continuación se muestra el código.



static boolean estaAux (Cola cola, int dato) throws ColaVacia { int elem; boolean resul; if (! cola.colaVacia ()) { elem = cola.desencolar (); if (elem == dato) { resul = true; cola.invertirCola (); } else resul = estaAux (cola, dato); cola.encolar (elem); } else resul = false; return resul; } static boolean esta (Cola cola, int dato) throws ColaVacia { cola.invertirCola (); return estaAux (cola, dato); }

2.4.6.5.2.2.3.6.5.2. Conociendo el número de elementos. Técnica recursiva. El algoritmo es más sencillo que en el caso anterior. El proceso es un conjunto desencolar – encolar (controlado por el argumento que indica inicialmente el valor de los elementos de la cola) en el que se pregunta si el elemento desencolado coincide con el dato que se busca. En caso negativo se realiza una nueva llamada recursiva y en caso afirmativo se asigna el valor que devolverá el método: true (no se realizan posteriores llamadas recursivas pero habrá que “recolocar” completamente la cola, por medio del método auxiliar recorrer). El cumplimiento de la condición pesimista (el módulo se ha ejecutado tantas veces como elementos tiene la cola) implica que el método devuelve el valor false. A continuación se muestra una posible solución. static boolean recorrer (Cola cola, int n) throws ColaVacia { boolean resul; int elem; if (n > 0) { elem = cola.desencolar (); cola.encolar (elem); resul = recorrer (cola, n-1); } else resul = true; return resul; } static boolean estaRecursivo (Cola cola, int n, int dato) throws ColaVacia { int elem; boolean resul; if (n > 0) { elem = cola.desencolar (); cola.encolar (elem); if (elem == dato) resul = recorrer (cola, n-1); else resul = estaRecursivo (cola, n-1, dato); } else resul = false; return resul; }



2.4.6.5.3.2.3.6.5.3. Conociendo el número de elementos. Técnica iterativa. Si tenemos el número de elementos, y queremos realizar el tratamiento de manera iterativa, el algoritmo será similar al caso anterior, si bien aquí sí es necesario complicar la lógica para facilitar la terminación anticipada (n > 0) && (!resul). Una vez que se ha encontrado el dato, hay que continuar desencolando y encolando hasta terminar de dar la vuelta completa a la cola (bucle for (i = 1; i<= n; i++)), como se puede ver en la siguiente solución: static boolean estaIterativo (Cola cola, int dato) throws ColaVacia { int n, elem, i; boolean resul; resul = false; n = cola.numElemCola (); while ((n > 0) && (!resul)) { elem = cola.desencolar (); cola.encolar (elem); if (elem == dato) resul = true; n = n-1; } for (i = 1; i <= n; i++) { elem = cola.desencolar (); cola.encolar (elem); } return resul; }

2.4.6.5.4.2.3.6.5.4. Obtener el elemento del final de una cola. Lo que se propone en este apartado es conseguir un efecto similar al de la operación desencolar pero actuando sobre el extremo opuesto, es decir, no queremos sacar el primer elemento de la cola, sino el último que hemos insertado. Se muestra como ejemplo de manera recursiva, sin conocer el número de elementos. Se propone al alumno la realización del mismo ejemplo siguiendo los otros dos métodos propuestos. Es un caso similar al explicado en el apartado de pilas (desfondar) con la salvedad de que aquí es necesario restaurar el orden inicial en los elementos de la cola. Para ello se utiliza la operación InvertirCola una vez ejecutado el tratamiento recursivo. Al contrario de lo que ocurría en el apartado 2.3.5.6.1., en este caso excepcionalmente no hay que invertir lo que queda de cola en la transición, dado que en este momento la cola está vacía.



static int quitarUltimo (Cola cola) throws ColaVacia { int elem, dato = -9999; if (!cola.colaVacia ()) { elem = cola.desencolar (); if (! cola.colaVacia ()) { dato = quitarUltimo (cola); cola.encolar (elem); } else dato = elem; } return dato; } static int quitarUltimoRecursivo1 (Cola cola) throws ColaVacia { int resul; resul = quitarUltimo (cola); System.out.println ("resultado "+resul); cola.invertirCola (); return resul; }

2.4.6.6.2.3.6.6.

Mezclar dos colas.

De forma análoga a lo explicado en el caso de mezcla de pilas, el problema específico de este tipo de procesos es la naturaleza “destructiva” de la operación desencolar. El problema puede resolverse mediante los tres enfoques habituales con colas: No se conoce el número de elementos. Se deberá utilizar necesariamente un tratamiento recursivo similar al explicado con pilas, pero teniendo en cuenta la circunstancia de que las colas pueden quedar total o parcialmente desordenadas y por tanto habrá que utilizar el módulo invertir. Se deja su resolución como ejercicio propuesto al alumno. Se conoce el número de elementos (n1 y n2). Se puede hacer: o De manera iterativa. Se deja como ejercicio propuesto al alumno o De manera recursiva. Se explica a continuación. Explicación de la técnica. La técnica es ligeramente diferente a la explicada en el caso de la mezcla de pilas. En este caso hay que desencolar “por adelantado”. Es decir: en la instancia actual se desencola de una o de ambas colas y se pasan como argumentos los elementos desencolados (elem1|elem2). En caso de desencolar de una sola cola, el elemento de la otra se propaga a la instancia siguiente. Este tipo de tratamiento supone una singularidad en la primera llamada: se necesita un módulo (de “lanzamiento”), no recursivo, que desencola y encola el primer elemento de cada una de las colas y los pasa como argumentos al módulo recursivo.



Condición de terminación. En este caso el control de la condición de finalización se realiza mediante los argumentos n1 y n2 que representan inicialmente el número de elementos de las respectivas colas. Dichos argumentos deberán pasarse por valor y decrementarse en cada llamada recursiva. La condición ((n1 == 0) || (n2 == 0)) significa que se ha desencolado el último elemento de la cola correspondiente (condición necesaria) pero no suficiente, dado que no se asegura que dichos elementos se hayan tratado (lo que se deberá hacer en la fase de”transición”). Así pues el proceso recursivo tiene lugar si (n1 >= 0 && n2 >= 0)9 Fase de “ida”: Se realiza el tratamiento específico con los elementos (elem1 y elem2) que se reciben como argumentos. Se desencola-encola de una de las colas o de ambas. Se realiza una llamada recursiva. Fase de “transición”: Se realiza, si procede, el tratamiento específico del ejercicio en cuestión. Se restaura, si procede, el orden establecido de las colas. Fase de “vuelta”: Se realiza, si procede, el tratamiento específico del ejercicio en cuestión. En general no será necesario realizar la operación de encolar dado que ya se ha hecho en la fase de “ida” (mecanismo desencolar-encolar). 2.4.6.6.1.2.3.6.6.1. Ejemplo 1. Realizar la intersección de dos colas. En este ejemplo se parte de dos colas (cola1 y cola2) ordenadas ascendentemente desde el punto de salida hacia el de llegada para obtener una nueva cola (cola3) con los elementos comunes de ambas ordenados en el mismo sentido. La Figura 2.11. muestra un ejemplo. 2

4

6

77

cola1 2

3

4

5

2 6

8

4

6

cola 3

cola2

Figura 2.11.Ejemplo de obtención de una cola con los elementos comunes de otras dos

9

O, dicho en otros términos: finaliza si: (n1 < 0 || n2 < 0)



Para resolver este ejemplo, utilizaremos la técnica recursiva conociendo el número de elementos. Como en este caso queremos introducir en la cola3 todos los elementos comunes de la cola1 y la cola2, la condición de parada de la recursividad será cuando hayamos tratado todos los elementos de una de las dos colas (n1 < 0 || n2 < 0). El diseño propuesto requiere el empleo de instrucciones externas al algoritmo recursivo: Previamente es necesario desencolar-encolar de ambas colas para disponer de los valores iniciales de elem1 y elem2. Así pues la cabecera del método recursivo quedaría: static void mezclaAndR2 (Cola cola1, Cola cola2, Cola cola3, int elem1, int elem2, int n1 , int n2)

Fase de “ida”: Se comparan los elementos procedentes de ambas colas. Tanto elem1 como elem2 proceden de operaciones de desencolar-encolar ejecutadas en instancias anteriores por lo que se procederá a encolar el menor de ellos (o uno cualquiera si son iguales) en cola3 (como cola3 debe tener sus elementos ordenados en el mismo sentido que cola1 y cola2, los elementos se encolarán en cola3 antes de realizar la correspondiente llamada recursiva). Se desencola-encola de las cola/s pertinentes si es posible (n1 |2 > 0), pasando así elem1|2 a la instancia siguiente. Fase de “transición”: Si una de las colas tiene elementos por tratar y la otra no, se llama al método auxiliar reOrdenar, que recoloca la cola que tiene elementos pendientes por tratar. Fase de “vuelta”: No hay que realizar ningún tratamiento específico, ni es necesario realizar la operación de encolar dado que ya se ha hecho en la fase de “ida” (mecanismo desencolar-encolar). A continuación se muestra el algoritmo que resuelve el problema



static void reOrdenar (Cola cola, int n) throws ColaVacia { int elem; if (n > 0) { elem = cola.desencolar (); cola.encolar (elem); reOrdenar (cola, n-1); } } static void mezclaAndR2 (Cola cola1, Cola cola2, Cola cola3, int elem1, int elem2, int n1 , int n2) throws ColaVacia { if ((n1 >= 0) && (n2 >= 0)) if (elem1 < elem2) { if (n1 > 0) { elem1 = cola1.desencolar (); cola1.encolar (elem1); } mezclaAndR2 (cola1,cola2,cola3,elem1,elem2,n1-1,n2); } else if (elem1 > elem2) { if (n2 > 0) { elem2 = cola2.desencolar (); cola2.encolar (elem2); } mezclaAndR2 (cola1,cola2,cola3,elem1,elem2,n1,n2-1); } else { cola3.encolar (elem1); if (n1 > 0) { elem1 = cola1.desencolar (); cola1.encolar (elem1); } if (n2 > 0) { elem2 = cola2.desencolar(); cola2.encolar (elem2); } mezclaAndR2 (cola1,cola2,cola3,elem1,elem2,n1-1,n2-1); } else { if (n1 >= 0) reOrdenar (cola1, n1 ); else if (n2 >= 0) reOrdenar (cola2, n2); } } static void mezclarColasAndR2 (Cola cola1,Cola cola2, Cola cola3) throws ColaVacia { int elem1, elem2, n1 , n2; n1 = cola1.numElemCola (); n2 = cola2.numElemCola (); if ((n1 > 0) && (n2 > 0)) { elem1 = cola1.desencolar (); cola1.encolar (elem1); elem2 = cola2.desencolar (); cola2.encolar (elem2); mezclaAndR2(cola1, cola2, cola3, elem1, elem2, n1-1, n2-1); } }



2.4.6.6.2.2.3.6.6.2. Ejemplo 2. Realizar la unión de dos colas. En este ejemplo se parte de dos colas (cola1 y cola2) ordenadas ascendentemente desde el punto de salida hacia el de llegada, y se desea obtener una nueva cola (cola3) con todos los elementos de ambas (sin repeticiones), ordenados en el mismo sentido. La Figura 2.12. muestra un ejemplo. 2

4

77

cola1 2

3

4

2 5

3

6

4

5

6

77

cola3

cola2

Figura 2.12.Ejemplo de obtención de una cola con los elementos de otras dos Para resolver este ejemplo, utilizaremos la técnica recursiva conociendo el número de elementos. Como en este caso queremos introducir en la cola3 todos los elementos de la cola1 y la cola2 sin repeticiones, la condición de parada de la recursividad será cuando hayamos tratado todos los elementos de ambas colas (n1 < 0 && n2 < 0). El diseño propuesto requiere el empleo de instrucciones externas al algoritmo recursivo: Previamente es necesario desencolar y encolar de ambas colas para disponer de los valores iniciales de elem1 y elem2. Así pues la cabecera del método recursivo quedaría: Static void MezclaOrR2 (Cola cola1, Cola cola2,Cola cola3,int elem1,int elem2,int n1 ,int n2);

El tratamiento implica básicamente, lo siguiente: Fase de ida: Comparar los elementos procedentes de ambas colas. Tanto elem1 como elem2 proceden de operaciones de desencolar ejecutadas en instancias anteriores por lo que se procederá a encolar el menor de ellos (o uno cualquiera de los dos si son iguales) en cola3 (como cola3 debe tener sus elementos ordenados en el mismo sentido que las cola1 y cola2, los elementos se encolan en cola3 antes de realizar la llamada recursiva). Se desencola-encola de las colas pertinentes si es posible (n1 |2 > 0), pasando así elem1|2 a la instancia siguiente. Fase de transición: Si una de las colas tiene elementos por tratar y la otra no, se copia el elemento pendiente de tratar en cola3 y se llama al método auxiliar copiarcola, que copia lo que queda de una de las colas en cola3.



Fase de “vuelta”: No hay que realizar ningún tratamiento específico, ni es necesario realizar la operación de encolar dado que ya se ha hecho en la fase de “ida” (mecanismo desencolar-encolar). A continuación se muestra el algoritmo que resuelve el problema. static void copiarcola (Cola origen, Cola destino, int n) throws ColaVacia { int elem; if (n > 0) { elem = origen.desencolar (); destino.encolar (elem); origen.encolar (elem); copiarcola (origen, destino, n-1); }

} static void mezclaOrR2 (Cola cola1, Cola cola2, Cola cola3, int elem1, int elem2, int n1 , int n2) throws ColaVacia { if ((n1 >= 0) && (n2 >= 0)) if (elem1 < elem2) { cola3.encolar (elem1); if (n1 >0) { elem1 = cola1.desencolar (); cola1.encolar (elem1); } mezclaOrR2 (cola1, cola2, cola3, elem1, elem2, n1-1, n2); } else if (elem1 > elem2) { cola3.encolar (elem2); if (n2 > 0) { elem2 = cola2.desencolar (); cola2.encolar (elem2); } mezclaOrR2 (cola1,cola2,cola3,elem1,elem2,n1,n2-1); } else { cola3.encolar (elem1); if (n1 > 0) { elem1 = cola1.desencolar (); cola1.encolar (elem1); } if (n2 > 0) { elem2 = cola2.desencolar (); cola2.encolar (elem2); } mezclaOrR2(cola1,cola2,cola3,elem1,elem2,n1-1,n2-1); } else { if (n1 >= 0) { cola3.encolar (elem1); copiarcola (cola1, cola3, n1); } else if (n2 >= 0) { cola3.encolar (elem2); copiarcola (cola2, cola3, n2); } } }



static void mezclarColaOrR2 (Cola cola1, Cola cola2, Cola cola3) throws ColaVacia { int elem1 = -9999, elem2 = -9999, n1 , n2; n1 = cola1.numElemCola (); n2 = cola2.numElemCola (); if (n1 > 0) { elem1 = cola1.desencolar (); cola1.encolar (elem1); } if (n2 > 0) { elem2 = cola2.desencolar (); cola2.encolar (elem2); } mezclaOrR2 (cola1, cola2, cola3, elem1, elem2, n1-1, n2-1); }

2.4.6.7.2.3.6.7.

Mezcla de colas con terminación anticipada.

Dadas dos colas (cola1 y cola2) ordenadas ascendentemente desde el inicio hasta el final (sin elementos repetidos en cada una de las colas), se desea realizar un método booleano que indique si los elementos de la cola2 están contenidos en la cola1. Este ejemplo se puede resolver a partir de la consideración de mezcla de colas en la modalidad AND (termina cuando se ha procesado por completo cualquiera de las colas). En este caso se produce una situación de terminación anticipada cuando, en su caso, aparece por primera vez un elemento de cola2 que no está en cola1 (elem1 > elem2). El proceso debe terminar y el método devuelve false. En caso contrario (terminación “pesimista”) pueden darse las siguientes circunstancias: Se ha procesado completa cola1 (n1 < 0) pero cola2 no (n2 >=0). Aún quedan elementos en cola2 por tanto no cumple la condición de “estar contenida” en cola1, y en consecuencia el resultado será false. Se ha procesado cola2 completa (n2 < 0) y pero cola1 no (n1 >= 0). Por tanto, cola2 estará contenida en cola1, y en consecuencia el resultado será true. Se ha conseguido llegar a la terminación “pesimista” (se han procesado completamente ambas colas: n1 < 0 y n2 < 0). Por lo tanto, cola2 está contenida en cola1 y el método devolverá el valor true. El diseño propuesto requiere el empleo de instrucciones externas al algoritmo recursivo: Previamente es necesario desencolar-encolar de ambas colas para disponer de los valores iniciales de elem1 y elem2. Aplicando a este caso el tratamiento genérico, se trata de: Fase de “ida”. Desencolar-encolar si procede (en función del valor de los argumentos n1 y n2). Se pueden dar los siguientes casos:



o elem1 > elem2. Es imposible que la cola2 se encuentre contenida en la cola1, por lo que habrá que recolocar ambas colas, utilizando el método auxiliar ordenada, y devolver false como resultado. o elem1 < elem2. Hay que desencolar de cola1 en la siguiente ejecución. La llamada recursiva se hace con n1-1 y n2. o elem1 == elem. La llamada recursiva se hace con n1-1 y n2-1. Fase de “transición” Si queda algún elemento pendiente de tratar en alguna de las colas (n1 >= 0 o n2 >= 0), habrá que reordenar la cola que corresponda (con ordenada) y asignar el resultado correspondiente al método. Fase de “vuelta”: No hay que realizar ningún tratamiento específico, ni es necesario realizar la operación de encolar dado que ya se ha hecho en la fase de “ida” (mecanismo desencolar-encolar). El código se muestra a continuación: static void ordenar (Cola cola, int n) throws ColaVacia { int elem; if (n > 0) { elem = cola.desencolar (); cola.encolar (elem); ordenar (cola, n-1); } } static boolean contenida (Cola cola1, Cola cola2, int elem1, int elem2, int n1 , int n2) throws ColaVacia { boolean resul; if ((n1 >= 0) && (n2 >= 0)) if (elem1 < elem2) { if (n1 > 0) { elem1 = cola1.desencolar (); cola1.encolar (elem1); } resul = contenida (cola1, cola2, elem1, elem2, n1-1, n2); } else if (elem1 > elem2) { ordenar (cola1, n1 ); ordenar (cola2, n2); resul = false; } else { if (n1 > 0) { elem1 = cola1.desencolar (); cola1.encolar (elem1); } if (n2 > 0) { elem2 = cola2.desencolar (); cola2.encolar (elem2); } resul = contenida (cola1, cola2, elem1, elem2,n1-1,n2-1); } else { if (n1 >= 0) { ordenar (cola1, n1); resul = true; }



else if (n2 >= 0) { ordenar (cola2, n2); resul = false; } else resul = true;

} return resul;

} static boolean estaContenida (Cola cola1, Cola cola2) throws ColaVacia { int elem1, elem2, n1, n2; boolean resul; n1 = cola1.numElemCola (); n2 = cola2.numElemCola (); if ((n1 > 0) && (n2 > 0)) { elem1 = cola1.desencolar (); cola1.encolar (elem1); elem2 = cola2.desencolar (); cola2.encolar (elem2); resul = contenida (cola1, cola2, elem1, elem2, n1-1, n2-1); } else if (n2 > 0) resul = false; else resul = true; return resul; }



2.5.2.4. CONSTRUCCIÓN DE UN TAD A PARTIR DE OTRO. Se pretende en este apartado mostrar la posibilidad de construir nuevos TAD a partir de otros. A continuación se muestra un ejemplo en el que se construye a partir del TAD pila un TAD vector de números enteros tad_Vector. Dispone de las siguientes funcionalidades: o crearVector (). Prepara un nuevo vector de tipo TSVector. El método solicita al el número de elementos y los inicializa con 0. o escribirVector (pos, dato). Método que lleva a la posición pos del vector el valor indicado en el argumento dato. Deberá de verificar que se trata de una posición válida (no superior al número de elementos indicado en la creación del vector). o leerVector (pos). Método que devuelve el contenido de la posición pos del vector. Deberá verificar, igualmente, que se trata de una posición válida. o tamaño ().Método que devuelve el tamaño actual del vector. En virtud de la característica de ocultamiento, propia de la los TAD’s, el imagina y trabaja con algo que se comporta como un vector sin saber cómo está construido (Figura 2.13.).

0 10

1 0

2 30

3 0

4 50

Figura 2.13. TAD Vector. Primero definiríamos un interfaz en el que indicaríamos cuales son las operaciones del nuevo TAD: import java.io.IOException; public interface Vector { void crearVector () throws NumberFormatException, IOException; int leerVector (int posicion) throws PilaVacia; void escribirVector (int posicion, int contenido) throws PilaVacia; int tamaño (); }

A continuación, se construyen las operaciones. Se utilizan dos métodos auxiliares (leer y escribir), que se definen como privados.



import java.io.IOException; import java.io.InputStreamReader; import tadPila.Pila; import tadPila.TadPila; import tadPila.PilaVacia; public class TadVector implements Vector { Pila vector; public int tamano; public void crearVector () throws NumberFormatException, IOException { int i; BufferedReader linea = new BufferedReader(new InputStreamReader (System.in)); Pila auxv = new TadPila ();

}

System.out.println ("Numero de elementos: "); tamano = Integer.parseInt(linea.readLine()); for (i = 1; i <= tamano; i++) auxv.apilar (0); vector = auxv;

private int leer (int i, int posicion, Pila vector) throws PilaVacia { int resul, elem;

}

if (i < posicion) { elem = vector.desapilar (); resul = leer (i+1, posicion, vector); vector.apilar (elem); } else { elem = vector.desapilar (); resul = elem; vector.apilar (elem); } return resul;

public int leerVector (int posicion) throws PilaVacia { int resul, i;

}

if ((posicion > tamano) || (posicion <= 0)) { System.out.println ("Error. Valor fuera de rango"); resul = 99999; } else { i = 0; resul = leer (i+1, posicion, vector); } return resul;

private void escribir (int i, int posicion, int contenido, Pila vector) throws PilaVacia { int elem;

}

if (i < posicion) { elem = vector.desapilar (); escribir (i+1, posicion, contenido, vector); vector.apilar (elem); } else { elem = vector.desapilar (); vector.apilar (contenido); }



public void escribirVector (int posicion, int contenido) throws PilaVacia { if ((posicion > tamano) || (posicion < 0)) System.out.println ("Error. Indice fuera de rango"); else escribir (1, posicion, contenido, vector); } public int tamaño () { return tamano; } }

El siguiente es un sencillo programa que prueba el nuevo TAD. import java.io.IOException; public class PruebaVector { public static void main(String[] args) throws NumberFormatException, IOException, Pilavacia { Vector v = new TadVector (); int d,i; v.crearVector (); v.escribirVector (5, 77); v.escribirVector (3, 87); v.escribirVector (8, 97); for (i = 1; i <= v.tamaño (); i++) { d = v.leerVector (i); System.out.println ("El dato de la posicion "+i+" es: "+d); } } }



TEMA 2 ...................................................................................................................... 51 2.1.

Concepto ....................................................................................................... 51

2.2.

TAD Pila de números enteros. ..................................................................... 53

2.2.1.

Concepto. .............................................................................................. 53

2.2.2.

Modelo gráfico ..................................................................................... 53

2.2.3.

Especificaciones ................................................................................... 53

2.2.4.

Interfaz del TAD Pila. .......................................................................... 54

2.2.5.

Prueba del TAD pila. ............................................................................ 55

2.2.6.

Algoritmos básicos con pilas. ............................................................... 56

2.3.

TAD Cola de números enteros. .................................................................... 70

2.3.1.

Concepto. .............................................................................................. 70

2.3.2.

Modelo gráfico. .................................................................................... 70

2.3.3.

Especificaciones ................................................................................... 70

2.3.4.

Interfaz del TAD Cola. ......................................................................... 71

2.3.5.

Prueba del TAD Cola. .......................................................................... 72

2.3.6.

Algoritmos básicos con colas. .............................................................. 73

2.4.

Construcción de un TAD a partir de otro. .................................................... 90


LISTAS 93

TEMA 3

Listas. 3.1. CONCEPTOS GENERALES. Una lista es una estructura de datos lineal que se puede representar simbólicamente como un conjunto de nodos enlazados entre sí. Las listas permiten modelar diversas entidades del mundo real como por ejemplo, los datos de los alumnos de un grupo académico, los datos del personal de una empresa, los programas informáticos almacenados en un disco magnético, etc. La figura 3.1 muestra un ejemplo de lista correspondiente a los nombres y apellidos de un conjunto de alumnos con su código de matrícula. Arias González, Felipe

aa1253 García Sacedón, Manuel

ax0074

López Medina, Margarita

Ramírez Heredia, Jorge

Yuste Peláez, Juan

lp1523

gb1305

Figura 3.1. Ejemplo de Lista

mj7726

94 LISTAS


Tal vez resulte conveniente identificar a los diferentes elementos de la lista (que normalmente estarán configurados como una estructura de registro) mediante uno de sus campos (clave) y en su caso, se almacenará la lista respetando un criterio de ordenación (ascendente o descendente) respecto al campo clave. Una definición formal de lista es la siguiente: “Una lista es una secuencia de elementos del mismo tipo, de cada uno de los cuales se puede decir cuál es su siguiente (en caso de existir).” Existen dos criterios generales de calificación de listas: Por la forma de acceder a sus elementos. o Listas densas. Cuando la estructura que contiene la lista es la que determina la posición del siguiente elemento. La localización de un elemento de la lista es la siguiente:  Está en la posición 1 si no existe elemento anterior.  Está en la posición N si la localización del elemento anterior es (N-1). o Listas enlazadas: La localización de un elemento es:  Estará en la dirección k, si es el primer elemento, siendo k conocido.  Si no es el primer elemento de la lista, estará en una dirección, j, que está contenida en el elemento anterior. Por la información utilizada para acceder a sus elementos: o Listas ordinales. La posición de los elementos en la estructura la determina su orden de llegada. o Listas calificadas. Se accede a un elemento por un valor que coincide con el de un determinado campo, conocido como clave. Este tipo de listas se pueden clasificar a su vez en ordenadas o no ordenadas por el campo clave.


LISTAS 95

3.2. IMPLEMENTACIÓN DE LISTAS. El concepto de lista puede implementarse en soportes informáticos de diferentes maneras. Mediante estructuras estáticas. Con toda seguridad resulta el mecanismo más intuitivo. Una simple matriz resuelve la idea (figura 3.2). 0 1 2 3 4

Arias González, Felipe García Sacedón, Manuel López Medina, Margarita Ramírez Heredia, Jorge Yuste Peláez, Juan

aa1253 ax0074 mj7726 lp1523 gb1305

Figura 3.2. Implementación de una lista densa mediante una estructura estática (matriz). El problema de esta alternativa es el derivado de las operaciones de inserción y modificación. En efecto, la declaración de una lista mediante una matriz implica conocer de antemano el número (o al menos el orden de magnitud) de elementos que va a almacenar, pudiendo darse las circunstancias de que si se declara pequeño podría desbordarse su capacidad o, en caso contrario, declararlo desproporcionadamente elevado provocaría un decremento de eficiencia. Otro problema asociado es el tratamiento de los elementos eliminados. Dado que en el caso de no informar, de alguna manera, de la inexistencia de dicho elemento el nodo previamente ocupado (y ahora no válido) quedaría como no disponible. Adicionalmente, si se desea trabajar con listas ordenadas el algoritmo de inserción debería alojar a los nuevos elementos en la posición o con la referencia adecuada. Algunas soluciones, más o menos ingeniosas, permiten tratar estas circunstancias. La figura 3.3 muestra un ejemplo basado en una matriz de registros. 0 1

2

3

4

5

6

7

8

1 10 77 12 26 21 11 13 18 2 3 4 7 6 0 8 5 0

Figura 3.3. Ejemplo de implementación de lista enlazada mediante una estructura estática (matriz). Otra posible representación de esta lista sería la siguiente:

96 LISTAS


10

12

13

21

Figura 3.4. Lista enlazada correspondiente a la figura 3.3. El tratamiento de las listas sobre matriz (tanto densas como enlazadas) se desarrollará más adelante, en el apartado 3.8. Mediante estructuras dinámicas. Sin duda se trata de la mejor alternativa para la construcción de listas. Se trata de hacer uso de la correspondiente tecnología que implica el uso de referencias. La idea consiste en declarar una referencia a un nodo que será el primero de la lista. Cada nodo de la lista (en la memoria dinámica) contendrá tanto la propia información del mismo como una referencia al nodo siguiente. Se deberá establecer un convenio para identificar el final de la lista1. La figura 3.5 muestra un ejemplo de implementación dinámica de la lista de la figura 3.4.

Memoria estática

Lista

10

21 1

Memoria dinámica

*

12 13

Figura 3.5. Implementación de una lista mediante estructuras dinámicas. Lo explicado hasta el momento consiste en la solución más sencilla: cada nodo de la lista “apunta” al siguiente, con las excepciones del último elemento de la lista (su “apuntador, o “referencia” es un valor especial, por ejemplo null, en java) y del primero, que es “apuntado” por la referencia declarada en la memoria estática. Esta tecnología se identifica como “Listas enlazadas o unidireccionales”. Existen otras posibilidades entre las que cabe mencionar: listas bidireccionales o doblemente enlazadas, listas circulares, listas con cabecera, listas con centinela o cualquier combinación de ellas.

1

En java la referencia final tomará el valor null.


LISTAS 97

3.3. TRATAMIENTO DE LISTAS EN JAVA Para la utilización de listas es necesario definir la clase NodoLista utilizando la siguiente sintaxis: class NodoLista { public int clave; public NodoLista sig; public NodoLista(int x, NodoLista n) { clave = x; sig = n; } }

Así como la clase Lista: public class Lista { public Lista (String nombreLista) { inicio = null; nombre = nombreLista; } public NodoLista inicio; public String nombre; }

La representación gráfica de una variable de la clase Lista llamada lista1 que contenga los elementos 10, 13 y 21 sería: lista1

“lista1”

Variable estática

nombre

10 inicio

Clase Lista

dato

13 sig

NodoLista

dato

sig

NodoLista

Figura 3.6. Ejemplo de lista enlazada.

21

null

dato

sig

NodoLista

98 LISTAS


3.4. ALGORITMOS BÁSICOS CON LISTAS2. Los algoritmos que implican el recorrido, parcial o total, de la lista pueden implementarse tanto de forma recursiva como iterativa. 3.4.1. Recorrido completo. El recorrido de una lista de manera recursiva se puede realizar por medio de un método static invocado desde un programa que utilice la clase Lista. Esto implica utilizar el tipo NodoLista para avanzar por la lista y ver el contenido del campo clave. Merecen una consideración especial: La llamada inicial donde lista es el valor de la variable estática. El final del recorrido, que se alcanza cuando la lista está vacía. En el siguiente método estático (escribirLista), se recorre una lista (nodoLista) mostrando en la pantalla el contenido de sus campos clave. Se utiliza un método de llamada (escribirListaCompleta), que recibe como argumento un objeto de la clase Lista (lista): static void escribirLista (NodoLista nodolista) { if (nodoLista != null) { System.out.print (nodoLista.clave + " "); escribirLista (nodoLista.sig); } else System.out.println (" FIN"); } static void escribirListaCompleta (Lista lista) { if (lista != null) { System.out.print (lista.nombre + “: “); escribirLista (lista.inicio); } else System.out.println ("Lista vacía); }

Si se aplica el algoritmo anterior a la lista de la figura 3.6, el resultado sería la secuencia: lista1: 10 13 21 FIN.

La ejecución de escribirListaCompleta implicaría una llamada inicial al método escribirLista, pasando como argumento lista.inicio (la referencia al nodo de clave 10) y 3 llamadas recursivas al método escribirLista:

2

Los siguientes algoritmos se han desarrollado considerando implementaciones de la lista como estructuras dinámicas. A efectos de la realización de prácticas se utiliza la sintaxis del lenguaje java.


LISTAS 99

En la primera llamada recursiva, nodoLista es el contenido del campo sig del nodo de clave 10. Es decir, una referencia al nodo de clave 13. En la segunda, nodoLista es el contenido del campo sig del nodo de clave 13. Es decir, una referencia al nodo de clave 21. En la tercera, nodoLista es el contenido del campo sig del nodo de clave 21, es decir, null. Cuando se ejecuta esta tercera llamada se cumple la condición de finalización y, en consecuencia, se inicia el proceso de “vuelta”. Ahora nodoLista toma sucesivamente los valores: o Referencia al nodo de clave 21 (campo sig del nodo de clave 13). o Referencia al nodo de clave 13 (campo sig del nodo de clave 10). o Referencia al nodo de clave 10 (el primer elemento de la lista). El recorrido de una lista es una operación necesaria en los algoritmos de eliminación y, en muchos casos, también en los de inserción. La condición de finalización “pesimista” consiste en alcanzar el final de la lista (nodoLista == null). No obstante, normalmente se produce una terminación anticipada que se implementa no realizando nuevas llamadas recursivas. En los siguientes apartados se van a presentar los diferentes tipos de listas, sobre las cuales se explican algunos algoritmos básicos: inicialización, búsqueda, inserción y eliminación.

100 LISTAS


3.5. LISTAS ORDINALES. En las listas ordinales el orden dentro de la estructura lo establece la llegada a la misma. A diferencia de las listas calificadas, en este tipo de listas no existe ningún elemento que identifique el nodo, y por lo tanto, los valores se pueden repetir. El criterio de inserción resulta específico en cada caso (se podría insertar por el principio, o bien por el final). Veremos a continuación dos ejemplos de listas ordinales que ya hemos tratado como TADs: las pilas y las colas. 3.5.1. Pilas. Como se ha visto en el tema 2, una pila es una agrupación de elementos de determinada naturaleza o tipo (datos de personas, números, procesos informáticos, automóviles, etc.) entre los que existe definida una relación de orden (estructura de datos). En función del tiempo, algunos elementos de dicha naturaleza pueden llegar a la pila o salir de ella (operaciones / acciones). En consecuencia el estado de la pila varía. En una pila (comportamiento LIFO -Last In First Out-) se establece el criterio de ordenación en sentido inverso al orden de llegada. Así pues, el último elemento que llegó al conjunto será el primero en salir del mismo, y así sucesivamente. Las figuras 2.12 y 2.13 ilustran respectivamente el concepto de pila de números enteros y su implementación mediante una lista dinámica. desapilar

apilar 5 4 1 7 2

cima

fondo

Figura 3.7. Modelo gráfico de Pila 5

4

1

7

2

null

Pila apilar

desapilar

Figura 3.8. Implementación de una pila mediante una lista dinámica La estructura de datos de la pila y el constructor utilizado sería:


LISTAS 101

package tadPila; //En esta clase se define el nodo: class NodoPila { // Constructor NodoPila (int elemento, NodoPila n) { dato = elemento; siguiente = n; } // Atributos accesibles desde otras rutinas del paquete int dato; NodoPila siguiente; }

Y la interfaz utilizada sería la que se ha visto en el tema de TADs: package tadPila; import java.io.*; public interface Pila { void inicializarPila (); boolean pilaVacia (); void eliminarPila (); int cima () throws PilaVacia; void apilar (int x); int desapilar () throws PilaVacia; void decapitar () throws PilaVacia; void imprimirPila (); void leerPila () throws NumberFormatException, IOException; int numElemPila (); }

A continuación se muestra la clase TadPila, con el constructor y los algoritmos correspondientes a las operaciones pilaVacia, inicializarPila, así como apilar y desapilar que operan al principio de la lista por razones de eficiencia. package tadPila; public class TadPila implements Pila { protected NodoPila pila; public TadPila () { pila = null; } public void inicializarPila() { pila = null; } public boolean pilaVacia () { return pila == null; } public void apilar (int dato) { NodoPila aux = new NodoPila (dato,pila); pila = aux; }

102 LISTAS


public int desapilar () throws PilaVacia { int resultado; if (pilaVacia ()) throw new PilaVacia ("Desapilar: La pila está vacía"); resultado = pila.dato; pila = pila.siguiente; return resultado; } }

3.5.2. Colas. Como se ha visto en el tema 2, una cola es una agrupación de elementos de determinada naturaleza o tipo (datos de personas, números, procesos informáticos, automóviles, etc.) entre los que existe definida una relación de orden. En función del tiempo, pueden llegar a la cola o salir de ella algunos elementos de dicha naturaleza (operaciones/acciones). En consecuencia el estado de la cola varía. En una cola (comportamiento FIFO -First In First Out-) se respeta como criterio de ordenación el momento de la llegada: el primero de la cola, será el que primero llegó a ella y, en consecuencia, el primero que saldrá, y así sucesivamente. Las figuras 2.14 y 2.15 ilustran respectivamente el concepto de cola de números enteros y su implementación mediante una lista dinámica. desencolar

2 1 4 3 5

encolar

Figura 3.9. Modelo gráfico de Cola Debido al comportamiento de la cola, la forma más eficiente de implementarla por medio de listas enlazadas, es utilizando dos referencias: una al principio de la cola (por donde desencolaremos) y otra al final (por donde encolaremos): principio

fin

Cola 2

1

4

3

desencolar

5

null

encolar

Figura 3.10. Implementación de una cola mediante una lista dinámica La estructura de datos de la cola y el constructor sería:


LISTAS 103

package tadCola; //En esta clase se define el nodo: class NodoCola { // Constructor NodoCola (int elemento, NodoCola n) { dato = elemento; siguiente = n; } // Atributos accesibles desde otras rutinas del paquete int dato; NodoCola siguiente; }

Y la interfaz utilizada sería la que se ha visto en el tema de TADs: package tadCola; import java.io.IOException; public interface Cola { void inicializarCola (); boolean colaVacia (); void eliminarCola (); int primero ()throws ColaVacia; void encolar (int x); int desencolar () throws ColaVacia void quitarPrimero ()throws ColaVacia; void mostrarEstadoCola (); void imprimirCola (); void leerCola () throws NumberFormatException, IOException; int numElemCola (); void invertirCola ()throws ColaVacia; }

A continuación se muestrala clase TadCola, que contiene el constructor, así como los algoritmos correspondientes a las operaciones inicializarCola, colaVacia, desencolar (opera al principio de la lista verificando la situación de excepción de recibir una cola vacía), encolar (opera al final de la lista)3, numElemCola e invertirCola.

104 LISTAS


public class TadCola implements Cola { private NodoCola principio; private NodoCola fin; public TadCola () { principio = null; fin = null; } public void inicializarCola () { principio = null; fin = null; } public boolean colaVacia () { return principio==null; } public void encolar (int x) { NodoCola aux = new NodoCola(x,null); if (principio == null) { principio = aux; fin = aux; } else { fin.siguiente = aux; fin = aux; } } public int desencolar () throws ColaVacia { int resultado; if (colaVacia ()) throw new ColaVacia ("Desencolar: La cola está vacía"); resultado = principio.dato; principio = principio.siguiente; if (principio == null) fin = null; return resultado; } public int numElemCola () { NodoCola aux; int resul; aux = principio; resul = 0; while (aux != null) { ++resul; aux = aux.siguiente; } return resul; } public void invertirCola ()throws ColaVacia { int elem; if (!colaVacia ()) { elem = desencolar (); invertirCola (); encolar (elem); } } } 3

Se propone otra solución basada en una lista circular (apartado 3.7.1.) en la que la referencia a la lista es la del último nodo. De esta forma también se tiene a ambos extremos (cola: último y cola.sig: primero).


LISTAS 105

3.6. LISTAS CALIFICADAS. Se caracterizan por la existencia de un campo que identifica de manera unívoca cada uno de los nodos de la lista (identificativo o clave); lógicamente dicho valor debe ser único. Consideraremos dos casos: listas calificadas ordenadas y listas calificadas no ordenadas, en función de que la organización física de la lista se establezca siguiendo un criterio de ordenación (ascendente o descendente) o no de la clave. En ambos casos, no se permitirá la inserción de elementos con la clave repetida. A lo largo de los siguientes apartados utilizaremos una lista calificada, cuyos nodos estarán compuestos por una clave y la referencia al siguiente nodo, utilizando la siguiente estructura: public class NodoLista { public int clave; public NodoLista sig; public NodoLista (int x, NodoLista n) { clave = x; sig = n; } }

La clase Lista incluirá las variables miembro y el constructor que aparecen a continuación: public class Lista { public NodoLista inicio; public String nombre; public Lista (String nombreLista) { inicio = null; nombre = nombreLista; } }

3.6.1. Listas calificadas no ordenadas. En los siguientes apartados, utilizaremos una lista calificada, con sus elementos sin ordenar. La inicialización y el recorrido completo serían similares a los vistos en el apartado 3.2. (algoritmos básicos con listas), cambiando los tipos de datos. En los siguientes apartados, veremos como se buscan, añaden y borran elementos de una lista calificada no ordenada.

106 LISTAS


3.6.1.1. Búsqueda. Se trata de localizar una clave de valor determinado (pasado como argumento) sin entrar en consideraciones de qué se va a hacer con ella. En cualquier caso este tipo de algoritmos no tienen efecto alguno sobre la estructura (no se modifica el número de nodos). En principio la condición de finalización se consigue al llegar al final de la lista (inicio == null). Se produce una terminación anticipada en caso de encontrar la clave buscada. El siguiente algoritmo es un ejemplo de método booleano de objeto (busqueda) que recibiendo como argumento un dato (elem) devuelve true en caso de encontrar el elemento, y false si el elemento no está en la lista. static boolean busqueda (NodoLista nodoLista, int x) { boolean resul = false; if (nodoLista != null) if (nodoLista.clave == x) resul = true; else resul = busqueda (nodoLista.sig, x); return resul; } public boolean busqueda (int x) { return busqueda (inicio, x); }

3.6.1.2.Inserción. El efecto de este tipo de algoritmos es incrementar el número de nodos. Para crear un nuevo nodo es necesario conocer tanto la naturaleza de la estructura utilizada (estática o dinámica) como los recursos del lenguaje de programación empleado. Por ejemplo, en el caso de las estructuras dinámicas en java el método es el siguiente: NodoLista aux = new NodoLista (dato, null);

De esta forma se crea un nuevo nodo (apuntado por aux) cuya clave contiene el dato a insertar. De momento el nuevo nodo no está enlazado en la lista. El punto de inserción dependerá del criterio que se establezca. Lo más sencillo y eficiente es insertar el nuevo nodo al principio de la lista. El resultado será el ilustrado en la figura 3.7.


inicio

aux

LISTAS 107

Situación inicial 10

13

Creación del nuevo nodo aux

11

21

null

null

Inserción al principio 11

inicio

10

13

21

inicio

Situación final 11

10

13

21

null

Figura 3.11. Inserción al principio de la lista. El siguiente algoritmo muestra el método completo4: public void insertarAlPrincipio (int x) { NodoLista aux = new NodoLista (x, inicio); inicio = aux; }

El problema que tendría este algoritmo es que, dado que no comprueba si el elemento existe o no en la lista, podrá insertar claves repetidas. Para evitarlo, se podría realizar primero una búsqueda, y si la clave no estuviese ya en la lista (resultado del método busqueda (dato) == true), se insertaría. Otra posibilidad es realizar la inserción al final de la lista, comprobando si existe ya algún nodo con la clave buscada, utilizando un algoritmo recursivo. Se utilizará un método de objeto de la clase Lista, que invoca a un método static al que se le pasa como argumento un NodoLista, y devuelve como resultado un NodoLista. En el método static vamos avanzando por la lista, haciendo las llamadas recursivas con nodoLista.sig. Si llegamos hasta el final de la lista sin localizar la clave buscada, se crea un nuevo nodo (aux), y lo devuelve como resultado. Para enlazar correctamente el nodo, a la vuelta de la recursividad, se hace que nodoLista.sig apunte al mismo sitio que nos ha devuelto la llamada anterior como resultado. static NodoLista insertarAlFinal (NodoLista nodoLista, int dato) { NodoLista aux = nodoLista; if (nodoLista!= null) if (nodoLista.clave != dato) nodoLista.sig = insertarAlFinal (nodoLista.sig, dato); else System.out.println ("la clave ya existe"); else aux = new NodoLista (dato, nodoLista); return aux; } public void insertar (int dato) { inicio = insertarAlFinal (inicio, dato); }

4

Se contempla la situación excepcional de que la lista se encuentre inicialmente vacía.

108 LISTAS


La figura 3.8 ilustra el proceso seguido tras alcanzar la condición de finalización (nodoLista == null)5.

inicio


13

21

null

Inserción al final aux

11

inicio

10

13

21

inicio

Situación final 10

13

21

null

11

null

Figura 3.12. Inserción al final de la lista. Si se desea realizar la inserción en una lista calificada no ordenada de manera iterativa, se podría utilizar el algoritmo que aparece a continuación. Obsérvese que, además de la variable aux, es necesario utilizar otros dos referencias, actual y anterior para recorrer la lista y verificar que el elemento no existe. Se utiliza, además, la variable seguir, de tipo boolean, que inicialmente es true y lo seguirá siendo a no ser que encontremos la clave en la lista. public void insertarIterativo (int dato) { NodoLista anterior, actual, aux; boolean seguir; anterior = inicio; actual = inicio; seguir = true; while ((actual != null) && seguir) if (actual.clave == dato) seguir= false; else { anterior = actual; actual = actual.sig; } if (seguir) { aux = new NodoLista (dato, null); if (inicio == null) inicio = aux; else anterior.sig = aux; } else System.out.println ("Error. Elemento repetido"); }

Al realizar la inserción de manera iterativa, es necesario distinguir dos casos posibles: cuando insertamos un nodo en una lista vacía (tenemos que cambiar la referencia inicio), y cuando la lista ya tenía elementos previamente (insertamos al final, como nodo siguiente del elemento apuntado por anterior) 5

Obsérvese que el algoritmo es válido cuando se recibe una lista inicialmente vacía.


LISTAS 109

3.6.1.3.Eliminación. Este tipo de algoritmos reduce el número de nodos de la estructura. En la mayoría de los lenguajes de programación deberá prestarse atención especial a liberar el espacio de memoria de los nodos eliminados para posibles usos posteriores.6 Se procede a recorrer la lista comparando las sucesivas claves con el argumento recibido (dato). La condición de finalización “pesimista” sería alcanzar el final de la lista, lo que significaría que no se habría encontrado la clave a eliminar. No obstante lo normal es que se produzca una terminación anticipada en el momento en que se encuentra la clave a eliminar. La figura 3.9 ilustra gráficamente el mecanismo de eliminación. Situación inicial y localización de la clave a borrar aux inicio

10

23

21

null

21

null

Cambio de los enlaces aux inicio

10

23

inicio

Situación final 10

21

null

Figura 3.13. Eliminación de un nodo de la lista El algoritmo utilizado es: static NodoLista eliminar (NodoLista nodoLista, int dato) { NodoLista resul = nodoLista; if (nodoLista!= null) if (nodoLista.clave != dato) nodoLista.sig = eliminar (nodoLista.sig, dato); else resul = nodoLista.sig; else System.out.println ("la clave no existe"); return resul; } public void eliminar (int dato) { inicio = eliminar (inicio, dato); }

6

En java no es necesario porque se realiza automáticamente, pero en los ejemplos se liberará la memoria no utilizada.

110 LISTAS


3.6.1.4. Listas Reorganizables. Se denomina así al tipo de listas en las que la posición de los elementos va variando en función de los s que se hacen sobre la estructura. Cada vez que se accede a un nodo de la lista, éste pasa a convertirse en el primer elemento de la misma, desplazando al elemento que antes era el primero. Normalmente este tipo de listas se emplean con la intención de mejorar la eficiencia de un proceso. Por ejemplo, cuando se piensa que existe cierta probabilidad de acceder con mayor frecuencia a determinadas claves, suele proporcionar buenos resultados reubicar los nodos a los que se haya accedido recientemente al principio de la lista, mientras que los que se consultan poco se desplazan a las posiciones finales de la lista. Lógicamente este tratamiento no tiene sentido para listas calificadas ordenadas. Los métodos de inserción o borrado, serían los correspondientes a las listas enlazadas calificadas no ordenadas. A continuación, se realizará la búsqueda de un elemento de la lista (pasamos la clave que estamos buscando, y recibimos como resultado true si hemos encontrado dicha clave, y false en caso contrario). El algoritmo se desarrolla en dos métodos (reorganizar, y buscarYSaltar), que utilizan la variable miembro aux de tipo NodoLista. El método reorganizar recibe como argumento la clave, y se la pasa a buscarYSaltar. Dicho método devolverá como resultado una referencia (aux) con la dirección del nodo de clave cuyo valor se busca (o null en caso de que no exista) a la vez que separa dicho nodo de la lista. Una vez conocida dicha referencia, si es distinta de null, se procede a insertar al principio de la lista el nodo apuntado por aux. La figura 3.23 muestra una ilustración del proceso en el que se accede al nodo de clave 13.

inicio


15

13

21

14

9

null

inicio

Después de buscarYSaltar 10 15

13

21

14

9

null

inicio

Situación final 13

15

21

14

9

null

aux

10

Figura 3.14. Lista reorganizable. El método de búsqueda, con tratamiento recursivo, es equivalente al explicado para las listas calificadas no ordenadas, si bien incluye la variante de desenlazar de la lista el nodo cuya clave se busca para pasar su referencia al módulo principal.


En el código que aparece a continuación se muestra la solución descrita. static NodoLista buscarYSaltar (NodoLista nodoLista, int dato) { NodoLista resul; if (nodoLista == null) resul = null; else if (nodoLista.clave != dato) { resul = buscarYSaltar (nodoLista.sig, dato); if ((nodoLista.sig == resul) && (resul != null)) nodoLista.sig = resul.sig; } else resul = nodoLista; return resul; } static boolean reorganizar (Lista lista, int dato) { boolean resul = false; NodoLista aux; aux = buscarYSaltar (lista.inicio, dato); if (aux != null) { aux.sig = lista.inicio; lista.inicio= aux; resul = true; } return resul; }

LISTAS 111

112 LISTAS


3.6.2. Listas calificadas ordenadas. En los siguientes apartados, utilizaremos una lista calificada, con sus elementos ordenados ascendentemente. Los algoritmos de búsqueda, inserción y eliminación en listas calificadas ordenadas presentan las siguientes diferencias con respecto al caso de las listas no ordenadas: Los algoritmos de búsqueda y eliminación deben considerar como posibilidad adicional de finalización anticipada la situación de encontrar una clave superior al dato pasado como argumento. Esto se interpreta como una situación de error consistente en que la clave buscada no existe. En el caso de inserción la condición de finalización pesimista (nodoLista == null) se entiende como que la clave a insertar es de valor superior a la última de la lista. También es válido para insertar en una lista vacía. La terminación anticipada se produce cuando, como consecuencia de la exploración de la lista se encuentra una clave de valor igual o superior al de la clave a insertar. A continuación se muestran ejemplos de dichos algoritmos. 3.6.2.1. Búsqueda. Se trata de localizar una clave de valor determinado (pasado como argumento) sin entrar en consideraciones de qué se va a hacer con ella. En cualquier caso este tipo de algoritmos no tienen efecto alguno sobre la estructura (no se modifica el número de nodos). En principio la condición de finalización se consigue al llegar al final de la lista (inicio == null). Se produce una terminación anticipada en caso de encontrar la clave buscada o una de valor superior a la misma. El siguiente algoritmo es un método de objeto (busqueda) que, recibiendo como argumento un dato (elem) devuelve true en caso de encontrarlo, y false si el elemento no está en la lista. Llamamos a un método recursivo static (también llamado busqueda) al que le pasamos como argumento un NodoLista (inicio). static boolean busqueda (NodoLista nodoLista, int x) { boolean resul = false; if (nodoLista != null) if (nodoLista.clave == x) resul = true; else if (nodoLista.clave < x) resul = busqueda (nodoLista.sig, x); return resul; } public boolean busqueda (int x) { return busqueda (inicio, x); }


LISTAS 113

3.6.2.2. Inserción. En este caso se realiza un tratamiento recursivo recorriendo la lista y terminando anticipadamente en cuanto se accede a la primera clave de valor superior a la que se desea insertar (la condición de terminación general sería llegar al final de la lista, es decir, nodoLista == null). El nuevo nodo se deberá insertar en la posición anterior al nodo actual. La Figura 3.10 ilustra el proceso de inserción de un nodo de clave 11 en una lista en el momento de la finalización anticipada.

Inicio

Inicio


13

Creación del nuevo nodo aux

11

10

13

Inserción en su lugar aux

21

null

21

null

11

Inicio

10

13

21

Inicio

Situación final 10

11

13

21

null

Figura 3.15. Inserción en una lista ordenada. A continuación se muestra un algoritmo de inserción7. static NodoLista insertar (NodoLista nodoLista, int dato) { NodoLista resul = nodoLista; if (nodoLista != null) if (nodoLista.clave < dato) nodoLista.sig = insertar (nodoLista.sig, dato); else if (nodoLista.clave > dato) resul = new NodoLista (dato, nodoLista); else System.out.println ("la clave ya existe"); else resul = new NodoLista (dato, nodoLista); return resul; } public void insertar (int dato) { inicio = insertar (inicio, dato); }

Como en el caso de las listas calificadas no ordenadas, el método estático insertar, si añade el nuevo nodo, lo devuelve como resultado, para que a la vuelta se enlace el campo sig del nodo anterior con el nodo nuevo. Si todavía no hemos llegado a la posición de inserción, devolvemos como resultado el nodo actual. 7

Obsérvese que el algoritmo es válido para insertar un elemento nuevo delante del primero, detrás del último y en una lista vacía. Así mismo, contempla el caso de intentar insertar una clave ya existente. Este último caso también produce una situación de terminación anticipada.

114 LISTAS


Para realizar la inserción se podría utilizar también un algoritmo iterativo. Como en el caso de las listas calificadas no ordenadas, tendríamos que utilizar las variables auxiliares actual y anterior para recorrer la lista. Además, utilizaríamos la variable encontrado, de tipo boolean, para salir del bucle de localización del hueco. public void insertarIterativo (int dato) { NodoLista anterior, actual, aux; boolean encontrado; anterior = inicio; actual = inicio; encontrado = false; while ((actual != null) && !encontrado) if (actual.clave >= dato) encontrado = true; else { anterior = actual; actual = actual.sig; } if (actual == null) { aux = new NodoLista (dato, null); if (inicio == null) inicio = aux; else anterior.sig = aux; } else if (encontrado && (actual.clave > dato)) { aux = new NodoLista (dato, actual); if (inicio == actual) inicio = aux; else anterior.sig = aux; } else System.out.println ("Error. Elemento repetido"); }

Al realizar la inserción en una lista calificada ordenada de manera iterativa, es necesario distinguir dos posibles casos: cuando insertamos un nodo al principio de la lista (tenemos que cambiar la referencia inicio), y cuando la lista ya tenía elementos previamente (insertamos o bien por la parte central de la lista, o bien al final, poniendo el nodo nuevo aux entre los elementos apuntados por anterior y actual)


LISTAS 115

3.6.2.3. Eliminación. Para borrar un elemento, se procede a recorrer la lista comparando las sucesivas claves con el argumento pasado. La condición de finalización “pesimista” se alcanza al llegar al final de la lista, lo que significa que no se ha encontrado ni la clave a eliminar ni ninguna mayor. No obstante lo normal es que se produzca una terminación anticipada en el momento en que se encuentra o bien la clave a eliminar, o bien una clave de valor mayor que la buscada. La figura 3.11 ilustra gráficamente el mecanismo de eliminación. Situación inicial y localización de la clave a borrar aux inicio

10

13

21

null

21

null

Cambio de los enlaces aux inicio

10

13

inicio

Situación final 10

21

null

Figura 3.16. Eliminación de un nodo de una lista calificada ordenada. El algoritmo utilizado es: static NodoLista eliminar (NodoLista nodoLista, int dato) { NodoLista resul = nodoLista; if (nodoLista != null) if (nodoLista.clave < dato) nodoLista.sig = eliminar (nodoLista.sig, dato); else if (nodoLista.clave > dato) System.out.println ("la clave no existe"); else resul = nodoLista.sig; else System.out.println ("la clave no existe"); return resul; } public void eliminar (int dato) { inicio = eliminar (inicio, dato); }

116 LISTAS


3.6.2.4. Mezcla de listas. Se tratan a continuación dos casos en los que partiendo de dos listas (lista1 y lista2) ordenadas de forma ascendente, se trata de obtener una nueva lista (lista3), con elementos de ambas. En el primer ejemplo crearemos lista3 con los elementos comunes de lista1 y lista2 (intersección) en tanto que en el segundo lista3 contendrá todos los elementos (sin repeticiones) de lista1 y lista2 (unión). En ambos casos realizaremos métodos static (pasando como argumentos objetos de la clase NodoLista). 3.6.2.4.1. Obtención de una lista con los elementos comunes de otras dos. La condición de finalización se produce cuando se ha terminado de explorar alguna de las listas (nodoLista1 == null || nodoLista2 == null). El avance recursivo por nodoLista1, nodoLista2 o ambas tiene lugar como consecuencia del resultado de comparar los elementos actuales de ambas listas. En caso de que sean iguales, además, se produce la inserción del correspondiente nodo de lista3. A continuación se muestra el código. static NodoLista mezclaAnd(NodoLista nodo1, NodoLista nodo2, NodoLista nodo3){ NodoLista resul; if (nodo1 != null && nodo2 != null) if (nodo1.clave < nodo2.clave) resul = mezclaAnd (nodo1.sig, nodo2, nodo3); else if (nodo1.clave > nodo2.clave) resul = mezclaAnd (nodo1, nodo2.sig, nodo3); else { nodo3 = mezclaAnd (nodo1.sig, nodo2.sig, nodo3); resul = new NodoLista (nodo1.clave, nodo3); } else resul = null; return resul; } static void mezclaAnd (Lista lista1, Lista lista2, Lista lista3) { lista3.inicio = mezclaAnd (lista1.inicio, lista2.inicio, lista3.inicio); }

3.6.2.4.2. Obtención de una lista con todos los elementos de otras dos. En este caso hay que recorrer ambas listas en su totalidad. La condición de finalización será ((nodoLista1 == null) && (nodoLista2 == null)). Si una de las listas está vacía, o la otra tiene un elemento menor, lo insertaremos en la lista resultado y avanzaremos por esa lista. En caso de que ambas listas tengan el mismo elemento, lo insertaremos y avanzaremos por ambas a la vez. El proceso presenta tres situaciones (1+2) en función de que haya elementos en las dos listas o en una sí y en otra no:


LISTAS 117

o Cuando queden elementos en ambas listas (1 caso), compararemos su valor para insertar el menor de los elementos y avanzar por la lista con el elemento menor (o por ambas si son iguales), o Cuando sólo queden elementos en una de las dos listas (2 casos), utilizaremos un método auxiliar (copiar), que copiará lo que quede en dicha lista sobre la lista resultado. El algoritmo utilizado aparece a continuación: static NodoLista copiar (NodoLista nodoListaO) { NodoLista resul; if (nodoListaO != null) { resul = copiar (nodoListaO.sig); resul = new NodoLista (nodoListaO.clave, resul); } else resul = null; return resul; } static NodoLista mezclaOr (NodoLista nodoLista1, NodoLista nodoLista2, NodoLista nodoLista3) { NodoLista resul; if (nodoLista1 != null && nodoLista2 != null) if (nodoLista1.clave < nodoLista2.clave) { nodoLista3 = mezclaOr (nodoLista1.sig, nodoLista2, nodoLista3); resul = new NodoLista (nodoLista1.clave, nodoLista3); } else if (nodoLista1.clave > nodoLista2.clave) { nodoLista3 = mezclaOr (nodoLista1, nodoLista2.sig, nodoLista3); resul = new NodoLista (nodoLista2.clave, nodoLista3); } else { nodoLista3 = mezclaOr (nodoLista1.sig, nodoLista2.sig, nodoLista3); resul = new NodoLista (nodoLista1.clave, nodoLista3); } else if (nodoLista1 != null) resul = copiar (nodoLista1); else if (nodoLista2 != null) resul = copiar (nodoLista2); else resul = null; return resul; } static void mezclaOr (Lista lista1, Lista lista2, Lista lista3) { lista3.inicio = mezclaOr (lista1.inicio, lista2.inicio, lista3.inicio); }

118 LISTAS


3.7. OTRAS IMPLEMENTACIONES. El concepto de lista ite diferentes implementaciones con estructuras de datos tanto estáticas como dinámicas. A continuación se muestran, a título de ejemplo, dos posibles soluciones implementadas mediante estructuras dinámicas: listas circulares y bidireccionales. Así mismo, se plantea la técnica de realización de listas con cabecera y centinela, utilizada para las listas calificadas. 3.7.1. Listas circulares (anillos). Se entiende por lista circular aquella en la que el último elemento de la lista tiene definido un enlace al primer elemento de la lista. Desde un punto de vista físico una lista circular por propia naturaleza no tiene principio ni fin. No obstante, desde el punto de vista lógico, la referencia a la lista establece cómo determinar la finalización de su recorrido tanto iterativo como recursivo. El nodo de referencia podría ser cualquiera de los nodos de la lista. A continuación se muestra como ejemplo (figura 3.16) el tratamiento de una lista calificada ordenada en que el nodo de referencia es el último (la clave de valor más alto). Este diseño facilita el inmediato a ambos extremos de la lista lo que significaría un diseño eficiente, por ejemplo, para la implementación de colas8 realizando la operación de encolar a continuación del nodo apuntado por ultimo (a la derecha en la figura) y desencolar en el extremo contrario (siguiente nodo). ultimo

2

4

6

Figura 3.17. Ejemplo de lista circular

8

Se sugiere al alumno como ejercicio.


LISTAS 119

3.7.1.1.Inserción. Si se desea realizar la inserción en una lista calificada ordenada circular, hay que tener en cuenta tres casos diferentes: La lista está vacía (ultimo == null): deberemos crear un nodo y enlazarlo consigo mismo. Vamos a insertar al final, después del último elemento: tendremos que cambiar la referencia ultimo. El elemento se inserta en cualquier otra posición. Para realizar la inserción de manera iterativa siguiendo los anteriores criterios, se puede utilizar el siguiente algoritmo, que crea el nodo y lo enlaza en su hueco correspondiente, una vez localizado el sitio donde se va a añadir el elemento: public void insertar (int dato) { NodoLista aux, actual, anterior; if (ultimo == null) { aux = new NodoLista (dato); ultimo = aux; ultimo.sig = ultimo; } else { anterior = ultimo; actual = ultimo.sig; while ((actual.clave < dato) && (actual != ultimo)) { anterior = actual; actual = actual.sig; } if (actual.clave != dato) { aux = new NodoLista (dato); if ((actual != ultimo) || (actual.clave > dato)) { aux.sig = actual; anterior.sig = aux; } else if (actual.clave < dato) { aux.sig= actual.sig; actual.sig= aux; ultimo = aux; } } else System.out.println ("error, el elemento ya existe"); } }

120 LISTAS


3.7.1.2.Eliminación. Si se va a realizar la eliminación de un nodo en una lista circular calificada ordenada de manera iterativa hay que contemplar, como en el caso de la inserción, tres casos diferentes: La lista tiene un solo nodo, que deseamos eliminar: deberemos borrar el nodo y apuntar la lista a null. Vamos a borrar el nodo final, (el que estamos apuntando con ultimo): tendremos que cambiar la referencia ultimo. El elemento se elimina de otra posición cualquiera. Para realizar la eliminación de manera iterativa siguiendo los anteriores criterios, se puede utilizar el siguiente algoritmo: public void eliminar (int x){ NodoLista ant, act; if (ultimo != null) { ant = ultimo; act = ultimo.sig; while (act != ultimo && act.clave < x) { ant = act; act = act.sig; } if (act.clave == x) { ant.sig = act.sig; if (ultimo == act) if (ultimo != ant) ultimo = ant; else ultimo = null; } else System.out.println ("No existe el nodo de clave " + x); } else System.out.println ("La lista está vacía "); }


LISTAS 121

3.7.2. Listas bidireccionales (doblemente enlazadas). Una lista se dice que es bidireccional o doblemente enlazada cuando, para cada uno de los elementos que la forman, existe una referencia al elemento anterior y otra al elemento siguiente dentro de la estructura. Gracias a esta estructura, se puede recorrer la lista en ambos sentidos. En la implementación de este tipo de listas hay que considerar dos situaciones particulares: El elemento anterior al primero será el elemento nulo. El elemento siguiente al último será también el elemento nulo. La figura 3.17 muestra un ejemplo de esta estructura: inicio

2

4

6

null

null

Figura 3.18. Ejemplo de lista bidireccional. Para implementar una lista de estas características mediante una estructura de datos dinámica se puede utilizar la clase NodoLista modificada para incluir las dos referencias. La clase NodoLista, conteniendo las variables miembro y el constructor quedaría: public class NodoLista { int clave; NodoLista sig, ant; public NodoLista (int x) clave = x; sig = null; ant = null; } }

{

Para realizar la inicialización, búsqueda y recorrido completo de este tipo de listas utilizaríamos los mismos algoritmos que con las listas unidireccionales. A continuación se muestran ejemplos de los algoritmos de inserción (insertar) y eliminación (eliminar) para una lista calificada ordenada9 implementada mediante estructuras dinámicas bidireccionales.

9

Se sugiere al alumno que realice los algoritmos correspondientes para listas calificadas no ordenadas.

122 LISTAS


3.7.2.1. Inserción. Con carácter general la inserción se produce la primera vez que se encuentra un nodo cuya clave es de un valor superior al dato que se pretende insertar. Esto implica la modificación de cuatro referencias (dos en el nuevo nodo, otro en el que apunta al nodo de clave superior y otro del nodo siguiente que apunta al actual. La figura 3.18 ilustra el proceso (se supone que se intenta insertar un nodo de clave 5 en el momento de haber encontrado un nodo de clave superior, 6). inicio

2

4

null

Aux

inicio

2

null

null

6

5

4

Nuevo

6

null

5

Figura 3.19. Simulación del módulo de inserción delante de un nodo El código utilizado para insertar el nodo aux delante del nodo apuntado por inicio es el siguiente: nuevo.sig = inicio; nuevo.ant = inicio.ant; inicio.ant = nuevo; inicio = nuevo;

La terminación del proceso debe realizarse cuando se alcance el nodo cuyo campo sig sea null (inicio.sig == null) pues en caso de progresar más allá se perdería la referencia al nodo anterior. Si la clave que queremos insertar es superior a la última de la lista, habrá que insertarla en este momento, a la derecha del último nodo. El código siguiente indica como implementarlo y la figura 3.19 ilustra gráficamente el proceso. nuevo.sig = null; nuevo.ant = inicio; inicio.sig = nuevo;


LISTAS 123

null 2

inicio

4 null

77

aux

inicio

6

2

4

6

null

aux

77

null

Figura 3.20. Inserción al final de la lista. Para realizar la inserción en este tipo de listas de manera iterativa, se utilizan tres referencias auxiliares: anterior y actual para ir recorriendo la lista, y nuevo para generar el nodo. Además, necesitamos utilizar la variable booleana encontrado, para salir del bucle si localizamos el hueco donde debemos insertar el nodo. El algoritmo utilizado aparece a continuación: void insertar (int clave) { NodoLista anterior, actual, nuevo; boolean encontrado = false; anterior = inicio; actual = inicio; while ((actual != null) && !encontrado) if (actual.clave < clave) { anterior = actual; actual = actual.sig; } else encontrado = true; if (actual == null) { nuevo = new NodoLista (clave); if (inicio == null) inicio = nuevo; else { nuevo.ant = anterior; anterior.sig = nuevo; } }

124 LISTAS


else if (actual.clave > clave) { nuevo = new NodoLista (clave); nuevo.sig = actual; nuevo.ant = actual.ant; actual.ant = nuevo; if (inicio != actual) anterior.sig = nuevo; else inicio = nuevo; } else System.out.println (“error, la clave ya existe”); }

3.7.2.2.Eliminación. Al realizar la eliminación de manera iterativa, de forma similar que en el caso de la inserción, se utilizan dos referencias auxiliares: anterior y actual para ir recorriendo la lista. Además, necesitamos utilizar la variable booleana encontrado, para salir del bucle si localizamos el nodo o una clave mayor. Si hemos encontrado el nodo que queremos eliminar, será necesario modificar dos referencias: El campo ant del nodo que sigue al que se va a eliminar deberá apuntar al anterior al eliminado (actual.sig.ant = actual.ant) Además será necesario distinguir dos casos: o si queremos borrar el primer nodo, y por tanto debemos modificar inicio, (inicio = inicio.sig) o o bien si queremos borrar un nodo intermedio (anterior.sig = actual.sig) La figura 3.21 ilustra el proceso (eliminación del nodo de clave 4). null inicio

2

null

4

6

actual

null inicio

2

null

4

6

Figura 3.21. Eliminación de un nodo intermedio


La codificación es la siguiente: public void eliminar (int clave) { NodoLista anterior, actual; boolean encontrado = false; anterior= inicio; actual= inicio; while ((actual != null) && !encontrado) if (actual.clave < clave) { anterior = actual; actual = actual.sig; } else encontrado = true; if (actual == null) System.out.println ("Error, el elemento no existe"); else if (actual.clave > clave) System.out.println ("Error, el elemento no existe"); else if (inicio == actual) { inicio = inicio.sig; inicio.ant = null; } else { anterior.sig = actual.sig; actual.sig.ant = anterior; } }

LISTAS 125

126 LISTAS


3.7.3. Listas con cabecera ficticia y centinela. Las técnicas denominadas cabecera ficticia y centinela se utilizan para mejorar la eficiencia en la codificación iterativa de las listas calificadas..

cent cab

1

2

67

Cabecera

Centinela

Figura 3.22. Utilización combinada de las técnicas de cabecera ficticia y centinela. En esta técnica se utilizará la siguiente clase NodoLista: class NodoLista { int clave; NodoLista sig; NodoLista (int dato) { clave = dato; sig = null; } }

En cuanto a la clase Lista, se redefine como un registro de dos referencias a nodos de la lista: cab (cabecera), y cent (centinela). public class Lista { NodoLista cab, cent; ... }

La cabecera ficticia consiste en incorporar un nodo falso al principio de la lista. Cualquier proceso de búsqueda se iniciará con la referencia anterior apuntando al elemento ficticio y la referencia actual apuntando al primer elemento de la lista real (segundo nodo de la lista física). Con esto se elimina la excepción que se produce: Cuando se quiere insertar un elemento al principio de la lista. Cuando se va a eliminar el primer nodo de la lista. La figura 3.23 explica esta técnica


LISTAS 127

Anterior

Actual

cent cab Cabecera

Primer elem.

Figura 3.23. Técnica de cabecera ficticia con valores iniciales de las referencias anterior y siguiente El campo clave del nodo apuntado por cab a veces se utiliza para guardar algún tipo de información relativa a la lista, por ejemplo el número de elementos de la misma. La referencia centinela (cent) apunta a otro nodo ficticio (no contiene información de la lista) que se inserta al final. La técnica del centinela se basa, tanto en las operaciones de búsqueda y eliminación como en las de inserción, en copiar antes de la ejecución del tratamiento iterativo la clave pasada como argumento en el nodo centinela (cent.clave = dato). Con esto se consigue simplificar la lógica de las condiciones de finalización dado que siempre se va a encontrar la clave buscada. El cumplimiento de la condición (actual == cent), se interpreta en el sentido de que hemos llegado al final de la lista y la clave buscada no se encuentra realmente en la lista. Combinando las dos técnicas anteriores se consigue una gran mejora de rendimiento en la localización de información de una lista calificada así como una simplificación de la lógica. El consumo adicional de espacio (necesario para alojar los nodos cab y cent) suele quedar compensado por las ventajas anteriormente expuestas. 3.7.3.1. Creación. Para crear una lista con cabecera y centinela (constructor vacío), primero crearemos los dos nodos ficticios y después pondremos el centinela como siguiente de la cabecera: Lista () { cab = new NodoLista (0); cent = new NodoLista (0); cab.sig = cent; }

128 LISTAS


3.7.3.2.Recorrido completo. Si lo que deseamos hacer es recorrer completamente una lista, como por ejemplo, para escribir todas las claves que contiene, tendremos que tener en cuenta que las claves contenidas en la cabecera y el centinela no forman parte de la lista real. void imprimirLista () { NodoLista actual; actual = cab.sig; while (actual != cent) { System.out.print (actual.clave + " "); actual = actual.sig; } System.out.println (" FIN"); }

3.7.3.3. Búsqueda. Para realizar una búsqueda de una clave en la lista con cabecera y centinela, utilizaremos las referencias auxiliares anterior (que apuntará inicialmente a la cabecera), y actual (que al principio apuntará al primer nodo de la lista, si ya hay nodos reales en la lista, y al centinela si está vacía), para recorrer la lista. Al finalizar el recorrido de la lista, devolveremos true si hemos encontrado la clave buscada, y false en caso de no haberla localizado (o bien hemos localizado una clave mayor, o bien hemos llegado al centinela). public boolean busqueda (int dato) { NodoLista anterior, actual; boolean resul = false; anterior = cab; actual = anterior.sig; cent.clave = dato; while (actual.clave < dato) { anterior = actual; actual = actual.sig; } if ((actual != cent) && (actual.clave == dato)) resul = true; return resul; }

3.7.3.4. Inserción. Para insertar un nuevo elemento en la lista, utilizaremos las referencias auxiliares anterior y actual para recorrer la lista, así como aux para crear el nuevo nodo. A continuación, copiamos la clave buscada en el centinela, y buscamos el hueco donde insertar el nuevo nodo. Una vez localizado el hueco (si la clave no existe), vamos a realizar la inserción siempre de la misma forma, ya que siempre insertaremos el nodo en la parte interior de la lista, nunca en un extremo de la misma.


LISTAS 129

public void insertar (int dato) { NodoLista anterior, actual, aux; anterior = cab; actual = anterior.sig; cent.clave = dato; while (actual.clave < dato) { anterior = actual; actual = actual.sig; } if ((actual.clave > dato) || (actual == cent)) { aux = new NodoLista (dato); aux.sig = actual; anterior.sig = aux; } else System.out.println ("Error, el elemento está repetido"); }

3.7.3.5. Eliminación. De forma similar a lo que ocurría en la inserción, para eliminar un elemento de la lista, utilizaremos las referencias auxiliares anterior y actual para recorrer la lista. Una vez localizada la clave en la lista, verificaremos que no hemos llegado al centinela (en ese caso la clave no estaría en la lista), y procederemos a desenganchar el nodo correspondiente. public void eliminar (int dato) { NodoLista anterior, actual; anterior = cab; actual = anterior.sig; cent.clave = dato; while (actual.clave < dato) { anterior = actual; actual = actual.sig; } if ((actual == cent) || (actual.clave > dato)) System.out.println ("Error, elemento inexistente"); else anterior.sig = actual.sig; }

130 LISTAS


3.8. IMPLEMENTACIÓN DE LISTAS UTILIZANDO MATRICES 3.8.1. Listas densas. A lo largo de los siguientes apartados veremos otra posible implementación de algunas de las listas analizadas hasta ahora. En particular, veremos como contruir un ejemplo de lista ordinal (una pila), así como una lista calificada ordenada. 3.8.1.1.Lista densa ordinal Si deseamos construir una pila utilizando una matriz, podríamos utilizar la siguiente estructura: Ejemplo de pila con 5 elementos (y como máximo 10 elementos): 0

1

2

3

4

5

6

7

8

9

1

7

6

2

7

0

0

0

0

0

numNodos = 5 N = 10

Como en las pilas los elementos se insertan y eliminan por el mismo extremo, consideraremos que el primer elemento se apilará en la posición 0 de la matriz, el segundo en la posición 1, y así sucesivamente. Utilizaremos la variable miembro numNodos, para saber cuál es el último nodo apilado (numNodos – 1, que sería el primero a desapilar), y si hay espacio todavía para apilar nuevos elementos. Para implementar el TadPila con la misma interfaz que hemos visto en el tema de Tipos Abstractos de Datos (y en la implementación mediante una lista enlazada), podríamos utilizar las siguientes variables y constructor: public class TadPila implements Pila { int [ ] matriz; final int N = 10; int numNodos; TadPila () { matriz = new int [N]; numNodos = 0; } ..... }


LISTAS 131

Como ya se ha indicado, numNodos representaría el número de elementos que se han apilado hasta ahora. A su vez, la variable miembro matriz contendrá los elementos de la pila, y N el número máximo de elementos que puede llegar a contener. A continuación, se desarrollan las operaciones apilar, desapilar y pilaVacia. Obsérvese que la operación apilar devolverá un mensaje de error si numNodos == N (la pila está llena), y desapilar si numNodos == 0 (la pila está vacía). Para comprobar si la pila está vacía es suficiente con verificar el valor de numNodos. public boolean pilaVacia () { return numNodos == 0; } public void apilar (int dato) { if (numNodos < N) { matriz [numNodos] = dato; numNodos++; } else System.out.println ("la pila está llena"); } public int desapilar () throws PilaVacia { int resul = -9999; if (numNodos != 0) { numNodos--; resul = matriz [numNodos]; } else throw new PilaVacia ("la pila está vacía"); return resul; }

132 LISTAS


3.8.1.2. Lista densa calificada ordenada. Para construir una lista calificada ordenada utilizando una matriz, podemos plantear las siguientes variables miembro y constructor (para una lista densa): public class Lista { int [ ] matriz; final int N = 10; int numNodos; Lista () { matriz = new int [N]; numNodos = 0; } ... }

Un posible ejemplo de lista densa calificada en la que se han insertado cinco elementos sería: 0

1

2

3

4

5

6

7

8

9

1

3

4

7

9

0

0

0

0

0

numNodos = 5 N = 10

A continuación desarrollaremos los métodos de objeto de la clase Lista. 3.8.1.2.1. Búsqueda. Por ejemplo, para realizar la búsqueda de una clave, recorreremos la matriz hasta encontrar una clave mayor o igual que la buscada, o bien llegar hasta el final de la lista. Se desarrollan dos métodos: busqueda (int dato), que si la lista no está vacía, invoca a otro auxiliar recursivo privado (busqueda (int i, int dato) que busca el elemento por la matriz: public boolean busqueda (int dato) { boolean resul = false; if (numNodos != 0) resul = busqueda (0, dato); return resul; } private boolean busqueda (int i, int dato) { boolean resul = false; if (i < numNodos) if (matriz[i] < dato) resul = busqueda (i+1, dato); else if (matriz [i] == dato) resul = true; return resul; }


LISTAS 133

3.8.1.2.2. Inserción. Para realizar la inserción en una lista densa calificada ordenada, primero se comprueba si hay espacio para el nuevo nodo con el método insertar (int dato) (comprobando si numNodos < N), y en caso afirmativo, se utiliza un método auxiliar estático privado (insertar (int i, int dato)), que recorre la lista hasta localizar la posición en la que se debe insertar un nuevo elemento. public void insertar (int dato) { if (numNodos < N) insertar (0, dato); else System.out.println ("la lista está llena"); } private void insertar (int i, int dato) { if (i == numNodos) { matriz [numNodos] = dato; numNodos++; } else if (matriz[i] < dato) insertar (i+1, dato); else if (matriz [i] > dato) { for (int j = numNodos; j > i; j--) matriz [j] = matriz [j-1]; matriz [i] = dato; numNodos++; } else System.out.println ("la clave ya existe"); }

Por ejemplo, si tenemos originalmente la siguiente lista ordenada: 0

1

2

3

4

5

6

7

8

9

1

3

4

7

9

0

0

0

0

0

numNodos = 5

Si fuésemos a insertar un elemento mayor que el último, tan solo lo colocaríamos en la posición numNodos, e incrementaríamos el valor de dicha variable: 0

1

2

3

4

5

6

7

8

9

1

3

4

7

9

12

0

0

0

0

numNodos = 6

Sin embargo, si queremos insertar un elemento por la parte central de la lista (por ejemplo, el 5), desplazaremos todos los elementos a partir de la posición 3 una posición a la derecha e incrementaremos el valor de numNodos: 0

1

2

3

4

5

6

7

8

9

1

3

4

5

7

9

12

0

0

0

numNodos = 7

134 LISTAS


3.8.1.2.3. Eliminación. Para realizar la eliminación en una lista densa calificada ordenada, primero se comprueba si hay algún elemento con el método eliminar (int dato) (comprobando si numNodos > 0), y en caso afirmativo, se utiliza un método auxiliar estático privado (eliminar (int i, int dato)), que recorre la lista hasta localizar la posición en la que se debe eliminar el elemento. public void eliminar (int dato) { if (numNodos != 0) eliminar (0, dato); else System.out.println ("la lista está vacía"); } private void eliminar (int i, int dato) { if (i < numNodos) if (matriz[i] < dato) eliminar (i+1, dato); else if (matriz [i] > dato) System.out.println ("la clave no existe"); else { for (int j = i; j < numNodos-1; j++) matriz [j] = matriz [j+1]; numNodos--; } }

Si partimos del ejemplo anterior: 0

1

2

3

4

5

6

7

8

9

1

3

4

5

7

9

12

0

0

0

numNodos = 7

Si queremos eliminar el último elemento (12), tan solo sería necesario cambiar el valor de numNodos: 0

1

2

3

4

5

6

7

8

9

1

3

4

5

7

9

12

0

0

0

numNodos = 6

Sin embargo, si deseamos eliminar un elemento situado por la parte central de la lista (por ejemplo, el 4), desplazaríamos hacia la izquierda todos los elementos a partir de la posición 3 y decrementaríamos el valor de numNodos. 0

1

2

3

4

5

6

7

8

9

1

3

5

7

9

9

12

0

0

0

numNodos = 5

Obsérvese que en ninguno de los dos casos el último elemento en realidad no se elimina, pero como se ha modificado numNodos (ahora su valor es 5), las posiciones 5 y 6 no se tendrán en cuenta a menos que se inserte un nuevo elemento.


LISTAS 135

3.8.1.2.4. Ejemplos de recorrido completo. Por ejemplo, utilizando la anterior estructura, podríamos realizar un recorrido completo (escribir el contenido de una lista densa) con el siguiente método estático: static void escribirLista (Lista lista) { for (int i = 0; i < lista.numNodos; i++) System.out.print (lista.matriz [i] + " System.out.println (“FIN”); }

");

En el siguiente ejemplo, recorremos completa la lista sumando los elementos que contiene: static int sumaElementos (Lista lista) { int resul = 0; for (int i = 0; i <lista.numNodos; i++) resul = resul + lista.matriz [i] ; return resul; }

136 LISTAS


3.8.2. Lista enlazada sobre matriz Al principio del tema vimos el siguiente ejemplo basado en una matriz de registros. 0 1

clave sig

2

3

4

5

6

7

8

1 10 77 12 26 21 11 13 18 2 3 4 7 6 0 8 5 0

Figura 3.24. Ejemplo de implementación de lista enlazada mediante una estructura estática (matriz). Su interpretación es la siguiente: o Las claves de la lista se representan en el primero de los campos. o El primer elemento del vector (índice 0) es especial. Su primer campo hace referencia al primer nodo de la lista (el que ocupa el primer campo de la posición 1, es decir 10) y el segundo la posición del primer “hueco” (índice 2 cuyo contenido –77– es irrelevante). o El segundo campo de cada nodo indica la posición (índice) del nodo que le sigue, salvo que se trate de un cero que indicaría el final de la lista de nodos. o El segundo campo de cada hueco indicaría la posición del siguiente hueco, salvo que se trate de un cero que indicaría el final de la lista de huecos. Así pues, la estructura definida en la figura 3.24., permitiría almacenar hasta 8 elementos en la lista (índices 1 a 8). En la situación actual almacenaría la secuencia de datos de la figura 3.4: 10, 12, 13 y 21 (índices 1, 3, 7 y 5, respectivamente). 10

12

13

21

Figura 3.25. Lista enlazada correspondiente a la figura 3.24. Y aún quedaría espacio para almacenar otros 4 datos (el primer espacio disponible es el nodo de índice 2 y el último el de índice 8). Para poder utilizar una matriz para implementar una lista calificada ordenada, pordemos utilizar la estructura y constructor de la página siguiente.


LISTAS 137

class NodoLista { int clave, sig; NodoLista () { clave = 0; sig = 0; } } public class Lista { final int NULL = 0, N = 9; NodoLista [] matriz; Lista () { int i; matriz = new NodoLista [N]; for (i = 0; i < N-1; i++) { matriz [i] = new NodoLista (); matriz [i].sig = i + 1; } matriz [i] = new NodoLista (); } .... }

Utilizaremos la clase NodoLista para incluir los campos clave y sig. La clase Lista contendrá las constantes N (con valor 9, que representa el número máximo de nodos de la lista + 1) y NULL (con valor 0, que representa la posición vacía, equivalente a null en las listas enlazadas); además incluye la variable miembro matriz (que es un vector de elementos de la clase NodoLista), que contiene la lista vacía. A continuación desarrollaremos los métodos de objeto de la clase Lista. 3.8.2.1.1. Búsqueda. Para realizar la búsqueda de una clave, recorreremos la matriz siguiendo los enlaces hasta encontrar una clave mayor o igual que la buscada, o bien llegar hasta el final de la lista. Se desarrollan dos métodos: busqueda (int dato), que si la lista no está vacía, invoca a otro auxiliar recursivo privado (buscar (int pos, int dato) pasándole como argumento la posición del primer elemento de la lista. El método buscar se encarga de localizar si el elemento aparece en la matriz o no: public boolean busqueda (int dato) { boolean resul = false; int pos = matriz [0].clave; if (pos != 0) resul = buscar (pos, dato); return resul; }

138 LISTAS


private boolean buscar (int pos, int dato) { boolean resul = false; if (matriz [pos].clave < dato) { if (matriz [pos].sig != 0) resul = buscar (matriz [pos].sig, dato); } else if (matriz [pos].clave == dato) resul = true; return resul; }

3.8.2.1.2. Inserción. Para realizar la inserción en una lista calificada ordenada enlazada sobre matriz, primero se comprueba en el método insertar (int dato): si la lista está llena (la lista de huecos estaría vacía: matriz [0].sig == NULL), en cuyo caso se produciría un mensaje de error, o bien si la lista está vacía vacía (comprobando si matriz [0].clave != 0), en dicho caso se inserta directamente el elemento utilizando el método auxiliar inser, en cualquier otro caso, se llama a un método auxiliar estático privado (insertar (int pos, int ant, int dato)), que recorre la lista hasta localizar la posición en la que se debe insertar un nuevo elemento (y volveríamos a llamar al método auxiliar inser). public void insertar (int dato) { if (matriz [0].sig != NULL) { int pos = matriz [0].clave; if (pos != 0) insertar (matriz [0].clave, 0, dato); else inser (0, 0, dato); } else System.out.println ("lista llena"); } private void insertar (int pos, int ant, int dato) { if (matriz [pos].clave < dato) if (matriz [pos].sig != 0) insertar (matriz [pos].sig, pos, dato); else inser (0, pos, dato); else if (matriz [pos].clave > dato) inser (pos, ant, dato); else System.out.println ("la clave ya existe"); }


LISTAS 139

private void inser (int pos, int ant, int dato) { int nuevo = matriz [0].sig; matriz [0].sig = matriz [nuevo].sig; matriz [nuevo].clave = dato; if (ant != 0) { matriz [nuevo].sig = pos; matriz [ant].sig = nuevo; } else { int sig = matriz [0].clave; matriz [0].clave = nuevo; if (pos == 0) matriz [nuevo].sig = 0; else matriz [nuevo].sig = sig; } }

3.8.2.1.3. Eliminación. Para realizar la eliminación de un elemento, se ha optado por hacer un método iterativo. Primero se verifica si la lista está vacía, y en caso contrario, se recorre la lista hasta encontrar la clave buscada (desenganchando el elemento de la lista de claves, y enlazándolo en la lista de huecos), o bien una clave mayor que la buscada (en cuyo caso se producirá un mensaje de error). public void eliminar (int d) { int ant, pos, posAnt = 0; if (matriz [0].clave != NULL) { pos = matriz [0].clave; ant = matriz [pos].clave; while (ant < d) { posAnt = pos; pos = matriz [pos].sig; ant = matriz [pos].clave; } if (ant == d) { if (pos == matriz [0].clave) matriz [0].clave = matriz [pos].sig; else matriz [posAnt].sig = matriz[pos].sig; matriz [pos].sig = matriz [0].sig; matriz [0].sig = pos; } else System.out.println ("la clave no existe"); } else System.out.println ("Error. La lista está vacía"); }

140 LISTAS


3.8.2.1.4. Ejemplos de recorrido completo. Por ejemplo, utilizando la anterior estructura, podríamos realizar un recorrido completo (escribir el contenido de una lista enlazada sobre matriz) con el siguiente método estático: static void escribirLista (Lista lista) { int i = lista.matriz [0].clave; while (i != 0) { System.out.print (lista.matriz [i].clave+" "); i = lista.matriz [i].sig; } System.out.println (“FIN”); }

En el siguiente ejemplo, recorremos completa la lista sumando los elementos que contiene: static int sumaElementos (Lista lista) { int i = lista.matriz [0].clave, resul = 0; while (i != 0) { resul = resul + lista.matriz [i].clave; i = lista.matriz [i].sig; } return resul; }


LISTAS 141

3.9. UTILIZACIÓN DE UN TAD LISTA. Los algoritmos explicados en las secciones anteriores implican el conocimiento interno de la estructura de la lista. Otra opción consiste en que el programador dispusiera de un Tipo Abstracto de Datos del que, dada su característica de ocultamiento, se desconoce absolutamente su implementación y, en consecuencia, solo es posible disponer de sus funcionalidades mediante un conjunto de especificaciones. Estas deberían ser, al menos, las siguientes: public interface Lista { void crearNodo (); /*Crea un nuevo nodo en el tadLista*/ int devolverClave (); /*Devuelve la clave contenida en el nodo del tadLista*/ NodoLista devolverSiguiente (); /*Devuelve una referencia al siguiente del tadLista*/ void asignarClave (int dato); /*Asigna el dato al primer nodo del TadLista*/ void asignarReferencia (NodoLista referencia); /*Hace que el primer nodo del TadLista apunte al mismo sitio que referencia*/ void asignarReferenciaSiguiente (NodoLista referenciaNueva); /*Hace que el siguiente del nodo actual apunte ahora al mismo sitio que referenciaNueva*/ void asignarNulo (); /*Hace que el tadLista tome el valor null*/ boolean esNulo (); /*Devuelve true si el inicio del TadLista tiene valor null; false en caso contrario*/ boolean esIgual (NodoLista referencia); /*Devuelve true si referencia apunta al mismo sitio que el tadLista, false en caso contrario*/ }

A continuación se muestra un sencillo ejemplo que permite contar el número de nodos de una lista del TAD lista descrito arriba. static int contar (TadLista lista) { TadLista aux = new TadLista (); int resul; if (!lista.esNulo ()) { aux.asignarReferencia (lista.devolverSiguiente ()); resul = 1 + contar (aux); } else resul = 0; return resul; }

142 LISTAS


3.9.1. Implementación del TAD Lista. package tadLista; public class TadLista implements Lista { NodoLista inicio; public TadLista () { inicio = null; } public void crearNodo () { /*Crea un nuevo nodo en el TadLista al principio de la lista*/ inicio = new NodoLista (0, inicio); } public int devolverClave () { /*Devuelve la clave contenida en el nodo del tadLista*/ return inicio.clave; } public NodoLista devolverSiguiente () { /*Devuelve una referencia al siguiente del TadLista*/ return inicio.sig; } public NodoLista devolverReferencia () { /*Devuelve una referencia al primer nodo del TadLista*/ return inicio; } public void asignarClave (int dato) { /*Asigna el dato al primer nodo del TadLista*/ inicio.clave = dato; } public void asignarReferencia (NodoLista referencia) { /*Hace que el inicio del TadLista apunte al mismo sitio que referencia*/ inicio = referencia; } public void asignarReferenciaSiguiente (NodoLista referenciaNueva) { /*Hace que el siguiente del nodo inicio apunte ahora al mismo sitio que referenciaNueva*/ inicio.sig = referenciaNueva; } public void asignarNulo () { /*Hace que el inicio del TadLista tome el valor null*/ inicio = null; } public boolean esNulo () { /*Devuelve true si el inicio del TadLista tiene valor null; false en caso contrario*/ return inicio == null; } public boolean esIgual (NodoLista referencia) { /*Devuelve true si referencia apunta al mismo sitio que el inicio del TadLista, false en caso contrario*/ return inicio == referencia; } }


LISTAS 143

TEMA 3 ................................................................................................................................ 93 3.1.

Conceptos Generales. ............................................................................................... 93

3.2.

Implementación de listas. ......................................................................................... 95

3.3.

Tratamiento de listas en java .................................................................................... 97

3.4.

Algoritmos básicos con Listas. ................................................................................. 98 3.4.1.

3.5.

3.6.

3.7.

3.8.

3.9.

Recorrido completo. ............................................................................. 98

Listas ordinales. ...................................................................................................... 100 3.5.1.

Pilas. ................................................................................................... 100

3.5.2.

Colas. .................................................................................................. 102

Listas calificadas. ................................................................................................... 105 3.6.1.

Listas calificadas no ordenadas. ......................................................... 105

3.6.2.

Listas calificadas ordenadas. .............................................................. 112

Otras implementaciones. ........................................................................................ 118 3.7.1.

Listas circulares (anillos).................................................................... 118

3.7.2.

Listas bidireccionales (doblemente enlazadas). ................................. 121

3.7.3.

Listas con cabecera ficticia y centinela. ............................................. 126

IMPLEMENTACIÓN DE LISTAS UTILIZANDO MATRICES ........................ 130 3.8.1.

Listas densas. ...................................................................................... 130

3.8.2.

Lista enlazada sobre matriz ................................................................ 136

Utilización de un TAD Lista. ................................................................................. 141 3.9.1.

Implementación del TAD Lista: ......................................................... 142


ÁRBOLES 143

TEMA 4.

ÁRBOLES 4.1. CONCEPTOS GENERALES. Un árbol es una estructura de datos ramificada (no lineal) que puede representarse como un conjunto de nodos enlazados entre sí por medio de ramas. La información contenida en un nodo puede ser de cualquier tipo simple o estructura de datos. Los árboles permiten modelar diversas entidades del mundo real tales como, por ejemplo, el índice de un libro, la clasificación del reino animal, el árbol genealógico de un apellido, etc. La figura 4.1. muestra un ejemplo de estructura en árbol (la numeración de los nodos es arbitraria). Se entiende por “topología” de un árbol a su representación geométrica. 1

2

5

10

3

6

4

7

8

11

9

12

Figura 4.1. Ejemplo de árbol.

144 ÁRBOLES


Una definición formal es la siguiente: Un árbol es una estructura de datos base que cumple una de estas dos condiciones: Es una estructura vacía, o Es un nodo de tipo base que tiene de 0 a N subárboles disjuntos entre sí. Al nodo base, que debe ser único, se le denomina raíz y se establece el convenio de representarlo gráficamente en la parte superior. En un árbol se representa una relación jerárquica a partir del nodo raíz en sentido vertical descendente, definiendo niveles1. El nivel del nodo raíz es 1. Desde la raíz se puede llegar a cualquier nodo progresando por las ramas y atravesando los sucesivos niveles estableciendo así un camino. En la figura 4.1. el nodo 7 está a nivel 3 y la secuencia de nodos 4, 8 y 11 constituye un (sub)camino. Se dice que un nodo es antecesor de otro cuando ambos forman parte de un camino y el primero se encuentra en un nivel superior (numeración más baja) al del segundo (numeración más alta). En el ejemplo anterior el nodo 4 es antecesor del 11. Por el contrario, el nodo 11 es descendiente del 4. La relación entre dos nodos separados de forma inmediata por una rama se denomina padre/hijo. En el ejemplo de la figura 4.1., el nodo 5 es hijo del nodo 2 y, recíprocamente, el nodo 2 es padre del nodo 5. En un árbol un padre puede tener varios hijos pero un hijo solo puede tener un padre. Se denomina grado al número de hijos de un nodo. Por ejemplo, en la figura 4.1. el nodo 4 tiene grado 3 y el nodo 7 tiene grado 0. Se dice que un nodo es hoja cuando no tiene descendientes (grado 0). Se establecen los siguientes atributos para un árbol: Altura / profundidad / nivel: La mayor altura / profundidad / nivel de sus nodos. La altura del árbol de la figura 4.1. es 4 (la alcanzan sus nodos 10, 11 y 12). Amplitud / Anchura: El número de nodos del nivel más poblado. En el ejemplo, 5 (nivel 3). Grado: el mayor de los grados de los nodos. En el ejemplo, 3 (nodos 1 y 4).

1

Los términos “altura” o “profundidad” son sinónimos del de nivel.


ÁRBOLES 145

Finalmente, indicar que se dice que un árbol es completo cuando todos sus nodos (excepto las hojas) tienen el mismo grado y los diferentes niveles están poblados por completo. A veces resulta necesario completar un árbol añadiéndole nodos especiales. La figura 4.2. representa el resultado de completar el árbol de la figura 4.1. (en la figura los nodos especiales aparecen sombreados) 1

2

5

3

4

6

7

10

8

11

9

12

Figura 4.2. Árbol completo de grado 3. En un árbol completo de grado g, la amplitud del nivel n es An == gn-1, y el número total de nodos del árbol es: Nn

g g

n

1 1

.

146 ÁRBOLES


4.2. ÁRBOLES BINARIOS. Se definen como árboles de grado 2. Esto es, cada nodo puede tener dos, uno o ningún hijo. Al tratarse como mucho de dos hijos, cada uno de ellos puede identificarse como hijo izquierdo o hijo derecho. 4.2.1. Implementación física. El gráfico de un árbol es una representación conceptual cuya implementación física ite diversas posibilidades condicionadas, en primer lugar, por el dispositivo de almacenamiento del mismo (memoria principal o memoria externa). A los efectos del curso nos ocuparemos exclusivamente de la memoria principal en donde puede optarse por dos filosofías principales: Estructuras de datos estáticas, normalmente matrices. Estructuras de datos dinámicas En cualquier caso, la representación física de un árbol requiere contemplar tres componentes: La clave (simple o compuesta). Dos punteros, indicando las ubicaciones respectivas de los nodos hijo izquierdo e hijo derecho2. Ejemplo. La figura 4.3. representa un árbol binario que podría implementarse físicamente según se ilustra en las figuras 4.4. (estructura estática) ó 4.5. (estructura dinámica). 15

25

20

10

5

45

Figura 4.3. Ejemplo de árbol binario. Clave Hijo izquierdo Hijo derecho

0 15 3 1

1 20 5 2

2 5 4 *

3 25 * *

4 45 * *

5 10 * *

Figura 4.4. Ejemplo de árbol binario. Implementación estática.

2

Deberá establecerse un convenio para indicar la inexistencia de hijo(s).


ÁRBOLES 147

Puntero al árbol

raíz

20

15 25

*

*

10 5

*

*

* 45

*

*

Figura 4.5. Ejemplo de árbol binario. Implementación dinámica. 4.2.2. Algoritmos básicos con árboles binarios3. Para la utilización de árboles binarios es necesario definir las clases NodoArbol y Arbol siguiendo la sintaxis siguiente: public class NodoArbol { public NodoArbol (int dato) { clave = dato; iz = null; de = null; } public int clave; public NodoArbol iz, de; } public class Arbol { public NodoArbol raiz; public Arbol () { raiz = null; } }

4.2.2.1.Recorridos. Se entiende por recorrido el tratamiento realizado para acceder a los diferentes nodos de un árbol. El recorrido puede afectar a la totalidad de los nodos del árbol (recorrido completo), por ejemplo si se desea conocer el número de nodos, o finalizar anticipadamente en función de determinada/s circunstancia/s, por ejemplo al encontrar el valor de una clave determinada. En cualquier caso, el recorrido se puede realizar basándose en las siguientes modalidades:

3

Los siguientes algoritmos se han desarrollado en Java considerando la implementación del árbol por medio de una estructura dinámica. A efectos de la realización de prácticas se utiliza la sintaxis del lenguaje Java.

148 ÁRBOLES


En profundidad. Se progresa verticalmente desde la raíz hacia las hojas y, en principio, de izquierda a derecha. Se plantean tres posibilidades atendiendo al momento en que se procesa la clave. o Preorden. La clave se procesa en primer lugar. Posteriormente se realizan las llamadas recursivas (por la izquierda y por la derecha). La exploración en preorden del árbol de la figura 4.3.a. daría el siguiente resultado: 15, 25, 20, 10, 5, 45. Este tipo de recorrido es el más utilizado pues atiende a la estructura de organización jerárquica del árbol. También es el más eficiente cuando se trata de buscar claves. En general, el algoritmo de recorrido en preorden es el siguiente: // Escribe las claves del árbol binario de raiz “a” en preorden. static void preOrden (NodoArbol arbol) { if (arbol != null) { System.out.print (arbol.clave + " ") ; // Nodo preOrden (arbol.iz); // Izquierda preOrden (arbol.de); // Derecha } } public void preOrden () { preOrden (raiz); }

o Orden central. Se desciende recursivamente por la rama izquierda. Al alcanzar la condición de finalización (arbol == null) se retorna y se procesa la clave, y a continuación se progresa por la rama derecha. La exploración en orden central del árbol de la figura 4.3.a. daría el siguiente resultado: 25, 15, 10, 20, 45, 5. Este tipo de recorrido es especialmente útil en todos aquellos procesos en los que sea necesario recorrer los nodos de acuerdo al orden físico de los mismos. En general, el algoritmo de recorrido en orden central es el siguiente: // Escribe las claves del árbol binario en orden central. static void ordenCentral (NodoArbol arbol) { if (arbol != null) { ordenCentral (arbol.iz); // Izquierda System.out.print (arbol.clave + " ") ; // Nodo ordenCentral (arbol.de); // Derecha } } public void ordenCentral () { ordenCentral (raiz); }


ÁRBOLES 149

o Postorden. Se desciende recursivamente por la rama izquierda, al alcanzar el final de dicha rama, se retorna y se desciende por la rama derecha. Cuando se alcanza el final de la rama derecha, se procesa la clave. La exploración en postorden del árbol de la figura 4.3.a. daría el siguiente resultado: 25, 10, 45, 5, 20, 15. Este recorrido es el menos utilizado. Se utiliza para liberar memoria, o bien cuando la información de los niveles más profundos del árbol afecta a la información buscada. En general, el algoritmo de recorrido en postorden es el siguiente: // Escribe las claves del árbol binario en postorden. static void postOrden (NodoArbol arbol) { if (arbol != null) { postOrden (arbol.iz); // Izquierda postOrden (arbol.de); // Derecha System.out.print (arbol.clave + " ") ; // Nodo } } public void postOrden () { postOrden (raiz); }

Ejemplo de algoritmo de recorrido en profundidad: desarrollar un método estático (sumaClaves) que obtenga la suma de las claves del árbol4. static int sumaClaves (NodoArbol arbol) { int resul; if (arbol != null) resul = arbol.clave + sumaClaves (arbol.iz) + sumaClaves (arbol.de); else resul = 0; return resul; } static int sumaClaves (Arbol a) { return sumaClaves (a.raiz); }

Como ejercicio se propone al alumno la realización de un algoritmo que cuente los nodos que tiene un árbol, utilizando uno de los tres recorridos en profundidad propuestos.

4

Puede realizarse indistintamente con cualquiera de las modalidades de recorrido, en la solución propuesta se hace un recorrido en preorden.

150 ÁRBOLES


Recorrido en amplitud. Implica un a las claves recorriendo cada nivel de izquierda a derecha y descendiendo al siguiente. Por ejemplo, la exploración en amplitud del árbol de la figura 4.3.a. daría el siguiente resultado: 15, 25, 20, 10, 5, 45. Para la implementación del recorrido en amplitud se requiere la utilización de la técnica iterativa así como de la disponibilidad de una estructura de datos auxiliar: TAD cola de nodos de árbol: class NodoCola { NodoArbol dato; NodoCola siguiente; // Constructores NodoCola (NodoArbol elemento, NodoCola n) { dato = elemento; siguiente = n; } }

Por ejemplo, el algoritmo siguiente permite obtener un listado de las claves de un árbol binario recorrido en amplitud: static void listarAmplitud (NodoArbol arbol) { NodoArbol p; Cola c = new TadCola (); p = arbol; if (p != null) c.encolar (p); while (! c.colaVacia ()) { p = c.desencolar (); System.out.print (p.clave + " "); if (p.iz != null) c.encolar (p.iz); if (p.de != null) c.encolar (p.de); } } public void listarAmplitud () { listarAmplitud (raiz); }

La idea, básicamente, consiste en encolar en la cola de punteros las direcciones (referencias) de los posibles hijos de cada nodo procesado (su dirección se encuentra en la variable p). A continuación, en cada iteración se extrae el primer elemento de la cola que se corresponde con el nodo actual del árbol. Si su hijo izquierdo y/o su hijo derecho son distintos de null se encolan, y el proceso terminará cuando la cola se encuentre vacía.


ÁRBOLES 151

4.2.2.2.Búsqueda. Hasta ahora se han presentado distintos modos de recorrer el árbol completo. En algunas ocasiones, será necesario finalizar antes de completar el recorrido, no realizando posteriores llamadas recursivas. En algunos casos se requiere el empleo de un argumento adicional (pasado por referencia) que permita evitar, en su caso, la ejecución de posteriores llamadas recursivas. El siguiente ejemplo implementa un método (búsqueda) que recibe como argumentos un árbol y una clave (ambos pasados por valor) y devuelve true si dicha clave se encuentra en el árbol, y false en caso contrario. Se procede a recorrer en principio todo el árbol. Cada vez que se alcanza un extremo (llamada desde una hoja) se cumple la condición arbol == null y el método devuelve el valor false. Si a lo largo del recorrido se encuentra la clave buscada, el método devolverá el puntero a dicho nodo, y ya no se realizan nuevas llamadas recursivas, siendo este valor el que se entrega al módulo que llamó a el método, lo que evita el error que supondría alcanzar la condición de finalización en el extremo derecho del árbol (hijo derecho de la última hoja). Por razones de eficiencia se realiza un recorrido en preorden. static boolean busqueda (NodoArbol arbol, int dato) { boolean resul = false; if (arbol != null) if (arbol.clave == dato) resul = true; else { resul = busqueda (arbol.iz, dato); if (!resul) resul = busqueda (arbol.de, dato); } return resul; } public boolean busqueda (int dato) { return busqueda (raiz, dato); }

4.2.2.3. Creación de un árbol. Para insertar claves en un árbol es necesario establecer previamente un criterio. Normalmente no se permite insertar claves repetidas. En el apartado 4.3.2.1. se muestra cómo insertar nodos en un árbol binario de búsqueda. Para los árboles binarios que no sean de búsqueda, se puede utilizar el método juntar, que recibe una clave y dos árboles (a1 y a2), y devuelve un árbol con la clave en la raíz, a1 como subárbol izquierdo, y a2 como subárbol derecho:

152 ÁRBOLES


public void juntar (int dato, Arbol a1, Arbol a2) { if (a1.raiz == a2.raiz && a1.raiz != null) { System.out.println ("no se pueden mezclar, t1 y t2 son iguales") ; return; } // Crear el nodo nuevo raiz = new NodoArbol (dato, a1.raiz, a2.raiz) ; // Borrar los árboles a1 y a2 if (this != a1) a1.raiz = null; if (this != a2) a2.raiz = null; }

En el siguiente ejemplo, se muestra como generar el árbol de la figura 4.6: public static Arbol a1 = Arbol a3 = Arbol a5 = Arbol a7 = Arbol a2 = Arbol a4 = Arbol a6 =

void main new Arbol new Arbol new Arbol new Arbol new Arbol new Arbol new Arbol

(String [] args) { (1) ; (3) ; (5) ; (7) ; (); (); ();

a2.juntar (2, a1, a3) ; a6.juntar (6, a5, a7) ; a4.juntar (4, a2, a6) ; }

4

2

1

6

3

5

7

Figura 4.6. Ejemplo de árbol binario. 4.2.2.4.Tratamiento de hojas. En este tipo de algoritmos se trata de evaluar la condición de que un nodo del árbol sea una hoja: (arbol.iz == null) && (arbol.de == null).

Por ejemplo, el siguiente método de tipo entero (cuentaHojas) devuelve como resultado el número de hojas del árbol que se le entrega como argumento.


ÁRBOLES 153

static int cuentaHojas (NodoArbol arbol) { int resul = 0; if (arbol != null) if ((arbol.iz == null) && (arbol.de == null)) resul = 1; else resul = cuentaHojas (arbol.iz) + cuentaHojas (arbol.de); return resul; } static int cuentaHojas (Arbol a) { return cuentaHojas (a.raiz); }

4.2.2.5. Procesamiento con constancia del nivel. Determinados tratamientos requieren conocer el nivel en que se encuentran los nodos visitados, para lo cual es necesario conocer el nivel actual. Recorrido en profundidad. Cuando se va a realizar un tratamiento en profundidad, pasamos como argumento (por valor) el nivel actual. En cada llamada recursiva (por la derecha o por la izquierda) se incrementa el nivel en una unidad. La inicialización de dicho argumento (a 1) se realiza en la primera llamada (no recursiva). Por ejemplo, el siguiente método (clavesNiveles) recorre un árbol en preorden5 mostrando en la pantalla el valor de las diferentes claves así como el nivel en que se encuentran. static void clavesNiveles (NodoArbol arbol, int n) { if (arbol != null) { System.out.println ("Clave: " + arbol.clave + " en el nivel: " + n); clavesNiveles (arbol.iz, n+1); clavesNiveles (arbol.de, n+1); } } static void clavesNiveles (Arbol a) { clavesNiveles (a.raiz, 1); }

Recorrido en amplitud. El algoritmo explicado para el recorrido en amplitud en el apartado 3.2.2.2., permite recorrer el árbol en amplitud, sin embargo, no se tiene constancia del nivel en que se encuentran los nodos a los que se accede. En caso de que esto sea necesario debería modificarse, bien la estructura de la cola añadiendo el nivel, o bien el algoritmo visto anteriormente de manera que su estructura sea una iteración anidada en dos niveles.

5

La modalidad de recorrido es indiferente.

154 ÁRBOLES


Si se puede cambiar la estructura de la cola, podría utilizarse una cola con el siguiente tipo de elementos: TElemento (NodoArbol a, int n) { nivel = n; arbol = a; } NodoColaN (NodoArbol a, int n, NodoColaN sig) { elem = new TElemento (a, n); siguiente = sig; }

Utilizando los siguientes métodos para obtener el árbol y el nivel: public NodoArbol obtenerArbol (TElemento e) { return e.arbol; } public int obtenerNivel (TElemento e) { return e.nivel; }

De tal forma que al encolar el árbol completo, pondríamos el nivel a 1, y posteriormente, cada vez que se va a encolar un elemento, lo primero que haremos será actualizar el nivel. static void listarAmplitudNiveles (NodoArbol arbol) { NodoArbol p; int n; ColaN c = new TadColaN (); p = arbol; if (p != null) { TElemento elem = new TElemento (p, 1); c.encolar (elem); while (! c.colaVacia ()) { elem = c.desencolar (); p = elem.obtenerArbol (); n = elem.obtenerNivel (); System.out.println ("nivel: " + n + " " + p.clave + " "); if (p.iz != null) { elem = new TElemento (p.iz, n+1); c.encolar (elem); } if (p.de != null){ elem = new TElemento (p.de, n+1); c.encolar (elem); } } } } public void listarAmplitudNiveles (){ listarAmplitudNiveles (raiz); }

Si no se puede alterar la estructura de la cola, sería necesario cambiar el algoritmo de manera que existan dos niveles de iteración. El nivel externo es el general (para todo el árbol) y el nivel interno para cada nivel del árbol. Cuando se inicia el recorrido de un nivel


ÁRBOLES 155

(controlado por medio de la variable contador) es necesario conocer a priori su amplitud (variable actual) y según se va explorando dicho nivel se cuenta el número de hijos del siguiente nivel (variable siguiente). Al iniciar el proceso del siguiente nivel se pasa a la variable actual el último valor encontrado en la variable siguiente. A continuación se muestra como ejemplo una variante del ejemplo anterior. static void listarAmplitudNiveles (NodoArbol arbol) { NodoArbol p; Cola c = new TadCola (); int actual, siguiente, contador, altura; altura = 0; siguiente = 1; p = arbol; if (p != null ) c.encolar (p); while (!c.colaVacia()) { actual = siguiente; siguiente = 0; contador = 1; altura++; while (contador <= actual) { p = c.desencolar (); System.out.println ("clave: " + p.clave + " nivel: " + altura); contador++; if (p.iz != null) { c.encolar (p.iz); siguiente++; } if (p.de != null) { c.encolar (p.de); siguiente++; } } } } public void listarAmplitudNiveles (){ listarAmplitudNiveles (raiz); }

156 ÁRBOLES


4.2.3. Ejemplo. A continuación se desarrolla un método que intenta verificar si dos árboles son iguales o no. static boolean iguales (NodoArbol a, NodoArbol b) { boolean resul ; if ((a == null) && (b == null)) resul = true; else if ((a == null) || (b == null)) resul = false; else if (a.clave == b.clave) resul = iguales(a.iz, b.iz) && iguales (a.de, b.de); else resul = false; return resul; } static boolean iguales (Arbol a1, Arbol a2) { return iguales (a1.raiz, a2.raiz); }


ÁRBOLES 157

4.3. ÁRBOLES BINARIOS DE BÚSQUEDA. Un árbol binario de búsqueda es un tipo de árbol binario en el que se verifica para todo nodo que las claves de su subárbol izquierdo son menores que las de dicho nodo y las claves de su subárbol derecho son mayores. La figura 4.10. muestra un ejemplo. 30

20

35

10

22

5

1

15

24

12

18

17

Figura 4.7. Ejemplo de árbol binario de búsqueda. La utilización de árboles binarios de búsqueda implica en términos generales las siguientes consideraciones: 4.3.1. Algoritmos de consulta. En caso de búsqueda de alguna clave el proceso resulta de mayor eficiencia que en el caso general, dado que el encaminamiento se produce de forma dirigida (por la derecha si arbol.clave < dato y por la izquierda si arbol.clave > dato). La condición de finalización pesimista es alcanzar un extremo del árbol (arbol == null) que en caso de alcanzarse (una sola vez, no varias como podría suceder para árboles binarios genéricos) implicaría que no se ha encontrado la clave buscada y el proceso finalizaría. La terminación anticipada (no es necesario hacer más llamadas recursivas) se produce cuando se encuentra la clave buscada (arbol.clave == dato). A continuación se muestra como ejemplo el método busqueda que devuelve un puntero al nodo que contiene la clave coincidente con el argumento dato y null en caso de que no exista dicha clave. static boolean busqueda (NodoArbol arbol, int dato) { boolean resul = false; if (arbol != null) if (arbol.clave == dato) resul = true; else if (arbol.clave > dato) resul = busqueda (arbol.iz, dato); else resul = busqueda (arbol.de, dato); return resul; } public boolean busqueda (int dato) { return busqueda (raiz, dato); }

158 ÁRBOLES


En caso de no buscar una clave determinada el recorrido del árbol binario de búsqueda no ofrece ninguna particularidad respecto al árbol binario genérico, pudiendo realizarse dicho recorrido en cualquier modalidad: orden central, preorden o postorden, así como en amplitud. No obstante, cuando se desea recuperar el conjunto de claves del árbol ordenadas, el recorrido deberá ser en orden central (de izquierda a derecha para secuencia ascendente y de derecha a izquierda para secuencia descendente). A continuación se muestra como ejemplo el método booleano esBusqueda que devuelve true si el arbol binario, que se pasa como argumento, es de búsqueda y false en caso contrario. Consiste en verificar que la secuencia de claves es ascendente, por lo que habrá que hacer un recorrido en orden central (de izquierda a derecha) y comparar el valor de cada clave con la anterior (ant) que, debidamente inicializada, deberá pasarse como argumento en las sucesivas llamadas recursivas. Es necesario identificar el primer elemento de la lista (no tiene elemento anterior con el que comparar la clave), con una variable auxiliar booleana (primero), inicializada a true desde fuera de el método. static class Busqueda { static int ant; static boolean primero = true; static boolean esBusqueda (NodoArbol arbol) { boolean resul; if (arbol == null) resul = true; else { resul = esBusqueda (arbol.iz); if (primero) primero = false; else if (arbol.clave <= ant) resul = false; if (resul) { ant = arbol.clave; resul = esBusqueda(arbol.de); } } return resul; } } static boolean esBusqueda (Arbol a) { return Busqueda.esBusqueda(a.raiz); }


ÁRBOLES 159

4.3.2. Algoritmos de modificación. 4.3.2.1. Inserción. Se trata de crear un nuevo nodo en la posición que le corresponda según el criterio de árbol binario de búsqueda. A continuación se muestra el algoritmo. static NodoArbol insertar (NodoArbol arbol, int dato) { NodoArbol resul = arbol; if (arbol != null) if (arbol.clave < dato) arbol.de = insertar (arbol.de, dato); else if (arbol.clave > dato) arbol.iz = insertar (arbol.iz, dato); else System.out.println ("la clave ya existe"); else resul = new NodoArbol (dato); return resul; } public void insertar (int dato) { raiz = insertar (raiz, dato); }

4.3.2.2. Eliminación. La eliminación de un nodo en un árbol binario de búsqueda implica una reorganización posterior del mismo con el objeto de que una vez eliminado el nodo el árbol mantenga su naturaleza de búsqueda. Para ello se procede de la manera siguiente: 15

10

2

1

20

12

7

17

13

25

18

23

Figura 4.8. Árbol binario de búsqueda Primero localizamos el nodo a eliminar. Una vez encontrado, tenemos tres posibles casos: 1.

Tenemos que borrar un nodo hoja: procedemos a borrarlo directamente. Por ejemplo, si en el árbol de la figura 4.11, queremos borrar la clave 13, el resultado sería la figura 4.12. 15

10

2

1

20

12

7

17

25

18

23

Figura 4.9. Borrado de un nodo hoja en un árbol binario de búsqueda

160 ÁRBOLES

2.


Hay que borrar un nodo con un único descendiente: ascendemos a su descendiente. Por ejemplo, si en el árbol de la figura 4.12, queremos borrar la clave 17, el resultado sería la figura 4.13. 15

10

2

1

20

12

18

25

7

23

Figura 4.10. Borrado de un nodo con un solo hijo en un árbol binario de búsqueda 3.

El nodo que queremos borrar tiene dos hijos. En este caso, sustituimos la clave a borrar por la clave del mayor de sus descendientes menores (el nodo más a la derecha del subárbol izquierdo), y borramos el nodo que tenía anteriormente dicha clave. Para poder hacer esto: Nos situamos en la raíz del subárbol izquierdo de dicho nodo. Se desciende por la derecha de dicho subárbol hasta encontrar un nodo (n) sin descendiente derecho. Se sustituye la clave a eliminar por la del nodo n. Se elimina el nodo n6. Por ejemplo, si se desea eliminar la clave 10 del árbol representado en la figura 4.13., sustituiremos dicha clave por la mayor de sus descendientes menores (el 7), y borraremos el nodo con la clave 7 (el nodo que deberemos borrar ahora será en este caso un nodo hoja, aunque también podríamos encontrarnos con un nodo con un solo descendiente). Como resultado, obtendremos el árbol que se muestra en la figura 4.14. 15

7

2

1

20

12

17

25

23

Figura 4.11. Borrado de un nodo con dos hijos en un árbol binario de búsqueda. A continuación se muestra el código del algoritmo de eliminación.

6

Obsérvese que se elimina la clave deseada pero no el nodo físico que la albergaba sino otro.


ÁRBOLES 161

static class Eliminar { static NodoArbol eliminar2Hijos (NodoArbol arbol, NodoArbol p) { NodoArbol resul; if (arbol.de != null) { resul = arbol; arbol.de = eliminar2Hijos (arbol.de, p); } else { p.clave = arbol.clave; resul = arbol.iz; } return resul; } static NodoArbol eliminarElemento (NodoArbol arbol, int elem) { NodoArbol p; if (arbol != null) if (arbol.clave > elem) arbol.iz = eliminarElemento (arbol.iz, elem); else if (arbol.clave < elem) arbol.de = eliminarElemento (arbol.de, elem); else { p = arbol; if (arbol.iz == null) arbol= arbol.de; else if (arbol.de == null) arbol = arbol.iz; else arbol.iz = eliminar2Hijos (arbol.iz, p); } else System.out.println ("la clave buscada no existe"); return arbol; } } public void eliminar (int elem) { raiz = Eliminar.eliminarElemento (raiz, elem); }

4.3.3. Ejemplo. Dado un árbol binario de búsqueda y una lista enlazada por medio de punteros, implementar un algoritmo en Java que, recibiendo al menos un árbol y una lista ordenada ascendentemente, determine si todos los elementos del árbol están en la lista. Implementaremos un método booleano con el arbol y la lista como argumentos. Como la lista está ordenada ascendentemente, y el árbol binario es de búsqueda, realizaremos un recorrido del árbol en orden central, parando en el momento en que detectemos algún elemento que existe en el árbol, pero no en la lista.

162 ÁRBOLES


static boolean estaContenido (NodoArbol arbol, NodoLista lista) { boolean seguir, saltar; if (arbol == null) seguir = true; else { seguir = estaContenido (arbol.iz, lista); if (seguir && (lista != null)) if (arbol.clave < lista.clave) seguir = false; else { saltar = true; while ((lista != null) && saltar) if (arbol.clave == lista.clave) saltar = false; else lista = lista.sig; if (!saltar) seguir = estaContenido (arbol.de, lista.sig); else seguir = false; } else seguir = false; } return seguir; } static boolean estaContenido (Arbol a, Lista l) { return estaContenido (a.raiz, l.inicio); }


ÁRBOLES 163

4.4. ÁRBOL SOBRE MATRIZ. 4.4.1. Clases y constructores. Si se desea implementar un árbol binario de búsqueda utilizando una matriz, se pueden definir las siguientes clases NodoArbol y Arbol: class NodoArbol { int clave, izq, der; NodoArbol () { clave = 0; izq = -1; der = -1; } } public class ArbolMatriz { final int NULL = -1, N = 10; NodoArbol [ ] matriz; int numNodos; ArbolMatriz () { matriz = new NodoArbol [N]; for (int i = 0; i < N; i++) matriz [i] = new NodoArbol (); numNodos = 0; } ... }

Utilizando las clases anteriores, utilizaríamos la siguiente matriz para guardar el contenido del árbol de la figura 4.12.: Clave Hijo izquierdo Hijo derecho

0 10 3 2

1 20 6 4

2 5 -1 -1

3 15 -1 -1

4 45 5 -1

5 15 -1 -1

6 0 -1 -1

7 0 -1 -1

8 0 -1 -1

9 0 -1 -1

10

5

20

15

45

25

Figura 4.12. Ejemplo de árbol binario. La clave de la raíz del árbol (10) aparece en la posición 0 de la matriz, en el campo clave. Su hijo izquierdo (el 5), está en la posición 3 de la matriz (dado que matriz [0].izq =3), mientras que el hijo derecho (15) estará en la posición 2. Cuando un elemento es una hoja (por ejemplo, el 15), su hijo izquierdo y su hijo derecho tendrán como valor NULL (es decir, -1).

164 ÁRBOLES


4.4.1.1. Recorridos en profundidad. A continuación se detallan los códigos correspondientes a los tres recorridos en profundidad. En cualquiera de los casos, desde el método de llamada se llama a uno auxiliar recursivo, pasándole como argumento la posición de la raíz (0). Recorrido en preorden: En el método recursivo privado preOrdenAux, se escriben las claves del árbol en preorden: primero escribimos la clave del nodo (matriz [i].clave), luego se avanza por la izquierda (haciendo la llamada con matriz [i].izq), y luego por la derecha (matriz [i].der). private void preOrden (int i) { if (i != NULL) { System.out.print (matriz [i].clave+", "); preOrden (matriz [i].izq); preOrden (matriz [i].der); } } public void preOrden () { preOrden (0); }

Recorrido en orden central: private void ordenCentral (int i) { if (i != NULL) { ordenCentral (matriz [i].izq); System.out.print (matriz [i].clave+", "); ordenCentral (matriz [i].der); } } public void ordenCentral () { ordenCentral (0); }

Recorrido en post-orden: En el método recursivo privado ordenCentralAux, se escriben las claves del árbol en post orden: primero se avanza por la izquierda (haciendo la llamada con matriz [i].izq, ), luego por la derecha (matriz [i].der) y por último escribimos la clave del nodo (matriz [i].clave). private void postOrden (int i) { if (i != NULL) { postOrden (matriz [i].izq); postOrden (matriz [i].der); System.out.print (matriz [i].clave+", "); } } public void postOrden () { postOrden (0); }


ÁRBOLES 165

4.4.1.2. Búsqueda. Para realizar una búsqueda en un árbol binario de búsqueda sobre matriz, es necesario comprobar primero si no hemos llegado a un nodo vacío (if (i != NULL), en cuyo caso devolveremos false como resultado), y luego vamos avanzando por la rama correspondiente: si la clave es mayor que la buscada seguiremos por la izquierda (resul = busqueda (matriz [i].izq, dato)), si la clave es menor que la buscada seguiremos por la derecha (resul = busqueda (matriz [i].der, dato)), y si la clave es la que estamos buscando, pararemos devolviendo como resultado true. public boolean busqueda (int dato) { return busqueda (0, dato); } private boolean busqueda (int i, int dato) { boolean resul = false; if (i != NULL) if (matriz [i].clave > dato) resul = busqueda (matriz [i].izq, dato); else if (matriz [i].clave < dato) resul = busqueda (matriz [i].der, dato); else resul = true; return resul; }

166 ÁRBOLES


4.4.1.3. Inserción. Para realizar la inserción en un árbol binario de búsqueda sobre matriz, es necesario comprobar primero si todavía no está lleno el árbol (comprobando la variable miembro numNodos). Si se va a insertar en un árbol vacío, la inserción se hará en el método de llamada (insertar): public void insertar (int dato) { if (numNodos == 0){ matriz [0].clave =dato; numNodos++; } else if (numNodos < N) insertar (0, dato); else System.out.println ("árbol lleno"); }

Para el resto de los nodos utilizaremos el método recursivo insertarAux. Para ello, primero habrá que localizar dónde deberíamos insertar el nodo (realizando una búsqueda guiada por el árbol). Una vez localizado, utilizaremos para el nuevo nodo la primera posición libre en la matriz (la posición numNodos). private int insertar (int i, int dato) { int j = NULL; if (i != NULL) if (matriz [i].clave > dato) { j = insertar (matriz [i].izq, dato); if (j != NULL) matriz [i].izq = j; j = i; } else if (matriz [i].clave < dato) { j = insertar (matriz [i].der, dato); if (j != NULL) matriz [i].der = j; j = i; } else System.out.println ("la clave ya existe"); else { j = numNodos; matriz [j].clave = dato; numNodos++; } return j;

}


ÁRBOLES 167

4.4.1.4. Eliminación. Para eliminar una clave, se sigue la misma estrategia que en el apartado 4.3.2.2: El método recursivo eliminar busca la clave que se desea eliminar. Si es una hoja se elimina directamente, Si es un nodo con un hijo se sustituye por el hijo, Y si es un nodo con dos hijos se llama al método eliminarDosHijos para sustituir la clave del nodo por la inmediatamente anterior (bajando una vez a la izquierda y luego todo el rato a la derecha hasta encontrar un nodo sin hijo izquierdo). public void eliminar (int dato) { eliminar (0, dato); } private int eliminar (int i, int dato) { int j = NULL; if (i != NULL) if (matriz [i].clave > dato) { j = eliminar (matriz [i].izq, dato); if (j != NULL) matriz [i].izq = j; j = i; } else if (matriz [i].clave < dato) { j = eliminar (matriz [i].der, dato); if (j != NULL) matriz [i].der = j; j = i; } else { numNodos--; if (matriz [i].der == NULL) { j = matriz [i].izq; borrarNodo (i); } else if (matriz [i].izq == NULL) { j = matriz [i].der; borrarNodo (i); } else { matriz [i].izq = eliminarDosHijos (matriz [i].izq, i); j = i; } } else System.out.println ("la clave no existe"); return j; }

168 ÁRBOLES


private int eliminarDosHijos (int i, int j) { int resul = i; if (matriz [i].der != NULL) matriz [i].der = eliminarDosHijos (matriz [i].der, j); else { matriz [j].clave = matriz [i].clave; borrarNodo (i); resul = matriz [i].izq; } return resul; }

Por último, si encontramos el nodo a eliminar, en cualquiera de los casos (tenga cero, uno o dos hijos) se utilizará un método auxiliar (borrarNodo) para desplazar los elementos que haya a continuación del nodo eliminado. private void borrarNodo (int i) { for (int j = i; j < numNodos; j++) { matriz [j].clave = matriz [j+1].clave; matriz [j].der = matriz [j+1].der; matriz [j].izq = matriz [j+1].izq; } for (int j = 0; j <= numNodos; j++) { if (matriz [j].der >= i) matriz [j].der = matriz [j].der -1; if (matriz [j].izq >= i) matriz [j].izq = matriz [j].izq -1; }

}

Por ejemplo, si en el árbol de la figura 4.13., representado por la matriz que aparece a continuación, eliminamos el nodo 20, el resultado sería el de la figura 4.14: Clave Hijo izquierdo Hijo derecho

0 10 2 1

1 20 3 4

2 5 -1 -1

3 15 -1 -1

4 45 5 -1

5 25 -1 -1

6 0 -1 -1

7 0 -1 -1

10

5

20

15

45

25

Figura 4.13. Árbol binario antes de eliminar.

8 0 -1 -1

9 0 -1 -1


ÁRBOLES 169

Resultado:

Clave Hijo izquierdo Hijo derecho

0 10 2 1

1 15 -1 3

2 5 -1 -1

3 45 4 -1

4 25 -1 -1

5 25 -1 -1

6 0 -1 -1

7 0 -1 -1

8 0 -1 -1

9 0 -1 -1

10

5

15

45

25

Figura 4.14. Árbol binario después de eliminar la clave 20. Obsérvese que, al haber desplazado los elementos de la matriz hacia la izquierda, la clave 25 aparece repetida. De todas formas, dicho valor no se tendrá en cuenta, dado que la posición 5 sólo se alcanzará en caso de insertar una nueva clave (y se sustituirá dicha clave por su nuevo valor).

170 ÁRBOLES


4.5. UTILIZACIÓN DE UN TAD ÁRBOL. Los algoritmos explicados en las secciones anteriores implican el conocimiento interno de la estructura del árbol binario. Otro tanto podría haberse hecho en caso de que el árbol se hubiera implementado mediante cualquier otra alternativa posible. Otra opción consiste en que el programador dispusiera de un Tipo Abstracto de Datos del que, dada su característica de ocultamiento, se desconoce absolutamente su implementación y, en consecuencia, solo es posible disponer de sus funcionalidades mediante un conjunto de especificaciones. A continuación se muestra un ejemplo de un TAD árbol binario de números enteros positivos: package tadArbol; public interface Arbol { void crearNodo (); /*Crea un nuevo nodo en el árbol, que queda apuntando a ese nodo*/ int obtenerClave (); /*Devuelve la clave contenida en la raiz del árbol*/ NodoArbol devolverRaiz (); /*Devuelve una referencia a la raiz del arbol*/ NodoArbol devolverHijoIzquierdo (); /*Devuelve el hijo izquierdo del árbol*/ NodoArbol devolverHijoDerecho (); /*Devuelve el hijo derecho del árbol*/ void ponerClave (int Clave); /*pone la clave pasada como argumento en la raíz del árbol*/ void ponerReferencia (NodoArbol nuevoArbol); /*Hace que el árbol apunte al mismo sitio que nuevoArbol*/ void ponerHijoIzquierdo (NodoArbol arbolAsignado); /*Hace que el hijo izquierdo del arbol apunte ahora a arbolAsignado*/ void ponerHijoDerecho (NodoArbol arbolAsignado); /*Hace que el hijo derecho del arbol, apunte ahora a arbolAsignado*/ void asignarNulo (); /*Hace que el arbol tome el valor null*/ boolean esNulo (); /*Devuelve true si el arbol tiene valor null y false en caso contrario*/ boolean iguales (NodoArbol otroArbol); /*Devuelve true si la raíz del árbol y la de otroArbol apuntan al mismo sitio, false en caso contrario*/ }

Dado el TAD árbol anterior, se propone desarrollar un método (sumaClaves) que obtenga la suma de las claves del árbol. static int sumaClaves (Arbol arbol) { int resul = 0; Arbol izq = new TadArbol (), der = new TadArbol (); if (!arbol.esNulo()) { izq.ponerReferencia (arbol.devolverHijoIzquierdo ()); der.ponerReferencia (arbol.devolverHijoDerecho ()); resul = arbol.obtenerClave () + sumaClaves (izq) + sumaClaves (der); } return resul; }


ÁRBOLES 171

4.5.1. Implementación del TAD Árbol package tadArbol; public class TadArbol implements Arbol { NodoArbol raiz; public TadArbol () { raiz = null; } /*Crea un nuevo nodo en el árbol, que queda apuntando a ese nodo*/ public void crearNodo () { raiz = new NodoArbol (); } /*Devuelve la clave contenida en la raíz del árbol */ public int obtenerClave () { int resul = 0; if (raiz != null) resul = raiz.clave; return resul; } /*Devuelve el hijo izquierdo del árbol*/ public NodoArbol devolverHijoIzquierdo () { NodoArbol resul = null; if (raiz!= null) resul = raiz.iz; return resul; } /*Devuelve el hijo derecho del árbol*/ public NodoArbol devolverHijoDerecho () { NodoArbol resul = null; if (raiz != null) resul = raiz.de; return resul; } /*pone la clave pasada como argumento en la raíz del árbol*/ public void ponerClave (int clave) { if (raiz != null) raiz.clave = clave; } /*Hace que el árbol apunte al mismo sitio que nuevoArbol*/ public void ponerReferencia (NodoArbol nuevoArbol) { raiz = nuevoArbol; } /*Hace que el hijo izquierdo del arbol apunte ahora a arbolAsignado*/ public void ponerHijoIzquierdo (NodoArbol arbolAsignado) { if (raiz != null) raiz.iz = arbolAsignado; else System.out.println ("Error, el árbol está vacío"); } /*Hace que el hijo derecho del arbol, apunte ahora a arbolAsignado*/ public void ponerHijoDerecho (NodoArbol arbolAsignado) { if (raiz != null) raiz.de = arbolAsignado; else System.out.println ("Error, el árbol está vacío"); }

172 ÁRBOLES


/*Hace que el arbol tome el valor null*/ public void asignarNulo () { raiz = null; } /*Devuelve true si la raíz del arbol tiene valor null y false en caso contrario*/ public boolean esNulo () { return raiz == null; } /*Devuelve true si la raíz del árbol apunta al mismo sitio que otroArbol, false en caso contrario*/ public boolean iguales (NodoArbol otroArbol) { return raiz == otroArbol; } /*Devuelve una referencia a la raiz del arbol*/ public NodoArbol devolverRaiz() { return raiz; } }


ÁRBOLES 173

TEMA 4. ................................................................................................................... 143 4.1.

Conceptos generales. .................................................................................. 143

4.2.

Árboles Binarios. ........................................................................................ 146

4.2.1.

Implementación física. ....................................................................... 146

4.2.2.

Algoritmos básicos con árboles binarios. ........................................... 147

4.2.3.

Ejemplo. ............................................................................................. 156

4.3.

Árboles Binarios de Búsqueda. .................................................................. 157

4.3.1.

Algoritmos de consulta. ...................................................................... 157

4.3.2.

Algoritmos de modificación. .............................................................. 159

4.3.3.

Ejemplo. ............................................................................................. 161

4.4.

Árbol sobre matriz. ..................................................................................... 163

4.4.1. 4.5.

Clases y constructores. ....................................................................... 163

Utilización de un TAD árbol. ..................................................................... 170

4.5.1.

Implementación del TAD Árbol......................................................... 171


GRAFOS 173

TEMA 5

Grafos. 5.1. DEFINICIÓN DE GRAFO A menudo, cuando se observa la red de rutas aéreas de un país interesa observar cómo ir de una ciudad a otra por las rutas posibles. En consecuencia, se tiene dos conjuntos de objetos distintos: ciudades y rutas. La Figura 5.1 muestra una manera de representar la relación existente entre las ciudades y las rutas, así como la distancia entre las distintas ciudades.

BILBAO OVIEDO 445

606

395 MADRID

531 SEVILLA

BARCELONA

622 437

538 ALICANTE

1006

534 207 MELILLA

221

MALAGA

Figura 5.1. Representación de las conexiones entre ciudades.

174 GRAFOS


En general, un grafo es una manera de representar relaciones que existen entre pares de objetos. Así, un grafo es un conjunto de objetos, llamados vértices1, y relaciones entre objetos que establecen una relación entre pares de vértices, representadas por aristas. En el ejemplo anterior, el grafo de la Figura 5.1 representa las conexiones aéreas entre ciudades. Los vértices representarían las ciudades. Las aristas representan las conexiones entre ciudades y, en este caso, se almacenan la distancia en kilómetros entre las ciudades que une. Definición 1. Un grafo se define como un par G = (V, A), donde V es un conjunto finito no vacío de vértices y A es un conjunto de pares de vértices de V, es decir, las aristas. Definición 2. Un grafo G se define como un par ordenado, G = (V, A), donde V es un conjunto finito y A es un conjunto que consta de dos elementos de V.

1

La terminología de la teoría de grafos no es estándar. El concepto de vértice también se referencia como nodo. Asimismo, aristas (edges en inglés) y arcos denotan el mismo elemento. En algunos libros, sin embargo, se establece una diferencia entre aristas (unen vértices en un grafo no dirigido) y arcos (unen vértices en grafos dirigidos). En este capítulo, se dará preferencia a los términos vértice y arista.


GRAFOS 175

5.2. TERMINOLOGÍA Y CONCEPTOS 5.2.1. Grafos dirigidos y no dirigidos Dependiendo del tipo de relación entre los vértices del grafo, se definen distintos tipos de grafos. Así se distinguen aristas dirigidas y no dirigidas: Arista dirigida: es aquella que define un par ordenado de vértices (u,v), donde el primer vértice u es el origen de la arista y el segundo vértice v es el término (o vértice final). El par (u, v) ≠ (v, u). Arista no dirigida: es aquella que define un par no ordenado de vértices (u, v), donde (u, v) = (v, u). De esta forma se distinguen entre grafos dirigidos y grafos no dirigidos. Grafo dirigido: Es aquel cuyas aristas son dirigidas. Los grafos dirigidos suelen representar relaciones asimétricas como por ejemplo: relaciones de herencia, los vuelos entre ciudades, etc. Grafo no dirigido: Es aquel cuyas aristas son no dirigidas. Representan relaciones simétricas como relaciones de hermandad y colaboración, conexiones de transportes, etc. 5.2.2.

Incidencia, adyacencia y grado de un vértice

Sea un grafo G = (V, A), los vértices u y v pertenecientes a V; y una arista (u,v) perteneciente a A, se dice que: Incidencia: la arista (u,v) es incidente con los vértices u y con v. Adyacencia: Dos vértices u y v son adyacentes si existe una arista cuyos vértices sean u y v: o El vértice u es adyacente a v o El vértice v es adyacente desde u Grado: El grado de un vértice u es el número de vértices adyacentes a u. Para un grafo dirigido, el grado de salida de un vértice u es el número de vértices adyacentes desde u, mientras que el grado de entrada de un vértice u es el número de vértices adyacentes a u. La Figura 5.2 muestra los grados de los vértices para un grafo no dirigido y un grafo dirigido.

176 GRAFOS


Grafo no dirigido:

a

Grafo dirigido:

a

b

b

e c

e c

d

Grado (a) = 3 Grado (b) = 3 Grado (c) = 2 Grado (d) = 4 Grado (e) = 4

d

GradoE (a) = 2 GradoE (b) = 3 GradoE (c) = 0 GradoE (d) = 2 GradoE (e) = 1

GradoS (a) = 1 GradoS (b) = 0 GradoS (c) = 2 GradoS (d) = 2 GradoS (e) = 3

Figura 5.2. Grado de los vértices en un grafo no dirigido y dirigido. 5.2.3.

Grafos simples y multigrafos

Un grafo simple es aquel que no tiene aristas paralelas o múltiples que unan el mismo par de vértices. Un grafo que cuente con múltiples aristas entre dos vértices se denomina multigrafo. La Figura 5.3 muestra un ejemplo de grafo simple y de multigrafo, donde existen aristas paralelas incidentes a los vértices a y d, y e y d. En este caso, se dice que el grafo tiene multiplicidad 2 (máximo de aristas paralelas entre dos vértices). MULTIGRAFO:

GRAFO SIMPLE: a

a

b

b

e c

e

d

d

Figura 5.3. Grafo simple y grafo no simple Si asumimos un grafo simple, se observan las siguientes propiedades: Si G es un grafo no dirigido con m vértices, entonces

Σ grado(v) = 2m.

v en G

Una arista (u, v) se cuenta dos veces en este sumatorio, uno como vértice final u y otro como vértice final v. Entonces, la contribución total de las aristas a los grados de los vértices es dos veces el número de las aristas.


GRAFOS 177

Si G es un grafo dirigido con m vértices, entonces: grado E(v) = Σ grado S(v) = m Σ v en G v en G En un grafo dirigido, una arista (u,v) contribuye una unidad al grado de salida de su origen u y una unidad al grado de entrada de su vértice final v. Por tanto, la contribución total de las aristas al grado de salida de los vértices es igual al número de aristas, y similar para los grados de salida. Sea G un grafo simple con n vértices y m aristas, entonces: Un arco (u,v) se cuenta dos veces en este sumatorio, uno como ENDPOINT o como Si G es no dirigido: ≤ n(n-1)/2. u y otro ENDPOINT V.m Entonces, la contribución total de los arcos a los grados de los vértices es dos veces el número de los arcos. o Si G es dirigido: m ≤ n(n-1). 5.2.4.

Camino, bucle y ciclo

Un camino es una secuencia que alterna vértices y aristas que comienza por un ∊ vértice y termina en vértice tal que cada arista es incidente a su vértice predecesor y sucesor. Es decir, un camino es un sucesión de vértices de vi V: que cumple que: (vi,,vi+1) ∊ A ∀ i ∊ {0 … k-1}. Se dice que este camino tiene longitud k. Es decir, el número de aristas de un camino o ciclo es la longitud del camino. Un camino es simple si cada vértice en el camino es distinto, excepto posiblemente por el primero y el último vértice. Un camino simple cumple la siguiente restricción: vi ≠ vj ∀ i ∊ {0…k}, j ∊ {1…k-1}, i≠j Para todo vértice x, existe el camino simple <x>, que sería el camino de longitud 0. Un bucle es un camino de longitud 1 que comienza y termina en el mismo vértice: <xi, xi>. Un ciclo es un camino simple que cumple las siguientes restricciones: v0= vk Si es no dirigido, k = 1 (es un bucle) o k ≥ 3. La Figura 5.4 ilustra estos conceptos para un grafo no dirigido y un grafo dirigido.

178 GRAFOS


GRAFO NO DIRIGIDO: a

GRAFO DIRIGIDO: a

b

b e

e c

c

d

: camino simple de longitud 4. : camino de longitud 5. : no es un camino. <e,e>: camino, bucle y ciclo

d

: camino simple de longitud 1. <e,d,a,b>: camino de longitud 3. : no es un camino. <e,e>: camino, bucle y ciclo

Figura 5.4. Caminos, bucles y ciclos en un grafo dirigido y no dirigido. 5.2.5.

Grafos conexos

Sea G = (V, A) un grafo no dirigido, se le denomina conexo si existe un camino entre dos vértices cualesquiera de G. Para un grafo dirigido G, su grafo asociado no dirigido es aquel que se obtiene ignorando la dirección de las aristas. G se considera conexo si su grafo asociado es conexo. La Figura 5.5 muestra ejemplos de grafos conexos y no conexos. GRAFO 1: NO DIRIGIDO CONEXO a

GRAFO 2: DIRIGIDO CONEXO a

b

b

e c

e c

d

GRAFO 3: NO DIRIGIDO NO CONEXO a

GRAFO 4: DIRIGIDO NO CONEXO a

b

d

b e

e c

d

c

d

Figura 5.5. Ejemplos de grafos conexos y no conexos


GRAFOS 179

5.2.6. Grafos valorados y grafos etiquetados2 Un grafo valorado (o ponderado) es una terna donde es un grafo y f es una función cualquiera, denominada función de coste, que asocia un valor o peso a cada arista en el grafo. El peso de un camino en un grafo con pesos es la suma de los pesos de todas las aristas atravesadas. En un grafo etiquetado, la función f tiene como imagen un conjunto de etiquetas no numéricas. GRAFO VALORADO

GRAFO ETIQUETADO Museo Municipal

a 3.6 c

1 0.5 2

está-en

estilo b 2 2 d

diseñado-por

2.8 nacido-en

e 5

churrigueresco estilo Plaza Mayor

Figura 5.6. Grafo valorado y grafo etiquetado

2

Pedro de Ribera

En este curso no se van a tratar los grafos valorados ni etiquetados.

Madrid está-en

Salamanca

180 GRAFOS


5.3. IMPLEMENTACIONES DE GRAFOS Los dos tipos de implementación más frecuentes (independientemente del lenguaje de programación) para la representación de grafos son las matrices de adyacencias y las listas de adyacencias. En este tema, se detallarán ambas implementaciones en el lenguaje Java. 5.3.1. Interfaz del TAD Grafo. Los métodos de objeto que podremos utilizar sobre las variables de la clase Grafo (no etiquetado ni ponderado) aparecen en la siguiente interfaz: import java.io.IOException; public interface Grafo { public void insertaVertice(int n); /** Inserta un vértice en el grafo siempre que no se supere el número máximo de nodos permitidos **/ public void eliminarVertice(int v) /** Elimina un vértice del grafo **/ public void insertaArista(int i, int j); /** Inserta una arista entre los vértices i y j **/ public void eliminarArista(int i, int j); /** Elimina la arista entre los vértices i y j **/ public boolean esVacio(Grafo g); /** Devuelve true si el grafo no contiene ningún vértice **/ public boolean existeArista(int i, int j); /** Devuelve true si existe una arista que una los vértices i y j. **/ public int gradoIn(int i) ; /** Devuelve el grado de entrada del vértice i **/ public int gradoOut(int i); /** Devuelve el grado de salida del vértice i **/ public int incidencia (int i) /** Devuelve la incidencia del vértice i **/ public int tamano(); /** Devuelve el tamaño (número de aristas) del grafo **/ public boolean esDirigido (Grafo g) ; /** Devuelve true si el grafo g es dirigido **/ public void ponerMaxNodos(int n); /** Asigna el número máximo de nodos o vértices permitidos en el grafo**/ public void ponerDirigido(boolean d); /** Determina si es un grafo dirigido o no dirigido **/ }


5.3.2.

GRAFOS 181

Matriz de adyacencias

Una matriz de adyacencias A (implementada como una matriz bidimensional) determina las adyacencias entre pares de vértices de un grafo. En una matriz de adyacencias, los vértices se conciben como enteros en el conjunto {0,1,…,n-1} y las aristas como pares de tales enteros. Esto permite almacenar referencias a las aristas en las celdas de la matriz bidimensional de nxn. Cada fila y cada columna representan un vértice del grafo y cada posición representa una arista (o la ausencia de esta) cuyo vértice origen se encuentra en la fila y vértice final se encuentra en la columna. La Figura 5.7 muestra la representación gráfica de un grafo y su matriz de adyacencias.

a

b e c

d

a b c d e

a 0 0 1 1 0

b 1 0 0 1 1

c 0 0 0 0 0

d 0 0 1 0 1

e 0 0 0 0 1

Figura 5.7. Grafo y matriz de adyacencias correspondiente Nótese que la matriz de adyacencias para un grafo no dirigido es una matriz simétrica como se puede apreciar en la Figura 5.8:

a

b e c

d

a b c d e

a 0 1 1 1 0

b 1 0 0 0 1

c 1 0 0 1 0

d 1 0 1 0 0

e 0 1 0 0 0

Figura 5.8. Grafo y matriz de adyacencias para un grafo no dirigido En una tabla de adyacencias, los vértices se representan mediante índices. Así, sea un grafo con los vértices {a,b,c,d,e}, estos serán representados mediante sus índices {0,1,2,3,4} tal y como se muestra en la Figura 5.9.

a

b e

c

d

VÉRTICES: a

b

c

d

e

ÍNDICES:

1

2

3

4

0

Figura 5.9. Relación entre vértices e índices

182 GRAFOS


De esta manera, podemos definir una matriz A bidimensional de n x n donde la celda [i, j] guarda información referente a la arista (v, w), en caso de que exista, donde v es el vértice con índice i y w es el vértice con índice j. Existen varias posibilidades para representar la arista (v, w) en su correspondiente celda A [i, j]: Si no es etiquetado: un valor booleano que toma el valor 1 si existe la arista y 0 en caso contrario. Si es valorado: un real con el valor f (i, j) si existe la arista. En caso contrario, toma el valor ∞. Se obtendría la matriz de costes del grafo. Si es etiquetado: una etiqueta con el valor f (i, j) si existe la arista. En caso contrario, toma el valor “etiqueta imposible”. Se obtendría la matriz de etiquetas del grafo. A continuación, se muestra una posible implementación de un grafo en una matriz de adyacencias en Java. Se asume que se trata de un grafo simple no etiquetado (tanto dirigido como no dirigido). 5.3.2.1. Representación de la clase Grafo La siguiente sintaxis muestra la implementación de la clase grafo con un matriz de adyacencias: public class GrafoMA implements Grafo { private boolean dirigido; // Indica si es dirigido o no. private int maxNodos; // Tamaño máximo de la tabla. private int numVertices; // Número de vértices del grafo. private boolean matrizAdy [ ] [ ]; // Matriz de adyacencias del grafo. }

La representación gráfica de una variable de la clase Grafo llamada “grafo1” que represente el grafo de la Figura 5.7 sería:

grafo1

true

5

5

Variable estática

dirigido

maxNodos

numVertices

Clase Grafo

matrizAdy

a b c d e

a 0 0 1 1 0

b 1 0 0 1 1

c 0 0 0 0 0

Figura 5.10. Representación gráfica de la variable “grafo1”

d 0 0 1 0 1

e 0 0 0 0 1


GRAFOS 183

5.3.2.2. Constructores de la clase Grafo3. Se utiliza para crear un grafo vacío, con un tamaño máximo y número de vértices igual a 0. Se pasa como argumento un booleano que indica si se trata de un grafo dirigido o no dirigido. public GrafoMA (boolean d) { maxNodos = numVertices = 0; dirigido = d; }

También se puede incluir un constructor al que se le pasen como argumentos el número de vértices del grafo y el valor para el campo dirigido: public GrafoMA (int n, boolean d) { dirigido = d; maxNodos = n; numVertices = 0; matrizAdy = new boolean[n][n]; }

5.3.2.3. Algoritmos básicos de modificación: insertar y eliminar aristas. La inserción de una arista (i, j) en la matriz supone asignar a la celda correspondiente el valor true. Si se trata de un grafo dirigido, debe tenerse en cuenta que el vértice origen i corresponde a fila, mientras que el vértice destino j corresponde la columna. En caso de que se trate de un grafo no dirigido, debe recordarse que la arista (i, j) es igual a la arista (j, i) para que la matriz mantenga la propiedad de la simetría. public void insertaArista (int i, int j) { matrizAdy [i] [j] = true; if (!dirigido) matrizAdy [j] [i] = matrizAdy [i] [j]; }

La eliminación de la arista (i, j) es sencilla, consiste en asignar el valor false a la celda correspondiente de la matriz. En caso de que se trate de un grafo no dirigido, habrá de modificarse igualmente el valor correspondiente a la arista (j, i): public void eliminarArista (int i, int j) { matrizAdy [i] [j] = false; if (!dirigido) matrizAdy [j] [i] = false; }

3

Antes de ejecutar esta operación deberá asegurarse de que no existe previamente ningún grafo con el mismo nombre pues su ejecución haría que se perdiese el contenido del grafo preexistente.

184 GRAFOS


5.3.2.4. Algoritmos básicos de modificación: insertar vértices La modificación de los vértices del grafo supone un grado de complejidad mayor que el tratamiento de las aristas. Para la inserción de un vértice, el código aquí mostrado simplifica el método de manera que no deja insertar vértices si se supera el límite de vértices del grafo (valor del campo maxNodos). En caso de que no se supere el número máximo de vértices, simplemente se asigna el valor false a las celdas correspondientes y se actualiza el campo numVertices: public void insertaVertice (int n) { if ( n > maxNodos - numVertices ) System.out.println ("Error, se supera el número de nodos máximo"); else { for (int i=0; i < numVertices + n; i++) { for (int j = numVertices; j < numVertices + n; j++) matrizAdy [i] [j] = matrizAdy [j] [i] = false; } numVertices = numVertices + n; } }

La eliminación de un vértice supondría cambiar los índices de los vértices. De manera que no se va a reproducir esta operación. Se deja al alumno como ejercicio la posible implementación de eliminación de un vértice. 5.3.2.5. Otros métodos Puede ser interesante conocer el grado de entrada y de salida de un vértice. Retómese el grafo y su matriz de la Figura 5.7. En un grafo dirigido, el grado de entrada de un vértice, por ejemplo d, viene dado por la suma de los valores de la columna d; mientras que su grado de salida vendría dado por la suma de los valores de la fila d:

a

b e c

d

a b c d e

a 0 0 1 1 0

b 1 0 0 1 1

c 0 0 0 0 0

d 0 0 1 0 1

e 0 0 0 0 1

Grado de salida (b) = 0

Grado de entrada (b) = 3

Figura 5.11. Grados de entrada y salida en una matriz de adyacencias. public int gradoIn(int j) { int gIn = 0; for (int i = 0; i < numVertices; i++) //recorrido por filas if (matrizAdy [i] [j]) gIn++; //manteniendo la posición de la columna en [j] return gIn; }


GRAFOS 185

public int gradoOut(int i) { int gOut = 0; for (int j= 0; j < numVertices; j++) if (matrizAdy [i][j]) gOut++; // manteniendo la posición de la fila en [i] return gOut; }

En un grafo no dirigido, la incidencia de un vértice vendría dada por su grado de entrada: public int incidencia (int i) { if (!dirigido) return gradoIn (i); else return gradoIn (i) + gradoOut (i); }

El tamaño de un grafo viene dado por el número de aristas. Debe notarse que las aristas de un grafo no dirigido se cuentan dos veces. public int tamano() { int tm = 0; for (int i = 0; i < numVertices; i++) for (int j=0; j < numVertices; j++) if (matrizAdy [i] [j]) tm++; if (dirigido) return tm; else return tm/2; }

Para comprobar si un grafo es dirigido o no, basta con comprobar si se trata de una matriz simétrica, donde la posición [i, j] = [j, i]: public boolean esDirigido (Grafo g) { boolean dir = true; for (int i = 0; i < numVertices; i++) for (int j = 0; j < numVertices; j++) if (matrizAdy [i] [j] != matrizAdy [j] [i]) dir = false; return dir; }

Por último, el siguiente método imprime una matriz de adyacencias de un grafo: public void imprimirTabla () { System.out.println ("La matriz contiene " + numVertices + " vértices: \n"); for (int i = 0; i < numVertices; i++) { for (int j = 0; j < numVertices; j++) { if (matrizAdy [i] [j]) System.out.print ("1 "); else System.out.print ("0 "); } } }

186 GRAFOS

5.3.3.


Lista de adyacencias

Otra implementación frecuente para la estructura grafo es la lista de adyacencias. En una lista de adyacencias, a cada vértice i se le asocia una lista enlazada con todos los vértices j adyacentes a i. De esta forma sólo se reserva memoria para las aristas adyacentes a i y no para todas las posibles aristas que pudieran tener como origen i (como ocurre en una matriz de adyacencias). El grafo, por tanto, se representa por medio de un vector de n componentes, siendo n el número de vértices del grafo, donde cada componente constituye la lista de adyacencias correspondiente a cada uno de los vértices del grafo. Cada nodo de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado o valorado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta o el peso de la arista. La Figura 5.12 muestra un grafo y su representación en una lista de adyacencias.

0

1 4 2

3

null

0

1

1

null

2

0

3

null

3

0

1

null

4

1

3

4

null

Figura 5.12. Grafo dirigido y lista de adyacencias asociada

5.3.3.1. Representación de la clase Grafo como lista de adyacencias Para la implementación de la clase Grafo como una lista de adyacencias, se hará uso de la clase Lista Calificada Ordenada (tal y como se vio en el tema 3.6.), así como la clase NodoLista con las siguientes variables miembro y constructores: public class NodoLista { public int clave; public NodoLista sig; public NodoLista (int dato, NodoLista siguiente) { clave = dato; sig = siguiente; } }

public class Lista { public NodoLista inicio; public Lista () { inicio = null; }


GRAFOS 187

La implementación de los distintos métodos de la clase Grafo aquí propuesta utiliza los siguientes métodos de Lista: void insertar (int x) ; void eliminar (int x); boolean busqueda (int x);

La siguiente sintaxis muestra la implementación de la clase grafo con una lista de adyacencias: public class GrafoLA implements Grafo { boolean dirigido; // Indica si es dirigido o no. int maxNodos; // Tamaño máximo de la tabla. int numVertices; // Número de vértices del grafo. Lista listaAdy []; // Vector de listas de adyacencias del grafo. }

Figura 5.13. Clase Grafo 5.3.3.2. Constructores de Grafo El constructor Grafo(boolean d) se utiliza para crear un grafo vacío, con un tamaño máximo y número de vértices igual a 0. El argumento booleano indica si se trata de un grafo dirigido o no dirigido. public GrafoLA (boolean d) { maxNodos = numVertices = 0; dirigido = d; }

También se puede incluir un constructor al que se le pasen como argumentos el número de vértices del grafo y el valor para el campo dirigido. Se crea un vector de n listas inicializadas. public GrafoLA (int n, boolean d) { dirigido = d; maxNodos = n; numVertices = 0; listaAdy = new Lista[n]; }

188 GRAFOS


5.3.3.3. Algoritmos básicos de modificación: insertar aristas. La inserción de una arista (i, j) en la lista de adyacencias supone insertar un nodo con clave j en la lista con índice i. En caso de que se trate de un grafo no dirigido, debe recordarse que la arista (i, j) es igual a la arista (j, i) de forma que habrá que insertar en la lista con índice j el nodo con clave i. public void insertaArista (int i, int j) { if (i >= numVertices) System.out.println ("Error, no existe el vértice en el grafo"); else { listaAdy[i].insertar (j); if (!dirigido) listaAdy[j].insertar (i); } }

La eliminación de la arista (i, j) consiste en eliminar el nodo con clave j de la lista con índice i. Si el grafo es no dirigido, habrá que eliminar el nodo con clave i de la lista con índice j: public void eliminaArista (int i, int j) { if (j >= numVertices) System.out.println("Error, no existe el vértice en el grafo"); else { listaAdy[i].eliminar (j); if (!dirigido) listaAdy[j].eliminar (i); } }

5.3.3.4. Algoritmos básicos de modificación: insertar vértices Al igual que en la matriz de adyacencias, no se permite insertar vértices si se supera el límite de vértices del grafo (valor del campo maxNodos). El método aquí propuesto tiene como argumento un entero que indica el número de vértices que se desea añadir al grafo. En caso de que no se supere el número máximo de nodos del grafo, se inicializan las n listas correspondientes a los vértices que se añaden al grafo. public void insertaVertice (int n) { if (n > maxNodos - numVertices) System.out.println ("Error, se supera el número de nodos máximo del grafo"); else for (int i = numVertices; i < numVertices + n; i++) listaAdy[i]= new Lista(); numVertices += n; }

Dado que la eliminación de un vértice supondría cambiar los índices de los vértices, no se va a reproducir esta operación.


GRAFOS 189

5.3.3.5. Otros métodos Para conocer el grado de entrada de un vértice v en un grado dirigido, se deben contar las veces que aparece el nodo con clave v en las distintas listas de adyacencia. Para ello, se utiliza el método de objeto busqueda de la clase Lista. public int gradoIn (int v) { int gIn = 0; for (int i = 0; i < numVertices; i++) if (i != v) if (listaAdy[i].busqueda(v)) gIn++; return gIn; }

El grado de salida de un vértice v viene dado por el número de elementos de su lista de adyacencia (lista con índice v): public int gradoOut (int i) { //contar los elementos de la lista int gOut = 0; NodoLista aux = listaAdy[i].inicio; while (aux != null){ gOut++; aux = aux.sig; } return gOut; }

En un grafo no dirigido, la incidencia de un vértice vendría dada por su grado de entrada. En cambio, si se trata de un grafo dirigido, la incidencia de un vértice i es la suma de su grado de entrada y salida: public int incidencia (int i) { if (!dirigido) return gradoIn (i); else return gradoIn (i) + gradoOut (i); }

El número de aristas define el tamaño de un grafo. En una implementación basada en listas de adyacencias, el tamaño del grafo viene dado por el número de nodos total de las listas de adyacencias. Para ello, se hace uso del método auxiliar numElems que recibe como argumento una lista y devuelve el número de nodos de la lista de entrada. En el caso de que el grafo sea no dirigido, habría que dividir por dos la suma del número de nodos de las listas de adyacencias puesto que las aristas de un grafo no dirigido se cuentan dos veces:

190 GRAFOS


public int tamanno () { int tm = 0; for (int i=0; i
El siguiente método booleano devuelve un valor verdadero en caso de que el grafo sea no dirigido. En un grafo dirigido simple el par (i, j) es necesariamente distinto del par (j, i), mientras que en un grafo no dirigido se cumple que el par (i, j) = (j, i). El método propuesto comprueba para, cada par de vértices i, j, que el vértice j se encuentre en la lista de adyacencias del vértice i; e igualmente que el vértice i se encuentre en la lista de adyacencias del vértice j. public boolean esNoDirigido () { boolean dir = true; for (int i=0; i
Por último, el siguiente método imprime la lista de adyacencias para un grafo, dicho método utiliza el método de clase escribir (Lista): public void imprimirGrafo () { System.out.println("Tamaño máximo del grafo: " + maxNodos + "\n"); System.out.println("El grafo contiene " + numVertices + " vértices: \n"); for (int i = 0; i < numVertices; i++) { System.out.print ("vértice " + i + ": "); escribir (listaAdy [i]); } } static void escribir (Lista lista) { NodoLista aux; aux = lista.inicio; while (aux != null) { System.out.print (aux.clave +", "); aux = aux.sig; } System.out.println ("FIN"); }


GRAFOS 191

5.3.4. Consideraciones sobre la implementación del grafo como matriz o como lista de adyacencias La principal ventaja de la matriz de adyacencias es el rápido a la información de aristas. Es una estructura recomendable si se van a realizar consultas frecuentes del estilo: ¿existe la arista (u, v) en el grafo? O, en caso de ser un grafo valorado, ¿cuál es el coste de la arista (u, v)? También es una estructura recomendable para grafos con pocos vértices o bien grafos con muchos vértices y muchas aristas. La principal desventaja que presenta la matriz es que requiere un almacenamiento proporcional al cuadrado del número de vértices del grafo, aunque el grafo contenga muchas menos aristas de los posibles. Respecto a las listas de adyacencias, estas ahorran memoria en la representación de grafos con muchos vértices y pocas aristas. Asimismo, si el procesamiento se centra en el tratamiento de los vértices adyacentes a uno dado, la lista de adyacencias es preferible a la matriz.

192 GRAFOS


5.4. RECORRIDOS DE GRAFOS El concepto de recorrido del grafo, como se ha visto en el tema 4 de árboles, consiste en visitar todos los vértices del grafo sucesivamente de manera sistemática de manera que cada vértice se visite una única vez. En el recorrido de un grafo, existen dos tipos de vértices: Vértices visitados: vértices ya visitados en el recorridos Vértices frontera: vértices que aun no ha sido visitados pero están conectados con algún vértice visitado (están pendientes de visitar). Al igual que un árbol (de hecho, un árbol es un tipo de grafo orientado sin ciclos), un grafo puede ser recorrido en profundidad o en amplitud. Existen dos diferencias fundamentales a la hora de recorrer un grafo respecto de un árbol: a)

b)

5.4.1.

Puesto que un árbol es un grafo orientado sin circuitos, al avanzar en el recorrido no cabe la posibilidad de que se vuelva a visitar un vértice ya visitado. En el recorrido de un grafo sí cabe la posibilidad de al avanzar visitar un vértice ya visitado. Se deberá implementar algún mecanismo que evite esta situación. Partiendo de la raíz de un árbol se pueden visitar todos los vértices, mientras que en un grafo se puede dar la posibilidad de que no se alcancen todos los vértices desde un vértice. Habría que comenzar el recorrido en otro vértice para poder alcanzar todos los vértices.

Recorrido en profundidad

En el recorrido en profundidad, se da preferencia a visitar a los vértices conectados con el último visitado. Dado un grafo G, en el que inicialmente ningún vértice ha sido visitado, el recorrido en profundidad selecciona un vértice v de G como vértice inicial, que se marca como visitado. Entonces, se busca un vértice no visitado adyacente a v, w, que se marca como visitado y se selecciona como vértice inicial para reiniciar el recorrido. Una vez que se han visitado todos los vértices alcanzables de w se vuelve a v y se selecciona un nuevo vértice no visitado. Cuando se han visitado todos los vértices alcanzables desde v, se da por terminado el recorrido de v. Si quedan vértices por visitar, se selecciona uno de ellos como nuevo vértice de partida y se reproduce todo el proceso. Es decir: Sea un grafo G y un vértice v que pertenece a G, marcar v como visitado mientras queden vértices sin visitar hacer seleccionar un vértice no visitado, v, avanzarEnProfundidad a partir de v fin mientras

Donde avanzarEnProfundidad consiste en: marcar el vértice v como visitado seleccionar un vértice adyacente a v no visitado, w avanzar en profundidad a partir de w.


GRAFOS 193

Por ejemplo, sea el siguiente grafo G: 2 5 1

Figura 5.14.

3

4

Ejemplo de grafo

Se toma como vértice inicial 1, v1 ← visitado (el conjunto de vértices adyacentes a v1 es 2,3) Se toma vértice 2: v2 ← visitado (el conjunto de vértices adyacentes a v2 es 3,4) Se toma vértice 3 v3 ← visitado (el conjunto de vértices adyacentes a v3 es 1) //v1 ya está visitado por lo que se termina el recorrido en profundidad a partir del vértice 3.

Se toma el vértice 4 v4 ← visitado (el conjunto de vértices adyacentes a v4 es 3) //v3 ya está visitado por lo que se termina el recorrido en profundidad a partir del vértice 4. //v3 ya está visitado por lo que termina el recorrido en profundidad a partir del vértice 3.

No es posible alcanzar más vértices desde v1, de manera que hay que seleccionar un nuevo vértice desde el que recomenzar la exploración en profundidad, se elige el vértice 5: v5 ← visitado (el conjunto de vértices adyacentes a v5 es 4) //v4 ya está visitado de manera que se termina el recorrido en profundidad a partir del vértice 5

--- FIN---

El algoritmo de recorrido en profundidad cuenta con una parte recursiva que recorre parcialmente un subgrafo a partir de un vértice de inicio y una parte no recursiva que se encarga de relanzar el proceso en cada vértice no visitado. Se utiliza además un vector de valores lógicos para marcar los vértices visitados. Se utilizan los índices de los vértices para iniciar y marcar el proceso de recorrido. El código en Java para un recorrido en profundidad es el siguiente: //procedimiento recursivo public void recorrerProfundidad (Grafo g, int v, boolean [ ] visitados) { //se marca el vértice v como visitado visitados [v] = true; //el tratamiento del vértice consiste únicamente en imprimirlo en pantalla System.out.println (v); //se examinan los vértices adyacentes a v para continuar el recorrido for (int i = 0; i < g.numVertices; i++) { if ((v != i) && (!visitados [i]) && (g.existeArista (v, i)) ) recorrerProfundidad (g, i, visitados); } } //procedimiento no recursivo public void profundidad (Grafo g) { boolean visitados [ ] = new boolean [g.numVertices];

194 GRAFOS


for (int i = 0; i < g.numVertices; i++) //inicializar vector con campos false visitados [i] = false; for (int i = 0; i < g.numVertices; i++) { //Relanza el recorrido en cada if (!visitados [i]) //vértice visitado recorrerProfundidad (g, i, visitados); } }

5.4.2.

En amplitud

En un recorrido en amplitud, se elige un vértice no visitado v, como punto de partida y se pasa a visitar cada uno de sus vértices adyacentes, para continuar posteriormente visitando los adyacentes a estos últimos y así sucesivamente hasta que no se puedan alcanzar más vértices. Si queda algún vértice sin visitar, se selecciona y se vuelve a relanzar el proceso. Para realizar un recorrido en amplitud de un grafo es necesario utilizar una estructura de datos cola (cf. el recorrido en amplitud de la clase árbol). En la cola se van almacenando los vértices a medida que se llega a ellos. Los vértices se marcan en la cola como visitados y son tratados cuando se extraen de la cola al tiempo que se introducen en la cola los adyacentes al vértice tratado. El código en Java para el recorrido en amplitud es el siguiente: public static void amplitud (Grafo g) { Cola cola = new Cola (); boolean visitados [ ] = new boolean [g.obtenerNumVertices()]; int v; //vértice actual //Se inicializa el vector visitados [] a false for (int i = 0; i < g.obtenerNumVertices (); i++) visitados [i] = false; //El recorrido en amplitud se inicia en cada vértice no visitado for (int i = 0; i < g.obtenerNumVertices (); i++) { //se pone en la cola el vértide de partida y se marca como visitado if (!visitados [i]){ cola.encolar (i); visitados [i] = true; while (!cola.estaVacia ()) { v = cola.desencolar (); //desencolar y tratar el vértice System.out.println (v); //y encolo los nodos adyacentes a v. for (int j = 0; j < g.obtenerNumVertices (); j++){ if ((v !=j) && (g.existeArista (v, j) && (!visitados [j])) { cola.encolar ( j ); visitados [j] = true; } } } } } }


GRAFOS 195

TEMA 5 .................................................................................................................... 173 5.1.

definición de grafo...................................................................................... 173

5.2.

terminología y conceptos............................................................................ 175

5.2.1.

Grafos dirigidos y no dirigidos ........................................................... 175

5.2.2.

Incidencia, adyacencia y grado de un vértice ..................................... 175

5.2.3.

Grafos simples y multigrafos ............................................................. 176

5.2.4.

Camino, bucle y ciclo ......................................................................... 177

5.2.5.

Grafos conexos ................................................................................... 178

5.2.6.

Grafos valorados y grafos etiquetados ............................................... 179

5.3.

Implementaciones de Grafos ...................................................................... 180

5.3.1.

Interfaz del TAD Grafo. ..................................................................... 180

5.3.2.

Matriz de adyacencias ........................................................................ 181

5.3.3.

Lista de adyacencias ........................................................................... 186

5.3.4. Consideraciones sobre la implementación del grafo como matriz o como lista de adyacencias .......................................................................................... 191 5.4.

Recorridos de grafos ................................................................................... 192

5.4.1.

Recorrido en profundidad ................................................................... 192

5.4.2.

En amplitud ........................................................................................ 194

Estructura De Datos 376b3d

Overview 26281t

More details 6y5l6z

Related Documents 3h463d

Estructura De Datos Wikipedia) 2m6y3m

Practica Estructura De Datos 1zh3c

Estructura De Datos Antologia 1n4850

Estructura De Datos 376b3d

Estructura De Datos 1 101m6w

Estructura De Datos 376b3d

More Documents from "Nilas Arcanister" 633e3a

Estructura De Datos 376b3d

Un Medico Rural - Analisis 1q2nj

Algoritmo Sjf 1u6v3b

4p345f

Linea De Tiempo De La Historia De Internet 3v251h

Core Java Interview Questions List_ Part I - Dzone Java 2f4g5l