Analisis Dafo google

1o Ingenier´ Inform´tica
ıa
a
o
1 Matem´tica Computacional
a
EI1008/MT1008 Programaci´n II
o
M´dulo 3: Estructuras de datos b´sicas con memoria din´mica
o
a
a
Ejercicio 1
Considera la siguiente interfaz ListaCadenas:
package modulo3;
public interface ListaCadenas {
boolean add(String s);
void add(int i, String s);
void clear();
String get(int i);
int indexOf(String s);
intlastIndexOf(String s);
boolean isEmpty();
String remove(int i);
boolean remove(String s);
String set(int i, String s);
int size();
}
A continuaci´n, se describe el comportamiento de cada uno de los m´todos de la interfaz:
o
e
boolean add(String s);
A˜ade la cadena s al final de la lista. Devuelve como resultado true para indicar que la operaci´n se
n
o
realiz´ correctamente.
o
voidadd(int i, String s);
Inserta la cadena s en la posici´n i de la lista. El elemento en la posici´n dada (si existe) y todos
o
o
los siguientes quedan desplazados una posici´n a la derecha en la lista. Si la posici´n i no es v´lida
o
o
a
(i < 0 o i > size()), se debe lanzar la excepci´n IndexOutOfBoundsException.
o
void clear();
Elimina todos los elementos en la lista, es decir, la listaquedar´ vac´
a
ıa.
String get(int i);
Devuelve el elemento en la posici´n i. Si la posici´n i no es v´lida (i < 0 o i >= size()), se debe
o
o
a
lanzar la excepci´n IndexOutOfBoundsException.
o
int indexOf(String s);
Devuelve la posici´n de la primera ocurrencia de la cadena s en la lista o -1 si la cadena s no aparece
o
en la lista.
int lastIndexOf(String s);
Devuelve la posici´n dela ultima ocurrencia de la cadena s en la lista o -1 si la cadena s no aparece
o
´
en la lista.

2

Programaci´n II
o

boolean isEmpty();
Devuelve true si la lista no contiene elementos o false en caso contrario.
String remove(int i);
Elimina el elemento en la posici´n i de la lista. Los elementos posteriores quedan desplazados una
o
posici´n a la izquierda. Devuelve como resultadola cadena que se elimin´. Si la posici´n i no es v´lida
o
o
o
a
(i < 0 o i >= size()), se debe lanzar la excepci´n IndexOutOfBoundsException.
o
boolean remove(String s);
Elimina la primera ocurrencia de la cadena s en la lista, si esta existe. Si la cadena no aparece en la
lista, esta no se modifica. Devuelve un valor l´gico que indica si la lista ha sido modificada, es decir,
o
si se haborrado la cadena dada.
String set(int i, String s);
Sustituye la cadena en la posici´n i por la cadena s. Devuelve como resultado la cadena previa en la
o
posici´n indicada. Si la posici´n i no es v´lida (i < 0 o i >= size()), se debe lanzar la excepci´n
o
o
a
o
IndexOutOfBoundsException.
int size();
Devuelve la cantidad de elementos en la lista.
Escribe la claseListaCadenasEnlaceSimple que implemente1 la interfaz ListaCadenas. Para ello, debes utilizar nodos enlazados con s´lo un enlace al siguiente elemento. La lista debe tener como atributos
o
unicamente la talla y una referencia al primer nodo.
´
Expresa, empleando la notaci´n O, el coste temporal en el peor de los casos de cada uno de los m´todos
o
e
de la clase.
Para comprobar el correcto funcionamiento de tuclase puedes utilizar los programas de ejemplo que
tienes disponibles en el Aula Virtual de la asignatura.

Ejercicio 2
Escribe la clase ListaCadenasEnlaceDoble que implemente1 la interfaz ListaCadenas. Para ello, debes
utilizar nodos enlazados con enlaces a los elementos anterior y siguiente. La lista debe tener como atributos
unicamente la talla, una referencia al primer nodo y unareferencia al ultimo nodo.
´
´
Expresa, empleando la notaci´n O, el coste temporal en el peor de los casos de cada uno de los m´todos
o
e
de la clase. Compara estos resultados con los obtenidos en el ejercicio anterior.
Los programas de prueba del ejercicio anterior tambi´n deben funcionar en este caso.
e

Ejercicio 3
Un diccionario est´ compuesto por una serie de parejas clave–definici´n, de...