Algoritmos

Programaci´n Modular. ETSIT. 1o C.
o
Gui´n del profesor Juan Falgueras
o
Curso 2005
versi´n: 5 de mayo de 2005
o

5
Tipos abstractos de datos
Contenido
5. Tipos de datos abstractos
5.1. Definici´n de TDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
o
5.1.1. Historia de la abstracci´n de los datos en programaci´n . . . . . . .
o
o
5.1.2. Especificaciones . . . . .. . . . . . . . . . . . . . . . . . . . . . . . .
5.1.3. Operaciones y operadores . . . . . . . . . . . . . . . . . . . . . . . .
5.2. Ejemplos de TDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1. Ejemplo de TDA, los Naturales . . . . . . . . . . . . . . . . . . . . .
5.2.2. Segundo ejemplo, el Vector . . . . . . . . . . . . . . . . . . . . . . .
5.2.3. Especificaci´ndel TDA TVector . . . . . . . . . . . . . . . . . . . .
o
5.3. Implementaci´n mediante Objetos C++ . . . . . . . . . . . . . . . . . . . . .
o
5.4. Pilas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5. Especificaci´n del TDA pila . . . . . . . . . . . . . . . . . . . . . . . . . . .
o
5.5.1. Especificaci´n formal del TDA pila . . . . . . . . . . . . . . .. . . .
o
5.5.2. Procedimientos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.3. Excepciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6. Formas de implementaci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . .
o
5.6.1. Comparaci´n de las complejidades de las implementaciones de pilas
o
5.7. Aplicaciones de las pilas . . . . . . . . . . .. . . . . . . . . . . . . . . . . .
5.7.1. An´lisis de expresiones aritm´ticas . . . . . . . . . . . . . . . . . . .
a
e
5.7.2. Paso de par´metros . . . . . . . . . . . . . . . . . . . . . . . . . . .
a
5.7.3. Eliminaci´n de la recursividad con pilas . . . . . . . . . . . . . . . .
o
5.7.4. Comprobaci´n de par´ntesis . . . . . . . . . . . . . . . . . . . . . . .
o
e
5.7.5.Pilas.Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.8. Colas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.9. Especificaci´n del TDA cola . . . . . . . . . . . . . . . . . . . . . . . . . . .
o
5.9.1. Especificaci´n formal del TDA cola . . . . . . . . . . . . . . . . . . .
o
5.9.2. Constructores, Selectores, Iteradores . . . . . . . . . . . . .. . . . .
5.9.3. Excepciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.9.4. Formas de Implementaci´n . . . . . . . . . . . . . . . . . . . . . . .
o
5.9.5. Colas de prioridad . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.9.6. Colas.Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.10. Listas . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .
5.10.1. Especificaci´n formal del TDA lista . . . . . . . . . . . . . . . . . .
o
5.10.2. Interfaz e implementaciones . . . . . . . . . . . . . . . . . . . . . . .
5.10.3. Implementaciones acotada . . . . . . . . . . . . . . . . . . . . . . . .
5.10.4. Implementaci´n no acotada . . . . . . . . . . . . . . . . . . . . . . .
o
5.10.5. Listas.Ejercicios . .. . . . . . . . . . . . . . . . . . . . . . . . . . .
5.11. Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.11.1. Iteradores sobre tablas . . . . . . . . . . . . . . . . . . . . . . . . . .
5.11.2. Colisiones en hashing . . . . . . . . . . . . . . . . . . . . . . . . . .
5.11.3. Propiedades de las funciones hash . . . . . . . . . . . . . . . . . . .

..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
....