PDF de programación - Parte II: Estructuras de datos y algoritmos - 2. Tipos abstractos de datos.

Parte II: Estructuras de datos y
algoritmos

UNIVERSIDAD DE CANTABRIA

1. Introducción al análisis y diseño de algoritmos.
2. Tipos abstractos de datos.
3. Métodos de ordenación.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

4

© Javier Gutiérrez, Michael González

6/nov/08

1

Notas:

UNIVERSIDAD DE CANTABRIA

1. Introducción al análisis y diseño de algoritmos.

• Introducción. Diseño de un Programa. Concepto de algoritmo. Descripción de algoritmos: el
pseudolenguaje y diagramas de flujo. Tiempo de ejecución. La notación O(n). Ejemplos de
análisis.

2. Tipos abstractos de datos.

• Conceptos básicos. Listas. Pilas. Colas. Vectores. Conjuntos. Mapas. Árboles. Árboles

binarios.

3. Métodos de ordenación.

• El modelo de ordenación interna. Esquemas simples de ordenación. Ordenación rápida.

Ordenación por cajas. Ordenación por base.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

2

1. Concepto de clase o ADT

UNIVERSIDAD DE CANTABRIA

Una clase o tipo de datos abstracto (ADT) es:
• un tipo de datos con una determinada estructura, más
• un conjunto de operaciones para manejar esos datos

El conjunto de operaciones permite el uso de la estructura de
datos sin conocer los detalles de su implementación
• los programas que usan la clase son independientes de la

forma en la que éste se implementa

• no es necesario conocer los detalles internos del tipo de

datos ni de su implementación

Se dice que la clase encapsula el tipo de datos junto a sus
operaciones, ocultando los detalles internos.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

3

Notas:

UNIVERSIDAD DE CANTABRIA

El tipo de dato de una variable es el conjunto de valores que puede tomar esa variable. Un tipo de
datos abstracto (ADT) o clase es un modelo matemático de una estructura de información con un
conjunto de operaciones definidas sobre el modelo. Las operaciones se describen de forma
independiente a cómo se implementan.

Las ventajas principales que introduce la utilización del concepto de clase son:

1. Las operaciones de la clase permiten que el programa que lo usa sea independiente de la

forma en la que se implementa la clase.

2. Las clases encapsulan un tipo de datos junto a todas las operaciones a realizar con ese tipo
de datos. Esto quiere decir que todo lo relativo a esa clase está localizado en un lugar concreto
del programa, que tiene todos sus detalles internos ocultos

El encapsulado permite una gran facilidad en cualquier cambio en la estructura de una clase, ya que
afecta sólo a un reducido número de rutinas. ¡El programa que utiliza el tipo de datos no necesita
ser modificado!.

Por ejemplo, los conjuntos, junto con las operaciones de unión, intersección y diferencia de
conjuntos, forman un ejemplo de tipo abstracto de datos. Independientemente de cómo se
implemente el conjunto (mediante una lista, un array, etc.), el conjunto se puede utilizar en base a
las operaciones que se han definido.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

4

2. Listas

UNIVERSIDAD DE CANTABRIA

Una lista es una secuencia de objetos ordenados, en la que se
puede:
• insertar o eliminar elementos en cualquier posición
• recorrer los elementos de la lista hacia adelante y

opcionalmente, hacia atrás
- normalmente uno por uno mediante las operaciones

primer_elemento y siguiente (último y anterior)

• buscar un elemento en la lista
• etc.

Los objetos son todos del mismo tipo, el Elemento

La posición de los objetos es del tipo abstracto Posicion

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

5

Notas:

UNIVERSIDAD DE CANTABRIA

Las listas son secuencias de objetos ordenados con una estructura particularmente flexible, que se
puede aumentar o disminuir mediante la inserción o eliminación de elementos en cualquier posición.

Matemáticamente una lista es una secuencia de cero o más elementos de un tipo determinado, en
la que el orden se define en función de la posición en la lista.

• a1, a2, ... an con n ≥ 0.

Todos los elementos de la lista son del mismo tipo de datos, que llamaremos tipo “Elemento”. Para
independizar este tipo de la lista, lo declararemos como un parámetro genérico.

Las operaciones que se pueden realizar sobre listas son insertar o eliminar elementos en cualquier
posición, recorrer los elementos de la lista, buscar un elemento, etc. Dependiendo de la forma en
que está implementada la lista se permitirá recorrer la lista hacia adelante sólo, o indistintamente
hacia adelante y hacia atrás. Generalmente se suele recorrer la lista elemento a elemento, para lo
que existen operaciones para ver el primer elemento, y el siguiente elemento a uno dado. Ello
permite recorrer toda la lista. Si se desea recorrer en orden inverso las operaciones son último
elemento, y elemento anterior.

Cada objeto está localizado en una posición de la lista, que será del tipo abstracto “Posicion”. Este
tipo no es necesariamente un número.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

6

Operaciones básicas de las
listas

UNIVERSIDAD DE CANTABRIA

operación
Haz_Nula
Inserta_Al-
Principio
Inserta_Al-

Final

Inserta_-
Delante

in

out

el _elemento

el _elemento

el _elemento
la_posicion

Elimina

la_posicion

el_elemento

la_lista

Esta_Vacia

la_lista

booleano

in out
la_lista
la_lista

errores

no_cabe

la_lista

no_cabe

la_lista

no_cabe
posicion_-
incorrecta
posicion_-
incorrecta

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

7

Notas:

UNIVERSIDAD DE CANTABRIA

Para formar un tipo abstracto de datos basado en este modelo matemático debemos definir una
serie de operaciones a realizar con los objetos del tipo LISTA. Las operaciones más habituales
serán:

• Haz_nula. Inicializa la lista haciéndola nula. Imprescindible antes de poder usar una lista.
• Inserta_Al_Principio: Inserta un elemento al principio de la lista indicada (delante del primero);

falla si la lista está llena y no caben más elementos.

• Inserta_Al_Final: Inserta un elemento al final de la lista indicada (detrás del último); falla si la

lista está llena y no caben más elementos.

• Inserta_Delante: Inserta en la lista indicada el elemento indicado, delante del elemento cuya
posición se indica; falla si la lista está llena y no caben más elementos, o si la posición indicada
es incorrecta.

• Elimina: Elimina el elemento de la posición indicada de la lista indicada, y devuelve el elemento

eliminado. Falla si la posición indicada es incorrecta.

• Esta_Vacia: Devuelve True si la lista indicada está vacia, y False en caso contrario.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

8

Operaciones para recorrer la
lista

UNIVERSIDAD DE CANTABRIA

operación
Localiza

Elemento_de

Primera_Pos

Siguiente

Ultima_Pos

Anterior

in

out

in out

errores

el_elemento

la_lista

la_posicion

la_lista
la_lista

posicion_-

actual
la_lista
la_lista

posicion_-

actual
la_lista

la_posicion

el_elemento

la_posicion
posicion_-
siguiente

la_posicion
posicion_-
anterior

posicion_-
incorrecta

posicion_-
incorrecta

posicion_-
incorrecta

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

9

Notas:

UNIVERSIDAD DE CANTABRIA

Operaciones para recorrer las listas:

• Localiza: Busca en la lista indicada el elemento indicado, devolviendo su posicion. Devuelve

la constante Posicion_Nula si el elemento no se encuentra.

• Elemento_De: Es la operación contraria a Localiza; devuelve el elemento de la lista indicada

que se encuentra en la posición indicada. Falla si la posición indicada es incorrecta.

• Primera_Pos: Devuelve la posición del primer elemento de la lista indicada. Si la lista no tiene

elementos devuelve la constante Posicion_Nula.

• Ultima_Pos: Devuelve la posición del último elemento de la lista. Si la lista no tiene elementos

devuelve la constante Posicion_Nula.

• Siguiente: Devuelve la posición siguiente a la indicada, en la lista indicada. Si la posición

indicada es la última (en cuyo caso no hay más posiciones), devuelve Posicion_Nula. Falla
si la posición indicada es incorrecta.

• Anterior: Devuelve la posición anterior a la indicada, en la lista indicada. Si la posición indicada
es la primera (en cuyo caso no hay más posiciones), devuelve Posicion_Nula. Falla si la
posición indicada es incorrecta.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

10

Especificación de listas en
Ada, con parámetros de error

UNIVERSIDAD DE CANTABRIA

with Elementos; use Elementos; -- definición del tipo Elemento
package Listas is

type Posicion is private;
Posicion_Nula : constant Posicion;
type Lista is private;
type Errores_Listas is (Correcto,Posicion_Incorrecta,No_Cabe);

procedure Haz_Nula (La_Lista : in out Lista);
procedure Inserta_Al_Principio

procedure Inserta_Al_Final

(El_Elemento : in Elemento;
La_Lista : in out Lista;
Error : out Errores_Listas);

(El_Elemento : in Elemento;
La_Lista : in out Lista;
Error : out Errores_Listas);

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González

6/nov/08

11

Especificación de listas
(cont.)

UNIVERSIDAD DE CANTABRIA

procedure Inserta_Delante(

El_Elemento : in Elemento;
La_Posicion : in Posicion;
La_Lista : in out Lista;
Error : out Errores_Listas);

procedure Elimina (La_Posicion : in Posicion;

La_Lista : in out Lista;
El_Elemento : out Elemento;
Error : out Errores_Listas);

function Esta_Vacia (La_Lista : in Lista) return Boolean;

function Primera_Pos (La_Lista : in Lista) re