Tipos abstractos y estructuras de datos, algoritmos y formatos de información

Índice de Contenidos

ÍNDICE

..........

2

1. TIPOS ABSTRACTOS Y ESTRUCTURAS DE DATOS

3

1. Arrays

5

1. Registros.

7

1. Listas

8

1. Pilas

11

1. Colas

13

1. Conjuntos

14

1. Mapas

15

1. Diccionarios.

15

1. Tabla hash

15

1. Árboles

16

1. Grafos.

25

1. ALGORITMOS

29

1. Eficiencia de un algoritmo.

29

1. Recursividad

33

1. Algoritmos de búsqueda

35

1. Algoritmos de ordenación o clasificación

37

1. Algoritmos teoría de grafos

42

1. ORGANIZACIONES DE FICHEROS

43

1. Organización secuencial.

43

1. Variantes de la organización secuencial

45

1. FORMATOS DE INFORMACIÓN Y FICHEROS

50

1. Formatos de imágenes

50

1. Formatos de documentos

53

1. Formatos de intercambio de datos

53

1. Formatos de audio y video

57

PABLO ARELLANO

www.theglobeformacion.com

Página 2

1. Organización directa

44B2T3

Estructuras de Datos TAI

1. TIPOS ABSTRACTOS Y ESTRUCTURAS DE DATOS

Para empezar, hay que precisar la diferencia entre tres conceptos muy relacionados, pero formalmente distintos, aunque sea frecuente utilizar el mismo nombre para casos concretos y muy importantes. Se trata de los conceptos de "Tipo de Datos", "Tipo abstracto de Datos" y "Estructura de Datos". Las definiciones se pueden establecer de la siguiente forma:

Un Tipo de Datos (TD) es el conjunto de valores que puede tomar una variable.

Los datos se pueden clasificar en dos tipos:

• Dato elemental. Aquellos que pueden ser almacenados en cualquier soporte de información sin necesidad de ninguna estructura especial para su almacenamiento. Los datos elementales se pueden clasificar en tres grupos:
  1. Numéricos. Lo componen los guarismos (0, 1, 2, 3, ... , 9), se utilizan para representación de información de tipo numérico.
  2. Alfabéticos: compuestos por los caracteres del alfabeto (a, b, c, ... , x, y, z), se utilizan para representar información no numérica.
  3. Especiales: utilizados con fines sintácticos en la mayoría de los casos o con fines aritméticos en otros. Formados por todos los caracteres que no constituyen información por sí solos (¿, ?, =, ), (, /, &, %, etc.).
• Tipos compuestos. Los más frecuentes son los arrays, listas, árboles, grafos, registros y ficheros.

Los tipos de datos constituyen un primer nivel de abstracción, ya que no se tiene en cuenta cómo se implementan o se representa realmente la información sobre la memoria de la máquina. Para el usuario, el proceso de implementación o representación es invisible.

Un Tipo Abstracto de Datos (TAD) representa una abstracción donde se destacan los detalles de la especificación (el qué) y se ocultan los detalles de la implementación (el cómo).

Así un TAD es representado por su interfaz la cual muestra las operaciones que se pueden realizar sobre ese tipo de datos sin importar la implementación concreta.

Así podemos definir un TDA Lista, un TDA Arbol, un TDA Pila o un TDA Cola, independientemente de las estructuras de datos usadas para su implementación.

Una Estructura de Datos (ED) es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar la manipulación de estos datos como un todo o individualmente, es decir, es la representación o implementación de un TAD.

PABLO ARELLANO

www.theglobeformacion.com

Página 3TAI

Clasificación de Estructuras de Datos

1ª CLASIFICACIÓN: Según cómo se ubiquen en la memoria del ordenador:

• Contiguas: son aquellas que al representarse en el hardware del ordenador, lo hacen situando sus datos en áreas adyacentes de memoria. Ejemplos: cadenas, arrays, vectores, registros.
• Enlazadas: sus datos no tienen por que situarse de forma contigua en la memoria, en las estructuras enlazadas los datos se relacionan unos con otros mediante punteros. La localización del dato no es inmediata, sino que se produce a través de los punteros que relacionan unos datos con otros.

2ª CLASIFICACIÓN: Según la variabilidad de su tamaño durante la ejecución de un programa:

• Estáticas: son aquellas en las que el tamaño ocupado en memoria se define con anterioridad a la ejecución del programa que las usa (en tiempo de compilación), y su dimensión no puede modificarse durante el proceso. Ejemplo: array o matriz.
• Dinámicas: las estructuras de los datos pueden crecer o no en tamaño, durante la ejecución, dependiendo de las necesidades de la aplicación. Ejemplo: lista o árbol.

Ventajas e inconvenientes de las agrupaciones estáticas frente a las agrupaciones dinámicas:

• En agrupaciones estáticas es más fácil y rápido realizar búsquedas en vectores.
• En general, para un mismo número de elementos las agrupaciones dinámicas ocuparán más memoria que las estáticas (por cada elemento se tiene también un puntero en las agrupaciones dinámicas).
• En agrupaciones dinámicas es mayor la facilidad para insertar y eliminar elementos.
• Es preferible las agrupaciones dinámicas si el número de elementos va a ser cualquiera.

3ª CLASIFICACIÓN: Según los tipos de datos de contengan:

• Homogéneas: son aquellas en las que únicamente se utiliza un tipo de datos.
• Heterogéneas: las estructuras que permiten que sus elementos puedan ser de tipos de datos distintos.

PABLO ARELLANO

www.theglobeformacion.com

Página 4B2T3

Estructuras de Datos TAI

Tipos de Datos

boolean

char

Simples

integer

real

ESTÁTICAS

Strings

Arrays

Compuestas

Conjuntos

Registros

Estructuras

de datos

Arrays

Listas

Lineales

Pilas

DINÁMICAS

Colas

Árboles

No lineales

Grafos

Arrays

Colección de elementos homogéneos (de igual longitud y tipo) entre los que existe una relación lineal determinada por la posición del elemento dentro de la estructura, también se las conoce con el nombre de Array.

Los arrays son estructuras de datos complejas que se caracterizan porque sus unidades homogéneas de información se ubican en posiciones contiguas de memoria.

Los arrays dependiendo del lenguaje de programación pueden ser estáticos (de tamaño fijo determinado en tiempo de compilación) y dinámicos (el tamaño puede variar en tiempo de ejecución).

Un array viene definido por:

• La definición de sus elementos. Longitud y tipo de dato a almacenar en la estructura.
• Índice (o varios). Es una variable numérica entera positiva que permite el acceso a los distintos elementos de la estructura según el valor de éste y, por tanto, según la posición

PABLO ARELLANO

www.theglobeformacion.com

Página 5B2T 3

Estructuras de Datos TAI

en la que se encuentra el elemento dentro de la estructura. Un índice comienza en 0 y termina en tamaño-1.

Podemos distinguir varios tipos de arrays:

• VECTORES o arrays unidimensionales.

Índice 1| elemento = 0 - c[o]

-7

c[1]

0

C[2]

3

C[3]

8

C[4]

5

Longitud del array = 10

C[5]

-4

C[6]

6

C[7]

6

Índice n-ésimo elemento = n-1

C[8]

1

2

Índice último elemento C[9]

=0 longitud -1

Índice: expresión entera: 0 <= índice <= longitud-1

• MATRICES o arrays bidimensionales: los elementos quedan estructurados en filas y columnas para su representación gráfica. Para acceder a cada elemento lo haremos con dos índices i para las filas y j para las columnas.

nx m

arreglo [3][4]

m = Columnas

0

n = Filas

1 Posiciones filas

2

0

1 2 3

Posiciones Columnas

• ARRAYS MULTIDIMENSIONALES.

int a[10] ;

/* Array de una dimension

*/

int b [3] [5] ;

/* Array de dos dimensiones

*/

int c[6] [4] [2]; /* Array de tres dimensiones

*/

a

b

C

PABLO ARELLANO

www.theglobeformacion.com

Página 6

Cada elemento de un arreglo está asignado a una posición concreta del arreglo, designada por un índice.

Implementación de Arrays

Respecto a la implementación del array se establece el número de elementos que forman la estructura, que siempre habrá que fijarlo, de alguna de las siguientes maneras:

• Memoria estática (en tiempo de compilación): una vez que el programa ha sido preparado para ser ejecutado (compilado y enlazado), la posición y el espacio de memoria que utilizará el array en la ejecución del programa ya está fijado y no puede de ninguna forma cambiarse, hablamos de array estático.
• Memoria dinamica (en tiempo de ejecución): diremos que el array es dinámico, pues el espacio en memoria no es de tamaño fijo, pudiendo el espacio de memoria variar en tiempo de ejecución.

Las operaciones basicas que se realizan sobre un array son: crear el array, insertar/modificar/eliminar elementos, buscar un elemento concreto, ordenar los elementos del array y contar los elementos que contiene.

La estrategia utilizada para la búsqueda y ordenación de elementos de un vector se verá en un apartado posterior.

Registros

Las estructuras o registros son agrupaciones heterogeneas, contiguas y estáticas.

Los elementos contenidos en la agrupación pueden ser de distintos tipos y se denominan campos, y suelen estar relacionados con la información referente a un objeto concreto.

Ejemplos:

Una persona (Nombre, edad, DNI ... )

Un libro (Título, autor, precio, disponible/agotado ... )

Los registros o estructuras definen nuevos tipos de datos que podemos utilizar a lo largo de nuestro programa.

Es decir, una vez declarada la estructura podemos utilizar y declarar variables de ese nuevo tipo (de la misma forma que si declarásemos variables de tipo entero o real).

La manera de acceder a cada uno de los campos es mediante el operador de acceso 2.

Ejemplo:

//Definición registro

struct Nombre {

Tipo1 Campo1; Tipo2 Campo2; ...

};

//Declaración variable

NombreVar : Nombre

//Asignación

NombreVar . Campo1 = valor;

PABLO ARELLANO

www.theglobeformacion.com

Página 7B2T3

Estructuras de Datos TAI

Los registros tienen como característica el anidamiento de estructuras. Las estructuras se pueden anidar, es decir, uno de los campos de una estructura puede ser a su vez otra estructura.

Listas

Una lista es un TAD que se define como un conjunto lógico de elementos homogéneos (nodos) entre los que existe una relación lineal, considerados a cada uno de éstos como unidad básica de información dentro de la estructura. Cada elemento de la estructura puede estar formado por uno o varios campos.

Nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener. Es posible utilizar una estructura estática aunque no es lo habitual.

Lista = colección de elementos homogéneos entre los que existe una relación lineal:

• Cada elemento de la lista, a excepción del primero, tiene un único predecesor.
• Cada elemento de la lista, a excepción del último, tiene un único sucesor.

Una lista es una estructura de datos que cumple:

• Todos sus componentes son del mismo tipo.
• Cada elemento o nodo (datos+puntero) va seguido de otro del mismo tipo o de ninguno.
• Sus componentes se almacenan según cierto orden.

Lista

Nodo 1

Nodo 2

Nodo n

NODOS Y ENLACES

Las operaciones sobre una lista son: crear, insertar un elemento, buscar un elemento (si la lista es dinámica solo es posible la búsqueda secuencial) y eliminar un elemento.

De entre estas operaciones la de mayor complejidad técnica es la de inserción, existiendo 3 casuísticas.

PABLO ARELLANO

www.theglobeformacion.com

Página 8