María José Ferreiro Ramos
María Teresa García Horcajadas (Coordinadora)
Francisco Periáñez Gómez
Joaquín Pizarro Junquera
Jesús Román Álvarez-Ossorio

Esta asignatura comprende el estudio de los aspectos fundamentales de
organización de la información para su tratamiento automático por medio de un
programa. La construcción de programas y la organización de los datos que se
van a procesar son dos cuestiones inseparablemente unidas. No es posible tomar

decisiones sobre el modo de organizar los datos sin conocer los algoritmos que
van a aplicarse a éstos y, recíprocamente, el diseño de los algoritmos para
transformar los datos depende en gran medida de la representación y
organización de los mismos.
En consecuencia, el objetivo general de la asignatura es el estudio de una
metodología de programación basada en la creación de tipos abstractos de datos
que facilite la construcción de programas y el diseño de estructuras de datos
adecuadas para procesarlos eficientemente. Para alcanzar este objetivo general
se definen los siguientes objetivos específicos:

1. Dominio de la metodología de diseño de tipos de datos: abstracción,
especificación e implementación.
2. Estudio de tipos abstractos de datos lineales (pilas, colas, listas) y
algoritmos de tratamiento.
3. Análisis de las ventajas e inconvenientes de las diferentes
implementaciones de tipos abstractos de datos.
4. Encapsulamiento en módulos de programación de tipos abstractos de datos y
utilización en base a su especificación y no a su implementación.

Teoría: Tipos abstractos y estructuras de datos lineales. (30 horas)

Tema 1. Tipos abstractos de datos. (6 horas)
1.1. Conceptos, terminología y ejemplos.
1.2. Tipos abstractos de datos.
1.3. Modularidad.
1.4. Uso de TAD.
1.5. Ejemplo: Especificación e implementación del TAD Número Racional.
1.6. Ejemplo: Uso del TAD Número Racional.

Tema 2. Pilas. (5 horas)
2.1. Concepto de pila.
2.2. Especificación de operaciones.
2.3. Diferentes representaciones del TAD pila.
2.3.1. Estáticas.
2.3.2. Dinámicas.
2.4. Aplicaciones.

Tema 3. Colas. (5 horas)
3.1. Concepto de cola.
3.2. Especificación de operaciones.
3.3. Diferentes representaciones del TAD cola.
3.3.1. Estáticas: lineal y circular.
3.3.2. Dinámicas.
3.4. Aplicaciones.

Tema 4. Listas. (8 horas)
4.1. Concepto de lista.
4.2. Especificación de operaciones.
4.3. Diferentes representaciones del TAD lista.
4.3.1. Implementación mediante vectores.
4.3.2. Implementación mediante punteros.
4.4. Otras estructuras enlazadas.
4.4.1. Listas con cabecera.
4.4.2. Listas doblemente enlazadas.
4.5. TAD lista circular.
4.6. Aplicaciones de las listas.

Tema 5. Ficheros. (6 horas)
5.1. Introducción.
5.2. Conceptos básicos.
5.3. Organización secuencial.
5.3.1. Especificación del TAD fichero secuencial.
5.3.2. Implementación del TAD fichero secuencial.
5.4. Organización secuencial indexada.
5.5. Organización directa o aleatoria.

Prácticas: Resolución de problemas de programación utilizando tipos abstractos
de datos lineales. (30 horas)

Las prácticas de la asignatura se dedicarán a la resolución de problemas de
programación aplicando los principios de descomposición de problemas,
abstracción, especificación e implementación de tipos abstractos de datos
utilizando las características de modularidad que proporcione el lenguaje de
programación.
En cada tema del programa de prácticas se propondrán diversos problemas
pensados para incidir sobre los siguientes puntos:
• Crear diferentes tipos abstractos de datos y realizar distintas
implementaciones de cada tipo.
• Practicar con el uso eficiente de los distintos tipos abstractos de datos,
eligiendo los más adecuados para cada problema concreto.
• Trabajar con las especificaciones de los tipos sin hacer referencia a su
implementación.
• Practicar con la implementación más adecuada de cada tipo abstracto de
datos según el problema a resolver.

Tema 1. Tipos abstractos de datos (6 horas)
Tema 2. Pilas (5 horas)
Tema 3. Colas (5 horas)
Tema 4. Listas (8 horas)
Tema 5. Ficheros (6 horas)

Las clases teóricas se basarán fundamentalmente en las explicaciones del
profesor sobre el temario, así como en la realización de ejercicios prácticos
(sobre pizarra) asociados al mismo.
Se incentivará la participación activa del alumnado en las clases,
provocando el profesor un debate abierto sobre cada uno de los temas que se
traten, motivando a los alumnos para que propongan soluciones alternativas a
los problemas planteados y su posterior discusión.
A lo largo del curso se proporcionará al alumno guiones de prácticas en los
que se incluirán cuestiones teóricas y una serie de problemas de programación,
algunos se deberán resolver obligatoriamente y de los restantes habrá que
escoger un número determinado. El alumno realizará las prácticas bajo la
supervisión del profesor empleando un lenguaje de programación estructurada.

Prácticas:
El alumno realizará sus prácticas siguiendo las instrucciones de los guiones
de prácticas que se le proporcionarán a lo largo del curso. Al finalizar cada
práctica y antes de comenzar la siguiente, el alumno deberá hacer entrega de la
práctica realizada. A lo largo del curso se realizarán controles de prácticas,
consistentes en pruebas escritas sobre el contenido de las mismas, que se
anunciarán con suficiente antelación. Estos controles serán evaluados, dando
lugar a la nota de prácticas, que será la media aritmética de las
calificaciones individuales de todos ellos. La nota de prácticas formará parte
de la calificación final en la asignatura. No obstante, para que
la evaluación de prácticas sea tenida en cuenta se considera obligatoria la
asistencia regular a las clases prácticas, por lo que no se admitirán más de
dos faltas no justificadas documentalmente durante el curso. Igualmente será
obligatoria la entrega en plazo de las prácticas, admitiéndose como máximo la
entrega fuera de plazo o la falta de una ellas.

Examen final:
Se realizará un examen final escrito que constará de dos partes, una
teórica y otra práctica. La primera constará de una serie de preguntas de
respuesta corta y la segunda incluirá diversos problemas para los que el alumno
deberá aportar una solución fundamentada en el contenido teórico de la
asignatura, así como implementar dicha solución. El examen se puntuará en una
escala de 0 a 10, ponderando al 25% la teoría y al 75% los problemas.

Calificación final:
Si la nota del examen es inferior a 4, la calificación final
será "suspenso". En caso contrario y si el alumno tiene una nota de prácticas
superior a la del examen final, la nota final será la media ponderada de ambas
(examen 60% y prácticas 40%); pero, si la nota de prácticas es inferior a la
del examen, entonces la nota final será la obtenida en el examen.

Alonso, J.A.; Argudo, J.F.; García, M.T.
Estructuras de Datos I.
Depto. Lenguajes y Sistemas Informáticos, UCA, 2003.
Ammernal, L.
Programs and Data Structures in C. Wiley, 1991.
Aho, A.; Hopcroft, J.; Ullman, J.
Estructuras de datos y algoritmos. Addison-Wesley, 1988.
Fernández-Valdivia, J.; Garrido, A.; García, M.
Estructuras de datos. Un enfoque práctico usando C. 1998.
Folk, M.J.; Zoellick, B.
Estructuras de Archivos. Addison-Wesley, 1992.
Heileman, G. L.
Estructuras de Datos, Algoritmos y Programación Orientada a Objetos.
McGraw-Hill, 1996.
Horowith, E.; Shanni, S.
Fundamentals of data structures in Pascal. Computer Science Press, 1990.
Knuth, D.
El arte de programar ordenadores. Ed. Reverté, 1987.
Kruse, R. L.; Leung, B. P.; Tondo, C. L.
Data Structures and Program Design in C. Prentice-Hall, 1991.
Langsam, Y; Augenstein, M. J.; Tenenbaum, A. M.
Estructuras de Datos con C y C++. Prentice-Hall, 1997.
Liskov, B.; Guttag, J.
Abstraction and specification in program development. MIT Press, 1989.
Schildt, H.
C: Manual de Referencia. McGraw-Hill, 1990.
Standish, T.A.
Data Structures, Algorithms and Software Principles in C.
Addison-Wesley, 1995.
Weiss, M.
Data Structures and Algorithm Analysis in C. Addison-Wesley, 1996.
Wirth, N.
Algoritmos + Estructuras de datos = Programas. Ed. del Castilllo, 1980.
Wirth, N.
Algoritmos y Estructuras de datos. Prentice-Hall, 1986.