Download Listas PPT
Document related concepts
no text concepts found
Transcript
Diplomado en Informática Aplicada Asignatura: Estructura de Datos Avanzada Tema: Listas Centro de Estudio de Ingeniería de Sistemas (CEIS) Instituto Superior Politécnico “José Antonio Echeverría” (CUJAE) Tema 2: Listas Contenido • Tipo de Dato Abstracto (TDA). • Listas lineales. • Tipos de implementaciones de listas. • Pilas y Colas. • Implementación en C++ y Java. Bibliografía • Data Structures / Algorithms in Java. Robert Lafore. Páginas: 33-247. • El C++. Lenguaje de Programación. Bjarne Stroustrup. Páginas 143-180. Tipo de Dato Abstracto Un Tipo de Dato Abstracto (TDA) se define como un modelo matemático con un conjunto de operaciones que se definen sobre este modelo. Define un tipo de dato e incluye la descripción de todo el comportamiento asociado al dato. No está asociado a ninguna implementación. El implementar un TDA supone la traducción de las especificaciones del TDA en las sintaxis de un lenguaje de programación en particular. Tipo de Dato Abstracto Al implementar un TDA en la POO, se debe encapsular toda la lógica de almacenamiento y lograr que la comunicación sea a través de los métodos de acceso que se definen en la interfaz pública de la implementación del TDA. Conceptos básicos Se denomina Nodo, elemento o también ítem, a la unidad de información más elemental o indivisible. TDA Lista Lineal Una lista lineal es un conjunto de N nodos l1, l2, … ln, con n 0, cuyas propiedades estructurales esenciales incluyen sólo las posiciones lineales (unidimensionales) relativas de los nodos; para ella se definen operaciones como las siguientes: • Tener acceso a un nodo. • Insertar y eliminar un nodo en la lista. • Combinar dos o más listas en una. • Dividir una lista en dos o más listas. • Determinar la cantidad de nodos de la lista. • Ordenar la lista de acuerdo a un criterio. • Buscar un elemento bajo una condición. TDA Lista Lineal Aclaraciones: • n = 0 denota a la lista vacía, o sea, una lista que no tiene elementos. • Si n > 0, l1 es el primer nodo. • Si 1 < k < n, lk es precedido por el nodo lk+1 y seguido por el nodo lk+1. • Si n > 0, IN es el último nodo. TDA Lista Lineal Una misma definición de un TDA puede conllevar a implementaciones diferentes en dependencia de las necesidades, así como de las características del lenguaje en el que se va a desarrollar dicha implementación. Por su forma de almacenamiento, la lista lineal se puede implementar en una de las siguientes disposiciones: • Secuencial • Enlazada Lista Secuencial Una de las formas más simples de implementación de este TDA es usando un arreglo unidimensional. Todos los elementos de la lista se almacenan en posiciones de memoria consecutivas. Por se habla de disposición secuencial en la memoria de la computadora. A la lista se le conoce como lista secuencial. Lista Secuencial ... 1 2 3 Índice del último nodo de la lista 4 5 N Cantidad física de elementos del arreglo Ventajas y desventajas Ventajas Con esta disposición se accede a cualquier elemento de la estructura de datos en tiempo constante. Desventajas Al asignar el arreglo en tiempo de compilación debe establecerse un límite a priori sobre el número de elementos que pueden ser almacenados en las listas. Para inserciones y eliminaciones frecuentes hay que hacer corrimientos costosos. Lista enlazada En una lista enlazada se asigna memoria para el almacenar los elementos de la lista conforme se va necesitando, es decir a medida que se añaden o insertan los elementos, y se conectan los elementos de la lista con punteros. La memoria es liberada cuando ya no se necesita más un elemento en la lista. Esquemáticamente una lista enlazada se representa por una secuencia de nodos conectados por enlaces. Lista enlazada primero Cada nodo está conectado al siguiente por un solo enlace, a esta estructura de datos se llama lista simplemente enlazada. Lista enlazada •Un nodo de una lista simplemente enlazada contiene dos campos: datos (contiene un elemento de la lista) y siguiente (almacena un enlace al siguiente nodo de la lista). •El campo siguiente del último nodo contiene un símbolo especial que indica el final de las lista. •Se accede a la lista por medio de un apuntador al primer elemento y solo se puede recorrer la lista en un sentido, del primer nodo al último nodo. Lista doblemente enlazada •… primero Cada nodo contiene tres campos: un campo que almacena el elemento de la lista y los otros dos almacenan los enlaces a los nodos precedente y siguiente de la lista. Se usan punteros extremos de la lista. nulos para marcar ambos Lista enlazada circular primero El campo siguiente del último nodo de la lista apunta al primer nodo de la lista. Lista doblemente enlazada circular primero •… El campo siguiente del último nodo apunte al primer nodo de la lista y el campo anterior del primer nodo apunte al último nodo de la lista. Ventajas y desventajas Ventajas No es preciso conocer la cantidad de elementos en tiempo de compilación. Ni las inserciones ni las eliminaciones implican realizar corrimientos de los elementos de la lista. Desventajas No permite el acceso directo a un elemento arbitrario de la lista. Para acceder al i-ésimo elemento, debemos recorrer la lista, comenzando por el primer nodo, hasta llegar al elemento deseado. primero (tope) Pila Una pila (stack) es un conjunto dinámico que obedece al orden LIFO. La pila es un caso particular de lista en la que todas las inserciones y extracciones de elementos se realizan por un solo extremo, llamado el tope de la pila. Operaciones en pilas Estas operaciones reciben nombres especiales: •Insertar (x). Inserta x en S. (Apilar o Push). •Tope. Devuelve el elemento que fue insertado más recientemente en S. (Cima). •Eliminar. Devuelve el elemento que fue insertado más recientemente y lo elimina. (Desapilar o Pop). •Vacía. Devolver si la pila está vacía. Cola primero Una cola (queue) es un conjunto dinámico que obedece al orden FIFO. La cola es un caso particular de lista para la que todas las inserciones se realizan siempre por un extremo y las extracciones se realizan siempre por el extremo opuesto. último Operaciones en colas Estas operaciones reciben nombres especiales: •Insertar (x). Inserta x en la cola. •Primero. Devuelve el elemento que lleva más tiempo en la cola. •Eliminar. Devuelve el elemento que lleva más tiempo en la cola y lo elimina. (Avanzar) •Vacía. Devolver si la cola está vacía. Ejemplos Un ejemplo de pila lo constituye el mecanismo que establecen los lenguajes de programación para garantizar las llamadas anidadas a subprogramas dentro de una aplicación. Un ejemplo de cola es la cola de impresión en el sistema operativo Windows. Cada usuario de una red de Windows coloca sus trabajos de impresión y el sistema lo imprime en el mismo orden en que fueron insertados en la cola de impresión. Cola secuencial ... 0 Índice del primer elemento 1 2 3 4 N-1 Índice del último elemento Cantidad física de elementos Cola secuencial •No hay correspondencia entre la posición del último nodo y la cantidad de nodos de la cola. •La condición de cola llena y de cola vacía, no se pueden verificar haciendo uso del índice del arreglo. Cola circular 0 1 N-1 . 2 . 3 13 4 12 5 11 6 10 7 9 8 La cola circular propone tratar el arreglo como un círculo donde cuando aLength se hace igual a aSize, el siguiente elemento es el de índice 0. Esto permite utilizar todos los espacios que quedan libres en el arreglo luego de realizar eliminaciones de nodos. Implementación en C++ •TBaseList •TSeqList •TGSeqList •TLinkedList •TGLinkedList •TDoubleList •TNode •TDoubleCirc •TDoubleNode •TCircLinked Iteradores en Java Los iteradores son objetos que contienen referencias a los elementos en la estructura de datos para atravesar esta estructura. Iteradores en Java class ListIterator { private Node aCursor; private Node aPrevios; private LinkedList aList; public ListIterator(LinkedList list) { aList = list; reset(); } public void reset(){ aCursor = aLIst.getFirst(); aprevios = null; } public void nextNode() { aPrevios = aCursor; aCursor = cursor.aNext; } … } Iteradores en Java class ListIterator { … public Node getCursor() { return aCursor; } public boolean atEnd() { return (aCursor.aNext == null); } } Iteradores en Java class ListIterator { … public void insertAfter(int 2) { Node node = new Node(3); if (aList.isEmpty()) { aList.setFirst(node); aCursor =node; } else { node.aNext = aCursor.aNext; aCursos.aNext = node; nextNode(); } } } Iteradores en Java Agregar un método a LinkedList class LinkedList { … public ListIterator getIterator() { return new ListIterator(this); } } Iteradores en Java } public static void main(String[] args){ LinKedList list = new LinkedList(); ListIterator it = list.getIterator(); it.insertAfter(21); it.insertAfter(8); it.insertAfter(24); list.displayList(); Facilidades de los lenguajes Los lenguajes de programación proporcionan utilidades que permiten al desarrollador crear estructuras de datos. Java posee el API Collections. Se introdujo con la Java2SE (versión 1.2 de Java Standar Edition) Objetivo: proporcionar clases, interfaces y algoritmos para utilizar las estructuras de una manera estandar. Base del API Collections de Java Collection List Set Map SortedMap SortedSet Conjunto de interfaces que forman la base del API Collections. API Collections de Java La jerarquía tiene dos raíces: Collection trabaja sobre conjuntos de elementos singulares. Map trabaja sobre pares de valores. Interfaz Collection boolean add(Object element) boolean remove(Object element) int size() boolean isEmpty() boolean contains(Object element) Iterator iterator() boolean containsAll(Collection collection) boolean addAll(Collection collection) void clear() void removeAll(Collection collection) void retainAll(Collection collection) Interfaz Collection Collection es una interfaz (no proporciona ninguna implementación concreta). La base para las clases concretas del API se encuentra en la clase AbstractCollection. Para crear estructuras se debe: 1. Crear una clase que implemente todos los métodos de Collection. 2. Crear una clase que herede de AbstractCollection e implemente los métodos necesarios, como por ejemplo size(). Interfaz List Define un conjunto de datos ordenados permitiendo elementos duplicados. Añade operaciones con índice y la posibilidad de trabajar con una parte de la lista. void add(int index, Object element) boolean addAll(int index, Collection collection) Object get(int index) int indexOf(Object object) int lastIndexOf(Object object) Object remove(int index) Object set(int index, Object element) Interfaz List ListIterator listIterator() ListIterator listIterator(int comienzo) List sublist(int inicio, int fin) Los dos primeros métodos devuelven una vista de la colección de datos (Iterator) que permiten recorrer sus elementos. La interfaz ListIterator extiende a Iterator permitiendo realizar recorridos bidireccionales, añadir o modificar elementos de la colección. Ejemplo List list = ......... ListIterator iterador = list.listIterator(list.size()); while (iterator.hasPrevious()) { Object element = iterator.previous(); System.out.println(element); } Se crea un iterador cuyo cursor se encuentra en la última posición de la lista. Se recorre la lista en orden inverso mostrando los elementos por pantalla. La combinación de List-ListIterator proporciona una forma elegante de recorrer la estructuras de datos. Interfaz List En el API Collections dispone de implementaciones concretas de la interfaz List: dos • ArrayList (Vector en Java 1.1 con métodos sincronizados) • LinkedList. List ArrayList LinkedList Clases ArrayList y LinkedList ArrayList: No tiene ningún método sincronizado (soporta el acceso concurrente a los datos). Se representa internamente utilizando un array de objetos. Comienza con un tamaño que se puede especificar en el constructor. Cuando se llena, aumenta su tamaño en un 50% o 100% dependiendo del SDK. LinkedList: Está implementada mediante una lista de nodos doblemente enlazada. Ejemplo import java.util.*; public class Ejemplo { public static void main(String[] args) { List list = new ArrayList(); list.add(“Liz”); Salida: list.add(“Rosa”); [Liz, Rosa, Marta, Luis] list.add(“Marta”); Liz Rosa Marta Luis list.add(“Luis”); System.out.println(list); List list1 = new LinkedList(list); Iterator it = list1.iterator(); while (it.hasNext()) { System.out.print(it.next() + “ ”); } } } Interfaz Set Hereda de Collection y no añade ningún método. Representa un conjunto de datos (sin duplicados). Si se intenta añadir un elemento que ya se encontraba, no se producirá ningún cambio. Para determinar si un dato ya se encuentra se basan en los métodos de la clase Object: equals() y hashCode(). El API de Collections proporciona implementaciones de esta interfaz : HashSet y TreeSet. dos Interfaz Set Set HashSet TreeSet AbstractSet HashSet y TreeSet son implementaciones de la interfaz Set. AbstractSet implementa algunos métodos de la interfaz Set y sobreescribe los métodos equals y el método hashCode(). Interfaz Set Implementa el conjunto de datos utilizando un tabla hash (HashMap). Los elementos no están ordenados y pueden variar la posición por las operaciones de balanceo. Al basarse en una tabla hash para añadir objetos propios hay que sobreescribir el método hashCode(). Por defecto, dos elementos se consideren iguales si: • Devuelven true al utilizar equals • Devuelven el mismo hashCode() Interfaz Set class MyObject { private int aValue = -1; public MyObject(int pValue) { this.aValue = pValue; } public boolean equals(Object pObj) { if (!(pObj instanceof MyObject)) return false; if (((MyObject)pObj).value == this.aValue) return true; else return false; } } Interfaz Set Set set = new HashSet(); set.add(new MyObject(5)); false set.add(new MyObject(7)); System.out.println(set.contains(new MyObject(5)); Se creó una clase MyObject y se sobreescribió el método equals(). Así dos instancias son iguales si tienen el mismo valor pero no se sobre escruibió el método hashCode(). Por lo tanto, contains() devuelve false porque se le pasa una instancia diferente (hashCode diferente que el de la instancia del conjunto con valor 5). Interfaz Set class MyObject { private int aValue = -1; public MyObject(int pValue) { this.aValue = pValue; } public boolean equals(Object pObj) { if (!(pObj instanceof MyObject)) return false; if (((MyObject)pObj).value == this.aValue) return true; else return false; Sobreescribir } hasCode() public int hashCode() { return aValue; } } Interfaz TreeSet Esta implementación utiliza un TreeMap para almacenar los objetos. Los objetos se guardan ordenados ascendentemente según el orden del comparador que se pase en el constructor. El comparador debe ser consecuente con el método equals() de los elementos del conjunto ya que el funcionamiento de la estructura se basa en el método equals pero el algoritmo de ordenamiento se basa en el método compareTo() de la interfaz Comparator. Si dos objetos son iguales paar el método compareTo() lo serán para el conjunto (no se inserta) aunque el método equals() diga lo contrario. Ejemplo import java.util.*; public class Ejemplo { public static void main(String[] args) { Set set = new HashSet(); set.add(“Inés”); set.add(“Ana”); set.add(“Sonia”); set.add(“Laura”); set.add(“Rebeca”); System.out.println(set); Set sortedSet = new TreeSet(set); System.out.println(sortedSet); } Salida: } [Laura, Inés, Sonia, Rebeca, Ana] [Ana, Inés, Laura, Rebeca, Sonia] Interfaz Map Define una estructura de datos que mapea claves con valores sin permitir claves duplicadas. Object put(Object clave, Object valor) void putAll(Map mapa) void clear() Object remove(Object clave) Object get(Object clave) boolean containsKey(Object key) boolean containsValue(Object value) int size() boolean isEmpty() Set keySet() Collection values() Set entrySet() Interfaz Map La API Collections ofrece dos implementaciones de la interfaz Map: HashMap y TreeMap. Interfaz HashMap Utiliza una tabla hash. Permite el valor null tanto como clave o valor. No garantiza el orden de los elementos. Tiene dos parámetros que afectan a su rendimiento : capacidad inicial (capacidad que tiene la tabla cuando es creada) y factor de carga (medida de la cantidad que podemos dejar llenarse a la tabla antes de que su tamaño deba aumentarse. Cuando el número de entradas en la tabla excede el producto del factor de carga y la capacidad actual, se doblará la capacidad llamando al método rehash. Si la capacidad inicial es mayor que el máximo número de entradas dividido por el factor de carga, la operación de rehash nunca ocurrirá. Interfaz TreeMap La implementación de esta clase ordena los elementos por orden ascendente de clave ya sea el orden natural de los objetos o el orden establecido por el comparador que se pase en el constructor. Como ocurre en la clase TreeSet el comparador ha de ser consistente con el método equals().