Informatica

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 del copyright, bajo lassanciones 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

Índice 7 ____________________________________________________________

______________________

Índice
Presentación ...........................................................................................................11 Prólogo ....................................................................................................................13

Capítulo1 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.1Signaturas 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................................................341.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 tipos de datos...