PDF de programación - Estructuras de datos básicas

Estructuras de
datos básicas

Secuencias

Xavier Sáez Pous

PID_00146766

Material docente de la UOC

© FUOC • PID_00146766

Estructuras de datos básicas

Primera edición: septiembre 2010
© Xavier Sáez Pous
Todos los derechos reservados
© de esta edición, FUOC, 2010
Av. Tibidabo, 39-43, 08035 Barcelona
Diseño: Manel Andreu
Realización editorial: Eureca Media, SL
ISBN: 978-84-693-4239-8
Depósito legal: B-33.175-2010

Ninguna parte de esta publicación, incluido el diseño general y de la cubierta, puede ser copiada,
reproducida, almacenada o transmitido de ninguna manera ni por ningún medio, tanto eléctrico
como químico, mecánico, óptico, de grabación, de fotocopia, o por otros métodos, sin la autorización previa
por escrito de los titulares del copyright.de los titulares del copyright.

c FUOC • PID_00146766

Índice

Estructuras de datos básicas

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. Pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.
Representación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Operaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.
Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.

2. Colas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.
Representación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Operaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.
2.4.
Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Representación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.
3.2. Operaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.
3.3.1.
Implementación secuencial . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2.
Implementación encadenada . . . . . . . . . . . . . . . . . . . . . . . . .
Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4.

4.1.
4.2.
4.3.

4. Punteros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Problemas de los vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
La alternativa: punteros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1.
Pila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.2. Cola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.3.
Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Peligros de los punteros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
La memoria dinámica no es infinita . . . . . . . . . . . . . . . . . .
4.4.1.
El funcionamiento del TAD depende de la
4.4.2.
representación escogida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.3.
Efectos laterales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.4.
Referencias colgadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.5.
Retales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.6. Conclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ejemplo de implementación definitiva: lista encadenada . . . . .

4.4.

4.5.

5

7

9
9
10
12
14

16
16
17
18
21

23
23
24
25
25
28
33

35
35
35
37
37
39
41
43
43

44
48
49
49
51
52

c FUOC • PID_00146766

Estructuras de datos básicas

4.6. Otras variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Listas circulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Listas doblemente encadenadas . . . . . . . . . . . . . . . . . . . . . .
Listas ordenadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.6.1.
4.6.2.
4.6.3.

55
55
56
56

Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

Actividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

Ejercicios de autoevaluación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

Solucionario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

Glosario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

Bibliografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

c FUOC • PID_00146766

Introducción

5

Estructuras de datos básicas

Una secuencia es un conjunto de elementos dispuestos en un orden específi-
co. Fruto de esta ordenación, dado un elemento de la secuencia, hablaremos
del predecesor (como el elemento anterior) y del sucesor (como el elemento
siguiente).

.

Dada la secuencia <v0 v1 ... vi vi+1 ... vn>, se dice que el elemento vi+1 es
el sucesor del elemento vi y que el elemento vi es el predecesor del ele-
mento vi+1. De la misma manera, diremos que v0 es el primer elemento
de la secuencia y que vn es el último.

La mayoría de algoritmos que desarrollaremos se centrarán en la repetición
de un conjunto de acciones sobre una secuencia de datos. Ahí radica la im-
portancia de saber trabajar con las secuencias. Sin ir más lejos, en asignaturas
anteriores ya habéis estudiado los esquemas de recorrido y búsqueda en una
secuencia.

Pero además, aparte de la importancia del tratamiento de las secuencias, en es-
te módulo averiguaremos cómo se almacenan de manera que posteriormente
podamos acceder a ellas secuencialmente.

.

Un tipo de datos consta de un conjunto de valores y de una serie de
operaciones que pueden aplicarse a esos valores. Las operaciones deben
cumplir ciertas propiedades que determinarán su comportamiento.

Las operaciones necesarias para trabajar con una secuencia son:

• Crear la secuencia vacía.

Insertar un elemento dentro de la secuencia.

•
• Borrar un elemento de la secuencia.
• Consultar un elemento de la secuencia.

El comportamiento que se establezca para cada una de las operaciones (¿dón-
de se inserta un elemento nuevo? ¿qué elemento se borra? ¿qué elemento se
puede consultar?) definirá el tipo de datos que necesitaremos.

c FUOC • PID_00146766

.

6

Estructuras de datos básicas

Un tipo abstracto de datos (abreviadamente TAD) es un tipo de datos
al cual se ha añadido el concepto de abstracción para indicar que la
implementación del tipo es invisible para los usuarios del tipo.

Un TAD cualquiera constará de dos partes:

• Especificación. En la que se definirá completamente y sin ambigüedades

el comportamiento de las operaciones del tipo.

•

Implementación. En la que se decidirá una representación para los valores
del tipo y se codificarán las operaciones a partir de esta representación.
Dado un tipo, podemos hallar varias implementaciones, cada una de las
cuales deberá seguir la especificación del tipo.

De este modo, el único conocimiento necesario para usar un TAD es la especifi-
cación, ya que explica las propiedades o el comportamiento de las operaciones
del tipo.

.

Las operaciones del TAD se dividirán en constructoras (devuelven un
valor del mismo tipo) y consultoras (devuelven un valor de otro tipo).
Dentro de las operaciones constructoras, se denominarán generadoras
las que formen parte del conjunto mínimo de operaciones necesarias
para generar cualquier valor del tipo, mientras que el resto se denomi-
narán modificadoras.

En este módulo nos centraremos en los tres TAD más típicos para representar
las secuencias:

• Pilas
• Colas
• Listas

La explicación de cada tipo seguirá la misma estructura. Primero, se presentará
el tipo de una manera intuitiva para entender el concepto. A continuación, se
describirá el comportamiento de las operaciones del tipo de una manera for-
mal. Y, para acabar, se desarrollará una implementación del tipo acompañada
de algún ejemplo para ver su uso.

c FUOC • PID_00146766

Objetivos

7

Estructuras de datos básicas

Al finalizar este módulo habréis alcanzado los objetivos siguientes:

1. Conocer los TAD pila, cola y lista; y saber qué propiedades los diferencian.

2. Dado un problema, decidir cuál es el TAD más adecuado para almacenar

los datos y saberlo usar.

3. Ser capaz de implementar cualquiera de los TAD presentados en el módulo,
mediante el uso de vectores o punteros. Ser también capaz d