EJEMPLO 8.1 package ListaPuntos; public class Punto { double x, y; public Punto(double x, double y) { this.x = x; this.y = y; } public Punto() // constructor por defecto { x = y = 0.0; } } package ListaPuntos; public class Nodo { Punto dato; Nodo enlace; public Nodo(Punto p) { dato = p; enlace = null; } public Nodo(Punto p, Nodo n) { dato = p; enlace = n; } }
EJEMPLO 8.2 import java.io.*; class Nodo { int dato; Nodo enlace; public Nodo(int x) { dato = x; enlace = null; } public Nodo(int x, Nodo n) { dato = x; enlace = n; } public int getDato() { return dato; } public Nodo getEnlace() { return enlace; } public void setEnlace(Nodo enlace) { this.enlace = enlace; } } public class Lista { private Nodo primero; public Lista() { primero = null; } private int leerEntero() { BufferedReader en = new BufferedReader( new InputStreamReader (System.in)); int d = -1;
}
try { System.out.print(" Entero: "); d = Integer.parseInt(en.readLine()); } catch(Exception o) { System.out.print(" Error entrada: " + o); } return d;
public Lista crearLista() { int x;
primero = null; do { x = leerEntero(); if (x != -1) { primero = new Nodo(x,primero); } }while (x != -1); return this; }
}
EJERCICIO 8.1 package ListaEnteros; // clase Nodo con las dos partes de un nodo y su constructor public class Nodo { int dato; Nodo enlace; public Nodo(int x) { dato = x; enlace = null; } } /* clase Lista con las operaciones: insertar por la cabeza y visualizar (recorre los nodos) para mostrar los datos. Además, el atributo primero, que apunta al primer nodo. */ package ListaEnteros; public class Lista { private Nodo primero; public Lista() { primero = null; } public Lista insertarCabezaLista(int entrada) { Nodo nuevo ; nuevo = new Nodo(entrada); nuevo.enlace = primero; primero= nuevo; return this; } public void visualizar() { Nodo n; int k = 0;
}
n = primero; while (n != null) { System.out.print(n.dato + " "); n = n.enlace; k++; System.out.print( (k%15 != 0 ? " " : "\n")); }
} // clase con método main import java.util.*; import ListaEnteros.*;
public class ListaAleatoria { public static void main(String [] a) { Random r; int d; Lista lista; int k; r = new Random(); lista = new Lista(); // crea lista vacía k = Math.abs(r.nextInt() % 55); // número de nodos // Son insertados elementos en la lista for (; k > 0; k-- ) { d = r.nextInt() % 99 ; lista.insertarCabezaLista(d); } // recorre la lista para escribir sus elementos System.out.println("Elementos de la lista generados al azar"); lista.visualizar(); }
}
EJERCICIO 8.2 import java.util.*; import ListaEnteros.ListaOrdenada; public class ListaEnOrden { public static void main(String [] a) { Random r; int d; ListaOrdenada lista; int k; r = new Random(); // generador de números aleatorios lista = new ListaOrdenada(); // crea lista vacía k = r.nextInt(99)+1; // número de elementos // inserta elementos en la lista for (; k >= 0; k-- ) { d = r.nextInt(); lista.insertaOrden(d); } // escribe los elementos de la lista System.out.println("Elementos de la lista ordenada \n"); lista.visualizar(); }
}
EJEMPLO 8.4 public Nodo buscarPosicion(int posicion) { Nodo indice; int i;
}
if (0 < posicion) // posición ha de ser mayor que 0 return null; indice = primero; for (i = 1 ;(i < posicion) && (indice != null); i++) indice = indice.enlace; return indice;
EJERCICIO 8.3 import java.util.Random; import java.io.*; import listaDobleEnlace.*; class ListaEnRango { public static void main(String [] ar) throws IOException { Random r; int d, x1,x2; final int M = 29; // número de elementos de la lista final int MX = 999; BufferedReader entrada = new BufferedReader( new InputStreamReader(System.in)); ListaDoble listaDb; r = new Random(); listaDb = new ListaDoble(); for (int j = 1; j <= M ; j++) { d = r.nextInt(MX) + 1; listaDb.insertarCabezaLista(d); } System.out.println("Elementos de la lista original"); listaDb.visualizar(); // rango de valores System.out.println("\nRango que va a contener la lista"); x1 = Integer.parseInt(entrada.readLine()); x2 = Integer.parseInt(entrada.readLine()); // IteradorLista iterador = new IteradorLista(listaDb); Nodo a;
} }
a = iterador.siguiente(); while (a != null) { int w; w = a.getDato(); if (!(w >= x1 && w <= x2)) // fuera de rango listaDb.eliminar(w); a = iterador.siguiente(); } System.out.println("Elementos actuales de la lista"); listaDb.visualizar();
EJERCICIO 8.4 package listaCircularPalabra; class Nodo { String dato; Nodo enlace; public Nodo (String entrada) {;} } public class ListaCircular { private Nodo lc; public ListaCircular(){;} public ListaCircular insertar(String entrada){;} public void eliminar(String entrada) { Nodo actual; actual = lc; while ((actual.enlace != lc) && !(actual.enlace.dato.equals(entrada))) { if (!actual.enlace.dato.equals(entrada)) actual = actual.enlace; } // Enlace de nodo anterior con el siguiente // si se ha encontrado el nodo.
}
if (actual.enlace.dato.equals(entrada)) { Nodo p; p = actual.enlace; // Nodo a eliminar if (lc == lc.enlace) // Lista con un solo nodo lc = null; else { if (p == lc) { lc = actual; // Se borra el elemento referenciado por lc, // el nuevo acceso a la lista es el anterior } actual.enlace = p.enlace; } p = null; }
public void borrarLista() { Nodo p; if (lc != null) { p = lc; do { Nodo t; t = p; p = p.enlace; t = null; // no es estrictamente necesario
}while(p != lc); } else System.out.println("\n\t Lista vacía."); lc = null; } public void recorrer(){;} } /* clase con el método main(). Se escribe un sencillo menu para elegir operaciones con la lista circular. */ import java.io.*; import listaCircularPalabra.*; class ListaPalabras { public static void main(String [] a) throws IOException { String palabra; ListaCircular listaCp; int opc; BufferedReader entrada = new BufferedReader( new InputStreamReader(System.in)); listaCp = new ListaCircular(); System.out.println("\n Entrada de Nombres. Termina con ^Z.\n"); while ((palabra = entrada.readLine())!= null) { String nueva; nueva = new String(palabra); listaCp.insertar(nueva); } System.out.println("\t\tLista circular de palabras"); listaCp.recorrer(); System.out.println("\n\t Opciones para manejar la lista"); do { System.out.println("1. Eliminar una palabra.\n"); System.out.println("2. Mostrar la lista completa.\n"); System.out.println("3. Salir y eliminar la lista.\n"); do { opc = Integer.parseInt(entrada.readLine()); }while (opc<1 || opc>3);
} }
switch (opc) { case 1: System.out.print("Palabra a eliminar: "); palabra = entrada.readLine(); listaCp.eliminar(palabra); break; case 2: System.out.println("Palabras en la Lista:\n"); listaCp.recorrer(); break; case 3: System.out.print("Eliminación de la lista."); listaCp.borrarLista(); } }while (opc != 3);
LISTA ORDENADA package ListaEnteros; public class ListaOrdenada extends Lista { public ListaOrdenada() { super(); } public ListaOrdenada insertaOrden(int entrada) { Nodo nuevo ; nuevo = new Nodo(entrada); if (primero == null) // lista vacía primero = nuevo; else if (entrada < primero.getDato()) { nuevo. setEnlace(primero); primero = nuevo; } else /* búsqueda del nodo anterior a partir del que se debe insertar */ { Nodo anterior, p; anterior = p = primero; while ((p.getEnlace() != null) && (entrada > p.getDato())) { anterior = p; p = p.getEnlace(); } if (entrada > p.getDato()) //inserta después del último nodo anterior = p; // Se procede al enlace del nuevo nodo nuevo.setEnlace(anterior.getEnlace()); anterior.setEnlace(nuevo); } return this; } // métodos a codificar: public void eliminar (int entrada){ ; } public Nodo buscarLista(int destino){ ; } }
LISTA DOBLEMENTE ENLAZADA package listaDobleEnlace; public class Nodo { int dato; Nodo adelante; Nodo atras; public Nodo(int entrada) { dato = entrada; adelante = atras = null; } public int getDato() {
return dato; } public Nodo getEnlace() { return adelante; } public void setEnlace(Nodo adelante) { this.adelante = adelante; } } package listaDobleEnlace; public class ListaDoble { Nodo cabeza; public ListaDoble() { cabeza = null; } public ListaDoble insertarCabezaLista(int entrada) { Nodo nuevo; nuevo = new Nodo(entrada); nuevo.adelante = cabeza; if (cabeza != null ) cabeza.atras = nuevo; cabeza = nuevo; return this; } public ListaDoble insertaDespues(Nodo anterior, int entrada) { Nodo nuevo; nuevo = new Nodo(entrada); nuevo.adelante = anterior.adelante; if (anterior.adelante !=null) anterior.adelante.atras = nuevo;
anterior.adelante = nuevo; nuevo.atras = anterior; return this; } public void eliminar (int entrada) { Nodo actual; boolean encontrado = false; actual = cabeza; // Bucle de búsqueda while ((actual != null) && (!encontrado)) { /* la comparación se realiza con el método equals()..., depende del tipo Elemento */ encontrado = (actual.dato == entrada); if (!encontrado) actual = actual.adelante; } // Enlace de nodo anterior con el siguiente if (actual != null) { //distingue entre nodo cabecera o resto de la lista if (actual == cabeza) { cabeza = actual.adelante; if (actual.adelante != null) actual.adelante.atras = null; } else if (actual.adelante != null) // No es el último nodo { actual.atras.adelante = actual.adelante; actual.adelante.atras = actual.atras; } else // último nodo actual.atras.adelante = null; actual = null; }
}
public void visualizar() { Nodo n; int k = 0; n = cabeza; while (n != null) { System.out.print(n.dato + " "); n = n.adelante; k++; System.out.print( (((k%10 != 0)&& (n!= null)) ? " " : "\n")); } }
}
ITERADOR DE LISTA DOBLE package listaDobleEnlace; public class IteradorLista { Nodo actual; public IteradorLista(ListaDoble ld) { actual = ld.cabeza; } public Nodo siguiente() { Nodo a; a = actual; if (actual != null) { actual = actual.adelante; } return a; } }
LISTA GENÉRICA // Declaración de la clase nodo package listaGenerica; public class Nodo { Object dato; Nodo enlace; public Nodo(Object x) { dato = x; enlace = null; } public Nodo(Object x, Nodo n) { dato = x; enlace = n; } public Object leerDato() { return dato; } public Nodo siguiente() { return enlace; } } // Declaración de la clase Lista. package listaGenerica; public class Lista { private Nodo primero; public Lista() { primero = null; } public Nodo leerPrimero() { return primero; } public Lista insertarCabezaLista(Object entrada) { Nodo nuevo ; nuevo = new Nodo(entrada) nuevo.enlace = primero; primero= nuevo; return this; } public Nodo leerPrimero() { return primero; } public Lista insertarLista(Nodo anterior, Object entrada) { Nodo nuevo;
nuevo = new Nodo(entrada); nuevo.enlace = anterior.enlace anterior.enlace = nuevo; return this; } public void eliminar (Object entrada) { Nodo actual, anterior; boolean encontrado; actual = primero; anterior = null; encontrado = false; // Bucle de búsqueda while ((actual!= null) && !actual.dato.equals(entrada)) { if (!actual.dato.equals(entrada)) { anterior = actual; actual = actual.enlace; } } if (actual != null) { // Se distingue entre que el nodo sea el cabecera // o del resto de la lista if (acual == primero) { primero = actual.enlace; } else { anterior.enlace = actual.enlace } actual = null; } }
}
public Nodo buscarLista(Object destino) // destino: dato que se busca en la lista. { Nodo indice; for (indice = primero; indice != null; indice = indice.enlace) if (indice.dato.equals(destino)) return indice; return null; } public void visualizar() { Nodo n; n = primero; while (n != null) { Sistem.out.print(n.dato + " "); n = n.enlace; } }
ITERADOR LISTA GENÉRICA package listaGenerica; public class ListaIterador { private Nodo prm, actual; public ListaIterador(Lista list) { prm = actual = list.leerPrimero(); }
}
public Object siguiente() { Object elemento = null; if (actual != null) { elemento = actual.leerDato(); actual = actual.siguiente(); } return elemento; } public void inicIter() { actual = prm; }