Estructuras de datos secuenciales.
1. Introducción. Tipos de datos secuenciales. Estructuras de datos secuenciales.
2. Secuencias de datos enlazados. La clase Nodo. Recorridos. Búsquedas. Inserción. Eliminación.
3. Representación de tipos de datos enlazados:
.-Pilas. Operaciones. Implementación con arrays. Implementación enlazada.
Comparación de implementaciones.
.- Colas. Operaciones. Implementación con arrays. Implementación enlazada.
Comparación de implementaciones.
.- Listas con punto de interés. Operaciones. Implementación con arrays.
Implementación enlazada. Comparación de implementaciones.
Introducción: Tipos de datos secuenciales.
• Los tipos de datos secuenciales son aquellos que sus elementos están formados por linealidades o secuencias
d0d1... dn-1
siendo n≥0, en los que los di son datos del mismo tipo, y sobre las que se pueden hacer operaciones de inserción y eliminación de datos, consulta del dato que ocupa una determinada posición, etc...
• Según la política de manipulación de los datos, se distinguen las tres estructuras de datos secuenciales que se presentan en el tema: pilas, colas y listas, cuyo uso resulta idóneo en una amplia variedad de aplicaciones informáticas.
Tipos de datos más comunes
Lineales:
Pilas
Colas
Listas
No lineales:
Árboles
Grafos
Se diferencian en la política de gestión de los datos.
Introducción. Tipos de datos lineales:
• El comportamiento temporal de las operaciones de un tipo de datos va a depender de cómo se implementen las operaciones, basándose en la representación o estructuración escogida de los datos.
• Estructura de datos: Es un tipo de datos con una representación de los datos determinada y la correspondiente implementación de las operaciones del tipo.
• En este tema se van a presentar las estructuras de datos lineales basadas en dos maneras alternativas de representar las secuencias (de enteros, por simplificar la exposición):
– Con arrays: PilaIntArray, ColaIntArray, ListaPIIntArray.
– Enlazada: PilaIntEnla, ColaIntEnla, ListaPIIntEnla.
• Este conjunto de clases puede constituir un primer ejemplo de librería de usuario, lineales, organizada como un paquete Java. Todas las clases han del paquete deben contener la declaración:
package lineales;
y estar incluidas en la misma carpeta lineales.
• Se puede dedicar un proyecto o carpeta, por ejemplo, libreriasAC, para contener este y otros paquetes de interés general:
libreriasAC
lineales
Pila
Cola
Lista
En BlueJ, se puede crear el paquete lineales dentro del proyecto
libreriasAC con la opción Edita>Nuevo Paquete.
• Para instalar estas librerías en el sistema, hay que añadir la ruta de libreriasAC en la variable de entorno del sistema CLASSPATH:
Cuando Java compila o ejecuta una clase busca los paquetes importados por la clase en las carpetas indicadas en CLASSPATH.
• Desde BlueJ, la variable CLASSPATH se modifica en la ventana desplegada por la opción Herramientas>Preferencias>Librerías.
• Pasa a Cargado después de cerrar y reiniciar BlueJ. Sólo entonces la librería queda instalada.
• Representación de secuencias con arrays.
Una manera obvia de representar una secuencia consiste en disponer sus elementos en las sucesivas posiciones de un array de longitud suficientemente grande.
• Esta representación permite que el acceso a los elementos de la secuencia se pueda realizar con coste constante.
• La talla de la secuencia está limitada a la longitud del array (MAX).
• La inserción/eliminación de un dato en la posición i-ésima de la secuencia exige reorganizar elArray[i..n-1].
elArray d ... ... 0
MAX-1
d1 dn-1
Secuencias enlazadas
• Representación enlazada de secuencias: representación de secuencias en la que se dispone de memoria para los datos a medida que se van insertando en la secuencia.
• Todo dato tiene asociado un enlace (o referencia) a la posición en donde se encuentra en el heap el siguiente dato de la secuencia; pero el acceso a los datos ya no es directo por su posición en la secuencia.
• En el siguiente subapartado veremos cómo agregar en un objeto secuencia un dato y un enlace.
• A continuación presentaremos técnicas básicas de manipulación de secuencias enlazadas: recorridos, búsquedas, inserción, borrado, ...
/**
* Clase NodoInt: Nodo cuyo dato es un int
*/
class NodoInt {
int dato;
NodoInt siguiente;
}
• Nodo: Estructura que asocia un dato con el enlace al siguiente dato.
Clase con atributos “friendly”, a incluir en el mismo paquete que aquellas clases que deseen usar secuencias enlazadas mediante nodos.
Secuencias enlazadas. La clase NodoInt con dos atributos y dos constructores.
class NodoInt {
int dato;
NodoInt siguiente;
/** Constructor A */
NodoInt(int d) {
this.dato = d;
this.siguiente = null;
}
/** Constructor B */
NodoInt(int d, NodoInt s) {
this.dato = d;
this.siguiente = s;
}
}
Ejemplo:
• Constructor A: Crea un nodo con un dato d sin enlazar.
NodoInt sec = null;
sec = new NodoInt(10);
• Constructor B: Crea un nodo con un dato d enlazado a un nodo preexistente.
sec = new NodoInt(5,sec);
sec = new NodoInt(-2,sec);
• resulta:
sec null (secuencia vacía, sin nodos)
sec
10 null
sec
5 10 null
sec
-2 5 10 null
Inserción en orden inverso:
NodoInt sec = null, ultimo = null;
• Los constructores de NodoInt facilitan la inserción en cabeza.
• La manipulación de enlaces permite acceder a otras posiciones. Ejemplo: el siguiente código se supone en una clase con acceso “friendly” a los atributos de NodoInt.
sec null ultimo null
sec ultimo
NodoInt sec = null;
sec = new NodoInt(10);
ultimo.siguiente = new NodoInt(5); // 1
ultimo = ultimo.siguiente; // 2
ultimo.siguiente = new NodoInt(-2);
ultimo = ultimo.siguiente;
sec = new NodoInt(10);
ultimo = sec;
sec
10 5 -2 null
Secuencias enlazadas. La clase Nodo
int i = 0;
while (i<a.length) {
//si 0<=i<a.length-1: i está en el rango de a
tratar(a[i]);
i++;
}
• Recorrido de arrays y de secuencias enlazadas, realizando una cierta operación tratar a todos sus elementos.
NodoInt aux = sec;
while (aux!=null) {
// aux!=null: aux referencia a un nodo
tratar(aux.dato);
aux = aux.siguiente;
}
Secuencias enlazadas. Recorridos
Si i estuviera fuera de rango, el acceso a a[i] daría IndexOutOfBoundsException
Si aux fuera null, el acceso a aux.dato y a aux.siguiente daría NullPointerException
• Ejemplo. Dada una secuencia enlazada de int, se desea que sus valores saturen a un cierto valor maximo, es decir, que los valores>maximo se cambien a maximo:
public static void saturar(NodoInt sec,int maximo) {
NodoInt aux = sec;
while (aux!=null) {
if (aux.dato>maximo) aux.dato = maximo;
aux = aux.siguiente;
}
}
Secuencias enlazadas. Búsquedas
• Si al terminar el bucle aux != null: Éxito en la búsqueda.
• Si aux == null: Fracaso en la búsqueda.
• Ejemplo. Dada la secuencia sec y el dato d, cambiar el signo de la primera ocurrencia de d en la secuencia. Si d no aparece, no se hace nada.
public static void cambiarSigno(NodoInt sec,int d){
//Búsqueda del primer nodo cuyo dato sea d:
NodoInt aux = sec;
while (aux!=null && aux.dato!=d)
aux = aux.siguiente;
//Si la búsqueda termina con éxito, se cambia el
//signo del dato:
if (aux!=null) aux.dato = -d;
}
PRG. Grupo J. ETSINF. UPV - Curso 2014/15 21
Secuencias enlazadas. Búsquedas
A continuación se presentan un par de trazas ejemplo, en las que sobre
una misma secuencia, se hará primero una búsqueda con fracaso, y
luego otra con éxito.
PRG. Grupo J. ETSINF. UPV - Curso 2014/15
Secuencias enlazadas. Búsquedas
aux
sec
7 1 9 4 null
sec
null
aux
7 1 9 4
sec
null
aux
7 1 9 4
sec
null
aux
7 1 9 4
aux null
sec
7 1 9 4 null
a) Traza ejemplo del método cambiarSigno con un valor de d igual a 25.
Después de la inicialización del bucle:
Después de la primera pasada:
Después de la segunda pasada:
Después de la tercera pasada:
Después de la cuarta y última pasada:
PRG. Grupo J. ETSINF. UPV - Curso 2014/15
Secuencias enlazadas. Búsquedas
aux
sec
7 1 9 4 null
sec
null
aux
7 1 9 4
-1
sec
null
aux
7 9 4
Después de la inicialización del bucle:
Después de la primera y última pasada:
Como el bucle acaba con aux!=null, entonces ha fallado la condición
aux.dato!=d, es decir, se ha encontrado en el nodo referenciado por aux el
dato buscado d, y se ejecuta el cambio de signo de aux.dato:
b) Traza ejemplo de cambiarSigno con un valor de d igual a 1.
• Ejemplo. El acceso al i-ésimo nodo de una secuencia se debe
resolver buscando el i-ésimo nodo:
24
NodoInt aux = sec; int k = 0;
while (aux!=null && k<i) {
aux = aux.siguiente;
k++;
}
• La posición del nodo se va registrando en la variable k.
• Al acabar el bucle:
Si aux!=null entonces k==i, y aux es el i-ésimo nodo,
sino la secuencia es más corta, dicho nodo no existe.
• Ejercicio. Escribir un método
public static int buscar(NodoInt sec,int d)
que retorne la posición de la primera aparición de d en sec. Si no
aparece, debe retornar 1.
PRG. Grupo J. ETSINF. UPV - Curso 2014/15 24
Secuencias enlazadas. Búsquedas
25
public static int buscar(NodoInt sec,int d)
NodoInt aux = sec; int k = 0;
while (aux!=null && aux.dato!=d) {
aux = aux.siguiente;
k++;
}
if (aux!=null) return k;
else return -1;
}
• Se usa un contador k
que registra en cada
momento la posición
del nodo aux en la
secuencia, empezando
de 0 en adelante:
PRG. Grupo J. ETSINF. UPV - Curso 2014/15 25
Secuencias enlazadas. Búsquedas
aux
sec
7 8 9 1 null
sec
null
aux
7 8 9 1
sec
null
aux
7 8 9 1
Después de la inicialización del bucle:
Después de la primera pasada:
Después de la segunda y última pasada:
k 1
k 2
Se ha encontrado el dato, se devuelve k.
a) Traza ejemplo con d igual a 9: k 0
26
Secuencias enlazadas. Búsquedas
sec
null
aux
7 8 9 1
aux null
sec
7 8 9 1 null
Después de la tercera pasada:
Después de la cuarta y última pasada:
k 3
k 4
b) Traza ejemplo con d igual a 25:
La traza coincide con la anterior en la inicialización y en las dos primeras pasadas,
pero aún se necesitan dos pasadas más para llegar al estado final del bucle:
Se ha agotado la secuencia sin encontrar el dato buscado, se devuelve 1.
El valor del contador en este estado final significa que no existen nodos desde
la posición 4 inclusive en adelante.
PRG. Grupo J. ETSINF. UPV - Curso 2014/15
• Al igual que en las búsquedas con arrays, si la condición a
comprobar para el dato es relativamente compleja, no se escribe en
la guarda del bucle.
• Ejemplo. Buscar en una secuencia sec la primera ocurrencia de un
dato impar y que esté en el intervalo [a,b[. Si existe, cambiarlo al
siguiente par.
27
NodoInt aux = sec; boolean encontrado = false;
while (aux!=null && !encontrado){
if (aux.dato%2!=0 && a<=aux.dato && aux.dato<b)
encontrado = true;
else aux = aux.siguiente;
}
if (encontrado) aux.dato++;
PRG. Grupo J. ETSINF. UPV - Curso 2014/15 27
Secuencias enlazadas. Búsquedas
• Gracias a la manipulación de los enlaces, la inserción de un dato en una
secuencia se puede resolver sin realizar ningún movimiento de los datos
existentes.
28
• Según donde se deba realizar la inserción se pueden dar dos casos:
a) El nuevo nodo se inserta en cabeza o primera posición (incluye el
caso de insertar en una secuencia vacía):
sec = new NodoInt(d,sec);
sec
d
...
sec
d
null
null
PRG. Grupo J. ETSINF. UPV - Curso 2014/15 28
Secuencias enlazadas. Inserción
29
b) El nuevo nodo se inserta en cualquier otra posición de sec, es a decir,
detrás de algún nodo (incluye el caso de insertar detrás del último).
Se debe tener acceso al nodo detrás del cual se deba hacer la
inserción. En la siguiente figura se supone que ya se ha situado la
referencia ant sobre dicho nodo. Entonces:
ant.siguiente = new NodoInt(d,ant.siguiente);
sec
...
ant
d
null
null
sec
...
ant
...
d
Se inserta en cabeza de una
subsecuencia de sec:
ant.siguiente
PRG. Grupo J. ETSINF. UPV - Curso 2014/15 29
Secuencias enlazadas. Inserción
30
• Ejemplo. Dada una secuencia, y un índice i≥0, insertar el dato d en la
posición i. Si el índice sobrepasa la longitud de la secuencia, la inserción no
se realiza.
if (i==0) sec = new NodoInt(d,sec);
else {
NodoInt aux = sec; int k = 0;
while (aux!=null && k<i-1) {
aux = aux.siguiente; k++;
}
if (aux!=null) // Éxito en la búsqueda
aux.siguiente = new NodoInt(d,aux.siguiente);
}
Casos:
a) i==0: la inserción se ha de hacer en cabeza.
b) i>0: se busca el nodo i-1, y si existe, se inserta detrás el nuevo nodo.
PRG. Grupo J. ETSINF. UPV - Curso 2014/15 30
Secuencias enlazadas. Inserción
31
• Ejemplo. Dada una secuencia cuyos datos están ordenados de menor
a mayor, insertar un dato d manteniendo la ordenación.
Hay que insertarlo al inicio de aquella subsecuencia que contenga a los
elementos ≥d.
Con aux se busca el primer nodo con un dato ≥d. La variable ant se usa
para referenciar en cada momento al nodo anterior a aux:
aux
...
sec
...
null
ant
?
elementos <d
PRG. Grupo J. ETSINF. UPV - Curso 2014/15 31
Secuencias enlazadas. Inserción
32
//Inicialización de aux a toda la secuencia
//Inicialización de ant: el primer nodo no
//tiene anterior definido
NodoInt aux = sec,
ant = null;
//Búsqueda del primer dato >=d:
while (aux!=null && aux.dato<d) {
ant = aux;
aux = aux.siguiente;
}
//Inserción de d (en cabeza o detrás de ant):
if (aux==sec) sec = new NodoInt(d,sec); // Caso a)
else ant.siguiente = new NodoInt(d,aux); // Caso b)
aux
...
sec
ant null
Caso a) aux==sec (o ant==null), sec está vacía o todos sus datos son ≥d.
Caso b) aux!=sec (o ant!=null), no todos sus datos son ≥d. La inserción
detrás de ant sitúa el nuevo nodo a continuación de todos los datos <d.
PRG. Grupo J. ETSINF. UPV - Curso 2014/15 32
Secuencias enlazadas. Inserción
PRG. Grupo J. ETSINF. UPV - Curso 2014/15
• La eliminación o borrado de un dato se resuelve igualmente sin
realizar ningún movimiento de los datos existentes.
33
• Sea nodo una referencia al nodo a eliminar. Se pueden dar dos casos:
a) Es el primero de la secuencia.
sec = sec.siguiente;
sec
...
nodo
En el caso particular de que sólo hubiera un nodo en la secuencia,
sec se haría null (se quedaría vacía).
33
Secuencias enlazadas. Eliminación
34
b) El nodo a eliminar tiene un anterior:
en donde ant es una referencia al nodo anterior. Se elimina
el nodo en cabeza de la subsecuencia ant.siguiente.
ant.siguiente = nodo.siguiente;
En el caso particular de que nodo fuera el último, ant.siguiente
se haría null (ant pasaría a ser el último).
sec
...
ant
...
nodo
PRG. Grupo J. ETSINF. UPV - Curso 2014/15 34
Secuencias enlazadas. Eliminación
ant.siguiente
35
• Ejemplo. Eliminar, si existe, la primera ocurrencia de un dato d. Si
no existe, no se hace nada.
NodoInt aux = sec, ant = null;
while (aux!=null && aux.dato!=d) {
ant = aux;
aux = aux.siguiente;
}
if (aux!=null) // Éxito en la búsqueda
if (aux == sec)
sec = aux.siguiente;
else ant.siguiente = aux.siguiente;
PRG. Grupo J. ETSINF. UPV - Curso 2014/15 35
Secuencias enlazadas. Eliminación
Representación enlazada de tipos
lineales
PRG. Grupo J. ETSINF. UPV - Curso 2014/15
• La implementación enlazada de las clases Pila, Cola y ListaPI con
datos de tipo entero se basará en la clase NodoInt.
• Se incluirán todas estas clases en un mismo paquete lineales.
• La clase NodoInt y sus componentes, atributos y métodos, serán
friendly: Serán public para el código de las clases del paquete,
private para el resto.
• El paquete lineales se completará con la implementación de
Pila, Cola y ListaPI de int basada en arrays.
Comentarios
Publicar un comentario