Download Implemente en el lenguaje de programación Java la clase publica

GH)HEUHURGH)XQGDPHQWRVGH7HOHPiWLFD
ÈUHDGH,QJHQLHUtD7HOHPiWLFD
'HSDUWDPHQWRGH,QJHQLHUtDGH6LVWHPDV\$XWRPiWLFD
(VFXHOD6XSHULRUGH,QJHQLHURV
8QLYHUVLGDGGH6HYLOOD
(MHUFLFLR3DUWH,SXQWRV
Implemente en el lenguaje de programación Java la clase publica
1RGR
, en el paquete
)HE
,
que contenga cinco atributos privados, cuatro del tipo 1RGR, con los siguientes identificadores:
SDGUH, KHUPDQR, SULPHU+LMR y VHFXHQFLD; y un atributo del tipo LQW con el identificador
LQIRUPDFLRQ. Una representa gráfica de los atributos de la clase 1RGR se muestra la Figura a). La
clase debe contener un único constructor público que configure el atributo LQIRUPDFLRQ.
Implementar los métodos JHW y VHW para todos los atributos mencionados.
(MHUFLFLR3DUWH,,SXQWRV
Un árbol es un tipo abstracto de datos que almacena elementos de forma jerárquica. Cada
elemento de un árbol tiene un elemento padre y cero o más elementos hijos, a excepción del elemento
de mayor nivel que es único en la representación del árbol y no tiene padre (este elemento se conoce
como raíz del árbol). Aplicándole una terminología, un árbol T es un conjunto de nodos que almacenan
elementos en una relación padre-hijo con las siguientes propiedades:
•
•
•
T tiene un nodo distinguido r, llamado raíz de T, que no tiene padre.
Cada nodo u de T distinto de r tiene un nodo padre v.
Para cada nodo u de T, la raíz r es un ascendente de u. (Una definición precisa de ascendente
puede ser formulada mediante recursividad. Un ascendente de un nodo es el nodo padre o un
ascendente del nodo padre).
Si el nodo v es el padre del nodo u, entonces se puede decir que u es un hijo de v. Si dos nodos son
hijos de un mismo padre entonces son hermanos. Un subárbol de T con raíz en el nodo u es el árbol
que consiste en todos los descendentes de u en T (incluyéndose al propio u). Todo esto puede verse en
la Figura b), donde aparece un árbol con nodos, el padre, hermano e hijo del nodo marcado.
Un árbol está ordenado si hay una ordenación lineal definida para los hijos de cada nodo de tal
forma que se identifica el hijo del nodo como el primero, segundo, tercero, y los demás. Esta
ordenación está determinada por el uso que se desea realizar del árbol, y se indica en el dibujo del
árbol. Los árboles ordenados normalmente indican la relación de orden lineal existente entre los
hermanos listándolos en una secuencia o enumeración en un orden exacto.
La Figura c) muestra la construcción de un árbol ordenado con nodos de la clase
1RGR
,
estableciendo las relaciones padre-hijo-hermano de un 1RGR.
Para mantener el criterio de ordenación que representa un árbol se utiliza además el campo
VHFXHQFLD. Este campo ordena primero el padre, luego el primer hijo (aplicado de forma recursiva
para todo el subárbol), luego el primer hermano (aplicado de forma recursiva para todo el subárbol),
hasta recoger todos los nodos del árbol. Para el árbol representado en la )LJXUD F la ordenación que
mantiene el campo VHFXHQFLD, se representa en la )LJXUDG.
a)Atributos privados
de la clase Nodo
informacion
padre
hemano
primerHijo
secuencia
b)Ejemplo de arbol
padre
del
nodo u
raíz (r)
c) Árbol ordenado con nodos
de la clase Nodo
hermano
del
nodo u
nodo u
Hijo del
nodo u
d) Árbol ordenado
con nodos
de la clase Nodo
Se proporciona parte del código de la clase $UERO, en el paquete
atributos privados: UDL], VHFXHQFLD, y QXP(OHPHQWRV.
)HE
!
(campo secuencia de Nodo)
Esta clase contiene tres
SDFNDJH)HE
LPSRUW)HE1RGR
SXEOLFFODVV$UERO^
SULYDWH1RGRUDL]
QXOO
SULYDWH1RGRVHFXHQFLD
QXOO
SULYDWHLQWQXP(OHPHQWRV
SXEOLF$UERO^`
SXEOLF1RGRJHW5DL]^&RGLJR`
SXEOLFLQWJHW1XP(OHPHQWV^&RGLJR`
SXEOLF1RGRJHW8OWLPR+HUPDQR1RGRSDGUH/RF^&RGLJR`
SXEOLFERROHDQWLHQH5DL]^&RGLJR`
SXEOLFERROHDQWLHQH3ULPHU+LMR1RGRQRGR^&RGLJR`
SXEOLFERROHDQWLHQH+HUPDQR1RGRQRGR^&RGLJR`
SXEOLFYRLGLQVHUWD5DL]1RGRQXHYR^&RGLJR`
SXEOLFYRLGLQVHUWD+HUPDQR1RGRKHUPDQR1RGRQXHYR^
&RGLJR`
SXEOLFYRLGLQVHUW1RGRSDGUH1RGRQXHYR^
&RGLJR`
`
Implemente el código de los métodos que aparecen en la clase de arriba parcialmente
implementados.
• JHW5DL]Devuelve el nodo raíz del árbol.
• JHW1XP(OHPHQWVDevuelve el número de elementos en el árbol.
• JHW8OWLPR+HUPDQRDevuelve la referencia al último hermano. Se le proporciona la
referencia al padre.
• WLHQH5DL]Devuelve WUXH si el árbol tiene un nodo raíz. En otro caso IDOVH.
• WLHQH3ULPHU+LMRDevuelve WUXH si el nodo que se le pasa como parámetro tiene un
hijo. En otro caso IDOVH.
• WLHQH+HUPDQRDevuelve WUXH si el nodo que se le pasa como parámetro tiene un
hermano. En otro caso IDOVH.
• LQVHUWD5DL]Inserta un nodo como raíz del árbol.
• LQVHUWD+HUPDQRInserta un nodo como hermano del nodo que se pasa como
parámetro.
• LQVHUWInserta un nodo como el último de los hijos del nodo que se pasa como
parámetro.
Página-2
(MHUFLFLRSXQWRV
Una forma de usar los hilos en Java es con los métodos ZDLW y QRWLI\ que son parte de la
clase 2EMHFW. Cada instancia y cada clase potencialmente tienen un monitor asociado con él. Se
presenta un programa con 3 clases: 3LQJ3RQJ, -XJDGRU y -XHJR. El programa crea dos hilos
con la clase -XJDGRU. El método PDLQ, aparece en la clase -XHJR. Un objeto de la clase
3LQJ3RQJ es utilizado por los dos hilos creados. Las clases están parcialmente implementadas y se
deberá rellenar los huecos para que la ejecución del programa sea la que se indica. El ejercicio se
contesta sobre el enunciado.
La primera clase llamada 3LQJ3RQJ consta de un único método sincronizado y una variable de
estado. El método es JROSHDU y el único parámetro que toma es el nombre del jugador. El
algoritmo que realiza es el siguiente:
$OJRULWPR
6DOLGDGHOSURJUDPD
6,
3,1*$OLFLD
este mi turno,
Comprobar cual es el siguiente turno,
Realizar el PING
Y notificarlo al que esté esperando.
3,1*ERE
3,1*DOLFLD
3,1*ERE
3,1*DOLFLD
Se declara una variable de estado TXLHQ-XHJD. Esta es declarada privada ya que los usuarios de la
clase no necesitan conocerla. El método debe ser sincronizado (public synchronized
boolean JROSHDU(String oponente)) para poder llamar de forma apropiada a ZDLW().
SXEOLFFODVV3LQJ3RQJ^
SULYDWH6WULQJTXLHQ-XHJD
QXOO
// identifica el turno.
SXEOLFV\QFKURQL]HGERROHDQJROSHDU6WULQJRSRQHQWH^
6WULQJ[
7KUHDGFXUUHQW7KUHDGJHW1DPH
LITXLHQ-XHJD
/*Nombre del propio hilo*/
/* Aquí se resuelve quien juega antes */
[/* puede ser cualquiera
*/
QXOO^
TXLHQ-XHJD
UHWXUQWUXH
`
LITXLHQ-XHJDFRPSDUH7R+(&+2
^
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
`
LIRSRQHQWHFRPSDUH7R+(&+2
^
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
`
/*
*
*
*
El "if" es cuando le toca al hilo actual.
Se ejecuta, actualiza el estado y devuelve el turno.
Luego notify() se llama para despertar al hilo
que está esperando la ejecución sobre este objeto. */
LI[FRPSDUH7RTXLHQ-XHJD
^
6\VWHPRXWSULQWOQ3,1*[
TXLHQ-XHJD
RSRQHQWH
QRWLI\
WU\^
ZDLW
`FDWFK,QWHUUXSWHG([FHSWLRQH^`
`
UHWXUQWUXH
// continua jugando.
`
`
Página-3
La implementación de los dos hilos se realiza con la clase -XJDGRU. Su código se presenta a
continuación.
SXEOLFFODVV-XJDGRULPSOHPHQWV5XQQDEOH^
SULYDWH3LQJ3RQJPL7DEOD7DEODGRQGHMXHJD
SULYDWH6WULQJPL2SRQHQWH
SXEOLF-XJDGRU6WULQJRSRQHQWH3LQJ3RQJWDEOD^
PL7DEOD
WDEOD
PL2SRQHQWH
RSRQHQWH
`
SXEOLFYRLGUXQ^
ZKLOHBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
`
`
SXEOLFFODVV-XHJR^
SXEOLFVWDWLFYRLGPDLQ6WULQJDUJV>@^
3LQJ3RQJWDEOD
QHZ3LQJ3RQJ
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
DOLFLDVHW1DPHDOLFLD
EREVHW1DPHERE
DOLFLDVWDUW
EREVWDUW
WU\^
/* Espera 5 segundos */
7KUHDGFXUUHQW7KUHDGVOHHS
`FDWFK,QWHUUXSWHG([FHSWLRQH^`
/*Hace que los jugadores salgan de sus hilos*/
BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
WU\^
7KUHDGFXUUHQW7KUHDGVOHHS
`FDWFK,QWHUUXSWHG([FHSWLRQH^`
`
`
Método de interés:
7KUHDG
7KUHDG
7KUHDG
7KUHDG
()
(Runnable target)
(Runnable target, String name)
(String name)
int FRPSDUH7R(String anotherString)
Método de la clase 6WULQJ.Compara dos 6WULQJ de forma
lexicográfica. El resultado es cero si son iguales. Distinto de
cero en otro caso.
Página-4
(MHUFLFLR3DUWH,
package Feb07;
public class Nodo{
private int informacion;
private
private
private
private
Nodo
Nodo
Nodo
Nodo
padre
hermano
primerHijo
todoEnSecuencia
=
=
=
=
null;
null;
null;
null;
public Nodo(int valor){
this.informacion = valor;
}
public void setPadre(Nodo padre){
this.padre = padre;
}
public Nodo getPadre( ){
return padre;
}
public void setHermano(Nodo hermano){
this.hermano = hermano;
}
public Nodo getHermano( ){
return hermano;
}
public void setPrimerHijo(Nodo nodo){
this.primerHijo = nodo;
}
public Nodo getPrimerHijo( ){
return this.primerHijo;
}
public int getInformacion(){
return this.informacion;
}
public void setSecuencia(Nodo seq){
this.todoEnSecuencia = seq;
}
public Nodo getSecuencia( ){
return this.todoEnSecuencia ;
}
}
Página-5
(MHUFLFLR3DUWH,,
package Feb07;
import Feb07.Nodo;
public class Arbol{
private Nodo raiz
= null;
private Nodo secuencia
= null;
private int numElementos =
0;
public Arbol(){}
public
public
public
public
public
Nodo getRaiz
(
){ return this.raiz;
}
boolean tieneRaiz
(
){ return (getRaiz() != null) }
int getNumElements
(
){ return this.numElementos; }
boolean tienePrimerHijo(Nodo nodo){ return (nodo.getPrimerHijo() != null); }
boolean tieneHermano(Nodo nodo){ return (nodo.getHermano() != null); }
public void InsertaRaiz ( Nodo nuevo ){
this.raiz
= nuevo;
this.secuencia = nuevo;
nuevo.setPadre(null);
/* El padre es null(no tiene) */
}
public void InsertaHermano (
nuevo.setSecuencia (
hermano.setSecuencia(
hermano.setHermano (
nuevo.setPadre
(
}
Nodo hermano, Nodo nuevo
hermano.getSecuencia()
nuevo
nuevo
hermano.getPadre()
){ /* Inserta un nodo a continuación */
); /* Se enlaza en la lista
*/
);
);
);
/* se le proporciona la referencia al padre y devuelve el elemento al que insertarle el nodo*/
public Nodo getUltimoHermano(Nodo padreLocal){
while(tieneHermano(padreLocal))
padreLocal = padreLocal.getHermano();
return padreLocal;
}
public void insert ( Nodo padre, Nodo nuevo ){
Nodo auxiliar = padre;
numElementos++;
if(tieneRaiz () && padre == null){ /* Es el nodo raiz
*/
this.InsertaRaiz( nuevo );
}else if( padre != null
){
/* El nodo tiene hijos
*/
if(tienePrimerHijo(padre)){
auxiliar = getUltimoHermano(padre);
}else{
padre.setPrimerHijo( nuevo );
}
InsertaHermano ( auxiliar , nuevo );
} else {
System.out.println("ERROR: Existe el arbol y la ref. al padre es null");
}
}
void imprimeSecuencia(){
Nodo auxiliar = this.secuencia ;
System.out.println("*********************************");
while(auxiliar != null){
System.out.println("---> "+auxiliar.getInformacion());
auxiliar = auxiliar.getSecuencia( ) ;
}
System.out.println("*********************************");
}
}
Página-6
package Feb07;
import Feb07.Nodo;
import Feb07.Arbol;
class Prueba{
public static void main(String args[]){
Arbol
Nodo
Nodo
Nodo
arbol
raiz
actual
aux
=
=
=
=
new Arbol ();
null;
null;
null;
aux
= new Nodo (1);
arbol.insert ( raiz, aux );
raiz
= aux;
aux
= new Nodo (2);
arbol.insert ( raiz , aux );
for (int i = 3 ; i < 6 ; i++){
arbol.insert ( raiz , new Nodo(i) );
}
for (int i = 20 ; i < 25 ; i++){
arbol.insert (raiz.getPrimerHijo() , new Nodo(i));
}
arbol.imprimeSecuencia();
System.out.println("Numero de Elementos = " + arbol.getNumElements
}
}
Página-7
());
(MHUFLFLR
public class PingPong {
private String quienJuega = null; // identifica quien tiene el turno.
public synchronized boolean golpear(String oponente) {
String x = Thread.currentThread().getName();
/* Nombre del propio hilo.
*/
if (quienJuega == null) { /* Aquí se resuelve quien juega antes */
quienJuega = x;
/* puede ser cualquiera
*/
return true;
}
if(quienJuega.compareTo("HECHO") == 0){
return false;
}
if(oponente.compareTo("HECHO") == 0){
quienJuega = oponente;
notify();
return false;
}
/*
*
*
*
*/
El "if" es cuando le toca al hilo actual.
Se ejecuta, actualiza el estado y devuelve el turno.
Luego notify() se llama para despertar al hilo
que está esperando la ejecución sobre este objeto.
if (x.compareTo(quienJuega ) == 0) {
System.out.println("PING! ("+x+")");
quienJuega = oponente;
notify();
try {
wait();
} catch (InterruptedException e) { }
}
return true; // continua jugando.
}
}
Página-8
public class Juego {
public static void main(String args[]){
PingPong tabla
Runnable Alicia
Runnable Bob
Thread alicia
Thread bob
=
=
=
=
=
new
new
new
new
new
PingPong
Jugador
Jugador
Thread
Thread
(
(
(
(
(
);
"bob"
,tabla );
"alicia" ,tabla );
Alicia
);
Bob
);
alicia.setName( "alicia" );
bob.setName( "bob" );
alicia.start( );
bob.start( );
try{
/* Espera 50 segundos */
Thread.currentThread().sleep(50);
}catch(InterruptedException e){}
tabla.golpear("HECHO"); /*Hace que los jugadores salgan de sus hilos*/
try{
Thread.currentThread().sleep(100);
}catch(InterruptedException e){}
}
}
public class Jugador implements Runnable{
private PingPong miTabla; //Tabla donde juega
private String miOponente;
public Jugador (String oponente, PingPong tabla){
miTabla
= tabla;
miOponente = oponente;
}
public void run(){
while(miTabla.golpear(miOponente))
;
}
}
Página-9