Estructuras de datos



Descargar 37,77 Kb.
Fecha de conversión14.03.2017
Tamaño37,77 Kb.

Alberto León Aparicio Algoritmos y Estructuras de Datos Estructuras de datos

____________________________________________________________________________________________________________________

ESTRUCTURAS DE DATOS
Un Tipo de dato abstracto (TDA) es un conjunto de datos u objetos al cual se le asocian operaciones. El TDA provee de una interfaz con la cual es posible realizar las operaciones permitidas, abstrayéndose de la manera en como estén implementadas dichas operaciones. Esto quiere decir que un mismo TDA puede ser implementado utilizando distintas estructuras de datos y proveer la misma funcionalidad.

El paradigma de orientación a objetos permite el encapsulamiento de los datos y las operaciones mediante la definición de clases e interfaces, lo cual permite ocultar la manera en cómo ha sido implementado el TDA y solo permite el acceso a los datos a través de las operaciones provistas por la interfaz.


Un programa orientado a objetos usa objetos para trabajar con datos. Estos datos objeto se organizan en estructuras de datos dependiendo de las funciones que realiza el programa. Una buena estructura de los objetos es crucial para realizar por ejemplo operaciones de búsqueda, inserción u borrado de datos.

Los lenguajes de programación orientados a objetos proporcionan estructuras de datos comunes en librerías. Las clases de estructuras de datos en java son eficientes y fáciles de usar. Estas clases estándar incluyen arreglos, vectores, pilas, diccionarios y tablas hash.


ARREGLOS
Un arreglo es una secuencia de variables o componentes del mismo tipo y las cuales son acezadas mediante un índice que en java empieza desde cero. El tamaño de un arreglo se fija cuando este es creado. El uso de un índice que cae fuera de rango del tamaño de un arreglo produce una excepción en tiempo de ejecución del tipo: ArrayIndexOutOfBoundsException. Todo arreglo es un objeto de la clase Objet, por tanto cualquier método de la clase Objet puede ser invocado por un arreglo.

Un tipo array es declarado y creado en java mediante la sintaxis:

Tipo nom_array = new tipo [tamaño]

Para obtener la longitud de un arreglo se utiliza



Nom_array.length

Java soporta arreglos multidimencionales. Por ejemplo, la expresión cliente [ ][ ] es un tipo que representa un arreglo de dos dimensiones que contendrá elementos de tipo cliente. La declaración y creación de un arreglo bidimensional se realiza de la misma forma que para los arreglos normales. Por ejemplo:

Cliente [ ] [ ] man = new Cliente[3 ][20 ]
ARREGLOS MULTIDIMENSIONALES Y POLINOMIO DE DERECCIONAMIENTO
Los registros se mapean en memoria usando la posición de sus componentes, es decir, la dirección del componente (campo) relativa a la dirección de origen del registro. Cuando se trabaja con arreglos de mas de una dimensión se le podría llamar una superestructura o estructura virtual que no se mapea directamente en la que posee la memoria de la computadora que sigue siendo un arreglo lineal (unidimensional).

El concepto de arreglo multidimensional es una generalización inmediata del concepto de arreglo lineal. Un arreglo de dos dimensiones es un arreglo de arreglos. Una matriz de m × n celdas, con m renglones y n columnas es, de hecho, un arreglo de m renglones, donde cada renglón es un arreglo de n celdas. Otra vez tenemos la restricción de que, una vez establecido el tamaño en cada dimensión este es inalterable. Sin embrago Java nos provee de la flexibilidad para diferir el establecimiento de cada uno de los tamaños siempre y cuando se haga en orden de izquierda a derecha. Por ejemplo:



int[ ][ ] matriz;

matriz = new int [nreng][];

for (i=0; i

matriz[i] = new int [ncols];

En el código diferimos la definición del tamaño del arreglo en columnas y sólo establecimos el número de renglones. Luego en el ciclo se establece el número de columnas de cada renglón visto como un arreglo por sí mismo.

Ahora el polinomio de direccionamiento calculado por el compilador es un poco más complicado. El arreglo bidimensional sigue estando en un área contigua de memoria, pero lineal, es decir los elementos del iesimo renglón se acomodan uno tras otro luego de los del renglón i − 1 en direcciones sucesivas.

Para obtener la dirección del byte inicial de la celda en la posición (ren, col) de un arreglo bidimensional de m renglones y n columnas se tendría que calcular:



dir = dir matriz + (n · ren + col) · tam

Por supuesto se pueden definir arreglos de un número arbitrario de dimensiones y se pueden acceder sus elementos haciendo uso de polinomios de direccionamiento mas complicados. En una matriz tridimensional de i × m × n (alto, ancho y largo) acomodada linealmente habría que desplazarse i x m x n celdas para llegar al piso i, luego desplazarse j n celdas para llegar al renglón j en ese piso y finalmente recorrer k celdas mas para llegar a la celda de coordenadas (i, j, k), es decir:



idx = (i · m · n + j · n + k)

sería el polinomio de direccionamiento para obtener el ´ındice, en un arreglo lineal, de la celda en cuestión.


VECTORES
Un vector organiza sus elementos al igual que un arreglo; en una secuencia y de igual forma se accesa a ellos mediante un índice.

La diferencia sustancial entre un array y un vector es que el arreglo es fijo y no puede cambiar su tamaño una vez que ha sido creado a diferencia del vector que puede expandirse o contraerse dinámicamente en respuesta a inserciones o a borrado de objetos en el. Otra diferencia corresponde a cerca de sus tipos de elementos, mientras los elementos de un arreglo pueden ser valores de un tipo primitivo, un objeto vector puede trabajar con objetos de diferentes tipos como elementos de el.

Para acceder a los elementos de un vector se utiliza el método elemental (índice). La clase vector extiende la clase Objet e implementa las interfaces Cloneable y Serializable. La clase vector define métodos para inserción, eliminación y búsqueda de objetos en vectores. Un objeto vector utiliza la noción size para denotar el número de objetos que actualmente tiene.

Un vector es creado utilizando cualquiera de sus siguientes constructores:



Vector()

Vector(int capacidad)

Vector(int capacidad, int incremento)

El primero es por default, el segundo crea un tamaño definido y el tercero define un tamaño y un incremento.

Un programa puede accesar o cambiar la capacidad de un vector con los siguientes métodos de instancia de la clase Vector: int capacidad (), void ensureCapacity(int minCapacity).

La clase Vector define métodos de instancia para accesar a los objetos almacenados en un vector tales como los siguientes: Objet firstElement(), Objet lastElement(), Objet elemental(int indice), etc. La case Vector define también métodos para modificar el contenido de un vector, por ejemplo: void addElement(Objet obj), void insertElementAt(Objet obj, int index),etc. Y también define métodos para comprobar el estado del vector como int size(), boolean isEmty() y otros.


COLAS
Una cola es una estructura de datos donde los elementos que se almacenan se van acomodando de forma tipo FIFO. Una cola siempre añade un elemento al final de la lista y remueve un elemento del principio o frente de dicha lista.

La funcionalidad FIFO de una cola puede ser implementada con los métodos de instancia de la clase Vector tales como: addElementObjet(Object obj) que añade un objeto obj al final de un vector y removeElementAt(0) que remueve el primer elemento y decrementa el tamaño de un vector en uno. Por lo anterior decimos que se puede usar una instancia de una clase vector como una cola.


COLAS DE PRIORIDAD

Una cola de prioridad es un tipo de datos abstracto que almacena un conjunto de datos que poseen una llave perteneciente a algún conjunto ordenado, y permite insertar nuevos elementos y extraer el máximo (o el mínimo, en caso de que la estructura se organice con un criterio de orden inverso).Dos formas simples de implementar colas de prioridad son:


Una lista ordenada:

    • Inserción: O(n)

    • Extracción de máximo: O(1)

Una lista desordenada:

    • Inserción: O(1)

    • Extracción de máximo: O(n)

    • PILAS

PILAS
La clase Stack del paquete java.util extiende la clase Vector con métodos de instancia que soporta el tipo LIFO. Cuando un objeto es puesto en la pila es colocado en la parte de arriba del stack y cuando un objeto es removido es el que esta en mas arriba.

La clase Stack define el constructor Stack(), esta clase hereda los métodos public y protected de la clase Vector. La propiedad LIFO de un Stack es soportada con los métodos push(Object obj) y pop para colocar y remover el objeto que esta en el tope de la pila. El método peek() de la clase Stack accesa al elemento que esta en el tope de la pila sin quitarlo de ella.


LISTAS LIGADAS
Los elementos que conforman un lista ligad son llamados nodos los cuales contienes información propia y un enlace a su sucesor (liga). Existen dos tipos de ligas: indexadas y referenciadas.

Los elementos de un array o vector pueden ser usados como una lista de nodos ligados. El índice del primer nodo en la lista ligada es mantenido en una variable (heder). Los nodos en la lista ligada pueden ser acezados a partir de header y los indices contenidos en los campos liga de los nodos.


LISTAS LIGADAS SIMPLES INDEXADAS (BASADAS EN INDICES)

La clase IndexedSinglyLinkedList tiene una clase interna Nodo definida con el código siguiente:

Class Nodo{

Object data;

Int next;

}

La clase IndexedSinglyLinkedList define dos variables de instancia: nodes y unusedNodes a través del código:



Private Nodo[ ] nodes;

Private int unusedNodes;

Cuando una instancia de la clase IndexedSinglyLinkedList es creada, un constructor inicializa la variable nodes con un array de nodos.

También se definen algunos métodos de instancia en la clase IndexedSinglyLinkedList para organizar y trabajar con los objetos tales como newList() que crea un header (cabeza) para una nueva lista ligada, addObject() que trata de encontrar un nodo no usado en el arreglo nodes y coloca un objeto dentro de el y otros mas.

LISTAS LIGADAS SIMPLES REFERENCIADAS

El termino lista ligada usualmente se refiere a una lista ligada basada en referencias o referenciada. La clase SinglyLinkedList implementa una lista ligada simple referenciada.

El conjunto de métodos de esta clase es equivalente a la clase IndexedSinglyLinkedList. Aquí mencionaremos los métodos hasMoreElements() y nextElement() para la enumeración de los datos (elementos) contenidos en una lista simple ligada.

La clase singlyLinkedList no proporciona métodos para borrar datos. Un método de borrado o eliminación busca la lista ligada simple para el nodo o dato (elemento) a ser borrado o eliminado.



HEAPS

Un heap es un árbol binario de una forma especial, que permite su almacenamiento en un arreglo sin usar punteros.

Un heap puede utilizarse para implementar una cola de prioridad almacenando los datos de modo que las llaves estén siempre ordenadas de arriba a abajo (a diferencia de un árbol de búsqueda binaria, que ordena sus llaves de izquierda a derecha). En otras palabras, el padre debe tener siempre mayor prioridad que sus hijos.

TDA Cola
Una cola es un tipo especial de lista en la cual los elementos se indertan en un extremo (el posterior) y se suprimen en el otro (el anterior o el frente). Las colas se conocen tambien como FIFO (first-in firts-out) o listas “primero en entrar, primero en salir”. Las operaciones para una cola son análogas a las de las pilas; las diferencias sustanciales consisten en que las inserciones se hacen al final de la lista, y no al principio, y en que la terminología tradicional para las colas y listas no es la misma. Se usaran las siguientes operaciones con colas:


  1. ANULA(C) convierte la cola C en una lista vacia.

  2. FRENTE(C) es una funcion que devuelve el valor del primer elemento de la cola C. FRENTE(C) se puede escribir en funcion de operaciones con listas, como RECUPERA(PRIMERI(C),C).

  3. PONE_EN_COLA(x,C) inserta el elemento x al final de la cola C. En funcion de operaciones con listas, PONE_EN_COLA(x,C) es INSERTA(x,FIN(C),C).

  4. QUITA_DE_COLA (C) suprime el primer elemento de C; es decir, QUITA_DE_COLA(C) es SUPRIME(PRIMERO(C),C).

  5. VACIA(C) devuelve verdadero si, y solo si, C es una cola vacia.

Saca_cliente




Cliente 9

Frente

Inserta_cliente





La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal