• Author / Uploaded
• Drid Durand Rodriguez

Citation preview

Curso: Estructura de datos y de la información TEMA: ADT Lista - Implementación mediante Arreglos, Ejemplos Docente: Ing. Freddy Infantes Quiroz Correo:

[email protected]

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

AGENDA

• • • •

ADT Lista. ADT Lista - Operaciones. ADT Lista - Implementación mediante Arreglos Ejemplo - Farmacia

Ing. Freddy Infantes Quiroz

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

ADT LISTA Colección de datos, con las siguientes características: • Por lo general los datos son de un mismo tipo. • Cada elemento tiene asociado un índice ó posición, a través del cual se puede acceder y que lo identifica de manera única en la colección. a0 a1 a2 a3 ... aN-1 Esto quiere decir que los elementos en una lista se encuentran organizados de una manera lineal e identificados a través de una posición. No se especifica cómo están organizados físicamente en la memoria.

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

ADT LISTA - OPERACIONES • • • • • • •

Crear - crea e inicializa la lista Destruir - destruye la lista Adicionar - adiciona un nuevo elemento, al final de la lista Insertar - inserta un nuevo elemento en una posición Eliminar - elimina un elemento dada su posición Obtener - retorna un elemento dada su posición Modificar - modifica un elemento dada su posición y el nuevo valor • Cantidad - retorna la cantidad de elementos de la lista • Vacia - retorna verdadero si la lista está vacía, falso si no • Buscar - determina la posición de un elemento en la lista Nota: Estas operaciones son las únicas permitidas sobre una lista. Son independientes de cómo sea implementada

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

ADT LISTA – INTERFACE JAVA public interface TLista { void Adicionar(Object dato); void Insertar(Object dato, int pos); void Eliminar(int pos);

int boolean Object void int int

Cantidad(); Vacia(); Obtener(int pos); Modificar(Object dato, int pos); Buscar(Object dato); Buscar(Object dato, TComparar cmp);

}

• Los elementos de la lista serán de tipo Object • La operación de Crear la hará el constructor de la clase que implementa TLista • La operación Destruir no es necesaria ya que la realiza el sistema automático de recolección de basura del Java

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

ADT LISTA – IMPLEMENTACIÓN MEDIANTE ARREGLOS Campos a considerar: • El Arreglo (de Objects) que almacenará los elementos de la lista • Cantidad de elementos que están en la lista • Máximo (ó capacidad) del Arreglo

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

ADT LISTA – IMPLEMENTACIÓN MEDIANTE ARREGLOS, JAVA public class TListaA implements TLista { private Object elem[]; private int cantidad; private int max; ....... }

Constructor: public TListaA() { cantidad=0; max=0; elem=null; }

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Adicionar public void Adicionar(Object dato) { if ( cantidad == max ) Crecer(); cantidad++; elem[cantidad-1] = dato; }

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Insertar public void Insertar(Object dato, int pos) { if ( pos >= 0 && pos pos; i--) elem[i] = elem[i-1]; elem[pos] = dato; } }

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Eliminar public void Eliminar(int pos) { if ( pos >= 0 && pos < cantidad ) { for (int i = pos; i < cantidad-1; i++ ) elem[i] = elem[i+1]; cantidad--; } }

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

public int Cantidad() { return cantidad; } public boolean Vacia() { return cantidad == 0; } public Object Obtener(int pos) { if ( pos < 0 || pos >= cantidad ) pos = 0; return elem[pos]; } public void Modificar(Object dato, int pos) { if ( pos < 0 || pos >= cantidad ) pos = 0; elem[pos] = dato; }

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

public int Buscar(Object dato) { int encontrado = -1; for ( int i=0; i < cantidad && encontrado == -1; i++ ) if ( elem[i].equals( dato ) ) encontrado = i; return encontrado; } public int Buscar(Object dato, TComparar cmp) { int encontrado = -1; for ( int i=0; i < cantidad && encontrado == -1; i++ ) if ( cmp.Compara(elem[i],dato) == 0 ) encontrado = i; return encontrado; }

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Ejemplo 1. Caso de la Farmacia:

En este caso sólo analizaremos lo relacionado con la lista de Medicamentos en la Farmacia

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Ejemplo 1. (continuación) Uso de arreglos public class Farmacia { private Medicamento medics[]; private int nmedics;

Arreglo, y la cantidad

public Almacen() { Reservar espacio medics = new Medicamento[100]; (limitado a 100) nmedics = 0; } public void nvoMedicamento( Medicamento m ) { medics[nmedics++] = m; Llevar el control de la } cantidad y posición public Medicamento obtMedicamento( int i ) { return medics[i]; } public int cantidadMedicamentos() { return nmedics; } }

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Ejemplo 1. (continuación) Uso del nuevo tipo de datos implementado (TListaA) public class Farmacia { private TListaA medics; public Almacen() { medics = new TListaA(); } public void nvoMedicamento( Medicamento m ) { medics.adicionar(m); } public Medicamento obtMedicamento( int i ) { return (Medicamento)medics.obtener(i); } public int cantidadMedicamentos() { return medics.cantidad(); } }

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Ejemplo 2. Programa que permita: • • •

Adicionar elementos a una lista Listar todos los elementos Buscar por dos criterios.

Los elementos de la lista serán personas (nombre y dni) private class TPersona { String nombre; long dni; }

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Ejemplo 2. (continuación…) Clases para buscar por Nombre y por DNI private class CmpNombre implements TComparar { public int Compara(Object a, Object b) { TPersona e1 = (TPersona)a; TPersona e2 = (TPersona)b; return e1.nombre.compareTo(e2.nombre); } } private class CmpDNI implements TComparar { public int Compara(Object a, Object b) { TPersona e1 = (TPersona)a; TPersona e2 = (TPersona)b; if ( e1.dni == e2.dni ) return 0; else if ( e1.dni < e2.dni ) return -1; else return 1; } }

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Ejemplo 2. (continuación…) Algoritmo principal BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); TListaA L; TPersona per; int opc, pos; String o; L = new TListaA(); do { System.out.println("1.-Nueva Persona"); System.out.println("2.-Listar todos"); System.out.println("3.-Buscar por nombre"); System.out.println("4.-Buscar por dni"); System.out.println("0.-Salir"); System.out.print("\n Ingrese la opcion: "); o = br.readLine(); opc = Integer.valueOf(o).intValue(); switch ( opc ) { …………… } while (opc != 0);

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Ejemplo 2. (continuación…) Opciones case 1: // Nueva persona per = new TPersona(); System.out.println(""); System.out.print("Nombre: "); o = br.readLine(); per.nombre = o; System.out.print("\nDNI: "); o = br.readLine(); per.dni = Long.valueOf(o).longValue(); L.Adicionar(per); break;

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Ejemplo 1. (continuación…) Opciones case 2: // Listar todas las personas System.out.println(""); for (int i=0; i < L.Cantidad(); i++ ) { per = (TPersona)L.Obtener(i); System.out.print(i+1); System.out.print(": "); System.out.print(per.nombre); System.out.print(": "); System.out.print(per.dni); System.out.println(""); } break;

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Ejemplo 1. (continuación…) Opciones case 3: // buscar por Nombre per = new TPersona(); System.out.println(""); System.out.print("Nombre a buscar: "); o = br.readLine(); per.nombre = o; pos = L.Buscar( per, new CmpNombre() ); if ( pos >= 0 ) { System.out.print("Nombre encontrado en la posicion: ");

System.out.println(pos+1);

} else System.out.print("NO ENCONTRADO");

break;

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Ejemplo 2. (continuación…) Opciones case 4: // buscar por DNI per = new TPersona(); System.out.println(""); System.out.print("DNI a buscar: "); o = br.readLine(); per.dni = Long.valueOf(o).longValue(); pos = L.Buscar( per, new CmpDNI() ); if ( pos >= 0 ) { System.out.print("DNI encontrado en la posicion: ");

System.out.println(pos+1);

} else System.out.print("NO ENCONTRADO");

break;

UPAO : Facultad de Ingeniería Curso: Programación Orientada a Objetos Ciclo : 2014

Ventajas del uso de arreglos para implementar listas: 1. Facilidad de implementación dado que los arreglos son parte del propio lenguaje y permiten representar precisamente una colección de datos, cada uno con una posición 2. Acceso a los elementos es directo. El costo es igual para cualquier elemento, independientemente de la posición

Desventajas del uso de arreglos para implementar listas: 1. Ineficiente uso de la memoria dado que es necesario reservar un espacio que puede ser demasiado grande en algunos casos, y en otros no ser suficiente 2. Las operaciones de inserción y eliminación requieren corrimiento de los elementos, a la derecha y a la izquierda respectivamente