UNIVERSIDAD METROPOLITANA DE EDUCACIÓN, CIENCIAS Y TECNOLOGÍA
LIC. EN SISTEMAS Y PROGRAMACIÓN
GRUPO A-A2018
Diocelin Maribel Osorio Copri
Cedula: 5-714-1775
Estructura de Datos
INTRODUCCION
Un Tipo de dato abstracto (en adelante 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 cómo 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.
tipos de abstracción de datos
LINEALES
Un tipo abstracto de datos lineal es un tipo abstracto de datos que se puede
representar como una secuencia de elementos {a1, . . . , ai , . . . , aj , . . . , an}, donde
un conjunto finito (y corto), de elementos son elementos destacados y la única relación
entre dos elementos ai e aj , si la hubiere, es la de ser el antecesor de o el sucesor de
o TDA LISTA
Una lista se define como una serie de N elementos E1, E2, ..., EN, ordenados de
manera consecutiva, es decir, el elemento Ek (que se denomina elemento k-ésimo) es
previo al elemento Ek+1. Si la lista contiene 0 elementos se denomina como lista vacía.
Las operaciones que se pueden realizar en la lista son: insertar un elemento en la
posición k, borrar el k-ésimo elemento, buscar un elemento dentro de la lista y
preguntar si la lista está vacía.
Una manera simple de implementar una lista es utilizando un arreglo. Sin embargo, las
operaciones de inserción y borrado de elementos en arreglos son ineficientes, puesto
que para insertar un elemento en la parte media del arreglo es necesario mover todos
los elementos que se encuentren delante de él, para hacer espacio, y al borrar un
elemento es necesario mover todos los elementos para ocupar el espacio desocupado.
Una implementación más eficiente del TDA se logra utilizando listas enlazadas.
A continuación se presenta una implementación en Java del TDA utilizando listas
enlazadas y sus operaciones asociadas:
Esta Vacía(): devuelve verdadero si la lista está vacía, falso en caso contrario.
insertar(x, k): inserta el elemento x en la k-ésima posición de la lista.
buscar(x): devuelve la posición en la lista del elemento x.
buscar (k): devuelve el k-ésimo elemento de la lista.
eliminar(x): elimina de la lista el elemento x.
En la implementación con listas enlazadas es necesario tener en cuenta algunos
detalles importantes: si solamente se dispone de la referencia al primer elemento, el
añadir o remover en la primera posición es un caso especial, puesto que la referencia a
la lista enlazada debe modificarse según la operación realizada. Además, para eliminar
un elemento en particular es necesario conocer el elemento que lo antecede, y en este
caso, ¿qué pasa con el primer elemento, que no tiene un predecesor?
Para solucionar estos inconvenientes se utiliza la implementación de lista enlazada con
nodo cabecera. Con esto, todos los elementos de la lista tendrán un elemento previo,
puesto que el previo del primer elemento es la cabecera. Una lista vacía corresponde,
en este caso, a una cabecera cuya referencia siguiente es null.
Los archivos [Link], [Link] y [Link] contienen una
implementación completa del TDA lista. La clase Nodo Lista implementa los nodos de
la lista enlazada, la clase Lista implementa las operaciones de la lista propiamente tal, y
la clase Iterador Lista implementa objetos que permiten recorrer la lista y posee la
siguiente interfaz:
avanzar(): avanza el iterador al siguiente nodo de la lista.
obtener(): retorna el elemento del nodo en donde se encuentra el iterador.
Costo de las operaciones en tiempo:
Insertar/eliminar elemento en k-ésima posición: O(k) (¿Se puede hacer en O(1)?).
Buscar elemento x: O(N) (promedio).
o TDA PILA
Una pila (stack o pushdown en inglés) es una lista de elementos de la cual sólo se
puede extraer el último elemento insertado. La posición en donde se encuentra dicho
elemento se denomina tope de la pila. También se conoce a las pilas como listas
LIFO (LAST IN - FIRST OUT: el último que entra es el primero que sale).
La interfaz de este TDA provee las siguientes operaciones:
apilar(x): inserta el elemento x en el tope de la pila (push en inglés).
desapilar(): retorna el elemento que se encuentre en el tope de la pila y lo
elimina de ésta (pop en inglés).
tope(): retorna el elemento que se encuentre en el tope de la pila, pero sin
eliminarlo de ésta (top en inglés).
Esta Vacía(): retorna verdadero si la pila no contiene elementos, falso en caso
contrario (isEmpty en inglés).
Implementación utilizando arreglos
Para implementar una pila utilizando un arreglo, basta con definir el arreglo del tipo de
dato que se almacenará en la pila.
class Pila Arreglo{
private Object[] arreglo;
private int tope;
private int MAX_ELEM=100; // máximo número de elementos en la pila
public Pila Arreglo() {
arreglo=new Object[MAX_ELEM];
tope=-1; // inicialmente la pila está vacía }
public void apilar(Object x) {
if (tope+1<MAX_ELEM) // si está llena se produce OVERFLOW {
tope++;
arreglo[tope]=x; }
}
public Object desapilar() {
if (!está Vacía()) // si esta vacía se produce UNDERFLOW {
Object x=arreglo[tope];
tope--;
return x;}
public Object tope() {
if (!está Vacía()) // si esta vacía es un error {
Object x=arreglo[tope];
return x; }
} public boolean está Vacía () {
if (tope==-1) {
return true; }
else {
return false;
}
TDA COLA
Una cola (que en inglés) es una lista de elementos en donde siempre se insertan
nuevos elementos al final de la lista y se extraen elementos desde el inicio de la lista.
También se conoce a las colas como listas FIFO (FIRST IN - FIRST OUT: el primero
que entra es el primero que sale).
Las operaciones básicas en una cola son:
encolar(x): inserta el elemento x al final de la cola (que en inglés).
sacar(): retorna el elemento que se ubica al inicio de la cola (que en inglés).
Esta Vacía(): retorna verdadero si la cola está vacía, falso en caso contrario.
Al igual que con el TDA pila, una cola se puede implementar tanto con arreglos como
con listas enlazadas. A continuación se verá la implementación usando un arreglo.
Las variables de instancia necesarias en la implementación son:
primero: indica el índice de la posición del primer elemento de la cola, es decir, la
posición el elemento a retornar cuando se invoque sacar.
ultimo: indica el índice de la posición de último elemento de la cola. Si se
invoca encolar, el elemento debe ser insertado en el casillero siguiente al que indica la
variable.
numElem: indica cuántos elementos posee la cola. Definiendo MAX_ELEM como el
tamaño máximo del arreglo, y por lo tanto de la cola, entonces la cola está vacía
si numElem==0 y está llena si numElem==MAX_ELEM.
Un detalle faltante es el siguiente: ¿qué pasa si la variable ultimo sobrepasa el rango
de índices del arreglo? Esto se soluciona definiendo que si después de insertar un
elemento el índice ultimo == MAX_ELEM, entonces se asigna ultimo = 0 , y los
siguientes elementos serán insertados al comienzo del arreglo. Esto no produce ningún
efecto en la lógica de las operaciones del TDA, pues siempre se saca el elemento
referenciado por el índice primero, aunque en valor absoluto primero > ultimo. Este
enfoque es conocido como implementación con arreglo circular, y la forma más fácil de
implementarlo es haciendo la aritmética de subíndices módulo MAX_ELEM.
class ColaArreglo
{
private Object[] arreglo;
private int primero, ultimo, numElem;
private int MAX_ELEM=100; // máximo número de elementos en la cola
public ColaArreglo()
{
arreglo=new Object[MAX_ELEM];
primero=0;
ultimo=-1;
numElem=0;
}
public void encolar(Object x)
{
if (numElem<=MAX_ELEM) // si esta llena se produce OVERFLOW
{
ultimo=(ultimo+1)%MAX_ELEM;
arreglo[ultimo]=x;
numElem++;
}
}
public Object sacar()
{
if (!está Vacía()) // si esta vacía se produce UNDERFLOW
{
Object x=arreglo[primero];
primero=(primero+1)%MAX_ELEM;
numElem--;
return x;
}
}
public boolean está Vacía()
{
return num_elem==0;
}
}
Nuevamente en este caso, dependiendo de la aplicación, se debe definir qué hacer en
caso de producirse OVERFLOW o UNDERFLOW.
Con esta implementación, todas las operaciones del TDA cola tienen costo O(1).
NO LINEALES
ARBOL
Una estructura de árbol con tipo base Valor es: (i) Bien la estructura vacía. (ii) Un
conjunto finito de uno o más nodos, tal que existe un nodo especial, llamado nodo raíz,
y donde los restantes nodos están separados en n≥0 conjuntos disjuntos, cada uno de
los cuales es a su vez un árbol (llamados subárboles del nodo raíz). La definición
implica que cada nodo del árbol es raíz de algún subárbol contenido en el árbol
principal.
EJEMPLOS DE ARBOL
Árboles de grado 2. Definición: Un árbol binario es un conjunto finito de nodos que
puede estar vacío o consistir en un nodo raíz y dos árboles binarios disjuntos, llamados
subárbol izquierdo y subárbol derecho
Propiedades de los Árboles Binarios
. El número máximo de nodos en el nivel (profundidad) i de un árbol binario es
2i-1, i≥1, y el número máximo de nodos en un árbol binario de altura k es 2k-1,
k≥1.
.Para cualquier árbol binario no vacío, si n0 es el número de nodos terminales y
n2 es el número de nodos de grado 2, entonces se cumple que n0 = n2 +1.
TAD ÁRBOL BINARIO
Insertar (ArbolB, Elemento) → ArbolB
Efecto: Introduce en el ArbolB un nuevo nodo cuyo valor está dado por el Elemento
pasado.
Excepción: Árbol lleno en implementa. estática.
Suprimir (ArbolB, Elemento) → ArbolB
Efecto: Borra del árbol binario el nodo cuyo valor coincide con el que se pasa en
Elemento, si éste existe.
Excepción: Error si el árbol binario está vacío.
Izquierdo (ArbolB) → ArbolB
Efecto: Devuelve el hijo izquierdo del árbol binario pasado como entrada.
Excepción: Error si el árbol binario está vacío.
Derecho (ArbolB ) → ArbolB
Efecto: Devuelve el hijo derecho del árbol binario pasado como entrada.
Excepción: Error si el árbol binario está vacío.
Raíz (ArbolB) → Elemento
Efecto: Devuelve el Elemento contenido en el nodo raíz del árbol binario pasado como
entrada. Excepción: Error si el árbol binario está vacío.
GRAFOS
Un grafo en el ámbito de las ciencias de la computación es un tipo abstracto de
datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un
conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto
de grafo TAD desciende directamente del concepto matemático de grafo.
Formalmente, un grafo se define como {\displaystyle G=(V,E)} , siendo V
un conjunto cuyos elementos son los vértices del grafo y, E uno cuyos elementos son
las aristas (edges en inglés), las cuales son pares (ordenados si el grafo es dirigido) de
elementos en V.
Formas de representación
Existen diferentes implementaciones del tipo grafo: con una matriz de
adyacencias (forma acotada) y con listas y multilistas de adyacencia (no acotadas).
Matriz de adyacencias: se asocia cada fila y cada columna a cada nodo del grafo,
siendo los elementos de la matriz la relación entre los mismos, tomando los valores de
1 si existe la arista y 0 en caso contrario.
Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos
aquellos nodos que sean adyacentes a él.
Especificación de los tipos abstractos de datos de un grafo no dirigido
Generadores
Crear un grafo vacío: Devuelve un grafo vacío.
op crearGrafo : -> Grafo [ctor] .
Añadir una arista: Dado un grafo, añade una relación entre dos nodos de dicho grafo.
op añadirArista : Grafo Nodo Nodo -> [Grafo] [ctor] .
Añadir un nodo: Dado un grafo, incluye un nodo en él, en caso en el que no exista
previamente.
op añadirNodo : Grafo Nodo -> Grafo [ctor] .
Constructores
Borrar nodo: Devuelve un grafo sin un nodo y las aristas relacionadas con él. Si dicho
nodo no existe se devuelve el grafo inicial.
op borrarNodo : Grafo Nodo -> Grafo .
Borrar arista: Devuelve un grafo sin la arista indicada. En caso de que la arista no
exista devuelve el grafo inicial.
op borrarArista : Grafo Nodo Nodo -> Grafo .
Selectores
Grafo Vacío: Comprueba si un grafo no tiene ningún nodo.
op esVacio : Grafo -> Bool .
Contener Nodo: Comprueba si un nodo pertenece a un grafo.
op contiene : Grafo Nodo -> Bool .
Adyacentes: Comprueba si dos nodos tienen una arista que los relacione.
op adyacentes : Grafo Nodo Nodo -> Bool .
Para la especificación de un grafo dirigido tenemos que modificar algunas de las
ecuaciones de las operaciones borrarArista y añadirArista para que no se considere el
caso de aristas bidireccionales.
Y sustituir la operación adyacentes por:
op predecesor : Grafo Nodo Nodo -> Bool .
op sucesor : Grafo Nodo Nodo -> Bool .
CONCLUSION
En el mundo de la programación existen diversos lenguajes de programación que se
han ido creando con el paso del tiempo y que se han perfeccionado debido a las
necesidades de los programadores de la época a la que pertenecen. Los primeros
lenguajes de programación eran de tipo lineal, ya que un programa se recorría desde
un punto marcado como Inicio hasta llegar a un punto Fin. Con el tiempo se fueron
creando nuevos lenguajes y en nuestros días los más utilizados son los llamados
“orientados a objetos”.
Los lenguajes orientados a objetos (LOO) tienen la característica de que no son
lenguajes lineales, sino que se forman de diversas funciones, las cuales son llamadas
en el orden en que el programa mismo las pide o el usuario determina. Para entender
mejor cómo funcionan los lenguajes orientados a objetos, vamos a introducir un
concepto fundamental en las Estructuras de Datos denominado Abstracción de Datos y
que es parte importante de estos Lenguajes y de la manera en que funciona la mayoría
del software comercial de nuestros días.
BIBLIOGRAFIA
[Link]
