Ariel

UNIVERSIDAD TECNICA DE ORURO
FACULTAD NACIONAL DE INGENIERIA
INGENIERIA DE SISTEMAS E INFORMATICA









TEXTO GUIA:



ESTRUCTURA DE DATOS
SIS2204





Docente: Ing. Juan Gregorio Choque Uño
Fecha de Realización: Marzo del 2008











Oruro - Bolivia
CONTENIDO

INTRODUCCION 6

1.1 ESTRUCTURA DE DATOS. 6

1.2 OPERACIONES SOBRE ESTRUCTURAS DEDATOS. 9

PILAS Y COLAS 10

2.1 PILAS. 10
PILA SECUENCIAL 10
OPERACIONES CON PILAS 11
DISTRIBUCIÓN DE PILAS. 14
Manejo de Dos Pilas y Operaciones Primitivas. 14

2.2 COLAS. 17
COLA SECUENCIAL 17
OPERACIONES CON COLAS 17
INICIAR COLA. 17
ACCEDER A UN ELEMENTO EN LA COLA 18
INSERTAR UN ELEMENTO EN LA COLA. 18
ELIMINAR UN ELEMENTO DE LA COLA. 19

2.3 COLASCIRCULARES. 19
INSERCIÓN EN COLA CIRCULAR 20
ELIMINAR EL NODO DELANTERO DE LA COLA 20

2.4 APLICACIONES DE LISTAS RESTRINGIDAS. 22
ALGORITMO DE NOTACIÓN INFIJA A POSFIJA 22
ALGORITMO DE EVALUACIÓN EN NOTACIÓN POSFIJA 24

ARCHIVOS, REGISTROS Y CAMPOS 26

3.1 ARCHIVOS 26

3.2 TIPOS DE ARCHIVOS. 26
ARCHIVOS SECUENCIALES. 26
ARCHIVOS DIRECTOS. 27
OPERACIONES SOBRE ARCHIVOS 27

3.3REGISTROS Y CAMPOS. 28
TIPOS DE REGISTROS 29
OPERACIONES SOBRE REGISTROS. 29

TRATAMIENTO DE ARCHIVOS 30

4.1 INTRODUCCION 30

4.2 OPERACIONES SOBRE ARCHIVOS 30
ADICION DE DATOS 31
ELIMINAR DATOS 32
CONSULTAS DE DATOS 33
BUSQUEDA DE DATOS 34

4.3 PARTICION DE ARCHIVOS 35
PARTICION POR CONTENIDO 36
PARTICION POR UNA SECUENCIA " P " DADA 36
PARTICIÓN DE ARCHIVOSPOR TRAMOS ORDENADOS 37

4.4 MEZCLAS DE ARCHIVOS 38
MEZCLA POR CONTENIDO TOTAL 39
MEZCLA POR SECUENCIAS " P " 39
MEZCLA POR TRAMOS ORDENADAS 41

4.5 ORDENACIÓN EXTERNA 42
ORDENACIÓN POR MEZCLA DIRECTA 42
ORDENACIÓN POR VON NEWMAN 45
ORDENACIÓN POR MEZCLA EQUILIBRADA 47
ORDENACIÓN POR DIGITOS 49

LISTAS ENCADENADAS 52

5.1 LISTAS ENCADENADAS 52
TIPOS DE LISTAS. 525.2 LISTAS SIMPLEMENTE ENLAZADAS 53
OPERACIONES EN LISTAS SIMPLEMENTE ENLAZADAS 54
RECORRIDO 54
BUSQUEDA 55
INSERCION DE DATOS 55
ELIMINAR DATOS 58

5.3 LISTAS SIMPLEMENTE ENLAZADAS CIRCULARES. 59
OPERACIONES EN LISTAS SIMPLEMENTE ENLAZADAS CIRCULARES 60
RECORRIDO 60
BUSQUEDA 61
INSERCION DE DATOS 61
ELIMINAR DATOS 63

5.4 LISTAS DOBLEMENTE ENLAZADAS. 64OPERACIONES EN LISTAS DOBLEMENTE ENLAZADAS. 65
RECORRIDO 66
INSERCION DE DATOS 67
ELIMINAR DATOS 69

5.5 LISTAS CIRCULARES DOBLEMENTE ENLAZADAS. 72
OPERACIONES EN LISTAS DOBLEMENTE ENLAZADAS CIRCULARES. 73
RECORRIDO 73
INSERCION DE DATOS 74
ELIMINAR DATOS 76

ÁRBOLES 78

6.1 DEFINICION. 78
REPRESENTACIÓN 78
MATRIZ DE ADYACENCIA 79
LISTA DE ADYACENCIA 79
ESTRUCTURADINÁMICA PURA 79

6.2 CONCEPTOS ASOCIADOS 80

6.3 ARBOL BINARIO 81
DEFINICION 82
OPERACIONES BASICAS 82
INSERCIÓN DE DATOS 88
ELIMINAR UN DATO 88
BÚSQUEDA DE DATOS 90

6.4 ÁRBOLES BINARIOS DE EXPRESIONES 91
CONSTRUCCIÓN A PARTIR DE UNA EXPRESIÓN EN NOTACIÓN CONVENCIONAL 91

6.5 ÁRBOLES EQUILIBRADOS O AVL 93
DEFINICIÓN 93
INSERCIÓN EN AVL 94
IMPLEMENTACIÓN DE LAINSERCIÓN 101
BORRADO EN AVL 103
IMPLEMENTACIÓN DE LA ELIMINACIÓN 109

ÁRBOLES BINARIOS DE EXPRESIONES 113

GRAFOS 115

7.1 DEFINICIONES. 115

7.2 ALMACENAMIENTO DE UN GRAFO EN MEMORIA. 122

7.3 APLICACIONES. 126
TEMA 1

INTRODUCCION

 OBJETIVOS
Conceptuar las diferentes etapas por las que atraviesa el procesamiento de datos desde la abstracción de los mismos hasta laobtención de los resultados en la computadora.
 CONTENIDO
1.1 Estructura de Datos
1.2 Operaciones Sobre Estructuras de Datos

1.1 ESTRUCTURA DE DATOS.

Estructuras de datos y tipos de datos abstractos (TDA)
Un tipo de datos es una colección de valores
Un tipo de datos abstracto (TDA) es un tipo de datos definido de forma única mediante un tipo y un conjunto dado de operaciones definidas sobre...