sistemas

UNIVERSIDAD TECNICA DE ORURO
FACULTAD NACIONAL DE INGENIERIA
INGENIERIA DE SIST EMAS E INFORMATICA

TEXTO GUIA:

ESTRUCTURA DE DATOS

SIS2204

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

Oruro - Bolivia

1

2

CONTENIDO
INTRODUCCION

6

1.1 ESTRUCTURA DE DATOS.

6

1.2 OPERACIONES SOB RE ES TRUCTURAS DE DATOS.

9

PILAS Y COLAS10

2.1 PILAS.
PILA S ECUENCIAL
OPERACIONES CON PILAS
DISTRIB UCIÓN DE PILAS.
Manejo de Dos Pilas y Operaciones Pri miti vas.

10
10
11
14
14

2.2 COLAS.
COLA S ECUENCIAL
OPERACIONES CON COLAS
INICIAR COLA.
ACCEDER A UN EL EMENTO EN LA COLA
INS ERTAR UN EL EMENTO EN LA COLA.
ELIMINAR UN ELEMENTO DE LA COLA.

17
17
17
17
18
18
19

2.3 COLAS CIRCULARES.
INS ERCIÓN ENCOLA CIRCULAR
ELIMINAR EL NODO DELANTERO DE LA COLA

19
20
20

2.4 APLICACIONES DE LIS TAS RES TRINGIDAS.
ALGORITMO DE NOTACIÓN INFIJA A POS FIJA
ALGORITMO DE EVALUACIÓN EN NOTACIÓN POSFIJ A

22
22
24

ARCHIVOS, REGISTROS Y CAMPOS

26

3.1 ARCHIVOS

26

3.2 TIPOS DE ARCHIVOS.
ARCHIVOS S ECUENCIALES.
ARCHIVOS DIRECTOS.
OPERACIONES SOB RE ARCHIVOS

26
26
27
27

3.3REGISTROS Y CAMPOS.
TIPOS DE REGIS TROS
OPERACIONES SOB RE REGIS TROS.

28
29
29

TRATAMIENTO DE ARCHIVOS

30

4.1 INTRODUCCION

30

4.2 OPERACIONES SOB RE ARCHIVOS
ADICION DE DATOS
ELIMINAR DATOS
CONSULTAS DE DATOS
BUSQUEDA DE DATOS

30
31
32
33
34

3

4.3 PARTICION DE ARCHIVOS
PARTICION POR CONTENIDO
PARTICION POR UNA SECUENCIA " P " DADA
PARTICIÓN DE ARCHIVOSPOR TRAM OS ORDENA DOS

35
36
36
37

4.4 MEZCLAS DE ARCHIVOS
MEZCLA POR CONTENIDO TOTAL
MEZCLA POR SECUENCIAS " P "
MEZCLA POR TRAMOS ORDENA DAS

38
39
39
41

4.5 ORDENACIÓN EXTERNA
ORDENACIÓN POR M EZCLA DIRECTA
ORDENACIÓN POR VON NEWMAN
ORDENACIÓN POR M EZCLA EQUILIBRADA
ORDENACIÓN POR DIGITOS

42
42
45
47
49

LISTAS ENCADENADAS

52

5.1 LISTAS ENCADENADAS
TIPOSDE LISTAS.

52
52

5.2 LISTAS SIMPLEMENT E ENLAZADAS
OPERA CIONES EN LISTAS SIMPLEM ENTE ENLAZA DAS
RECORRIDO
BUSQUEDA
INSERCION DE DATOS
ELIMINAR DATOS

53
54
54
55
55
58

5.3 LISTAS SIMPLEMENT E ENLAZADAS CIRCULARES.
OPERA CIONES EN LISTAS SIMPLEM ENTE ENLAZA DAS CIRCULARES
RECORRIDO
BUSQUEDA
INSERCION DE DATOS
ELIMINAR DATOS

59
60
60
61
61
63

5.4 LISTAS DOBLEMENTE ENLAZADAS.
OPERA CIONES EN LISTAS DOBLEM ENTE ENLAZA DAS.
RECORRIDO
INSERCION DE DATOS
ELIMINAR DATOS

64
65
66
67
69

5.5 LISTAS CIRCULARES DOB LEMENTE ENLAZADAS.
OPERA CIONES EN LISTAS DOBLEM ENTE ENLAZA DAS CIRCULARES.
RECORRIDO
INSERCION DE DATOS
ELIMINAR DATOS

72
73
73
74
76

ÁRBOLES

78

6.1 DEFINICION.
REPRESENTACIÓN
MATRIZ DE ADYA CENCIA
LISTA DE A DYACENCIA
ESTRUCTURA DINÁMICA PURA

78
78
79
79
79

6.2 CONCEPTOS ASOCIADOS

80

4

6.3 ARB OL B INARIO
DEFINICION
OPERA CIONES BASICAS
INSERCIÓN DE DATOS
ELIMINAR UN DATO
BÚSQUEDA DE DATOS

81
82
82
88
88
90

6.4 ÁRB OLES B INARIOS DE EXPRES IONES
CONSTRUCCIÓN A PA RTIR DE UNA EXPRESIÓN EN NOTACIÓN CONVENCIONAL

90
91

6.5 ÁRB OLES EQUILIB RADOS O AVL
DEFINICIÓNINSERCIÓN EN A VL
IMPLEM ENTACIÓN DE LA INSERCIÓN
BORRA DO EN A VL
IMPLEM ENTACIÓN DE LA ELIM INA CIÓN

92
93
93
100
103
109

ÁRB OLES B INARIOS DE EXPRES IONES

113

GRAFOS

115

7.1 DEFINICIONES.

115

7.2 ALMACENAMIENTO DE UN GRAFO EN MEMORIA.

122

7.3 APLICACIONES .

126

5

TEMA 1

INTRODUCCION
OBJETIVOS
Conceptuar las diferentes etapas por las queatraviesa el procesamiento de datos desde la abstracción de
los mismos hasta la obtenció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...