PDF de programación - Estructuras de datos, especificación, diseño e implementación

POLITEXT

Xavier Franch Gutiérrez

Estructuras de datos
Especificación, diseño e implementación

EDICIONS UPC

La presente obra fue galardonada en el segundo concurso
"Ajut a l'elaboració de material docent" convocado por al UPC.

Traducido al castellano de la obra original de
Xavier Franch Gutiérrez Estructures de dades.
Especificació, disseny i implementació, realizada
por Cristina Ana Ruiz Núñez

Primera edición: septiembre de 1994
Segunda edición: diciembre de 1996
Tercera edición: abril de 1999

Diseño de la cubierta: Manuel Andreu

Para la versión catalana original:
 Xavier Franch, 1993
 Edicions UPC, 1993

Edicions de la Universitat Politècnica de Catalunya, SL
Jordi Girona Salgado 31, 08034 Barcelona
Tel. 934 016 883 Fax. 934 015 885
Edicions Virtuals: www.edicionsupc.es
e-mail: [email protected]

Para la versión castellana:
 Xavier Franch, 1993
 Cristina Ana Ruiz Núñez, para la traducción, 1994
 Edicions UPC, 1993

Producción: CBS – Impressió digital
Pintor Fortuny 151, 08224 Terrassa (Barcelona)

Depósito legal: B-18002-99
ISBN: 84-8301-300-2

Quedan rigurosamente prohibidas, sin la autorización escrita de los titulares del copyright, bajo las
sanciones establecidas en las leyes, la reproducción total o parcial de esta obra por cualquier medio
o procedimiento, comprendidos la reprografía y el tratamiento informático y la distribución de
ejemplares de ella mediante alquiler o préstamo públicos, así como la exportación e importación

A mis padres, por todo lo que me han dado
A Cristina, por lo que nos espera juntos
A Miguel Angel, presente en mis recuerdos

7
Índice
__________________________________________________________________________________

Índice

Presentación...........................................................................................................11

Prólogo ....................................................................................................................13

Capítulo 1 Especificación de tipos abstractos de datos

Presentación...............................................................................................................19
1.1
Introducción a los tipos abstractos de datos .........................................................19
1.2 Modelo de un tipo abstracto de datos..................................................................25
1.2.1 Signaturas y términos...............................................................................26
1.2.2 Modelos asociados a una signatura...........................................................29
1.2.3 Evaluación de un término dentro de un álgebra .........................................32
1.2.4 Ecuaciones y especificaciones algebraicas................................................34
1.2.5 Modelo inicial de una especificación..........................................................37
1.2.6 Otros modelos posibles ...........................................................................43
1.3 Construcción sistemática de especificaciones......................................................45
1.3.1 Introducción al uso de especificaciones ....................................................45
1.3.2 Clasificación de las operaciones de una especificación...............................46
1.3.3 Método general de construcción de especificaciones................................47
Ecuaciones condicionales, símbolos auxiliares y errores.......................................48
1.4.1 Ecuaciones condicionales........................................................................48
1.4.2 Tipos y operaciones auxiliares ..................................................................50
1.4.3 Tratamiento de errores.............................................................................51
Estudio de casos ...............................................................................................53
1.5.1 Especificación de algunos tipos de datos clásicos......................................54
1.5.2 Especificación de una tabla de símbolos ...................................................60
1.5.3 Especificación de un sistema de reservas de vuelos ..................................63
Estructuración de especificaciones.....................................................................66
1.6.1 Uso de especificaciones ..........................................................................66
1.6.2 Ocultación de símbolos............................................................................67
1.6.3 Renombramiento de símbolos..................................................................68
1.6.4 Parametrización e instanciación ................................................................69
1.6.5 Combinación de los mecanismos..............................................................75
Ejecución de especificaciones............................................................................76
1.7.1 La deducción ecuacional..........................................................................77
1.7.2 La reescritura...........................................................................................78
Ejercicios ....................................................................................................................80

1.7

1.6

1.4

1.5

8
Estructuras de datos. Especificación, diseño e implementación
__________________________________________________________________________________

Capítulo 2 Implementación de tipos abstractos de datos

Presentación...............................................................................................................89
El lenguaje de implementación ...........................................................................89
2.1
2.1.1 Representación de tipos..........................................................................91
2.1.2 Sentencias..............................................................................................93
2.1.3 Funciones y acciones ..............................................................................95
2.1.4 Ejemplo: una implementación para los conjuntos.......................................97
2.2 Corrección de una implementación .....................................................................98
Estudio de la eficiencia de las implementaciones................................................108
2.3
2.3.1 Notaciones asintóticas ...........................................................................110
2.3.2 Órdenes de magnitud más habituales .....................................................114
2.3.3 Análisis asintótico de la eficiencia temporal ..............................................116
2.3.4 Análisis asintótico de la eficiencia espacial ...............................................119
2.3.5 Eficiencia y modularidad.........................................................................122
Ejercicios ..................................................................................................................125

Capítulo 3 Secuencias

Presentación.............................................................................................................129
3.1
Pilas................................................................................................................129
3.1.1 Especificación.......................................................................................131
3.1.2 Implementación.....................................................................................132
3.2 Colas...............................................................................................................136
3.2.1 Especificación.......................................................................................136
3.2.2 Implementación.....................................................................................137
Listas ..............................................................................................................140
3.3.1 Especificación de las listas con punto de interés ......................................140
3.3.2 Implementación de las listas con punto de interés....................................144
3.3.3 Implementación de estructuras de datos con punteros.............................149
3.3.4 Transparencia de la representación usando punteros ..............................156
3.3.5 Algunas variantes en la implementación de listas......................................162
Ejercicios ..................................................................................................................166

3.3

Capítulo 4 Tablas

Presentación.............................................................................................................171
Especificación .................................................................................................172
4.1
4.2
Implementación ...............................................................................................174
4.2.1 Implementación por listas desordenadas.................................................175
4.2.2 Implementación por listas ordenadas.......................................................175
4.2.3 Implementación por vectores de acceso directo.......................................178
4.2.4 Implementación por tablas de dispersión.................................................178

9
Índice
__________________________________________________________________________________

4.3

Funciones de dispersión..................................................................................179
4.3.1 Funciones de traducción de cadenas a enteros.......................................181
4.3.2 Funciones de restricción de un entero en un intervalo .............................182
4.3.3 Funciones de traducción de cadenas a enteros en un intervalo ................184
4.3.4 Caracterización e implementación de las funciones de dispersión.............185
4.4 Organizaciones de las tablas de dispersión...........................