PDF de programación - Introducción primera parte - Estructura de Datos y Algoritmos

Estructura de Datos y Algoritmos

1­Introducción

Tema­I­Introducción y conceptos fundamentales

En este capitulo se presentan los conceptos y definiciones fundamentales que acompañarán al alumno a lo 
largo   de   toda  la   asignatura.   Es   muy   importante   fijar   estos   conceptos   ya   que   de   ello  depende  que  la 
comprensión de esta asignatura sea más o menos compleja.

● Abstracción

○ Operación mediante la cual la inteligencia llega a formar conocimiento conceptual común a un 
conjunto de entidades, separando de ellos los datos contingentes e individuales para atender a 
lo que los constituye esencialmente. Es decir, aislar mentalmente o considerar por separado las 
cualidades de un objeto.

1.2­Estructuras de datos y Tipos de Datos Abstractos

● Tipo de datos

○ Un tipo de datos es una colección de valores

● Tipo de Datos Abstracto (TDA)

○ Es un tipo de datos definido de forma única mediante un tipo y un conjunto dado de operaciones 

definidas sobre el tipo.

● Estructura de datos

○ Implementación física de un tipo de datos abstracto.

Un ejemplos de esto conceptos es el siguiente:

En algunos lenguajes de programación que  implementan el tipo  Booleano,  éste está  formado por los 
valores   {True,  False},   pero   no   es  un  tipo  de  datos   abstracto   ya   que   sobre  él   no   se  han   definido   las 
operaciones para manipularlo. Sin embargo, el tipo Booleano junto con los operadores booleanos (AND, 
OR, NOT) constituyen un tipo de datos abstracto.

● Encapsulado

○ Es consecuencia misma del proceso de abstracción y consiste en “ocultar” la implementación de 
las operaciones que manipulan los objetos, ofreciendo únicamente una “interfaz” que permita 
realizar operaciones, funciones de acceso y variables de entrada salida. (Ej. representación 
enteros en diferentes notaciones, little endian o big endian).

Normalmente   existe   más   de   un   TDA   para   resolver   un   problema   concreto.   La   elección   de   uno   u   otro 
dependerá de algunas características del problema a resolver (disponibilidad de memoria, velocidad de 
resolución, etc). Ello implica que cada implementación de un TDA presentará un coste diferente. 
El   coste   de   un   TDA   no   viene   determinado   por   un   sólo   factor.   En   primer   lugar   se   deberá   analizar   el 
almacenamiento requerido por los datos y la cantidad de ellos que serán manejados. El segundo aspecto a 
considerar será el coste de las operaciones básicas. En el caso de los árboles, por ejemplo, serán los 
costes de las operaciones de inserción, búsqueda y eliminación. Para calcular el coste de esas operaciones 
deberán emplearse técnicas de análisis de algoritmos.

Enric Rubio Rodríguez (2008)
[email protected]

http://www.erubio.es
Página: 1

Estructura de Datos y Algoritmos

Por tanto, el diseño de un TDA (debido al proceso de abstracción) deberá realizarse siguiendo tres pasos 
fundamentales:

Tema­I­Introducción y conceptos fundamentales

1. Análisis de datos y operaciones.
2. Elección del Tipo de datos Abstracto.
3. Elección de la Implementación.

En el contexto global de la programación, independientemente del lenguaje utilizado, no suele atenderse a 
la diferencia entre tipo de dato y TDA. Sin embargo, todos ellos son de hecho TDAs. De este modo la 
definición de los tipos de datos estándar son las siguientes:

● Entero

○ Tiene   como   tipo   el   conjunto   de   números   enteros   definido   por   las   matemáticas 
{−1,−2,... ,∞}∪{1,2 ,... , ∞} y como operaciones la suma, resta, multiplicación y división 

entra.

● Real

○ Tiene   como   tipo   el   conjunto   de   números   reales   definido   por   las   matemáticas   y   como 

operaciones la suma, resta, multiplicación y división.

● Booleano

○ Tiene   como   tipo   el   conjunto   de   valores   booleanos   {True,   False}   y   como   operaciones   las 

definidas por el álgebra de Boole (AND, OR, NOT).

● Carácter

○ Tiene como tipo el conjunto de caracteres definido por un alfabeto dado y como operaciones 
todos   los   operadores   relacionales   (tomando   como   ejemplo   dos   variables   arbitrarias   (a,   b)

{ab , ab , a=b , a≤b , a≥b , a≠b}

Como ya se ha comentado, la implementación de TDA Real tiene diferentes implementaciones, aunque la 
más utilizada es la recomendada por el IEEE en su norma 754­1985. análogamente, para el TDA carácter, 
la implementación dependerá, básicamente, del alfabeto utilizado. En general, todos los alfabetos vendrán 
caracterizados por una secuencia de cotejo (en ASCII el carácter A corresponde a la secuencia de cotejo 
65), que no es otra cosa que una secuencia ordenada de los caracteres que constituyen su conjunto. Los 
tres conjuntos de caracteres más conocidos son:

1. CDC­Científico
2. EBCDIC (Extended Binary Coded Decimal Interchange Code)
3. ASCII (American Standard Code for Information Interchange)

En este contexto se puede definir el tipo de datos escalares que son aquellos en los que  el conjunto de 
valores está ordenado y cada valor es atómico.
Algunos tipos de datos escalares presentan una propiedad adicional, la ordinalidad. Se denominan tipos de 
datos ordinales a aquellos en los que cada valor tiene un único predecesor (excepto el primero) y un único 
sucesor (excepto el último).
Los tipos carácter, entero y Booleano son ordinales, pero el tipo real no lo es ya que según sabemos por las 
matemáticas, los números reales no forman un conjunto ordenado al no ser numerables. Se les puede 
aplicar operadores relacionales pero por ejemplo de, 5.1<5.2 podríamos concluir, erróneamente, que 5.1 es 
el predecesor de 5.2 y éste último el sucesor de 5.1, cuando entre ambos números existen infinitos números.

Enric Rubio Rodríguez (2008)
[email protected]

http://www.erubio.es
Página: 2

Estructura de Datos y Algoritmos

Tema­I­Introducción y conceptos fundamentales

A los tipos de datos que se han visto hasta ahora se les denomina primitivos o  predefinidos debido a que 
la mayoría de lenguajes de alto nivel los incorporan en sus normas básicas. No obstante, estos tipos de 
datos no suelen ser suficientes para realizar tratamiento de la información. En ese momento aparecen los 
tipos   de  datos  definidos  por   el   usuario,  siendo   los  característicos  de   la   programación   estructurada:  el 
conjunto, el arreglo y el registro. Dado son divisibles en componentes se denominarán  tipos de datos 
compuestos. 

La mayoría de estos tipos de datos son colecciones de componentes organizadas mediante la forma de 
acceso a cada una de sus componentes individuales. A este tipo de datos se le denomina tipo de datos 
estructurado.

En   general   las   operaciones   asociadas   a   los   tipos   estructurados   son:  almacenar  y  recuperar  sus 
componentes individuales. Cuanto todos los elementos de la colección son del un mismo tipo denominado 
tipo base, se dice que el tipo es homogéneo, mientras que cuando no lo son se dice que es heterogéneo.

Las siguientes definiciones precisan los TDA compuestos básicos.

● Conjunto

○ Colección   de   elementos   tratados   con   las   operaciones  unión,   intersección,   y   diferencia   de 

conjuntos.

● Arreglo

○ Colección   homogénea   de   longitud   fija   tal   que   cada   una   de   sus   componentes   pueden   ser 
accedidas individualmente mediante uno (unidimensional) o varios (multidimensional) índices, 
que serán de tipo ordinal y que indican la posición de la componente dentro de la colección.

● Registro

○ Tipo   de   datos   heterogéneo   compuesto   por   un   número   fijo   de   componentes   denominadas 

campos a las que se accede mediante un selector de campo (.) 

● Matriz

○ Tiene   como   tipo   el   conjunto   de   matrices   definido   por   las   matemáticas   y   los   operadores 
asociados   a   las   mismas:  Obtener_elemento,   Asignar_elemento,   Sumar,   Restar,   Negar, 
Producto_escalar, Producto_matricial, Determinante, Inversa y Transponer.

● Lista o secuencia

○ Colección homogénea de datos, ordenados según su posición en ella, tal que cada elemento 
tiene un predecesor (excepto el primero) y un sucesor (excepto el último) y sus operadores 
asociados son:
■ Insertar, Localizar, Recuperar, Suprimir (elemento p), Suprimir_dato (todas las apariciones 

de x), Anula (vacía lista), Primero (Fin), Imprimir.

○ En general, el término 'lista' se usa cuando el TDA se implementa sobre memoria principal, 

mientras que 'secuencia' suele reservarse para implementaciones en memoria secundaria.

○ Como puede observarse, desde el punto de vista lógico, la lista es una estructura de datos 
dinámica, ya que su tamaño vendrá determinado por el numero de elementos a contener. Una 
lista puede ser implementada de diversas formas. Con los TDA que se han visto hasta ahora se 
haría   mediante   arreglos.   Así,   la   lista,   que   es   dinámica,   independientemente   de   su 
implementación, se realiza mediante una implementación estática. Sin embargo también es 
posible implementarla dinámicamente mediante punteros.

Enric Rubio Rodríguez (2008)
[email protected]

http://www.erubio.es
Página: 3

Estructura de Datos y Algoritmos

1.2.3 Tipos de datos abstractos: Punteros y Listas enlazadas

Tema­I­Introducción y conceptos fundamentales

Un puntero es un tipo de datos simple cuyo valor es la dirección de una variable de otro tipo, denominada 
variable referenciada.

La utilidad de los punteros radica en que permiten realizar una reserva dinámica de memoria. Las variables 
referenciadas son variables dinámicas que son creadas y destruidas en “tiempo de ejecución” (recordad los 
tipos de datos que se pueden declarar en un programa: Const, Type, Var, que ocupan espacio durante toda 
la existencia del programa).

En la mayoría de los computadores el valor de un puntero es un número entero, sin embargo, este valor no 
es de tipo entero, sino una dirección, en algunas máquinas puede