estra. de dat. unidad iii listas enlazadas

Upload: manuel-rl

Post on 16-Jul-2015

83 views

Category:

Documents


1 download

TRANSCRIPT

III. Listas enlazadas. Una lista es una coleccin o secuencia de elementos ordenados uno tras otro, en la que cada elemento se conecta por medio de un apuntador. A cada elemento de la lista se le llama nodo. Cada nodo esta constituido por dos partes las cuales son:1a. Parte Informacin

2a. Parte Apuntador que seala al siguiente nodo

Representacin graficaNodo 1 Nodo 2 Nodo n /

Debido a que el ltimo elemento de la lista no esta sealando a ningn elemento existe diferentes formas de representarlo grficamente:

Nod x

/

Nodo x

Nodo x null

III.1.

Listas enlazadas.

III.1.1. Simples. Cada nodo contiene un nico enlace que conecta al siguiente nodo. La lista se recorre solamente hacia adelante.

e1

e2

e3

en

/

Apuntadores al inicio y al final de la listaPara poder manipular una lista de una manera eficiente es utilizar apuntadores al inicio de las lista y al final. Para poder lograr esto debemos utilizar un apuntador al frente o inicio de la lista y al final o cola.

65

inicio e1 e2 e3 en fin /

III.1.2. Dobles. Cada nodo contiene dos enlaces o apuntadores, el enlace izquierdo apunta al nodo predecesor y el enlace derecho apunta al nodo sucesor.

/ e1

e2

e3

en /

III.1.3. Circulares. El ltimo nodo de la lista apunta al primer elemento de la lista.

e1

e2

e3

en

Cada nodo esta enlazado a su predecesor y sucesor y el ltimo apunta a primer elemento y el primero apunta al ltimo.

e1

e2

e3

en

III.1.4. Multilistas. En las multilistas existen enlaces verticales y horizontales.

66

III.1.5. Clases para la implementacin de listas.

Clase nodoSimpleclass nodoSimple { private String dato; private nodoSimple enlace; nodoSimple( String d ) { this( d, null ); } nodoSimple( String d, nodoSimple e ) { dato = new String(d); enlace = e; } String obtenDato() { return dato; } nodoSimple obtenEnlace() { return enlace; } void cambiaDato(String d) { dato = new String(d); } void cambiaEnlace(nodoSimple e) { enlace = e; } }

Operaciones en listasLas operaciones bsicas sobre una lista son: Tipo de datos de la lista Declaracin de un nodo Crear la lista Comprobar si la lista esta vaca Insertar un elemento Eliminar un elemento Buscar un elemento Recorrer la lista 67

Tipo de datos de la listaEn cada tipo de lista se debe definir el tipo de dato que se va a manejar, para nuestro ejemplo tomaremos el tipo String.

Declaracin de un nodonodoSimple nodo, inicio = null, fin = null;

Comprobar si la lista esta vacaPara comprobar si la lista esta vaca, simplemente se debe de preguntar si inicio es igual a null.

Insertar un elementoExisten tres formas de insertar un nodo en una lista, los cuales pueden ser: Insertar al inicio de la lista

nodoSimple nodo, inicio = null, fin = null; ... .. . Capturar la informacin nodo = new nodoSimple(informacin); ... .. . nodo.cambiaEnlace(inicio); inicio = nodo; Producto de Aprendizaje: 1. Elabore un programa en Java que lea 5 nombres desde el teclado y los inserte al inicio en una lista ligada simple y al final imprima la lista.

68

Insertar al final de la lista

nodoSimple nodo, inicio = null, fin = null; ... .. . Capturar la informacin nodo = new nodoSimple(informacin); ... .. . fin.cambiaEnlace(nodo); fin = nodo; Producto de Aprendizaje: 2. Elabore un programa en Java que lea 5 nombres desde el teclado y los inserte al final en una lista ligada simple y al final imprima la lista.

Insertar entre elementos de la lista

nodoSimple nodo, inicio = null, fin = null; ... .. .

69

Capturar la informacin nodo = new nodoSimple(informacin); ... .. . pre.cambiaEnlace(nodo); nodo.cambiaEnlace(suc); Producto de Aprendizaje: 3. Elabore un programa en Java que lea 5 nombres desde el teclado, los inserte al final en una lista ligada simple, posteriormente solicite un nuevo nombre y un valor numrico e inserte el nuevo nombre despus del n-esimo nombre y al final imprima la lista.

Eliminar un elemento As como existen tres formas de insertar un elemento, existen tres formas de eliminarlo. Eliminar un elemento al inicio de la lista

nodoSimple nodo, inicio = null, fin = null; String x; ... .. . x = inicio.obtenDato(); nodo = inicio; inicio = inicio.obtenEnlace(); nodo.cambiaEnlace(null); nodo = null;

70

Producto de Aprendizaje: 4. Elabore un programa en Java que lea 5 nombres desde el teclado, los inserte al inicio en una lista ligada simple e imprima la lista, posteriormente elimine el primer nombre e imprima la lista final.

Eliminar un elemento al final de la lista

nodoSimple nodo, inicio = null, fin = null; String x; ... .. . x = fin.obtenDato(); nodo = inicio; while (nodo.obtenEnlace() != fin) nodo = nodo.obtenEnlace(); nodo.cambiaEnlace(null); fin = nodo; Producto de Aprendizaje: 5. Elabore un programa en Java que lea 5 nombres desde el teclado, los inserte al final en una lista ligada simple e imprima la lista, posteriormente elimine el ultimo nombre e imprima la lista final.

Eliminar un elemento en medio de la lista

71

nodoSimple nodo, inicio = null, fin = null; String x; ... .. . x = nodo.obtenDato(); pre.cambiaEnlace(nodo.obtenEnlace); nodo.cambiaEnlace(null); nodo = null; Nota: En ninguno de los algoritmos anteriores, se a validado si la lista esta vaca o si existe un solo elemento en la lista. Producto de Aprendizaje: 6. Elabore un programa en Java que lea 5 nombres desde el teclado, los inserte al inicio en una lista ligada simple e imprima la lista, posteriormente solicite un nmero entre 1 al 5 y elimine el n-esimo nombre, al final imprima la lista.

Buscar un elementoAl realizar la bsqueda un elemento en una lista, se debe realizar este proceso hasta que se localice el elemento o hasta que se llegar al final de la lista. boolean buscarL(nodoSimple nodo, String x) { while (nodo != null && !x.equals(nodo.obtenDato())) nodo = nodo.obtenEnlace(); if (nodo != null && x.equals(nodo.obtenDato())) return true; else return false; } nodoSimple buscarN(nodoSimple nodo, String x) { while (nodo != null && !x.equals(nodo.obtenDato())) nodo = nodo.obtenEnlace(); return nodo; } Producto de Aprendizaje: 7. Elabore un programa en Java que lea 5 nombres desde el teclado, los inserte al final en una lista ligada simple e imprima la lista, posteriormente solicite un nuevo nombre y lo busque en la lista, si encuentra el nombre indique en que posicin se encuentra, en caso de no localizarlo imprima -1.

72

Recorrer la listanodo = inicio; while (nodo != null) { System.out.print(nodo.ObtenDato() + "->"); nodo = nodo.obtenEnlace(); } Systema.out.println("/"); El siguiente programa solicita el nmero de elementos que se desea insertar en una lista, posteriormente mediante un men solicita la forma de insercin (Inicio o Final) y al final despliegue la lista en pantalla.1 // Ejemplo_Lista 2 3 import javax.swing.JOptionPane; 4 5 class nodoSimple { 6 private String dato; 7 private nodoSimple enlace; 8 9 nodoSimple( String d ) { 10 this( d, null ); 11 } 12 13 nodoSimple( String d, nodoSimple e ) { 14 dato = new String(d); 15 enlace = e; 16 } 17 18 String obtenDato() { 19 return dato; 20 } 21 22 nodoSimple obtenEnlace() { 23 return enlace; 24 } 25 26 void cambiaDato(String d) { 27 dato = new String(d); 28 } 29 30 void cambiaEnlace(nodoSimple e) { 31 enlace = e; 32 } 33 } 34 Programa: Ejemplo_Lista.java

1/2

73

35 public class Ejemplo_Lista { 36 public static void main(String [] args) { 37 nodoSimple inicio = null, fin = null, nodo; 38 String inf = ""; 39 int cuantos, tipo=0; 40 Object[] options = { "Inicio", "Final" }; 41 42 cuantos = Integer.parseInt( 43 JOptionPane.showInputDialog("Cuantos elementos deseas:") ); 44 if (cuantos > 0) { 45 tipo = JOptionPane.showOptionDialog(null, 46 "Insertar al", "Opcin de insercin", 47 JOptionPane.DEFAULT_OPTION, 48 JOptionPane.QUESTION_MESSAGE, 49 null, options, options[0]); 50 51 for(int i=1; i