PDF de programación - Capítulo 8 - Diseño e implementación de TADs lineales

Capítulo 8
Diseño e implementación de TADs
lineales1

Empieza por el principio dijo el Rey con
gravedad  y sigue hasta llegar al nal; allí te
paras.

Lewis Carroll deniendo, sin pretenderlo, el
recorrido de una estructural lineal en Alicia en el
país de las maravillas.

Resumen: En este tema se presentan los TADs lineales, dando al menos una im-
plementación de cada uno de ellos. Se presenta también el concepto de iterador que
permite recorrer una colección de objetos y se extiende el TAD lista para que soporte
recorrido y modicación mediante iteradores.

1. Motivación

El agente 0069 ha inventado un nuevo método de codicación de mensajes secretos. El

mensaje original X se codica en dos etapas:

1. X se transforma en X reemplazando cada sucesión de caracteres consecutivos que

no sean vocales por su imagen especular.

2. X se transforma en la sucesión de caracteres X obtenida al ir tomando sucesiva-
mente: el primer carácter de X, luego el último, luego el segundo, luego el penúltimo,
etc.

Ejemplo: para X = Bond, James Bond, resultan:
X = BoJ ,dnameB sodn
y
X = BnodJo s, dBneam
¾Serías capaz de implementar los algoritmos de codicación y decodicación?

1Marco Antonio Gómez es el autor principal de este tema.

175

176

Capítulo 8. Diseño e implementación de TADs lineales

Apostamos que sí; inténtalo. A buen seguro te dedicarás a utilizar vectores de caracteres
y enteros a modo de índice a los mismos. En este tema aprenderás a hacerlo de una forma
mucho más fácil gracias a los TADs lineales. Al nal del tema vuelve a implementarlo y
compara las dos soluciones.

2. Estructuras de datos lineales

Antes de plantearnos los distintos tipos abstractos de datos lineales nos planteamos
cómo podemos guardar en memoria una colección de datos lineal. Hay dos aproximaciones
básicas:

Todos los elementos de forma consecutiva en la memoria: vector de elementos.

Elementos dispersos en memoria guardando enlaces entre ellos: listas enlazadas.

Cada una de las alternativas tiene sus ventajas y desventajas. Las implementaciones
de los TADs lineales que veremos en el tema podrán hacer uso de una u otra estructura
de datos; la elección de una u otra podrá inuir en la complejidad de sus operaciones.

Veamos cada una de ellas. Es importante hacer notar que estamos hablando aquí de
estructuras de datos o estrategias para almacenar información en memoria. Por eso no
planteamos de forma exhaustiva qué operaciones vamos a tener, ni el invariante de la
representación ni relación de equivalencia. Introducimos aquí simplemente los métodos
típicos que las implementaciones de los TADs que hacen uso de estas estructuras de datos
suelen incorporar para el manejo de la propia estructura.

2.1. Vectores de elementos

La idea fundamental es guardar todos los elementos en un vector/array utilizando el
tipo primitivo del lenguaje. Dado que un vector no puede cambiar de tamaño una vez
creado, se impone desde el momento de la creación un límite en el número de elementos
que se podrán almacenar; de ellos solo los n primeros tendrán información útil (el resto
debe verse como espacio reservado para almacenar otros elementos en el futuro).

Para superar la limitación del tamaño jo es habitual hacer uso de vectores dinámicos:
se crea un array en la memoria dinámica capaz de albergar un número jo de elementos;
cuando el vector se llena se construye un nuevo array más grande, se copian los elementos
y se elimina el antiguo.

Denición de tipos

Las implementaciones que quieran hacer uso de esta estructura de datos utilizan nor-

malmente tres atributos:

Puntero al array almacenado en memoria dinámica.

Tamaño de ese array (o lo que es lo mismo, número de elementos que podría almacenar
como máximo).

Número de elementos ocupados actualmente. Los índices ocupados casi siempre se
condensan al principio del array.

Estructura de Datos y Algoritmos

2. Estructuras de datos lineales

177

template <class T>
class VectorDinamico {
public:

...

private:

l o s d a t o s . ∗/

/∗∗ Puntero a l a r r a y que c o n t i e n e
T *_v;
/∗∗ Tamaño d e l v e c t o r _v . ∗/
unsigned int _tam;
/∗∗ Número de e l e m e n t o s
unsigned int _numElems;

r e a l e s g u a r d a d o s . ∗/

};

Creación

La creación consiste en crear un vector con un tamaño inicial. En el código siguiente

ese tamaño (denido en una constante) es 10.

template <class T>
class VectorDinamico {
public:

/∗∗ Tamaño i n i c i a l d e l v e c t o r d i n á m i c o . ∗/
static const int TAM_INICIAL = 10;
/∗∗ C o n s t r u c t o r ∗/
VectorDinamico() :

_v(new T[TAM_INICIAL]),

_tam(TAM_INICIAL),
_numElems(0) {

}

...

};

Operaciones sobre la estructura de datos

Las operaciones relevantes en esta estructura de datos son:

Método para ampliar el vector: cuando el TAD quiera añadir un nuevo elemento en
el vector pero esté ya lleno debe crear un vector nuevo. Para que el coste amortizado
de las inserciones sea constante el tamaño del vector se dobla 2.

2El coste amortizado se utiliza cuando una función presenta costes muy distintos en distintas llamadas
y se quiere obtener un coste más preciso que el caso peor de la función. En ese caso se calcula el caso
peor de una secuencia de llamadas a la función. Decir que una función requiere un tiempo amortizado
constante signica que para cualquier secuencia de n llamadas, el tiempo total de la secuencia está acotado
superiormente por cn, para una cierta constante c > 0. Se permite por tanto un tiempo excesivo para una

Facultad de Informática - UCM

178

Capítulo 8. Diseño e implementación de TADs lineales

Al eliminar un elemento intermedio del vector hay que desplazar los elementos que
quedan a la derecha del eliminado.

template <class T>
class VectorDinamico {

...

protected:

/∗∗
D u p l i c a e l
∗/
void amplia() {

tamaño d e l v e c t o r .

T *viejo = _v;
_tam *= 2;
_v = new T[_tam];

for (unsigned int i = 0; i < _numElems; ++i)

_v[i] = viejo[i];

delete []viejo;

}
/∗∗
E l i m i n a un e l e m e n t o d e l v e c t o r ; compacta l o s
a l p r i n c i p i o d e l v e c t o r .
@param pos En e l
∗/
void quitaElem(int pos) {

i n t e r v a l o 0 . . numElems−1.

assert((0 <= pos) && (pos < _numElems));

--_numElems;
for (int i = pos; i < _numElems; ++i)

_v[i] = _v[i+1];

e l e m e n t o s

}

};

Destrucción

La destrucción requiere simplemente eliminar el vector creado en el constructor o en el

método amplia().
template <class T>
class VectorDinamico {
public:

...

~VectorDinamico() {

delete []_v;

llamada sólo si se han registrado tiempos muy breves anteriormente. En el caso de la inserción, el vector
se dobla tras n inserciones de coste O(1), por lo que el coste de la secuencia sería n ∗ O(1) + O(n) = O(n).
Puede entonces considerarse que el coste amortizado de cada insercion esta en O(1).

Estructura de Datos y Algoritmos

2. Estructuras de datos lineales

179

}
...

};

2.2. Listas enlazadas

En este caso cada elemento es almacenado en un espacio de memoria independiente
(un nodo) y la colección completa se mantiene utilizando punteros. Hay dos alternativas:

Listas enlazadas simples (o listas simplemente enlazadas): cada nodo mantiene un
puntero al siguiente elemento.

Listas doblemente enlazadas: cada nodo mantiene dos punteros: el puntero al nodo
siguiente y al nodo anterior.

Aquí aparece la implementación de esta segunda opción, por ser más versátil. No obs-
tante en ciertas implementaciones de TADs esa versatilidad no aporta ventajas adicionales
(por ejemplo en las pilas), por lo que sería más eciente (en cuanto a consumo de memoria)
el uso de listas enlazadas.

Denición de tipos

Dependiendo del TAD que utilice esta estructura de datos, sus atributos serán distintos.
Todas las implementaciones tendrán, eso sí, la denición de la clase Nodo que es la que
almacena por un lado el elemento y por otro lado los punteros al nodo siguiente y al nodo
anterior. Esa clase en C++ la implementaremos como una clase interna.
template <class T>
class ListaEnlazada {
public:

...

private:

/∗∗
C l a s e nodo que almacena i n t e r n a m e n t e
y dos p u n t e r o s , uno a l nodo a n t e r i o r y o t r o a l nodo s i g u i e n t e .
Ambos p u n t e r o s p o d r í a n s e r NULL s i
y /o ú l t i m o de l a
∗/
class Nodo {
public:

e l e m e n t o ( de t i p o T) ,

l i s t a e n l a z a d a .

e l

e l nodo e s

e l p r i m e r o

Nodo() : _sig(NULL), _ant(NULL) {}
Nodo(const T &elem) : _elem(elem), _sig(NULL), _ant(NULL) {}
Nodo(Nodo *ant, const T &elem, Nodo *sig) :

_elem(elem), _sig(sig), _ant(ant) {}

T _elem;
Nodo *_sig;
Nodo *_ant;

};

};

Facultad de Informática - UCM

180

Creación

Capítulo 8. Diseño e implementación de TADs lineales

Dado que una lista vacía no tiene ningún nodo, el proceso de creación solo implica
inicializar los atributos que apuntan al primero/último de la lista a NULL, para indicar la
ausencia de elementos.

Operaciones sobre la estructura de datos

Hay dos operaciones: creación de un nuevo nodo y su inserción en la lista enlazada y

eliminación.

La inserción que implementaremos recibe dos punteros, uno al nodo anterior y otro
al nodo siguiente al nodo nuevo a añadir; crea un nuevo nodo y lo devuelve. Notar
que algunos de los punteros pueden ser NULL (cuando se añade un nuevo nodo al
principio o al nal de la lista enlazada).

La operación de borrado recibe únicamente el nodo a eliminar. La implementación
utiliza el propio nodo para averiguar cuáles son los nodos anterior y siguiente para
modicar sus punteros. Notese que si estuvieramos implementado una lista enlaza-
da (y no doblemente enlazada) la operación necesitaría recibir un puntero al nodo
anterior.

template <class T>
class ListaEnlazada {

...

protected:

/∗∗
I n s e r t a un e l e m e n t o e n t r e
D e v u e l v e
Caso g e n e r a l :

nodo1−>_sig == nodo2
nodo2−>_ant == nodo1

e l nodo1 y e l nodo2 .

e l p u n t e r o a l nodo c r e a d o .

l o s dos nod