• Author / Uploaded
• Francesita Màrkz

Citation preview

16/08/2011

ESTRUCTURAS DE DATOS Conocer, comprender y analizar algunos de los principales tipos de estructuras de datos

DBD II Ing. Luis Reyes

Concepto
En programación, una estructura de datos es

una forma de organizar un conjunto de datos elementales (un dato elemental es la mínima información que se tiene en el sistema) con el objetivo de facilitar la manipulación de estos datos como un todo o individualmente.

1

16/08/2011

Organización
Una estructura de datos define la organización e

interrelacionamiento de estos, y un conjunto de operaciones que se pueden realizar sobre él. Las operaciones básicas son:
De Alta, adicionar un nuevo valor a la estructura.
De Baja, borrar un valor de la estructura.
De Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma SECUENCIAL o BINARIO (siempre y cuando los datos estén ordenados)...
Ordenamiento, de los elementos pertenecientes a la estructura.
Apareo, dadas dos estructuras originar una nueva ordenada y que contenga a las apareadas.

Consideraciones
Cada estructura ofrece ventajas y desventajas en

relación a la simplicidad y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datos apropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operación sobre los datos.

2

16/08/2011

Características
Pueden descomponerse en los elementos que la

forman.
La manera en que se colocan los elementos dentro de la estructura afectará la forma en que se realicen los accesos a cada elemento.
La colocación de los elementos y la manera en que se accede a ellos puede ser encapsulada.

Datos Simples
Binarios
Bit
Byte
Numéricos
Entero
Real
Coma fija
Coma flotante
Alfanuméricos
Carácter
Cadena

3

16/08/2011

Estructura de Datos
Arrays (Arreglos)
Vectores
Matrices
Registro
Tipo de datos algebraico
Listas Enlazadas
Listas Simples
Listas Dobles
Listas Circulares
Listas por saltos (Skip lists)
Pilas (stack)
Colas (queue)

Estructura de Datos
Árboles
Árboles Binarios






Árbol binario de búsqueda Árbol binario de búsqueda autoajustable Árboles Rojo-Negro Árboles AVL Árboles Biselados (Árboles Splay)


Árboles Multicamino (Multirrama)
Árboles B
Árboles B+
Árboles B*


Conjuntos (set)
Grafos
Tablas Hash

4

16/08/2011

Estructuras de Datos: Composición
Conjunto de datos de tipos iguales o diferentes

que se relacionan entre si y que se pueden operar como un todo. Datos Simples Hacen referencia a un único valor a la vez en memoria Entero, Real, Carácter, Lógico Estáticos

Arreglos, Registros, Archivos, Cadenas

Datos Estructurados Se refieren a un grupo de casillas de memoria Dinámicos

Listas, Arboles, Grafos

Estructuras de Datos - Implementación
Para implementar alguna estructura de datos,

primero es necesario tener muy claro cómo va a ser el manejo de memoria.
La diferencia entre estructuras estáticas y dinámicas es el manejo de memoria.

Estática Durante la ejecución del programa el tamaño de la estructura no cambia

Dinámica Durante la ejecución del programa el tamaño de la estructura puede cambiar

5

16/08/2011

Memoria Estática -Conceptos de Arreglos
Definición: Colección finita, homogenea y ordenada de

elementos. Finita: Porque todo arreglo tiene un límite. Homogenea: Porque todos los elementos son del mismo tipo. Ordenada: Porque se puede determinar cuál es el enésimo elemento.
Un arreglo tiene dos partes: Componentes e índices C1 C2 .... Cn i0







i1

Componentes

in

Índices Componentes:: Hacen referencia a los elementos que forman el Componentes arreglo. Índices ndices:: Permiten referirse a los componentes del arreglo en forma individual.

Memoria Estática -Arreglos Unidimensionales
Son los arreglos más simples y constan de un

solo índice, también se llaman vectores.
Notación: Podría ser de diferentes maneras. Por ej.: Array [0...9] de enteros: Vector Vector: x




14 43 .... 4

Componentes

x0

Índices

x1

x9

X hace referencia a todo el vector, mientras que x0, o x1 hace referencia los elementos en forma individual

6

16/08/2011

Memoria Estática -Arreglos Unidimensionales
Los arreglos se almacenan en forma adyacente, así que




su representación en memoria es: X0 ,Dirección z; X1 ,Dirección z+1; Xn ,Dirección z+n Cada elemento del arreglo se puede procesar como si fuera una variable simple.Ej: Suma X[2] i X[i]




Suma + x[2] 15 3 15

X[i+2] 15 Sobre los vectores se pueden realizar las siguientes operaciones: Lectura//Escritura, Asignación, Actualización(ins, eli, Mod), Lectura Ordenamiento y Búsqueda.

Memoria Estática -Arreglos Bidimensionales
Estos arreglos constan de dos índices, también se

llaman matrices.
Notación: Podría ser de diferentes maneras. Por ej.: Array [0...2, 0...2] de enteros: Matriz Matriz: M 0

1

2

Indices

34 43 90

0

83 2

1 2

41

56 75 3




Operaciones: Lectura, Escritura, Asignación.

Componentes

7

16/08/2011

Memoria Estática -Registros(Estructuras)
Un registro es una colección de datos, que pueden ser de

diferentes tipos. Cada uno de sus elementos se llama Campo.


Notación: Podría ser de diferentes maneras. Por ej:

Tipo registro: Domicilio Entero: Calle Entero: Numero Cadena: Ciudad Fin Tipo Domicilio: dir





Domicilio Calle

Numero

Ciudad

El acceso a los campos se hace así: variable_registro.id_campo variable_registro.id_campo.. Por Ej: Ej: dir.Calle dir.Calle,, dir.Numero, dir.Numero, dir.Ciudad. dir.Ciudad.

Memoria Estática -Arreglos y Registros
I.

Se pueden presentar las siguientes combinaciones: Arreglos de Registros: Cada elemento del registro es un arreglo.

Tipo registro: Cliente Cadena:: Nombre Cadena N Cadena:: Teléfono Cadena Real: Real: Saldo Fin Tipo Array [0...2 [0...2] de Cliente Cliente:: Vector

Vector T S 0

N T S 1

N T S 2

Notación: Vector[0].Nombre

8

16/08/2011

Memoria Estática -Arreglos y Registros II.

Registro Anidado: Por lo menos un campo del registro es de tipo registro. Tipo registro: Domicilio Entero: Calle Entero: Numero Cadena: Ciudad Nombre Fin Tipo Tipo registro: Cliente Cadena:: Nombre Cadena Domicilio:: Dirección Domicilio Real: Real: Saldo Fin Tipo

Cliente Dirección

Saldo

Cll Num Ciu Notación: Cliente.Nombre Cliente.Dirección.Calle

Memoria Estática -Arreglos y Registros III.

Registro con Arreglos: Por lo menos un campo del registro es un array. Array [0...2 [0...2] de Real: Real:Vector Tipo registro: Estudiante Cadena:: Nombre Cadena Cadena: Código Vector:: Notas Vector Fin Tipo

Estudiante Notas

Nombre

Código

Notación: Estudiante.Nombre Estudiante. Notas[0]

9

16/08/2011

Memoria Dinámica -Apuntadores
Las variables contienen valores especificos, las

variables apuntador contienen direcciones de memoria de otras variables.





La variable “ptrcont” contiene la dirección de memoria de la variable “cont”

ptrcont 29DC

cont 2

Las variables apuntador estan asociadas a un tipo de dato. Por ej. Si el valor de cont es entero la variable apuntador ptrcont debe ser de tipo entero.

Memoria Dinámica -Apuntadores
Operadores: Una variable apuntador responde a dos

operadores:
Operando de Dirección(&): Que devuelve la dirección de su operando. Por ej: Entero Y, *ptry Y 5 Ptry &Y
Operando de Indirección(*): Que devuelve el alias de su

operando. Por ej: Entero Y, *ptry Y 5 Ptry &Y Escribir(*Ptry)

10

16/08/2011

Memoria Dinámica -Asignación de Memoria
Es el proceso por el cual a una estructura, sea

cual fuere, se le coloca a apuntar una variable del mismo tipo y sobre ese apuntador se reserva o se libera memoria de acuerdo a si la estructura crece o decrece.

Memoria Dinámica -Conceptos de Listas
Una lista es una colección de elementos,

generalmente, llamados nodos.
En general un nodo tiene 2 partes:
Un campo de info que será del tipo de datos que se quiera almacenar en la lista.
Un campo de tipo apuntador que se utiliza para establecer un enlace con otro nodo de la lista. Si es el ultimo nodo su valor es null. Ya no es necesario que los nodos se guarden en forma contigua. ptrcont 5

.

7

.

null

11

16/08/2011

Memoria Dinámica -Operaciones con Listas
Crear: Define el primer elemento de la lista.
Insertar: Que coloca nuevos nodos al principio o

al final del nodo dado.
Recorrer: Que “visita” o “atiende” todos o algunos de los nodos de la lista bajo un criterio dado.
Eliminar: Que borra un nodo dado. Se puede eliminar el 1º nodo, el ultimo, el que tenga un info x o el anterior o posterior al que tenga una info x.

Memoria Dinámica -Tipos de Listas
Simplemente Encadenada


ptrcont




5 .

7 .

ptrcont

ptrcont null

5

null

Doblemente Encadenada

. 5. . 7.

Circular




.

7

.

Circular Doblemente Encadenada ptrcont

null

. 5. . 7.

12

16/08/2011

Memoria Dinámica -Listas de Acceso Restringido Lista de elementos a la cuál se puede insertar o eliminar elementos únicamente por uno de sus extremos.
Los elementos se eliminan en forma inversa a los que se insertaron, es decir, el ultimo elemento que ingresa es el primero que se elimina(LIFO).
Se pueden representar con arreglos o listas.
Pilas:

ptrcont 5

.

7

.

null

Memoria Dinámica -Listas de Acceso Restringido
Colas: Lista de elementos en la que

el primero en entrar es el primero en salir(FIFO).
Se pueden representar con arreglos o listas.

13

16/08/2011

Memoria Dinámica -Arboles
Son la estructura no-lineal más importante en

computación.
No-lineal porque a cada elemento(nodo) le pueden seguir varios elementos(nodos).
Los arboles AVL(balanceados) son las mejores estructuras para trabajar con memoria principal.
Los arboles B y los B+ son las mejores estructuras para trabajar en memoria secundaria.

Memoria Dinámica -Conceptos de Arboles
Es una estructura jerárquica aplicada sobre una

colección de elementos llamados nodos. Uno de los cuales es llamado raíz.
Además se crea una relación de parentesco entre los nodos de forma que hay términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc. Para definir un árbol se necesita recursión.
Se utilizan para representar formulas matemáticas, organizar información, árboles genealógicos, enumeración de capítulos y secciones de un libro, etc.

14

16/08/2011

Terminología de un Árbol
HIJO. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se











dice que X es descendiente directo de Y. PADRE. X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y. HERMANO. Dos nodos serán hermanos si son descendientes directos de un mismo nodo. HOJA. Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos). NODO INTERIOR. Es un nodo que no es raíz ni terminal. GRADO. Es el número de descendientes directos de un determinado nodo. GRADO DEL ARBOL Es el máximo grado de todos los nodos del árbol. NIVEL. Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1. ALTURA. Es el máximo número de niveles de todos los nodos del árbol. PESO. Es el número de nodos del árbol sin contar la raíz. LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.

Tablas Hash
Una tabla hash o mapa hash es una estructura de datos que asocia

llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos (teléfono y dirección, por ejemplo) almacenados a partir de una clave generada (usando el nombre o número de cuenta, por ejemplo). Funciona transformando la clave con una función hash en un hash, un número que la tabla hash utiliza para localizar el valor deseado.

15

16/08/2011

Memoria Dinámica -Representación de Arboles
Diagramas de Venn :

A B D I




C G

E

H

F J

K

L

Anidación de paréntesis :  (A(B(D(I),E,F(J,K)),C(G,H(L))))

16