Informatica

Ingeniería Técnica en
Informática de Gestión

Estructuras de Datos I

José Antonio Alonso de la Huerta
José Fidel Argudo Argudo
Mª Teresa García Horcajadas
Departamento de Lenguajes y Sistemas Informáticos

Estructuras de Datos I

Reservados todos los derechos de publicación. No se permite la reproducción total o parcial de este libro, ni el almacenamiento en un sistemainformático, ni transmisión en cualquier forma o por cualquier medio
electrónico, mecánico, fotocopia, registro u otros medios si el permiso
previo y por escrito de los titulares del copyright.
José Antonio Alonso de la Huerta
joseantonio.alonso@uca.es
José Fidel Argudo Argudo
josefidel.argudo@uca.es
Mª Teresa García Horcajadas
mayte.garcia@uca.es
Edita: Departamento de Lenguajes y SistemasInformáticos.
Universidad de Cádiz
ISBN: 84-89867-41-0
Primera edición – Marzo 2003

C ONTENIDO

1. Tipos Abstractos de Datos

1

1.1. Conceptos, terminología y ejemplos . . . . . . . . . . . . . .

1

1.2. Tipos Abstractos de Datos . . . . . . . . . . . . . . . . . . .

2

1.3. Modularidad . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.4. Uso de TAD...........................

5

1.5. Ejemplo: TAD número racional . . . . . . . . . . . . . . . .

7

1.6. Ejemplo: Uso del TAD número racional . . . . . . . . . . . 13
2. Tipo Abstracto de Datos PILA

17

2.1. Concepto de pila . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2. Especificación del TAD PILA

. . . . . . . . . . . . . . . . . 18

2.3. Implementación del TAD PILA . . . . . . .. . . . . . . . . 18
2.3.1. Implementación matricial de pilas . . . . . . . . . . 21
2.3.2. Implementación de pilas mediante celdas enlazadas 25
2.4. Aplicaciones de las pilas . . . . . . . . . . . . . . . . . . . . 27
3. Tipo Abstracto de Datos COLA

29

3.1. Concepto de cola . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2. Especificación del TAD COLA . . . . . . . . . . . . . .. . . 30
3.3. Implementación del TAD COLA . . . . . . . . . . . . . . . . 30
3.3.1. Implementación vectorial de colas . . . . . . . . . . 34
I

Contenido

II

3.3.2. Implementación de colas mediante estructuras enlazadas . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4. Aplicaciones de las colas . . . . . . . . . . . . . . . . . . . . 41
4. Tipo Abstracto de Datos LISTA

434.1. Concepto de lista . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2. Especificación del TAD LISTA . . . . . . . . . . . . . . . . . 44
4.3. Implementación del TAD LISTA . . . . . . . . . . . . . . . 45
4.3.1. Implementación vectorial . . . . . . . . . . . . . . . 45
4.3.2. Implementación mediante celdas enlazadas . . . . . 50
4.4. Otras estructuras enlazadas . . . . . . . . . . .. . . . . . . 56
4.4.1. Listas con cabecera . . . . . . . . . . . . . . . . . . . 56
4.4.2. Listas doblemente enlazadas . . . . . . . . . . . . . 60
4.5. TAD LISTA CIRCULAR . . . . . . . . . . . . . . . . . . . . 66
4.6. Aplicaciones de las listas . . . . . . . . . . . . . . . . . . . . 68
5. Ficheros

69

5.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2.Conceptos básicos . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3. Especificación del TAD Fichero Secuencial . . . . . . . . . . 75
5.4. Implementación del TAD Fichero Secuencial . . . . . . . . 76
5.5. Especificación del TAD Fichero Directo . . . . . . . . . . . . 79
5.6. Implementación del TAD Fichero Directo . . . . . . . . . . 81
5.7. Especificación del TAD Fichero Secuencial Indexado. . . . 86
5.8. Implementación del TAD Fichero Secuencial Indexado . . 88

Í NDICE

DE FIGURAS

1.1. Diferentes representaciones para un TAD . . . . . . . . . .

3

1.2. Resolución de un problema mediante el uso de TAD. . . . .

7

2.1. Modelo de una pila. . . . . . . . . . . . . . . . . . . . . . . . 17
2.2. Representación vectorial estática de una pila. . . . . . . . . 19...