listas. tratamiento de listas en java. listas. modelo

Download Listas. Tratamiento de listas en Java. Listas. Modelo

Post on 03-Feb-2015

17 views

Category:

Documents

14 download

Embed Size (px)

TRANSCRIPT

  • Diapositiva 1
  • Listas. Tratamiento de listas en Java
  • Diapositiva 2
  • Listas. Modelo.
  • Diapositiva 3
  • Modelo. 10 12 13 nullnull 21 Memoria esttica Memoria dinmica Lista nombre inicio NodoLista
  • Diapositiva 4
  • La clase Lista identifica una referencia (puntero) a un objeto (o null). La declaracin de la clase Lista debe incluir: Las variables miembro. El/los constructor/es. [Opcional] Otros mtodos que vayan a ser utilizados por objetos externos. Ejemplo: public class Lista { NodoLista inicio; String nombre; public ListaEnlazada () { inicio = null; nombre = null; } // Otros mtodos } Aspectos sintcticos: clase Lista.
  • Diapositiva 5
  • 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 mtodos que vayan a ser utilizados por objetos externos. Cdigo: class NodoLista { int clave; NodoLista sig; NodoLista (int dato) { clave = dato; sig = null; } // otros mtodos } Aspectos sintcticos: clase NodoLista
  • Diapositiva 6
  • Listas. Algoritmos bsicos con listas
  • Diapositiva 7
  • Algoritmos bsicos. Una sola ejecucin: Insertar al principio. Eliminar el primero. Recorrido de la lista (recursivo): Sin modificar la estructura: Recorrido completo: Mostrar el contenido de una lista.Mostrar el contenido de una lista. Modificando la estructura: Recorrido completo: Insertar al final. Obtener el duplicado de una lista. Destruir una lista.
  • Diapositiva 8
  • static void insertarAlPrincipio (Lista lista, int dato) { //ATENCION! No se verifica la introduccin de claves repetidas. NodoLista aux; aux = new NodoLista (dato); aux.sig = lista.inicio; lista.inicio = aux; } Insertar al principio. Crear nuevo nodo con la informacin de entrada Enlazar el nuevo nodo a la lista Proceso nico. 10 13 aux null 21 dato Lista nombre inicio NodoLista lista
  • Diapositiva 9
  • Insercin al principio. Modelo simplificado. Situacin inicial. Creacin de un nuevo nodo. Situacin final.
  • Diapositiva 10
  • Modelo de funcionamiento desde el programa principal public static void main (String [ ] args){ Lista lista; //Declaracin de la variable (puntero) lista de clase Lista Lista = new Lista (); // Construccin de un objeto de clase Lista insertarAlPrincipio (lista,10); //Ejecucin del mtodo insertarAlPrincipio } Memoria estticaMemoria dinmica Variable lista null Memoria estticaMemoria dinmica Variable lista nombre inicio Objeto de clase Lista Memoria estticaMemoria dinmica Variable lista nombre inicio Objeto de clase Lista null 10 Objeto de clase NodoLista
  • Diapositiva 11
  • 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 null 21 Lista nombre inicio NodoLista lista
  • Diapositiva 12
  • 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.
  • Diapositiva 13
  • Insertar al final. Algoritmo. Mdulo de llamada no recursivo (Lista). Mdulo 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 transicin se genera el nuevo nodo. El mtodo 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. Modificacin de la estructura. Recorrido completo nodoLista.sig = insertar (nodoLista.sig, dato); resul = nodoLista;
  • Diapositiva 14
  • 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; } Modificacin de la estructura. Recorrido completo. Insertar al final. Cdigo
  • Diapositiva 15
  • Modificacin de la estructura. Recorrido completo. Insertar al final. Modelo fsico. nombre inicio 2 Instancia 1 Instancia 2 Instancia 3 nodoLista resul 8 dato lanzadera lista 8 dato nodoLista resul 8 dato nodoLista resul 8 dato null 8 4 nodoLista.sig = insertarAlFinal (nodoLista.sig, 8);
  • Diapositiva 16
  • Situacin inicial. Fase de transicin. Fase de vuelta. Modificacin de la estructura. Recorrido completo. Insertar al final. Modelo simplificado Instancia 3 null 4 2 Lista nombre inicio NodoLista null 4 2 8 resul Lista nombre inicio NodoLista null 4 2 8 Instancia 1 Instancia 2 Lista nombre inicio NodoLista
  • Diapositiva 17
  • Combinacin de algoritmos bsicos: 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.
  • Diapositiva 18
  • Combinacin de algoritmos bsicos: (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.