estructuras de datos

POLITEXT

Xavier Franch Gutiérrez

Estructuras de datosEspecificación, diseño e implementación

EDICIONS UPC

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

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

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

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

Presentación...............................................................................................................191.1 Introducción a los tipos abstractos de datos .........................................................191.2 Modelo de un tipo abstracto de datos..................................................................25

1.2.1 Signaturas y términos...............................................................................261.2.2 Modelos asociados a una signatura...........................................................291.2.3 Evaluación de un término dentro de un álgebra .........................................321.2.4 Ecuaciones y especificaciones algebraicas................................................341.2.5 Modelo inicial de una especificación..........................................................371.2.6 Otros modelos posibles ...........................................................................43

1.3 Construcción sistemática de especificaciones......................................................451.3.1 Introducción al uso de especificaciones ....................................................451.3.2 Clasificación de las operaciones de una especificación...............................461.3.3 Método general de construcción de especificaciones................................47

1.4 Ecuaciones condicionales, símbolos auxiliares y errores.......................................481.4.1 Ecuaciones condicionales........................................................................481.4.2 Tipos y operaciones auxiliares ..................................................................501.4.3 Tratamiento de errores.............................................................................51

1.5 Estudio de casos ...............................................................................................531.5.1 Especificación de algunos tipos de datos clásicos......................................541.5.2 Especificación de una tabla de símbolos ...................................................601.5.3 Especificación de un sistema de reservas de vuelos ..................................63

1.6 Estructuración de especificaciones.....................................................................661.6.1 Uso de especificaciones ..........................................................................661.6.2 Ocultación de símbolos............................................................................671.6.3 Renombramiento de símbolos..................................................................681.6.4 Parametrización e instanciación ................................................................691.6.5 Combinación de los mecanismos..............................................................75

1.7 Ejecución de especificaciones............................................................................761.7.1 La deducción ecuacional..........................................................................771.7.2 La reescritura...........................................................................................78

Ejercicios ....................................................................................................................80

Índice 7__________________________________________________________________________________

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

Presentación...............................................................................................................892.1 El lenguaje de implementación ...........................................................................89

2.1.1 Representación de tipos..........................................................................912.1.2 Sentencias..............................................................................................932.1.3 Funciones y acciones ..............................................................................952.1.4 Ejemplo: una implementación para los conjuntos.......................................97

2.2 Corrección de una implementación .....................................................................982.3 Estudio de la eficiencia de las implementaciones................................................108

2.3.1 Notaciones asintóticas ...........................................................................1112.3.2 Órdenes de magnitud más habituales .....................................................1162.3.3 Análisis asintótico de la eficiencia temporal ..............................................1182.3.4 Análisis asintótico de la eficiencia espacial ...............................................121

2.4 Conflicto entre eficiencia y modularidad.............................................................1242.4.1 Falta de funcionalidad en la signatura ......................................................1252.4.2 Tipos abstractos de datos recorribles ......................................................1282.4.3 Tipos abstractos de datos abiertos..........................................................136

Ejercicios ..................................................................................................................148

Capítulo 3 Secuencias

Presentación.............................................................................................................1513.1 Pilas................................................................................................................151

3.1.1 Especificación.......................................................................................1533.1.2 Implementación.....................................................................................154

3.2 Colas...............................................................................................................1583.2.1 Especificación.......................................................................................1583.2.2 Implementación.....................................................................................159

3.3 Listas ..............................................................................................................1623.3.1 Especificación de las listas con punto de interés......................................1623.3.2 Implementación de las listas con punto de interés....................................1663.3.3 Implementación de estructuras de datos con punteros.............................1733.3.4 Transparencia de la representación usando punteros ..............................1783.3.5 Implementaciones encadenadas y TAD abiertos ......................................186

Ejercicios ..................................................................................................................189

Capítulo 4 Árboles

Presentación.............................................................................................................1954.1 Modelo y especificación ...................................................................................196

4.1.1 Modelo de árbol general.........................................................................1964.1.2 Modelo de árbol binario..........................................................................2014.1.3 Modelo de árbol con punto de interés.....................................................202

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

4.2 Implementación ...............................................................................................2044.2.1 Implementación de los árboles binarios ...................................................2044.2.2 Implementación de los árboles generales................................................2134.2.3 Variaciones en los otros modelos de árboles............................................2184.2.4 Estudio de eficiencia espacial .................................................................218

4.3 Recorridos.......................................................................................................2194.3.1 Recorridos en profundidad de los árboles binarios...................................2204.3.2 Árboles binarios enhebrados..................................................................2244.3.3 Recorrido por niveles de los árboles binarios ...........................................228

4.4 Colas prioritarias...............................................................................................2314.4.1 Implementación por árboles parcialmente ordenados y casi completos......2334.4.2 Aplicación: un algoritmo de ordenación...................................................238

Ejercicios ..................................................................................................................243

Capítulo 5 Tablas

Presentación.............................................................................................................2495.1 Especificación .................................................................................................250

5.1.1 Funciones totales..................................................................................2505.1.2 Conjuntos.............................................................................................2525.1.3 Tablas y conjuntos recorribles.................................................................252

5.2 Implementación ...............................................................................................2545.2.1 Implementación por listas desordenadas.................................................2545.2.2 Implementación por listas ordenadas.......................................................2555.2.3 Implementación por vectores de acceso directo.......................................2575.2.4 Implementación por tablas de dispersión.................................................258

5.3 Funciones de dispersión..................................................................................2595.3.1 Funciones de traducción de cadenas a enteros.......................................2605.3.2 Funciones de restricción de un entero en un intervalo .............................2635.3.3 Funciones de traducción de cadenas a enteros en un intervalo ................2655.3.4 Caracterización e implementación de las funciones de dispersión.............266

5.4 Organizaciones de las tablas de dispersión........................................................2705.4.1 Tablas de dispersión encadenadas .........................................................2705.4.2 Tablas de dispersión de direccionamiento abierto ....................................2785.4.3 Caracterización e implementación de los métodos de redispersión ...........2855.4.4 Variantes de las tablas de dispersión de direccionamiento abierto .............2885.4.5 Tablas dedispersión coalescentes ..........................................................2895.4.6 Evaluación de las diferentes organizaciones............................................2915.4.7 Elección de una organización de dispersión............................................2925.4.8 Las organizaciones de dispersión en tablas recorribles y tablas abiertas.....2955.4.9 Inconvenientes de la dispersión .............................................................296

5.5 Árboles binarios de búsqueda ..........................................................................2975.6 Árboles AVL ....................................................................................................303Ejercicios ..................................................................................................................315

Índice 9__________________________________________________________________________________

Capítulo 6 Relaciones binarias y grafos

Presentación.............................................................................................................3196.1 Relaciones binarias ..........................................................................................320

6.1.1 Especificación.......................................................................................3206.1.2 Implementación.....................................................................................324

6.2 Relaciones de equivalencia ..............................................................................3326.2.1 Implementaciones lineales .....................................................................3356.2.2 Implementación arborescente ................................................................3406.2.3 Compresión de caminos.........................................................................342

6.3 Grafos .............................................................................................................3466.3.1 Modelo y especificación.........................................................................3486.3.2 Implementación.....................................................................................352

6.4 Recorridos de grafos........................................................................................3606.4.1 Recorrido en profundidad ......................................................................3616.4.2 Recorrido en anchura.............................................................................3646.4.3 Recorrido en ordenación topológica .......................................................365

6.5 Búsqueda de caminos mínimos ........................................................................3696.5.1 Camino más corto de un nodo al resto.....................................................3706.5.2 Camino más corto entre todo par de nodos..............................................376

6.6 Árboles de expansión minimales.......................................................................3796.6.1 Algoritmo de Prim ..................................................................................3816.6.2 Algoritmo de Kruskal..............................................................................384

Ejercicios ..................................................................................................................387

Capítulo 7 Uso y diseño de tipos abstractos de datos

Presentación.............................................................................................................3977.1 Uso de tipos abstractos de datos existentes ......................................................398

7.1.1 Un evaluador de expresiones.................................................................3997.1.2 Un gestor de memoria dinámica ..............................................................4057.1.3 Un planificador de soluciones.................................................................412

7.2 Diseño de nuevos tipos abstractos de datos......................................................4207.2.1 Una tabla de símbolos............................................................................4207.2.2 Una cola compartida...............................................................................4237.2.3 Una emisora de televisión.......................................................................430

Ejercicios ..................................................................................................................439

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

Índice temático .....................................................................................................455

Índice de universos ..............................................................................................461

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

Presentación

Cuando me piden que escriba el prólogo de un libro, me da un poco de vergüenza, ya quese trata de una de mis asignaturas pendientes: he tenido hijos y he plantado árboles, ytambién he escrito muchas líneas, pero nunca un libro. Así que hacer de prologuista sinhaber sido autor me provoca un cierto sentimiento de jubilación anticipada. En este caso, noobstante, este sentimiento se confunde con una fuerte sensación de orgullo y satisfacción,provocada por el excelente trabajo de alguien que, en parte, me permito considerar discípulomío en el sentido ancestral de la palabra. Xavier Franch, autor de este libro, ha sido alumnomío durante sus estudios en la Facultat d'Informàtica de Barcelona, colaborador becariomientras era estudiante, después alumno de doctorado y compañero de departamento y,para terminar, siempre hemos trabajado juntos en proyectos de investigación y he dirigido sutesis doctoral. Tengo motivos, pues, para sentir esta satisfacción.

El texto en cuestión, además de actualizar el contenido de las materias ya clásicas deestructuras de datos, se adapta perfectamente al temario de una asignatura de los planes deestudio vigentes en la Facultat d'Informàtica de Barcelona, lo cual justificaría de por sí suexistencia. Pero, además, por su actualización del tema puede servir, total o parcialmente,para otros estudios de informática o para cualquier asignatura sobre estructuras de datos deotros planes de estudios en la Universitat Politècnica de Catalunya o en otras universidades.Y, como valor añadido, es destacable la experiencia del autor en la docencia de la asignatura“Estructuras de Datos y Algoritmos”, de los nuevos planes estudio vigentes en la Facultatd'Informàtica de Barcelona.

La notación empleada tanto en las especificaciones como en las implementaciones de lasestructuras de datos es Merlí, lenguaje emblemático del proyecto Excalibur y notación que,desde hace ya muchos años, ha caracterizado las diversas enseñanzas algorítmicas ennuestra facultad.

Por todo lo dicho es obvio que no soy nada imparcial a la hora de juzgar el trabajo del profesorXavier Franch, pero también tengo claro que la parcialidad es una pequeña licencia que, enuna presentación, nos podemos permitir.

Presentación 1 1__________________________________________________________________________________

Como ya he dicho, un excelente texto, que pone al día un tema clásico en informática. Mienhorabuena al autor. Y también al lector, que encontrará una muestra de aquello que elprofesor Turski decía hace muchos años: “no hay nada más práctico que una buena teoría”.Sobre todo si se explica desde un conocimiento sólido de la práctica.

Pere Botella i LópezCatedrático del Departamento de Lenguajes y Sistemas Informáticos (U.P.C.)

Decano de la Facultat d'Informàtica de Barcelona (U.P.C.)


Prólogo

El estudio de las estructuras de datos es casi tan antiguo como el nacimiento de laprogramación, y se convirtió en un tema capital en este ámbito desde finales de la década delos 60. Como es lógico, una de las consecuencias de este estudio es la aparición de unaserie de libros de gran interés sobre el tema, algunos de ellos ciertamente excelentes y quese han convertido en piedras angulares dentro de la ciencia de la programación (citemos, porejemplo, los textos de D.E. Knuth; de A.V. Aho, J. Hopcroft y J.D. Ullman; de E. Horowitz yD. Sahni; de N. Wirth; y, recientemente, de T.H. Cormen, C.E. Leiserson i R.L. Rivest).

Ahora bien, el progreso en el campo de la programación ha dado como resultado la apariciónde nuevos conceptos, algunos de los cuales no se han consolidado hasta la segunda mitadde la década de los 80. Muchos de estos conceptos están íntimamente interrelacionadoscon el ámbito de las estructuras de datos, y ésta es la razón por la cual los libros antes citadoshan quedado actualmente un poco desfasados en lo que respecta al método de desarrollode programas que siguen, incluso en sus reediciones más recientes.

En este contexto, he confeccionado el libro "Estructuras de datos. Especificación, diseño eimplementación", que trata el estudio de las estructuras de datos dentro del marco de lostipos abstractos de datos. La adopción de este enfoque se inscribe en una metodología dedesarrollo modular de programas, que abunda en diferentes propiedades interesantes en laproducción industrial de aplicaciones (corrección, mantenimiento, etc.), y permite enfatizardiversos aspectos importantes hoy en día: la necesidad de especificar el software, laseparación entre la especificación y la implementación, la construcción de bibliotecas decomponentes, la reusabilidad del software, etc. Diversos autores han explorado estametodología (sobre todo, desde las aportaciones de B. Liskov y J.V. Guttag), pero sinaplicarla en el contexto de las estructuras de datos.

DestinatarioEl libro ha sido concebido sobre todo como un texto de ayuda para alumnos de unaasignatura típica de estructura de datos en un primer ciclo de ingeniería en informática;también se puede considerar adecuado para cualquier otra titulación técnica superior omedia con contenido informático. A tal efecto, cubre el temario habitual de esta asignatura entono autoexplicativo, y se ilustra con numerosas figuras, especificaciones y programas.

Prólogo 1 3__________________________________________________________________________________

Dependiendo de los objetivos de la asignatura, el formalismo asociado al estudio de estostemas puede ser más o menos acusado; sea como sea, el libro puede usarse como textobásico de consulta.

Ahora bien, los temas que aparecen en el libro se han desarrollado con más profundidad quela estrictamente requerida por el alumno y, por ello, hay más posibles destinatarios. Por unlado, el mismo profesor de la asignatura, porque puede encontrar en un único volumen losaspectos de especificación y de diseño que no acostumbran a aparecer en los libros deestructuras de datos; además, la inclusión de especificaciones y de programas libera aldocente de la necesidad de detallarlos en sus clases. Por otro lado, cualquier informáticoque quiera profundizar en el estudio de las estructuras de datos más allá de su aspectopuramente de programación, puede encontrar aquí una primera referencia.

ContenidoEn el primer capítulo se introduce el concepto de tipo abstracto de datos. Después deanalizar su repercusión en el diseño de programas, nos centramos en el estudio de suespecificación formal, que es la descripción exacta de su comportamiento. De entre lasdiferentes opciones existentes de especificación formal, se sigue la llamada especificaciónecuacional interpretada con semántica inicial. El capítulo muestra un método general paraconstruir especificaciones para los tipos, les otorga un significado matemático (comoálgebras heterogéneas) y también estudia su estructuración, y aquí destaca la posibilidad dedefinir tipos genéricos, profusamente utilizados a lo largo del libro.

En el segundo capítulo se estudian diversos aspectos sobre la implementación de los tiposde datos. El proceso de implementación se lleva a cabo cuando existe una especificaciónpara el tipo; la segunda sección insiste precisamente en la relación formal entre los dosconceptos, especificación e implementación. También se introduce un punto clave en elanálisis de los algoritmos y las estructuras de datos que se desarrollarán posteriormente: elestudio de su eficiencia a través de las denominadas notaciones asintóticas. Por último, semuestran algunas situaciones de la programación con tipos abstractos de datos que puedencausar problemas de eficiencia, y se formulan algunos patrones de comportamiento parasolucionar estos problemas.

Las diversas familias de estructuras de datos se introducen en los cuatro capítulossiguientes: se estudian las secuencias; los árboles; las tablas y los conjuntos; y las relacionesbinarias y los grafos. Para todas ellas se sigue el mismo método: descripción informal,formulación de un modelo, especificación algebraica del tipo e implementaciones máshabituales. Por lo que se refiere a estas últimas, se detalla la representación del tipo y lacodificación de las operaciones (hasta el último detalle y buscando la máxima legibilidadposible mediante el uso de funciones auxiliares, diseño descendente, comentarios, etc.),siempre en el caso de implementación en memoria interna; a continuación, se estudia sueficiencia tanto temporal como espacial y se proponen varios ejercicios.


Por último, el capítulo final muestra la integración del concepto de tipo abstracto de datosdentro del desarrollo modular de programas, y lo hace bajo dos vertientes: el uso de los tiposabstractos previamente introducidos y el diseño de nuevos tipos de datos. El estudio sehace a partir de seis ejemplos escogidos cuidadosamente, que muestran la confrontación delos criterios de modularidad y eficiencia en el diseño de programas.

Para leer el texto, son necesarios unos conocimientos fundamentales en los campos de lasmatemáticas, de la lógica y de la programación. De las matemáticas, los conceptos básicos deconjunto, producto cartesiano, relación, función y otros similares. De la lógica, el conceptode predicado, los operadores booleanos y las cuantificaciones universal y existencial. De laprogramación, la habilidad de codificar usando un lenguaje imperativo cualquiera (Pascal, C,Ada o similares) que conlleva el conocimiento de los constructores de tipos de datos (tuplasy vectores), de las estructuras de control de flujo (asignaciones, secuencias, alternativas ybucles) y de los mecanismos de encapsulamiento de código (acciones y funciones).

Es importante destacar algunos puntos que el libro no trata, si bien por su temática se podríahaber considerado la posibilidad de incluirlos. Primero, no aparecen algunas estructuras dedatos especialmente eficientes que, por su complejidad, superan el nivel de una asignaturade primer ciclo de ingeniería; por ejemplo, diversas variantes de montículos y de árboles debúsqueda (Fibonnaci Heaps , Red-Black Trees, Splay Trees, etc.) y de dispersión (PerfectHashing, principalmente). También se excluyen algunas otras estructuras que se aplicanprincipalmente a la memoria secundaria, como pueden ser las diversas variantes de árboles By también los esquemas de dispersión incremental (Extendible Hashing , Linear Hashing ,etc.). Tampoco se tratan en el libro algunos temas característicos de la programación, comopueden ser el estudio de diversas familias de algoritmos (Greedy Algorithms, DynamicProgramming, etc.) de los cuales constan algunos casos particulares en el capítulo de grafos;o como las técnicas de derivación y de verificación formal de programas, si bien se usanalgunos elementos (invariantes de bucles, precondiciones y postcondiciones de funciones,etc.). Hay diversos libros de gran interés que sí tratan en profundidad estos temas, cuyasreferencias aparecen convenientemente en este texto. Por último, no se utilizan losconceptos propios de la programación orientada a objetos (básicamente, herencia yvinculación dinámica) para estructurar los tipos de datos formando jerarquías; se ha preferidoel enfoque tradicional para simplificar el volúmen de la obra y no vernos obligados a introducirla problemática inherente a este paradigma de la programación.

BibliografíaLas referencias bibliográficas del libro se pueden dividir en dos grandes apartados. Por unlado se citan todos aquellos artículos que son de utilidad para temas muy concretos, cuyareferencia aparece integrada en el texto en el mismo lugar en que se aplican. Por el otro, haydiversos textos de interés general que cubren uno o más capítulos del libro y que aparecendentro del apartado de bibliografía; estos libros han de considerarse como los másdestacables en la confección de esta obra y no excluye que haya otros, igualmente buenos,

Prólogo 1 5__________________________________________________________________________________

que no se citan, bien porque su temática es muy similar a alguno de los que sí aparecen, bienporque el desarrollo de los temas es diferente al que se sigue aquí.

LenguajeEn cualquier texto sobre programación, es fundamental la elección del lenguaje utilizadocomo vehículo para codificar (y, en este libro, también para especificar) los esquemas que seintroducen. En vez de especificar y programar usando algun lenguaje existente, he preferidoemplear la notación Merlí, diseñada por diversos miembros del Departament de Llenguatgesi Sistemes Informàtics (antiguamente, Departament de Programació) de la UniversitatPolitècnica de Catalunya. Esta notación ha sido utilizada desde principios de los años 80 porlos profesores del departamento en la impartición de las asignaturas de programación de losprimeros niveles de las titulaciones en informática y ha demostrado su validez comoherramienta para el aprendizaje de la programación. Las razones de esta elección sonbásicamente dos: por un lado, disponer de una notación abstracta que permita expresarfácilmente los diferentes esquemas que se introducen sin ningún tipo de restricciónimpuesta por el lenguaje; por otro, usar una sintaxis muy parecida tanto para especificar comopara implementar los tipos de datos (el hecho de que el mismo lenguaje se pueda usardesde estos dos niveles diferentes refuerza la relación entre la especificación y laimplementación de los tipos de datos, que es uno de los objetivos del texto). Elinconveniente principal es la necesidad de traducir las especificaciones y los programas queaparecen en este texto a los lenguajes que el lector tenga a su disposición; ahora bien, esteinconveniente no parece muy importante, dado que Merlí es fácilmente traducible acualquier lenguaje comercial (a algunos mejor que a otros, eso sí), y que podría haberaparecido el mismo problema fuera cual fuera el lenguaje de trabajo elegido.

TerminologíaDado que, hoy en día, el idioma dominante en el ámbito de la informática es el inglés, hehecho constar las acepciones inglesas junto a aquellos vocablos que denotan conceptosbásicos y universalmente aceptados; de esta manera, el lector puede relacionar rápidamenteestos conceptos dentro de su conocimiento de la materia o, en el caso de que sea el primerlibro que lee sobre estructuras de datos, adquirir el vocabulario básico para la lecturaposterior de textos ingleses. Los términos ingleses se escriben siempre en singularindependientemente del género con el que se usen en castellano.

Por el mismo motivo, se utilizan de manera consciente varios anglicismos usuales en elámbito de la programación para traducir algunos términos ingleses. Dichos anglicismos selimitan a lo estrictamente imprescindible, pero he creído conveniente seguir la terminologíatécnica habitual en vez de introducir vocablos más correctos desde el punto de vistalinguístico pero no tan profusamente usados.


AgradecimientosEste libro es el resultado de una experiencia personal de varios años de docencia en lasasignaturas de estructuras de datos en los planes de licenciatura e ingeniería de la Facultatd'Informàtica de Barcelona de la Universitat Politècnica de Catalunya, por lo que refleja ungran número de comentarios y aportaciones de todos los profesores que, a lo largo de esteperíodo, han sido compañeros de asignatura. Quizás el ejemplo más paradigmático sea lacolección de ejercicios propuestos en el texto, muchos de ellos provinentes de las listas deejercicios y exámenes de las asignaturas citadas. Para ellos mi más sincero agradecimiento.En particular, quiero citar al profesor Ricardo Peña por su ayuda durante el primer año queimpartí la asignatura "Estructuras de la Información"; a los profesores y profesoras M.T. Abad,J.L. Balcázar, J. Larrosa, J. Marco, C. Martínez, P. Meseguer, T. Moreno, P. Nivela, R.Nieuwenhuis y F. Orejas por la revisión de secciones, versiones preliminares y capítulosenteros del texto y por la detección de errores; y, sobre todo, al profesor Xavier Burgués portodos los años de continuos intercambios de opinión, sugerencias y críticas. A todos ellos,gracias.

ContactoEl lector interesado puede contactar con el autor en la dirección electró[email protected], o bien dirigiéndose al departamento de Llenguatges i SistemesInformàtics de la Universitat Politècnica de Catalunya. En especial, el autor agradecerá lanotificación de cualquier errata detectada en el texto, así como toda sugerencia o crítica a laobra. También existe una página web con información sobre el libro, que se intenta manteneractualizada, cuya dirección es http://www-lsi.upc.es/~franch/publis/libro-eds.html.

Barcelona, 10 de Junio de 1996 (primera edición)12 de Noviembre de 2001 (última edición)

Prólogo 1 7__________________________________________________________________________________

Bibliografía

[ADJ78] J.A. Goguen, J.W. Thatcher, E.G. Wagner. "An Initial Algebra Approach to theSpecification, Correctness and Implementation of Abstract Data Types". EnCurrent Trends in Programming Methodology, Vol. IV, Prentice Hall, 1978.

[AHU83] A.V. Aho, J.E. Hopcroft, J.D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983.

[Bal93] J.L. Balcázar. Programación Metódica. McGraw-Hill, 1993.[BrB97] G. Brassard, P. Bratley. Fundamentos de Algoritmia. Ed. Prentice Hall, 1997.[CLR90] T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms. The MIT

Press, 1990.[EhM85] H. Ehrig, B. Mahr. Fundamentals of Algebraic Specification , Vol. 1. EATCS

Monographs on Theoretical Computer Science, Springer-Verlag, 1985.[EhM90] H. Ehrig, B. Mahr. Fundamentals of Algebraic Specification , Vol. 2. EATCS

Monographs on Theoretical Computer Science, Springer-Verlag, 1990.[GoB91] G.H. Gonnet, R. Baeza-Yates. Handbook of Algorithms and Data Structures.

Addison-Wesley, 2ª edición,1991.[HoS94] E. Horowitz, S. Sahni. Fundamentals of Data Structures in Pascal . Computer

Science Press, 4ª edición,1994.[Knu68] D.E. Knuth. The Art of Computer Programming, Vol. 1. Addison-Wesley, 1968.[Knu73] D.E. Knuth. The Art of Computer Programming, Vol. 3. Addison-Wesley, 1973.[LiG86] B.H. Liskov, J.V. Guttag. Abstraction and Specification in Program Development .

The MIT Press, 1986.[Mar86] J.J. Martin. Data Types and Data Structures. Prentice-Hall, 1986.[Meh84] K. Mehlhorn. Data Structures and Algorithms, vols. 1 y 2. Springer-Verlag, 1984.[Peñ98] R. Peña. Diseño de Programas (2ª edición). Prentice Hall, 1998.[Tar83] R.E. Tarjan. Data Structures and Network Algorithms. Regional Conference Series

in Applied Mathematics (SIAM), Philadelphia, Pennsylvania, 1983.[TeA86] A.M. Tenenbaum, M.J. Augenstein. Data Structures using PASCAL. Prentice-Hall,

2ª edición, 1986.[vAP89] J.J. van Amstel, J.A.A.M. Poirters. The Design of Data Structures and Algorithms.

Prentice Hall and Academic Service, 1989.[Wir86] N. Wirth. Algorithms and Data Structures. Prentice-Hall, 1986.

Bibliografía 4 5 3__________________________________________________________________________________

Índice temático

A

Abstracción ....................................20,23Acción (en Merlí) ..................................95Acoplamiento de estructuras de datos.138Adyacencia........................................350Álgebra

cociente de términos..................40de términos................................31inicial .........................................40objeto matemático ................25, 30respecto una signatura ...............30

AlgoritmoBrent.......................................288compleción (Knuth-Bendix) ........79Dijkstra.....................................370Floyd.......................................376Kruskal.............................333, 384ordenación por inserción ..........122ordenación por montículo.........238Prim.........................................381voraz .......................................381

Altura (de un árbol) .............................198Antecesor (en un grafo)......................361Apiñamiento ..............................282, 290

primario....................................283Apuntador...........................................98

de sitio libre................................98externo....................................139

Árbol ...............................................195

2-3, B, B*, B+...........................303AVL.........................................303binario..............................196, 201de búsqueda....................221, 297casi-completo...................213, 233cerrado por prefijo ....................196compacto.................................196completo .................................213enhebrado...............................224de Fibonacci ............................303equilibrado...............................303etiquetado...............................196de expansión ...................379, 380de expansión de coste mínimo..380general ....................................196libre.........................................380n-ario.......................................196parcialmente ordenado.............233con punto de interés.........196, 202quadtree..................................246con raíz....................................380

Arco..................................................346Aridad

de un árbol...............................199de un símbolo............................28

Arista ..........................................v. arcoAscendente (en un árbol) ...................199Atajo .................................................138Axioma (especificación ecuacional) .......34

B

Basura...............................................178Biblioteca de módulos reusables...24, 125Bosque.............................................200Búsqueda

auto-organizativa......................255de caminos mínimos.................369dicotómica (binaria)...................256por interpolación ......................256lineal........................................256

Índice temático 4 5 5__________________________________________________________________________________

con movimiento al inicio ............255por transposición......................255

C

Cadena ...............................v. secuenciapredicado cadena.....................171de reubicación .........................282

Caminoen un árbol...............................198de un clave (de dispersión) .......278en un grafo ..............................350mínimo ....................................369

Campo (de tupla)..................................91Categoría ............................................74Ciclo ...............................................351Clave ...............................................249

indefinida.................................249invasora...................................278

Colisión.............................................258Cola

circular.....................................159compartida...............................423prioritaria ..........................231, 237TAD.........................................158

Complejidad..........................v. eficienciaComponente (fuertemente) conexo....350Compresión de caminos.....................342Conexión (en un grafo).......................350Congruencia induida por las ecuaciones39Conjunto

de base .....................................30TAD.........................................252

Constanteorden de magnitud ...................116valor ..........................................30

Constructor de tipopor enumeración........................91puntero ...................................173tupla..........................................91vector........................................91

Coste ...................................v. eficienciaCuadrado (método)............................263Cubeta..............................................258Cursor.................................................98

D

Deducción ecuacional..........................77Desbordamiento

en el cálculo.............................262en una tabla .............................274

Descendienteen un árbol...............................199en un grafo ..............................361

Desequilibrio .....................................305DD...................................305, 308DI.....................................307, 310

Digrafo ............................v. grafo dirigidoDiseño

descendente.............................22de estructuras de datos ............397modular (con TAD)......................22

Dispersiónconcepto.................................258función ............................258, 259incremental ..............................274organizaciones.........................270perfecta...................................260valor de dispersión ...................258

División (método)...............................263

E

Ecuación.............................................34condicional ................................49impurificadora.............................46parte derecha/izquierda..............35de recurrencia ..........................119

Eficiencia.....................................23, 108amortizada ...............................345

4 5 6 Estructuras de datos. Especificación, diseño e implementación __________________________________________________________________________________

en el caso peor..................110, 113Elemento

definido...................................249distinguido...............................162fantasma (centinela)..................170

Encadenamiento ...............................168Enlace.......................v. encadenamientoEnsayo..............................................278Enriquecimiento ..................................67Especificación .....................................20

algebraica (ecuacional) ..........25, 34método de construcción.............47parametrizada (genérica).............69pre-post.....................................97

Esquemas de programación ...............131de búsqueda....................131, 163de recorrido......................131, 163

Estructura de datos..............................25funcional..................................249lineal........................................151de partición..............................332

Etiqueta.....................................196, 346de coste nulo...........................369

Evaluador de expresiones..................399Extremidad (de un camino) .................350

F

Factorde carga (árbol).........................219de carga (tabla).........................292de equilibrio.............................304

Formade un árbol...............................196normal .......................................78

Funciónde abstracción..........................100de Ackerman............................345de asignación de variables ..........33de evaluación de términos ..........33de dispersión ...................258, 259

en Merlí .....................................95parcial ..............................249, 250de redispersión........................278de representación....................100TAD.........................................249total .................................249, 250universal ..................................263

Funtor.................................................75

G

Género .........................................v. tipoGrado v. aridadGrafo.................................................320

acíclico ....................................351bipartito ...................................346completo .................................348denso......................................348dirigido ....................................346disperso ..................................348etiquetado...............................346no dirigido................................346no etiquetado ..........................346TAD.........................................346

H

Hermano (en un árbol) ........................199Hijo (en un árbol) ................................199

derecho, izquierdo...................202izquierdo, hermano derecho.....214

Hoja ...............................................198

I

Identificador.......................................249Implementación ...................................20

corrección..................................98eficiencia .................................108

Índice temático 4 5 7__________________________________________________________________________________

lenguaje de implementación .......98universo de implementación..89, 90

Índicea tabla......................................249a vector......................................91

Instancia..............................................69parcial ........................................73

Invariantede un bucle................................93de una representación..............100

Invasor ...........................v. clave invasoraIsomorfismo.........................................32Iterador..............................................128

L

liberar_espacio ..................................174Lista

de adyacencia..........................355auto-organizativa......................255circular.....................................186doblemente encadenada..........187encadenada.............................143ordenada.................................161con punto de interés ................162

M

Marca ................................................143Matriz

de adyacencia..........................352dispersa...................................324

Memoria dinámica.......................174, 405MFSet ...............................................332Modelo

de un TAD............................25, 43inicial .........................................37

Módulo................................................23Montículo ..................................212, 235

de Fibonacci ............................370

Morfismo .............................................32Multilista (de grado dos)......................324Multilista de adyacencia ......................358

N

Nivel (en un árbol) ..............................198Nodo .................................195, 197, 346Notación asintótica

O.............................................112Ω .............................................112Θ .............................................113

Notación infix.....................................400Notació postfix (polaca).......................399NULO................................................174

O

Obsolescencia (de atajos)...................142obtener_espacio ...............................174Ocultación de símbolos........................67Operación ...........................................30

auxiliar (oculta, privada) ...............50consultora..................................46constructora...............................46constructora generadora.............46modificadora ..............................46

Orden de magnitud ............................113

P

Padre (en un árbol).............................199Parámetro

de entrada y/o de salida ..............95formal ........................................69real ............................................70

Parametrización ...................................69Paso de parámetros .............................70Pila


de sitios libres...................146, 169TAD.........................................151

Plegamiento-desplegamiento.............263Posición

de elemento ............................138de vector ...................................91

Postcondición .....................................97Precondición.......................................97Prioridad............................................231Programación dinámica.......................376Profundidad (en un árbol) .............v. nivelPuntero.............................................173Punto de acceso (en iterador).............128

R

Raíz...........................................195, 198Rama.................................................199Recolección de basura.......................178Recorrido

en anchura........219, 228, 361, 364inorden....................................220por niveles .......................219, 228en ordenación topológica..360, 365postorden................................220preorden .................................220en profundidad ........................360en profundidad hacia atrás ........362

Redispersión.....................................278Reescritura ..................................78, 247Referencia colgada ............................177Regla de escritura ................................78Relación

binaria (TAD).............................319binaria etiquetada.....................319de equivalencia (TAD) .......320, 332etiquetada ...............................320de igualdad..............................100m:n .................................v. binaria

Renombramiento de símbolos..............68Representante

canónico..............................41, 46de clase (de equivalencia).........340

Representación de tipo ..................90, 91encadenada.....................166, 168circular.....................................186doblemente.............................187secuencial........................154, 166

Reubicación...............................143, 145Reusabilidad..................................41, 46Robin Hood (método).........................289Rotación............................................306

S

S-aplicación.........................................32S-conjunto ..........................................27Secuencia.........................................151Semántica de un TAD...........................43

de comportamiento ....................44final ...........................................43inicial .........................................43laxa............................................44

SIG-álgebra..........................................30Signatura.............................................26Símbolo

de constante..............................28de operación..............................28

Sinónimo...........................................258Sistema de reescritura..........................78

Canónico...................................79Confluente ................................79Noetheriano...............................79

Subárbol....................................195, 199Subcamino........................................350Subciclo............................................351Subgrafo...........................................350Suma ponderada ...............................261

Índice temático 4 5 9__________________________________________________________________________________

T

Tablade dispersión...........................258de símbolos .......................60, 420TAD.........................................249

TAD ................v. Tipo Abstracto de DatosTeorema ecuacional .............................77Teoría ecuacional.................................77Término...............................................28

sobre SIG...................................28Tipo

auxiliar (oculto, privado)...............50de datos...............................19, 25de interés ..................................66

Tipo Abstracto de Datos (TAD) ..............19abierto.....................................146parcialmente abierto .................139recorrible .................................128recorrible ordenadamente.........128totalmente abierto ...........v. abierto

Tupla...................................................91variante......................................91

U

Union-find set ....................................332Universo..............................................26

de caracterización.......................69de definición (de especificación) .35genérico (parametrizado) ............70de implementación ...............89, 90

Uso ...............................................45, 66

V

Valor de dispersión.............................258Variable ...............................................29

de control (bucle) .......................93global ........................................95

local...........................................95Vector .................................................91Vértice ..............................................346

intermedio (en un camino).........350

Z

Zona de excedentes..........................274Zona principal ....................................274


Índice de universos

ALFABETO..........................................57

ARBOL_BINARIO...............................203

ARBOL_BINARIO_DE_BUSQUEDA.....30

ARBOL_BINARIO_ENC_1_VECTOR..210

ARBOL_BINARIO_ENC_PUNTEROS.205

ARBOL_GENERAL............................201

ARBOL_GENERAL_POR_BINARIO ...216

BOOL ............................................26, 35

CADENA........................................57, 76

CJT......................................................70

CJT_∈ .................................................71

CJT_∈ _ACOTADO.............................127

CJT_∈ _ACOTADO_IND......................137

CJT_∈ _ACOT._IND_PARC_ABIERTO 141

CJT_∈ _ACOTADO_POR_VECT...99, 127

CJT_∈ _ACOTADO_RECORRIBLE .....129

CJT_∈ _ACOT._REC._POR_VECT.....133

CJT_∈ _ACOTADO_REC._ORD..........131

CJT_∈ _ACOT._REC._ORD_VECT_1.134

CJT_∈ _ACOT._REC._ORD_VECT_2.135

CJT_RECORRIBLE............................253

CLAVE_DISPERSION ........................268

CLAVE_DISPERSION_LINEAL...........286

CLAVE_REDISPERSIÓN....................280

COLA ................................................159

COLA_CIRCULAR..............................161

COLA_PRIORITARIA..........................232

COLA_PRIOR._POR_MONTICULO....236

COMPOSICION_F_Y_G......................268

CONJUNTO .......................................252

COORDENADAS .................................69

DIGRAFO_ETIQ .................................349

DIGRAFO_ETIQ_LISTAS....................355

DIGRAFO_ETIQ_MATRIZ....................353

DIGRAFO_ETIQ_MULTILISTAS...........359

DIVISION............................................268

DOS_ENTEROS ............................69, 72

ELEM ..................................................70

ELEM_= ..............................................71

ELEM_< ..............................................76

ELEM_<_= ........................................130

ELEM_DISP_CONV...........................266

ELEM_2_ESP_= ...............................280

ELEM_ESP .......................................251

ELEM_ESP_<_=_+ ...........................369

ELEM_ORDENADO...........................332

ENTERO..............................................42

FUNCIONES_F ..................................266

FUNCIONES_G..................................267

FUNCION_TOTAL ..............................251

FUNCION_TOTAL_RECO._ORD ........253

LISTA_INTERES ................................165

LISTA_INTERES_ENC................172, 182

LISTA_INTERES_ENC_PUNT.....176, 184

LISTA_INTERES_SEC .......................166

MULTILISTA_TODO_CIRCULAR.........328

NAT..........................................27, 45, 52

PAR.....................................................72

PILA ..................................................153

PILA_SEC .........................................155

RACIONALES ................................69, 75

REDISPERSION_DOBLE...................287

REDISPERSION_LINEAL...................286

REDISP_LIN._SUMA_POND_Y_DIV...286

REDISP_DOB._SUMA_POND_Y_DIV 287

RELACION.........................................322

Índice de universos 4 6 1__________________________________________________________________________________

RELACION_DE_EQUIVALENCIA........335

RELACION_DE_EQUIV._ARB............343

RELACION_DE_EQUIV._LINEAL .......338

RELACION_ETIQUETADA..................323

SUMA_POND ....................................267

SUMA_POND_Y_DIV.........................269

TABLA_DIRECTA...............................276

TABLA_IND_PUNTEROS...................272

TABLA_ABIERTA...............................280

VAL_NAT.............................................73

VECTOR............................................157


Documents

estructuras de datos