listas. tratamiento de listas en java

18
Listas. Tratamiento de listas en Java

Upload: filia

Post on 10-Jan-2016

161 views

Category:

Documents


3 download

DESCRIPTION

Listas. Tratamiento de listas en Java. Listas. Modelo. 10. 12. 13. 21. Modelo. Lista. Memoria estática. nombre. inicio. Memoria dinámica. NodoLista. n u l l. Aspectos sintácticos: clase Lista. La clase Lista identifica una referencia (puntero) a un objeto (o null ). - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: Listas. Tratamiento de listas en Java

Listas.

Tratamiento de listas en Java

Page 2: Listas. Tratamiento de listas en Java

Listas.

Modelo.

Page 3: Listas. Tratamiento de listas en Java

Modelo.

1012

13null

21

Memoria estática

Memoria dinámica

Lista

NodoLista

Page 4: Listas. Tratamiento de listas en Java

La clase Lista identifica una referencia (puntero) a un objeto (o null).

La declaración de la clase Lista debe incluir:Las variables miembro.El/los constructor/es. [Opcional] Otros métodos que vayan a ser utilizados por

objetos externos.Ejemplo:

public class Lista {NodoLista inicio;String nombre;public ListaEnlazada () {

inicio = null;nombre = null;

} // Otros métodos}

Aspectos sintácticos: clase Lista.

Page 5: Listas. Tratamiento de listas en Java

La estructura de datos que representa los nodos de una lista debe contemplarse como una clase (NodoLista.java).Se debe declarar:

Las variables miembro (clave y sig). El/los constructor/es. El destructor [innecesario en Java]. [Opcional] Otros métodos que vayan a ser utilizados por objetos externos.

Código:class NodoLista {

int clave;NodoLista sig;

NodoLista (int dato) {clave = dato;sig = null;

}// otros métodos

}

Aspectos sintácticos: clase NodoLista

Page 6: Listas. Tratamiento de listas en Java

Listas.

Algoritmos básicos con listas

Page 7: Listas. Tratamiento de listas en Java

Algoritmos básicos.Una sola ejecución:

Insertar al principio. Eliminar el primero.

Recorrido de la lista (recursivo):Sin modificar la estructura:

Recorrido completo: Mostrar el contenido de una lista.Modificando la estructura:

Recorrido completo: Insertar al final. Obtener el duplicado de una lista. Destruir una lista.

Page 8: Listas. Tratamiento de listas en Java

static void insertarAlPrincipio (Lista lista, int dato) {//¡ATENCION! No se verifica la introducción de claves repetidas.

NodoLista aux;aux = new NodoLista (dato);aux.sig = lista.inicio;lista.inicio = aux;

}

Insertar al principio.Crear nuevo nodo con la

información de entradaEnlazar el nuevo nodo a

la lista

Proceso único.

10 13

aux

21

dato

Lista

NodoLista

lista

Page 9: Listas. Tratamiento de listas en Java

Inserción al principio. Modelo simplificado.Situación inicial.

Creación de un nuevo nodo.

Situación final.

Page 10: Listas. Tratamiento de listas en Java

Modelo de funcionamiento desde el programa principal

public static void main (String [ ] args) {

Lista lista; //Declaración de la variable (puntero) lista de clase Lista

Lista = new Lista (); // Construcción de un objeto de clase Lista

insertarAlPrincipio (lista,10); //Ejecución del método insertarAlPrincipio

}

Memoria estática Memoria dinámica

Variable lista

null

Memoria estática Memoria dinámica

Variable listaObjeto de clase Lista

Memoria estática Memoria dinámica

Variable listaObjeto de clase Lista

10Objeto de clase NodoLista

Page 11: Listas. Tratamiento de listas en Java

Proceso único. Eliminar el primero.

¿Y si la lista tiene un solo nodo?

static void eliminarPrimero (Lista lista) {if (lista.inicio != null)

lista.inicio = lista.inicio.sig;else System.out.println ("Error, lista vacia");

}

10 13

null21

Lista

NodoLista

lista

Page 12: Listas. Tratamiento de listas en Java

Ejemplo: Mostrar el contenido.

public void mostrarLista () {mostrarLista (inicio);

}

static void mostrarLista (NodoLista nodoLista) {if (nodoLista != null) {

System.out.println (nodoLista.clave + " ");mostrarLista (nodoLista.sig);

}else System.out.println ("FIN");

}

Recorrido completo de la lista.

Page 13: Listas. Tratamiento de listas en Java

Insertar al final. Algoritmo.• Módulo de llamada no recursivo (Lista).• Módulo recursivo (NodoLista).

• Devuelve un objeto de la clase NodoLista.• Se inicializa el valor devuelto con el propio

argumento:;• Se “reemplaza” el puntero nodoLista.sig por el

valor devuelto: );• En la fase de transición se genera el nuevo nodo.

• El método solo surte efecto en la instancia de la fase de vuelta correspondiente al último nodo original.

Se recuerda que en Java los argumentos solo pueden pasarse “por valor”.

Modificación de la estructura. Recorrido completo

nodoLista.sig = insertar (nodoLista.sig, dato);

resul = nodoLista;

Page 14: Listas. Tratamiento de listas en Java

static void insertarAlFinal (Lista l, int dato) {//¡ATENCION! No se verifica la introduccion de claves repetidas.l.inicio = insertarAlFinal (l.inicio,dato);

}

static NodoLista insertarAlFinal (NodoLista nodoLista, int dato) {NodoLista resul = nodoLista;if (nodoLista != null)

nodoLista.sig = insertarAlFinal (nodoLista.sig, dato);else {

resul = new NodoLista (dato);//resul.sig = nodoLista; (Innecesario, ya es null)

}return resul;

}

Modificación de la estructura. Recorrido completo.Insertar al final.

Código

Page 15: Listas. Tratamiento de listas en Java

Modificación de la estructura. Recorrido completo .Insertar al final. Modelo físico.

2

Instancia 1

Instancia 2

Instancia 3

nodoLista

resul8

dato

lanzadera

lista

8

dato

nodoLista

resul8

dato

nodoLista

resul8

dato

null

null8

4

nodoLista.sig = insertarAlFinal (nodoLista.sig, 8);

Page 16: Listas. Tratamiento de listas en Java

Situación inicial.

Fase de transición.

Fase de vuelta.

Modificación de la estructura. Recorrido completo.Insertar al final. Modelo

simplificado

Instancia 3

42Lista

nombre

NodoLista

42

8resul

Lista

nombre

NodoLista

42

8Instancia 1 Instancia 2

Lista

nombre

NodoLista

Page 17: Listas. Tratamiento de listas en Java

Combinación de algoritmos básicos:Recorrido completo sin modificar estructura (lista

origen).Insertar (lista destino). Alternativas:

En la fase de ida: insertarAlFinal. En la fase de vuelta: insertarAlPrincipio.

static void duplicarLista (Lista listaO, Lista listaD) {listaD.inicio = duplicarLista (listaO.inicio);

}static NodoLista duplicarLista (NodoLista nodoListaO) {

NodoLista resul;NodoLista aux;if (nodoListaO != null) {

resul = duplicarLista (nodoListaO.sig);aux = new NodoLista (nodoListaO.clave);aux.sig = resul;resul = aux;

}else resul = null;return resul;

}

Recorrido completo. Obtener el duplicado de una lista.

Page 18: Listas. Tratamiento de listas en Java

Combinación de algoritmos básicos: (lista origen) Recorrido completo sin modificar estructura (lista destino) Insertar un nodo al principio de la lista en

la fase de vuelta

static void duplicarLista (Lista listaO, Lista listaD) {listaD.inicio = duplicarLista (listaO.inicio);

}

static NodoLista duplicarLista (NodoLista nodoListaO) {NodoLista resul;NodoLista aux;

if (nodoListaO != null) {resul = duplicarLista (nodoListaO.sig);aux = new NodoLista (nodoListaO.clave);aux.sig = resul;resul = aux;

}else resul = null;return resul;

}

Recorrido completo. Obtener el duplicado de una lista.