Tipos de Datos abstractosEstructuras de Datos
MC Beatriz Beltrán Martínez
Características
Los programas actúan sobre la información.
La cual se dispondrá de una manera particular, organizada en forma que se faciliten las operaciones que conforman el algoritmo.
El término Estructura de Datos refiere a dos partes de la Organización de la Información.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 2
Características
Organización Lógica: Involucra todo aquello que tenga que ver con las partes de cada elemento, tipo de los elementos, referencia a alguno o algunos elementos, cantidad de los elementos que contiene la estructura, relaciones entre los elementos, etc.
Organización Física: Se refiere a todo aquello que tenga que ver con la ubicación de la información en la memoria y la forma de almacenarla de acuerdo a sus dominios.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 3
Características
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 4
Características
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 5
VínculoED Algoritmo
Plantea un concepto más amplio de lo que es el tipo
Ejemplo
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 6
A[1]
A[2]
A[3]
A[4]
A[50]
Organización Lógica:Arreglo de un índice;Inicio: 1, Fin: 50;Tipo de elementos: Entero;
Organización Física: Almacenamiento: Secuencial
Dirección Inicial: dir(A)Tamaño del elemento: 2 bytes;Número de elementos: 50;
Considerar
La eliminación de un elemento se puede pensar en dos formas:
1. Por desplazamiento.
2. Por marca. Podemos observar en los anteriores algoritmos
que el segundo es más rápido, mientras que el primero se limita a ocupar el espacio mínimo.
Cantidad de memoria que consume la estructura contra tiempo de realización de una operación.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 7
Tipos de ED y sus dominios
A partir de las diferentes formas que existen para organizar la información tenemos que en cuanto a la Organización Lógica los diversos lenguajes de programación proporcionan los elementos básicos de información y constructores para definir ED.
Se tienen tipos básicos, pero también se tienen constructores para formar diferentes estructuras.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 8
Tipos de ED y sus dominios
El REGISTRO proporciona heterogeneidad en este producto cartesiano; por ejemplo:
Sea x un REGISTRO con los campos
y de tipo ENTERO
z de tipo REAL
tiene como dominio Dom (x) = Z X R, cuyos elementos son de la forma (a, b) aZ y bR.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 9
Tipos de ED y sus dominios
En general, tenemos que por ejemplo:
Sea k un REGISTRO con los campos
l de tipo booleano
m de tipo xDom(k) = B X Dom(x)Para poder generalizar esto último, se deben
considerar los elementos de referencia, para ello consideremos que en el siguiente ejemplo el operador ^ define tales elementos.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 10
Tipos de ED y sus dominios
Sea p un REGISTRO con los campos
xc, yc de tipo Real
Sea l-p un REGISTRO con los campos
punto de tipo p
sp de tipo ^l-pDom (l-p) define un dominio recursivo:
Dom (l-p) = Dom (p) x dom (^l-p)Los elementos de Dom (^l-p) son de la forma
Dom(^l-p) = {nil} U [Dom (l-p)].MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 11
Organización física
la organización física tiene que ver con el “lugar” y la “forma” dentro de la memoria donde se almacena la información.
Tanto el “lugar” como la “forma” son representados por el “espacio” el cual puede ser “fijo” o “variable”.
De lo anterior, se tiene que las E.D. se clasifican en:Estáticas (Espacio Fijo)Dinámicas (Espacio Variante)
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 12
Memoria Dinámica y Estática
Catálogo de algunas estructuras de datos conocidas, dinámicas:Lista simple ligadaÁrbolesLista doblemente ligada
Estáticas:ArreglosPilaCola
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 13
Arreglos
Organización Lógica: Dimensiones.Límite inferior y superior de cada dimensión.Tipo de elementos.
Organización Física: Dirección inicial (de un intervalo de memoria)Tamaño de los elementos.Orden de las dimensiones.Desplazamientos .
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 14
Arreglos
Las operaciones con los arreglos son:Recuperación de uno de sus elementos.Actualización de un elemento.
Ambas operaciones se realizan en función de los índices que señalan la ubicación del elemento.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 15
ArreglosSea A un ARREGLO [1..20] con elementos de tipo
Carácter.Reserva un intervalo de memoria de 20 lugares
consecutivos a partir de una dirección que denotaremos por DirA.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 16
A[1]A[2]A[3]
A[20]
DirA
DirA+1
DirA+2
DirA+19
Intervalo de memoria:[DirA, DirA+19]
Polinomio de Direccionamiento
Suponiendo que el direccionamiento sea a nivel de bytes.
Las operaciones se reducen al cálculo del Polinomio de Direccionamiento (Pd).
El Pd obtiene la dirección absoluta de un elemento del arreglo dados sus índices.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 17
Polinomio de Direccionamiento
Por ejemplo:Si nos referimos a A[7] Pd (A[7]) = DirA + 6
Pd (A[x]) = DirA + x-1.
En general se tiene que si B es un ARREGLO [1..5] con elementos de tipo T
Pd (B[x]) = DirB + (x-1) lt; con lt igual a la longitud en bytes asignada al tipo T.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 18
Polinomio de Direccionamiento
Para almacenar los elementos de una matriz en la memoria que es lineal, podemos hacerlo por columnas o por renglones.
Matriz de 3X4
11 12 13 14
21 22 23 24
31 32 33 34
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 19
Polinomio de DireccionamientoPor columnas:
Dirección Elemento100=dir 11
101=dir+1 21 1ª. Columna 102=dir+2 31 103=dir+3 12 104=dir+4 22 2ª. Columna 105=dir+5 32 106=dir+6 13 107=dir+7 23 3ª. Columna 108=dir+8 33 109=dir+9 14 110=dir+10 24 4ª. Columna 111=dir+11 34
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 20
Polinomio de Direccionamiento
Para la dirección del elemento C[i][ j] y el almacenamiento por columnas, el PD es:
pd(C[i][ j])=dirC+[n*(j-1)+(i-1)]*T
Si el almacenamiento se hubiese realizado por renglones, entonces el PD quedaría como:
pd(C[i,j])=dirC+[m*(i-1)+(j-1)]*T
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 21
Polinomio de Direccionamiento
El caso más general, que es la declaración:
Tipo E [inf1,sup1] [inf2,sup2] …, [infn,supn];
dondeinfi, supi es el límite inferior y límite superior
de la i-ésima dimensión respectivamente. Sea ri el rango de la i-ésima dimensión definido
como: ri = supi-infi+1, y T el tamaño en bytes de Tipo.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 22
Polinomio de Direccionamiento
Entonces el PD es: pd(E[k1,k2,…,kn]) = dirE + [r1 * r2 * r3 * … * rn-1 *
(kn-infn) + r1* r2* r3 * … * rn-2 * (kn-1-infn-1) + … + r1 * (k2-inf2) + (k1-inf1)] * T
Para referenciar un elemento que se encuentra en una estructura utilizaremos la dirección inicial del registro y los tamaños en bytes de cada uno de los campos del registro de acuerdo a su tipo.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 23
Polinomio de Direccionamiento
Entonces la fórmula quedaría de la siguiente manera:
Sea estructura R {x1 : T1;x2 : T2;…xn : Tn;}
y sea dirR la dirección inicial de R.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 24
1
1i )()pd(R.x
i
jjxTamañodirR
Multipila
En este caso se administran varias pilas.La estructura de pila común hereda
características del almacenamiento estático y por este motivo tendremos:límite inferior (LI)límite superior (LS)posición del siguiente lugar libre (T)
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 25
Multipila
Las operaciones más comunes que se consideran para su manejo son:inserción de un elementoeliminación (extracción) de un elementoverificación de pila vacía o llena.
En particular se acostumbra anunciar saturación cuando la estructura no admite más elementos.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 26
Multipila
Considérese:LI : arreglo [1..n+1] de enteros;T : arreglo [1..n] de enteros;M : arreglo [1..MAX] de un Tipo;
tal que:LI[k] representa el límite inferior de la k-ésima pila.T[k] representa la posición del siguiente lugar libre
de la k-ésima pila.LI[n+1] es el límite superior de la n-ésima pila.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 27
Multipila
Al inicio todas las pilas están vacías, entonces el arreglo de límites inferiores y el de topes coinciden, excepto el último elemento del arreglo de límites inferiores.Por ejemplo, suponga que se quieren manejar 4
pilas con capacidad para 4 elementos cada una.
n=4 y MAX=16.Al inicio el contenido de los arreglos LI y T
quedaría de la siguiente manera:
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 28
Multipila
LI[1]=1 T[1]=1LI[2]=5 T[2]=5LI[3]=9 T[3]=9LI[4]=13 T[4]=13LI[5]=17
Al realizar la operación de inserción en alguna de las pilas, se necesita:
El número de la pila y El dato a insertar.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 29
Multipila
Para insertar se deben realizar las siguientes operaciones:1. M[T[1]]=dato; // insertar dato
2. inc(T[1],1); // incrementar el tope de la pila número 1
Si deseamos insertar los datos -4 y -8 en la pila número 3, entonces debemos incrementar en uno el tope de la pila 3 por cada inserción.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 30
Multipila
Cuando se pretende almacenar en la k-ésima pila y se tiene que T[k]=LI[k+1], es decir, el tope de la k-ésima pila coincide con el límite inferior de la siguiente pila (k+1-ésima pila), tenemos una saturación local.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 31
Pila 1
Pila 2
Pila 3
Pila 4M
LI[1]=1
LI[2]
LI[3]=9
LI[4]
12345678910111213141516
T[1]=2
T[2]=5
T[3]=11
T[4]=13
LI[5]=17
15
-4-8
Multipila
Por ejemplo, suponga que la pila 3 está saturada.
En este caso se pueden llevar a cabo los siguientes pasos:
1. Buscar j tal que: LI[j+1] - T[j] >0 y |k-j| sea mínimo.a) sino existe j entonces tenemos
una saturación total.
b) si existe entonces pasar al siguiente paso.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 32
Pila 2
Pila 3
Pila 4M
LI[3]=9
LI[4]
678
910111213141516
T[3]=13
T[4]=13
-4-8-8-8
.
.
.
Multipila
2. Mover una posición los elementos de las pilas k+1 hasta j hacia arriba cuando j > k o bien, desde los elementos k hasta j+1 hacia abajo cuando j < k.
3. Insertar el elemento.
4. Actualizar LI y T
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 33
j = Pila 1
Pila 2
k = Pila 3
Pila 4M
LI[1]=1
LI[2]
LI[3]=9
LI[4]
1234567891011121314
1516
T[1]=2
T[3]=13
15
-4-8-8-8
j =Pila 4
17Caso: j>k
Movimiento hacia arriba una posición
Caso: j<k
Movimiento hacia abajo una posición
Multipila
Cabe mencionar que la pila j (pila seleccionada) es aquella pila que tiene al menos un lugar vacío (LI[j+1]-T[j] > 0 o bien LI[j+1] <>T[j] ) y además es aquella pila que se encuentra más cerca de la pila saturada (|k-j| sea mínimo), entonces |k-j| nos da la distancia entre k y j.
Al darse estos movimientos de los elementos de las pilas, estamos modificando tanto los LI de las pilas como sus topes, por lo tanto se deben actualizar.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 34
Multipila
Cuando los movimientos sea hacia arriba se incrementan los LI y los topes de las pilas que se mueven, y cuando los movimientos son hacia abajo se decrementan.
En el caso de la eliminación, ésta operación se realiza de la misma manera que para una pila normal, con la diferencia de que necesitamos un parámetro para esta operación: el número de la pila de donde queremos eliminar.
MC Beatriz Beltrán Martínez FCC - BUAP Primavera 2014 35
Top Related