Introduccion a las estructuras de datos

INSTITUTO TECNOLÓGICO DE QUERÉTARO
ESTRUCTURA DE DATOS
¿Que es una abstracción?
Un proceso mental, mediante el cual se
extraen los rasgos esenciales de algo
para representarlos por medio de un
lenguaje gráfico o escrito.
Puesto que es un proceso mental la
acción es una acción subjetiva y creativa,
esto es depende del contexto psicológico
de la persona que lo realiza.

TIPO DE DATOS ABSTRACTO
UnTDA es un tipo de dato definido por el programador que se
puede manipular de un modo similar a los tipos de datos
definidos por el sistema.
• Está formado por un conjunto válido de
elementos y un número de operaciones
primitivas que se pueden realizar sobre ellos.
Para construir un tipo abstracto debemos:
1. Exponer una definición del tipo.
2. Definir las operaciones (funciones y
procedimientos)que permitan operar con
instancias de ese tipo.
3. Ocultar la representación de los elementos
del tipo de modo que sólo se pueda actuar
sobre
ellos
con
las
operaciones
proporcionadas.
4. Poder hacer instancias múltiples del tipo.

ESTRUCTURA DE DATOS
Cualquier colección o grupo de datos organizados de tal forma que
tengan asociados un conjunto de operaciones para poder
manipularlos, se dice queconforma una estructura de datos.
• Arreglos
Estáticas
• Matrices
Internas
• Lineales
Dinámicas

• Listas
• Pilas
• Colas

Estructuras
de Datos

• Árboles
• No Lineales
• Bases de Datos
Externas

• Archivos

• Grafos

MODULARIDAD
La Modulariad descompone un programa en un pequeño número de abstracciones
independientes unas de otras pero fáciles de conectarse entre si.
Un módulo se caracterizaprincipalmente por su interfaz y su implementación.

USO TDA
Un TDA es el elemento básico de la abstracción de datos. Debe verse como
una caja negra, pues la representación y la implementación deben
permanecer “ocultas”
El programador no tiene que preocuparse de cómo se representa un tipo
particular de datos y sólo tiene que trabajar con ellos en base a las
especificaciones sintácticas y semánticasdel diseñador.
1. Determinar, ante un problema, los objetos candidatos a tipos de datos,
estén o no estén en el lenguaje de partida.
2. Identificar las operaciones básicas, primitivas entre dichos objetos.
3. Especificar dichas operaciones
4. Construir un programa, que usando estos tipos y estas operaciones
resuelva el problema original.
5. Implementar los tipos y operaciones que no estén en ellenguaje de
partida, con los elementos de dicho lenguaje
6. Determinar la eficiencia de la implementación.

MANEJO DE MEMORIA
Para implementar alguna estructura de datos, primero es
necesario tener muy claro cómo va a ser 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 puedecambiar

MEMORIA ESTÁTICA
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

in

Componentes
Índices

 Componentes: Hacen referenciaa los elementos que forman el
arreglo.
 Í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 ejemplo:
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

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.
Ejemplo:
Suma
X[2]...