Juan

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
porCristina 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: edupc@sg.upc.es
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 delcopyright, 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
AMiguel Angel, presente en mis recuerdos

Índice
7
__________________________________________________________________________________

Índice
Presentación ...........................................................................................................11
Prólogo ....................................................................................................................13Capí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 dedatos..................................................................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 especificacionesalgebraicas................................................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
1.4 Ecuaciones condicionales, símbolos auxiliares y errores.......................................48
1.4.1 Ecuacionescondicionales........................................................................48
1.4.2 Tipos y operaciones auxiliares ..................................................................50
1.4.3 Tratamiento de errores.............................................................................51
1.5 Estudio de casos ...............................................................................................53
1.5.1 Especificación de algunos...