Enunciat
Se desea implementar una guía telefónica. Cada abonado es identificado por un String (su nombre).
La guía telefónica se ha de implementar usando una clase llamada Guía. Esto es, la práctica ha de tener una
clase:
public class Guia
{ /* implementación de la guía telefónica */}
Esta clase ha de incluir las siguientes operaciones
void crear_g ()
{/* código de crear_g */}
void incluir (String X, int N)
{/* código de incluir */}
void baja(String X)
{/* código de baja */}
int consulta (String X)
{/* código de consulta */}
void listar()
{/* código de listar */}
En concreto, la operación crear_g ha de crear la guía vacía.
La operación incluir, dado un abonado X y un número de teléfono N, añade X a la guía con el número de
t eléfono N. Si X ya estuviera en la guía, entonces substituye su número de teléfono viejo por N.
La operación baja, dado un abonado X, lo suprime de la guía. Si el abonado no se encontrara en la guía, se
escribirá: "No hay ningún abonado llamado así".
La operación consulta, dado un abonado X, nos devuelve su número de teléfono. Si X no estuviera en la
guía, entonces se devuelve el valor -1.
Por último, la operación listar escribe la lista de todos los abonados, junto sus teléfonos, por orden
alfabético.
La guía se ha de implementar por medio de una tabla con hash encadenado. Adicionalmente, todos los nodos
de la tabla estarán encadenados entre sí, formando una lista ordenada de abonados.
La práctica ha de contener, como comentarios, la especificación de la guía, de su implementación y la
justificación de su corrección. Además, las declaraciones de las clases, atributos métodos que se realicen
deben de incluir el atributo de visibilidad (public, private, etc) que se considere adecuado.
Sol·lució:
Nota: la sol·lució té diversos errors.
/**
*
*Nota: Se asume que el abonado PEDRO es diferente al abonado Pedro. Si se
* quiere hacer que estos abonados se comporten como uno se puede usar la
* función estándar "toLower" de Java para no distinguir entre mayúsculas y
* minúsculas.
*
*especificación guia
*tipos guia, nat
*operaciones
*crear_g: -> guia
*incluir: string x nat -> guia
*baja: string ->guia
*consulta: string -> nat
*listar: -> guia
*axiomas
*incluir(incluir(g,X,n),X,m) = incluir(g,X,m)
*incluir(incluir(g,X,n),Y,m) = incluir(incluir(g, Y,m),X,n)
*baja(incluir(g,X,n),X)= g
*consulta(crear_g,X)=-1
*consulta(incluir(g, X, n),X)=n
*X<>Y=> consulta(incluir(g,X,n),Y) = consulta(g,Y)
*listar(crear_g) = vacio
*fespecificación
*
*Clase nodo
*indice: string;
*valor: nat;
*sig: ^nodo;//Este nodo apunta al siguiente de la misma casilla de la tabla.
*alfasig: ^nodo;
*alfaant: ^nodo;//Estos nodos crean una lista doblemente encadenada de todos
* //los nodos. No tendría sentido hacer un encadenamiento simple
* //ya que entonces en la operación baja no podríamos aprovechar
* //las características de las tablas de hash (velocidad para
* //encontrar un elemento).
*fClase
*
*Clase guia
*acción crear_g(sal g: guia);
*acción incluir (ent/sal g: guia; ent X: string, N:nat);
*acción baja(ent/sal g: guia; ent X: string);
*función consulta (ent/sal g: guia; ent X: string) retorna h: nat;
*acción listar (ent g: guia);
*
*Implementación
*t: tabla [1:N] de ^nodo
*NUM: nat //Este número determina el tamaño de la tabla. Deber ser primo por la
* //función de hash usada.
*acceso: ^nodo //Acceso al primer elemento de la lista doblemente enlazada de
* //todos los nodos ordenada alfabéticamente.
*
*acción crear_g(sal g: guia);
*Pre: cierto
*Post: t contiene sólo accesos a nodos vacíos;
*var j: nat;
*para j:= 1 a N hacer g.t[j]:= nil;
*fpara
*f_acción
*
*acción incluir (ent/sal g: guia; ent X: string, N:nat);
*Pre: cierto
*Post: Si el abonado ya estaba en la tabla, se ha cambiado a N su número de
*teléfono; si no estaba, se incluye X en g.t con indice X y número de teléfono
*X. Además, se actualiza el valor de acceso si es necesario y se enlaza el
*nodo con su anterior y posterior alfabéticamente.
*var i: nat;b,existe:bool;bs,actual,z,posicion: ^nodo;
*i=Hash(X);
*new(bs);
*bs = g.t[i];
*
* Inv: {(existe=>bs^.indice = X)}
*
* mientras existe <> verdadero y bs <> nil hacer
* si bs^.indice = verdadero entonces
* existe:= verdadero;
* bs^.valor := N;//actualizo numero de telefono.
* sino bs^:=bs^.sig;
* fsi;
* fmientras;
* si no (existe) entonces
* z^.indice := X;
* z^.valor := N;
* z^.sig:=nil;
* si acceso <> nil entonces
* si ordenalfabetico(acceso^.indice, X)<=0 entonces
* new(actual);actual =acceso;
*
* Inv: {(b=>ordenalfabetico(bs^.indice.X) >0}
*
* mientras b = falso hacer
* si actual^.alfasig <> nil entonces
* si ordenalfabetico(actual^.alfasig^.indice,X)>0 entonces
* z^.alfasig := actual^.alfasig;z^.alfaant := actual;
* actual^.alfasig^.alfaant :=z; actual^.alfasig := z;
* b:=verdadero;
* sino actual = actual^.alfasig;
* fsi;
* sino
* z^.alfasig :=nil;
* z^.alfaant := actual;
* actual^.alfasig := z;
* b:=verdadero;
* fsi;
* fmientras;
* sino
* z^.alfaant := nil;
* z^.alfasig := acceso;
* acceso^.alfaant :=z;
* acceso := z;
* fsi;
* sino
* acceso := z;
* z^.alfasig = nil;
* z^.alfaant = nil;
* fsi;
* new(posicion);
* si g.t = nil entonces
* g.t[i]:=z;
* sino
* posicion := g.t[i];
*
* Inv{posicion <> nil}
*
* mientras posicion^.sig <>nil hacer
* posicion := posicion^.sig;
* fmientras;
* posicion^.sig := z;
* fsi;
*f_acción
*
*función ordenalfabetico(aa:string, bb: string) retorna d:nat;
*Pre: cierto
*Post:d < 0 si en orden alfabético aa precede a bb; d = 0 si en orden alfabético
* aa equivale a bb; d>0 si en orden alfabético bb precede a aa;
*ffunción
*
*acción baja(ent/sal g: guia; ent X: string);
*Pre:cierto
*Post: g es la guía sin el nodo correspondiente a la persona con nombre X, si
* el abonado X no estaba en la guía, se imprime un mensaje por pantalla.
*var i: nat;b : bool; actual, anterior: ^nodo;
*b := falso;
*i:=Hash(X);
*new(actual);
*new(anterior);
*actual := g.t[i];
*
* Inv: {(b=>actual^.indice = X)}
*
* mientras b <> cierto y actual <> nil
* si actual^.indice = X entonces
* b:=cierto;
* si actual = acceso entonces acceso := actual^.alfasig;
* si actual^.alfaant <> nil entonces actual^.alfaant^.alfasig = actual^.alfasig;
* si actual^.alfasig <> nil entonces actual^.alfasig^.alfaant = actual^.alfaant;
* si actual^.sig = nil y anterior = nil entonces
* g.t[i]:=nil;
* sino
* si anterior <> nil entonces
* anterior^.sig := actual^.sig;
* sino g.t[i] :=actual^.sig;
* fsi;
* fsi;
* sino
* anterior := actual;
* actual :=actual^.sig;
* fsi;
* fmientras;
* si b <> cierto entonces imprimir("No hay ningún abonado llamado así");
*facción
*
*función consulta (ent/sal g: guia; ent X: string) retorna h: nat;
*Pre: cierto
*Post: si X pertenece a g h = número de teléfono del abonado X, sino h=-1
*
*var i: nat; h: entero; b : bool; actual: ^nodo;
*h := -1;
*b = falso;
*i=Hash(X);
*new(actual);
*actual = g.t[i];
*
* Inv: {(b=>actual^.indice = X)}
*
* mientras b <> cierto y actual <> nil hacer
* si actual^.indice = X entonces
* b:= cierto;
* h:= actual^.valor;
* sino actual:= actual^.sig;
* fsi;
*fmientras;
*retorna h;
*ffunción
*
*acción listar (ent g: guia);
*Pre:cierto
*Post: Se imprime la lista de todos los abonados de la guia a con su nombre y su teléfono.
*var actual: ^nodo;
*new(actual);
*actual =acceso;
* mientras actual <> nil hacer
* imprimir(actual^.indice + " " + actual^.valor);
* actual = actual^.alfasig;
* fmientras;
*facción
*
*función hash (ent a:nat) retorna p: nat;
*Pre: cierto
*Post:1 <= p <= N.
*ffunción
*
*Justificación de la implementación:
*
*Invariante de la representación:
*Para cada j (1<=j<= NUM), g.t[j] apunta a una lista de nodos que cumplen que
* su campo índice y valor son no nulos; y si a es el contenido del campo indice
* de un nodo de la lista, entonces:
*1) a no aparece repetido en otro nodo de la lista (las variaciones de
* mayúsculas se consideran que hacen que a sea diferente) (ver nota inicial)
*2) hash(a)=j.
*
*g.NUM contiene el tamaño de la tabla. NUM tiene que ser primo.
*
*g.acceso contiene una referencia al nodo primero de una lista doblemente
* encadenada no circular que une a todos los nodos.
*
*Para ver que el invariante siempre se cumple; después de inicializar la guia,
*para cada j (1<=j<=NUM), i.t[j] apunta a una lsita vacía que, obviamente,
*cumple las condiciones que se dan en el invariante. Por otra parte, g.acceso
*apunta a un nodo nulo ya que no hay ningún nodo y, por tanto, no podemos poner
*ninguna referencia que sea no nula en él.
*
*Si suponemos que el invariante se cumple antes de realizar una inclusión, de
* acuerdo a la postcondición, después de realizarla tenemos que:
*1) Si el abonado estaba en la guía, actualizar el teléfono.
*
*2) Si no lo estaba, añadirlo como elemento a la lista apuntada por
* g.t[HASH(a)]. Además si hay más de un nodo, éste se encadena doblemente con
* el anterior y posterior a éste en orden alfabético si es que existen.
*
*3) El nodo acceso se actualiza para que apunte al nodo actual si éste es el
* primero en orden alfabético. Si no, no se cambia. Así pues sigue apuntando al
* primer nodo en orden alfabético.
*
*Equivalencia de la representación
*
*Dos guías g1 y g2 son equivalentes, g1=g2 si para todo j (1<=j<=NUM), g1.t[j]
*y g2.t[j] contienen los mismos índices (abonados) con los mismos valores
* (teléfonos)
*
*Finalmente, podemos ver que la implementación cumple los axiomas de la
* especificación:
*
*incluir(incluir(g,X,n),X,m) = incluir(g,X,m)
*
*Si incluimos un abonado X con telefono n y incluimos el mismo abonado X con
*telefono Y, la postcondición de incluir dice que se actualizará el teléfono
*por lo que será como si hubieésemos inicialmente incluido el abonado X con
*el teléfono m.
*
*incluir(incluir(g,X,n),Y,m) = incluir(incluir(g, Y,m),X,n)
*
*Si incluimnos un abonado X con telefono n y luego Y con telefono m, lo más que
*nos puede ocurrir es que los nodos correspondientes a los dos abonados
*aparezcan en las listas correspondientes en distinto orden, pero de acuerdo
*con la definición los dos inventarios serían equivalentes.
*
*baja(incluir(g,X,n),X)= g
*
*Si damos de baja a un abonado que acabamos de incluir, de acuerdo con la
*postcondición de la acción baja, eliminamos el nodo de la lista de la casilla
*de la tabla por lo que es como si no hubiéramos hecho nada a la guia.
*
*consulta(crear_g,X)=-1
*
*Si consultamos un abonado inexistente en la guia, esta función, nos devolverá
*-1 de acuerdo con su postcondición.
*
*consulta(incluir(g, X, n),X)=n
*
*Si incluimos en la guia un abonado X con teléfono n y a continuación
*consultamos el teléfono del abonado, esta función, de acuerdo con su
*postcondicicón nos devolverá n.
*
*X<>Y=> consulta(incluir(g,X,n),Y) = consulta(g,Y)
*
*La consulta de un teléfono de un abonado es independiente a que, previamente,
*se haya incluido otro abonado.
*
*listar(crear_g) = vacio
*
*Si listamos los nodos que hay en una guía vacía recién creadaa, como no hay
* ningún nodo, no nos devolverá nada.
**/
public class Guia{ /* implementación de la guía telefónica */
private class nodo{
String indice;
int valor;
//lista dentro de posición de tabla
nodo sig;
//todos los nodos forman una lista doblemente encadenada
nodo alfasig;
nodo alfaant;
}
private static final int NUM = 3;
private nodo tabla[]= new nodo[NUM];
private nodo acceso = null;
public void crear_g ()
{/* código de crear_g */
int i;
for (i=0;i<NUM;i++)
{
tabla[i] = null;
}
}
public void incluir (String X, int N)
{/* código de incluir */
int i;
boolean b = false;
boolean existe = false;
i=Hash(X);
//Existe nodo??
nodo bs = new nodo();
bs = tabla[i];
while (existe != true && bs != null){
if (bs.indice.equals(X)){
existe= true;
bs.valor = N;//actualizo numero de telefono.
}else{
bs=bs.sig;
}
}
//No existe
if (existe != true){
nodo z = new nodo();
z.indice = X;
z.valor = N;
z.sig=null;
if (acceso != null){
if (acceso.indice.compareToIgnoreCase (X)<=0){
nodo actual = new nodo();
actual =acceso;
while (b != true){
if (actual.alfasig != null){
if (actual.alfasig.indice.compareToIgnoreCase(X)>0){//caso en medio
z.alfasig = actual.alfasig;
z.alfaant = actual;//added
actual.alfasig.alfaant =z;
actual.alfasig = z;
b=true;
}else{
actual = actual.alfasig;
}
}else{//caso al final de todo
z.alfasig=null;
z.alfaant= actual; //added
actual.alfasig = z;
b=true;
}
}//fin bucle
}else{//caso al principio de todo
z.alfaant = null;//added
z.alfasig = acceso;
acceso.alfaant =z;
acceso = z;
}
}else{//acceso == null//caso es el único
acceso = z;
z.alfasig = null;
z.alfaant = null;//added
}
//guardar nodo en tabla
nodo posicion = new nodo();
if (tabla[i]==null){ //ok, posición no ocupada
tabla[i]=z;
} else{//posición ya ocupada
//nodo anterior = new nodo();
posicion = tabla[i];
while (posicion.sig != null){
posicion = posicion.sig;
}
posicion.sig = z;
}
}
}
public void baja(String X)
{/* código de baja */
int i;
boolean b = false;
i=Hash(X);
nodo actual = new nodo();
nodo anterior = new nodo();
anterior = null;
actual = tabla[i];
while (b != true && actual != null){
if (actual.indice.equals(X)){//abonado encontrado
b=true;
if (actual == acceso)acceso = actual.alfasig;//Por si se elimina el nodo acceso.
if (actual.alfaant !=null)actual.alfaant.alfasig = actual.alfasig;
if (actual.alfasig != null)actual.alfasig.alfaant = actual.alfaant;
if (actual.sig ==null && anterior ==null)//sólo hay un nodo
{
tabla[i]=null;
}else{//hay más de un nodo
if (anterior != null){
anterior.sig = actual.sig;
}else{
tabla[i]=actual.sig;
}
}
}else{
anterior = actual;
actual=actual.sig;
}
}
if (b !=true)System.out.println("No hay ningún abonado llamado así");
}
public int consulta (String X)
{/* código de consulta */
int i;
int h = -1;
boolean b = false;
i=Hash(X);
nodo actual = new nodo();
actual = tabla[i];
while (b != true && actual != null){
if (actual.indice.equals(X)){
b= true;
h= actual.valor;
}else{
actual=actual.sig;
}
}
return h;
}
public void listar()
{/* código de listar */
nodo actual = new nodo();
actual =acceso;
while (actual !=null)
{
System.out.println(actual.indice + " " + actual.valor);
actual = actual.alfasig;
}
}
private int Hash(String Clave)
{
int valor = Clave.charAt(0);
int tam = Clave.length();
for (int i = 1; i < tam ;i++) {
valor += Character.getNumericValue( Clave.charAt(i));
}
return (valor % NUM);
}
}