Listas. Tratamiento de listas en Java

  • Published on
    10-Jan-2016

  • View
    47

  • Download
    2

DESCRIPTION

Listas. Tratamiento de listas en Java. Listas. Modelo. 10. 12. 13. 21. Modelo. Lista. Memoria esttica. nombre. inicio. Memoria dinmica. NodoLista. n u l l. Aspectos sintcticos: clase Lista. La clase Lista identifica una referencia (puntero) a un objeto (o null ). - PowerPoint PPT Presentation

Transcript

<ul><li><p>Listas.Tratamiento de listas en Java </p></li><li><p>Listas.Modelo. </p></li><li><p>Modelo.</p></li><li><p>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:</p><p>public class Lista {NodoLista inicio;String nombre;public ListaEnlazada () {inicio = null;nombre = null;} // Otros mtodos}Aspectos sintcticos: clase Lista.</p></li><li><p>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;</p><p>NodoLista (int dato) {clave = dato;sig = null;}// otros mtodos}</p><p>Aspectos sintcticos: clase NodoLista</p></li><li><p>Listas.Algoritmos bsicos con listas </p></li><li><p>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.Modificando la estructura:Recorrido completo: Insertar al final.Obtener el duplicado de una lista.Destruir una lista.</p></li><li><p>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 entradaEnlazar el nuevo nodo a la listaProceso nico. </p></li><li><p> Insercin al principio. Modelo simplificado.Situacin inicial.</p><p>Creacin de un nuevo nodo.</p><p>Situacin final.</p></li><li><p> Modelo de funcionamiento desde el programa principalpublic static void main (String [ ] args){Lista lista; //Declaracin de la variable (puntero) lista de clase Lista</p><p>Lista = new Lista (); // Construccin de un objeto de clase Lista</p><p>insertarAlPrincipio (lista,10); //Ejecucin del mtodo insertarAlPrincipio</p><p>}</p></li><li><p>Proceso nico. Eliminar el primero.</p><p>Y si la lista tiene un solo nodo?</p><p>static void eliminarPrimero (Lista lista) {if (lista.inicio != null) lista.inicio = lista.inicio.sig;else System.out.println ("Error, lista vacia");}</p></li><li><p>Ejemplo: Mostrar el contenido.</p><p>public void mostrarLista () {mostrarLista (inicio);}</p><p>static void mostrarLista (NodoLista nodoLista) {if (nodoLista != null) {System.out.println (nodoLista.clave + " ");mostrarLista (nodoLista.sig);}else System.out.println ("FIN");}</p><p>Recorrido completo de la lista. </p></li><li><p>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.</p><p>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.</p><p>Modificacin de la estructura. Recorrido completo nodoLista.sig = insertar (nodoLista.sig, dato);resul = nodoLista;</p></li><li><p>static void insertarAlFinal (Lista l, int dato) {//ATENCION! No se verifica la introduccion de claves repetidas.l.inicio = insertarAlFinal (l.inicio,dato);}</p><p>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</p></li><li><p>Modificacin de la estructura. Recorrido completo .Insertar al final. Modelo fsico.</p><p>nodoLista.sig = insertarAlFinal (nodoLista.sig, 8);</p></li><li><p>Situacin inicial.</p><p>Fase de transicin.</p><p>Fase de vuelta.Modificacin de la estructura. Recorrido completo.Insertar al final. Modelo simplificado</p><p>Instancia 3</p></li><li><p>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.</p></li><li><p>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</p><p>static void duplicarLista (Lista listaO, Lista listaD) {listaD.inicio = duplicarLista (listaO.inicio); }</p><p> static NodoLista duplicarLista (NodoLista nodoListaO) {NodoLista resul;NodoLista aux;</p><p>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.</p></li></ul>

Recommended

View more >