Portada Estructura de datos y organización de archivos

CAPITULO 1 INTRODUCCION A LA ESTRUCTURA DE DATOS ....1

El uso de datos ....1
Fuentes de información, 2 Tipos de decisiones, 2 Datos y decisiones ....2

Manejo de datos ....3
Objetivos del manejo de datos ....3

Clasificación de estructuras de datos ....4
Estructuras lógicas de datos, 4 Estructuras primitivas y simples ....4
Estructuras lineales y no lineales, 5 Organización de archivos ....5

Primitivas ....5
Enteros, 5 Booleanos, 5 Caracteres ....6

Cadenas ....6
Definición, 7 Longitud de cadena, 7 Concatenación de cadenas, 7 Subcadenas ....8
Operaciones compuestas, 9 Cadenas y enteros ....9

Estructuras de datos en lenguajes de programación ....10
Estructuras de datos definidas por el programador, 10 Declaración de primitivas
en COBOL, 11 Declaración de primitivas en Pascal, 11 Declaración de cadenas en
COBOL, 12 Declaración de cadenas en Pascal, 12 Operaciones de cadenas ....12

Formas de almacenamiento: Enteros ....13

Representación por signo y magnitud, 13 Representación de complemento a dos ....13
Representación de complemento a uno ....14

Formas de almacenamiento: Caracteres ....14
EBCDIC, 15 ASCII, 15 Esquemas de propósito especial, 15 Uso de código ....15
Representación de datos numéricos, 15 Representación de decimal empacado ....17

Formas de almacenamiento: Cadenas ....17
Alternativas de almacenamiento, 17 Representación de cadenas empacadas 19 Representación de cadenas desempacadas 19 Selección de la forma adecuada de almacenamiento ....20

Resumen ....21
Terminología ....22
Referencias sugeridas ....22
Ejercicios de repaso ....22

CAPITULO 2 ARREGLOS ....25

Arreglos unidimensionales ....25
Subíndices, 26 Definición, 26 Ejemplos ....26

Arreglos multidimensionales ....27
Subíndices, 27 Definiciones, 28 Ejemplos, 28 Sección transversal 29 Transpuesta, 29 Extensiones a más dimensiones ....30

Arreglos en COBOL y Pascal ....31
Arreglos unidimensionales, 31 Arreglos bidimensionales, 32 Más dimensiones 33 Operaciones sobre los elementos del arreglo, 33 Operaciones sobre arreglos ....33

Formas de almacenamiento: Arreglos unidimensionales ....34
Límite inferior: Uno, 34 Generalización del límite inferior ....35

Formas de almacenamiento: Arreglos multidimensionales ....35
Orden por renglón, 35 Orden por columna, 37 Selección de una técnica de linealización ....39

Arreglos triangulares ....40
Definiciones, 40 Linealización, 40 Espacio compartido, 41 Cambio de acomodo ....41

Arreglos dispersos ....42
Definición, 42 Linealización, 42 Representación vectorial, 42 Representación de listas ligadas ....43

Resumen ....43
Terminología ....44
Referencias sugeridas ....44
Ejercicios de repaso ....45

CAPITULO 3 REGISTROS ....48

Definiciones ....48
Formación de registros, 49 Ejemplos, 49 Claves de identificación, 50 Archivos ....50

Registros en COBOL y Pascal ....50
COBOL, 51 Pascal, S2 Calificación de nombres, 52 Ejemplo de flujo de tráfico ....54

Formas de almacenamiento ....55
Resumen ....55
Terminología ....56
Referencias sugeridas ....56
Ejercicios de repaso ....56

CAPITULO 4 PILAS ....57

Definiciones ....57
Lista lineal, 57 Pila, 57 Ejemplos, 58 Operaciones sobre pilas, S9 Ejemplo ....60

Pilas en COBOL y Pascal ....61
Pilas alojadas en arreglos, 61 Declaración de pilas, 62 Operaciones sobre pilas, ....63

Ejemplos de aplicaciones de pilas ....64
Correspondencia de paréntesis, 65 Recursión, 66 Notación postfija ....68

Formas de almacenamiento ....74
Espacio compartido ....74

Resumen ....75
Terminología ....76
Referencias sugeridas ....76
Ejercicios de repaso ....76

CAPITULO 5 COLAS ....78

Definiciones ....78
Operaciones de colas, 79 Ejemplo ....81

Colas en COBOL y Pascal ....82
Alojamiento de colas en arreglos, 82 Declaración de colas, 83 Operaciones de colas, 83 Desplazamiento a través del almacenamiento ....85

Colas circulares ....87
Uso de colas circulares, 89 Variaciones, 90 Una representación alterna 93 Resumen ....94

Comportamiento de colas ....95
Par metros de comportamiento, 95 Observación, 95 Simulación, 95 Teoría de colas ....96

Resumen ....97
Terminología ....97
Ejercicios de repaso ....97

CAPITULO 6 LISTAS LIGADAS

Representación de listas ligadas ....99
Problemas con la representación secuencial, 99 Representación no secuencial 100 Conceptos básicos, 100 Ventajas, 100 Costos ....101

Operaciones básicas en una lista ligada ....101
Notación, 101 Remoción de nodos, 103 Inserción de un nodo, ....104

Manejo del espacio disponible ....105
Almacenamiento compartido, 105 Asignación de un nuevo nodo, 106 Liberación de un nodo, ....107

Listas ligadas en Pascal usando variables apuntadoras ....108
Definición de listas ligadas,108 Manejo de espacio 109 Supresión de un nodo 109 Inserción de un nodo ....110

Listas ligadas en COBOL y Pascal, sin el uso de variables apuntadoras ....110
Utilizando un arreglo, 110 Definición de una lista ligada, 111 Supresión de un nodo, 112 Inserción de un nodo, ....112

Otras manipulaciones de listas ligadas individuales ....113
Localización de un nodo particular, 113 Inserción al final de una lista 114 Inversión de una lista, ....117

Listas circulares ligadas y nodos principales ....118
El problema de José, 118 Nodos principales, 119 Supresión de un nodo
particular ....121

Listas doblemente ligadas ....122
Conceptos básicos, 122 Definición de una lista doblemente ligada, 123 Supresión
de un nodo 124 Inserción de un nodo ....125

Ejemplos de aplicación de listas ligadas ....127
Polinomios, 127 Una lista multiligada simple, 132 Arreglos dispersos ....132

Resumen ....134
Terminología ....135
Referencias sugeridas ....135
Ejercicios de repaso ....135

CAPITULO 7 GRAFOS ....139

Definiciones ....139
Trayectorias, 14l Ciclos, 141 Grafosdirigidos, 142 Grafos en programas ....143

Representación de la matriz de adyacencias l....43
Grafos dirigidos, 144 Matrices dispersas, 144 Definición de grafos en COBOL y
Pascal, 145 Cálculo de aristas, 145 Aristas ponderadas ....146
aristas 151 Representación de multi-lista ....151

Representaciones ligadas ....147
Representación de directorio de nodos, 148 Aristas ponderadas, 150 Cálculo de

Recorrido de grafos ....153
Recorrido en amplitud, 153 Recorrido en profundidad, 155 Comparaciones ....156

Alcance y trayectorias más cortas ....157
Alcance, 157 Trayectorias más cortas ....158

Rutas críticas ....159

Árboles de expansión ....161
Algoritmo de Kruskal ....162

Resumen ....164
Terminología ....164
Referencias sugeridas ....165
Ejercicios de repaso ....165

CAPITULO 8 ÁRBOLES GENERALES Y BINARIOS ....167

Árboles generales ....167
Formas de representación ....169

Árboles binarios ....170

Representación de árboles binarios ....173
Definición de árboles en Pascal, 173 Definición de árboles en COBOL ....174

Árboles binarios como representación de árboles generales ....174

Ejemplos de árboles ....177

Árboles de búsqueda binarios ....178

Búsquedas secuenciales ....179
Los algoritmos, 180 Recorrido en-orden 181 Recorrido en-orden norecursivo 18l Recorrido en-orden en Pascal, 182 Recorrido post-orden en COBOL, ....183

Árboles binarios enlazados ....184
Representación de nodos, 184 Recorrido en-orden, 188 Una representación
alternativa, ....188

Búsquedas directas ....189

Inserción de nodos ....193
Inserción desenhilada, 193 Inserción enhilada ....193

Inserción de nodos un árbol de búsqueda binario ....195

Supresión de nodos ....196
Eliminación enhilada ....196

Supresión de nodos de un árbol de búsqueda binario ....196
Balanceo de árboles de búsqueda binarios ....198

Árboles balanceados por su altura (AVL) ....199

Árboles balanceados por un límite (BB) ....201

Resumen ....202
Terminología ....203
Referencias sugeridas ....203
Ejercicios de repaso ....206

CAPITULO 9 BUSQUEDA Y ORDENAMIENTO ....211

Búsqueda secuencial ....211

Cómo mejorar la eficiencia de la búsqueda secuencial ....214

Muestreo de accesos, 214 Movimiento hacia el frente, 214 Transposición ....216
Ordenamiento ....217

Búsqueda binaria ....218

Introducción al ordenamiento ....221

Ordenamiento por selección ....222
Ordenamiento por selección con intercambio ....224

Ordenamiento por inserción ....226

Ordenamiento por intercambio: el método de la burbuja ....227

Ordenamiento por partición e intercambio (ordenamiento rápido o quicksort) ....230
Rendimiento ....233

Ordenamiento por apilamiento (heapsort) ....233
Estructura de apilamiento, 234 Creación de un apilamiento, 235 Procesamiento
del apilamiento ....237

Ordenamiento por torneo ....240
Desempeño ....246

Resumen ....247
Terminología ....248
Referencias sugeridas ....249
Ejercicios de repaso ....250

CAPITULO 10 SISTEMAS DE ARCHIVOS ....252

Archivos ....252

Clasificación de archivos por función, 253 Maneras de accesar archivos ....255

Organizaciones de archivos ....257

Operaciones sobre archivos ....257
Creación de un archivo, 258 Actualización de un archivo, 258 Recuperación de
información de un archivo, 259 Mantenimiento de un archivo ....260

Sistemas de archivo ....261

Directorios de archivo ....262

Dispositivos de control ....263
Canales, 263 Tipos de canales, 264 Tipos de dispositivos, 265 Actividades del
canal, 265 Procesamiento de una lectura, 266 Bloqueo de registros ....267

Manejo del buffer o almacenamiento temporal ....267
Almacenamiento temporal único por demanda, 267 Almacenamiento temporal por
anticipación, 268 Almacenamiento temporal con bloques, 269 Doble almacenamiento
temporal, 270 Triple almacenamiento temporal ....272

Apertura y cierre de archivos ....273

Sistemas de bases de datos ....274

Resumen ....276
Terminología ....277
Referencias sugeridas ....278
Ejercicios de repaso ....278

CAPITULO 11 ORGANIZACION DE ARCHIVOS SECUENCIALES ....281

Definiciones ....281
Ejemplo, 282 Ordenación de registros, 283 Procesamiento, 283 Ventajas y
desventajas ....284

Almacenamiento de archivos secuenciales ....284

Cinta magnética ....286
Representación de datos y densidad, 287 Control de error y paridad ....287
Bloqueo, 288 Marcas y etiquetas de cinta, 291 Empleo de cintas ....292

Declaración de archivos secuenciales ....292
COBOL, 292 Pascal ....295

Creación de un archivo secuencial ....296
Edición de transacciones, 297 Entrada inteligente de datos, 298 Escritura de
registros, 299 Archivos de reporte ....299

Recuperación de información de archivos secuenciales ....301

Actualización de archivos secuenciales ....303

¿Con que' frecuencia es necesaria la actualización?, 304 Generación de
archivos, 305 Tipos de actualización, 305 Manipulación de errores, 306 Lógica
de actualización ....306

Desempeño de archivos secuenciales ....308
Factor de bloqueo, 308 Longitud del archivo, 309 Selección de la llave ....311

Resumen ....311
Terminología ....312
Referencias sugeridas ....312
Ejercicios de repaso ....313

CAPITULO 12 ORDENAMIENTO Y MEZCLA DE ARCHIVOS ....31

Introducción al ordenamiento e intercalación de archivos ....317

Lógica de intercalación, 318 Fases, 318 Desempeño del
ordenamiento/intercalación, 319 Ordenamiento, 320 Intercalación ....320
Intercalaciones naturales ....320
Ejemplo, 321 Desempeño ....322

Intercalaciones balanceadas ....322
Ejemplo, 326 Desempeño ....326

Intercalaciones de polifase ....326
Ejemplo ....328

Intercalación de cascada ....329
Ejemplo ....330

Ordenamiento/intercalación con utilerías ....330
Especificación del proceso, 330 Ejemplo, 331 Otro ejemplo, 332 Procesamiento
sobre pedido ....332

Ordenamiento/intercalación en programas en COBOL ....333
Primer ejemplo, 334 Segundo ejemplo, 335 Intercalación de archivos
ordenados ....336

Desempeño del ordenamiento/intercalación ....336

Resumen ....337
Terminología ....338
Referencias sugeridas ....338
Ejercicios de repaso ....339

CAPITULO 13 ORGANIZACIÓN DE ARCHIVOS RELATIVOS

Definiciones ....340
Procesamiento, 341 Ejemplo, 342 Ventajas y desventajas ....343

Almacenamiento en disco magnético ....343
Características físicas de los discos magnéticos, 343 Representación
y direccionamiento de datos, 344 Acceso a disco de cabeza movible, 346 Acceso
a discos de cabeza fija, 348 Manejadores de una cabeza-por-pista y discos
Winchester, 348 Almacenamiento en disco flexible ....349

Técnicas de direccionamiento ....350

Técnicas de mapeo directo ....350
Direccionamiento absoluto, 350 Direccionamiento relativo ....351

Técnicas de búsqueda en el directorio ....352
Estructura del directorio, 353 Almacenamiento de registros, 354 Ventajas ....354
Desempeño, ....355

Técnicas de cálculo de direcciones ....355
Hashing por residuo de la división, 358 Hashing por cuadrado medio ....360
Hashing por pliegue 360 Comparación entre las funciones hash ....361

Métodos para el problema de las colisiones ....362
Sondeo lineal, 363 Doble hashing, 364 Comparación entre el sondeo lineal y
el doble hashing, 365 Encadenamiento de sinónimos, 367 Direccionamiento por
cubetas ....368

Uso de archivos relativos ....372
Declaración de un archivo relativo, 372 Creación de un archivo relativo, ....373
Recuperación de datos de archivos relativos, 373 Actualización de archivos
relativos 373 Responsabilidades del programador ....373

Archivos relativos en COBOL ....374
Declaración de un archivo relativo, 374 Creación de un archivo, ....375
Recuperación de registros, 377 Actualización de un archivo ....379

Desempeño de los archivos relativos ....380

Resumen ....382
Terminología ....382
Referencias sugeridas ....383
Ejercicios de repaso ....386

CAPITULO 14 ESTRUCTURAS INDEXADAS ....388

Árboles de búsqueda binarios como índices ....388

Árboles de búsqueda de M-vías ....390
Ejemplo, 391 Árboles de búsqueda de M-vías como índices, 391 Búsqueda en
árboles de búsqueda de M-vias, 392 Desempeño ....393

Árboles-B ....394
Ejemplo, 394 Búsqueda en árboles-B, ....396

Inserción en un árbol-B ....397
Ejemplo, 397 Desempeño ....400

Supresión de un árbol-B ....402
Ejemplo, ....402

Árboles-B* ....404
Inserción en un árbol-B* ....405

Tries ....409
Ejemplo, 410 Búsqueda en un trie, 412 Mantenimiento de un trie, 412 Variantes
de un trie ....414

Resumen ....415
Terminología ....416
Referencias sugeridas ....416
Ejercicios de repaso ....418

CAPITULO 15 ORGANIZACION DE ARCHIVOS SECUENCIALES INDEXADOS ....42

Definiciones ....420
Ejemplos ....421

Aplicaciones ....421
Estructuras de árbol-B+ ....422

Manipulación de un árbol-B+, 424 Búsqueda de árboles-B+ ....424

Ejemplo ....425
Acceso directo, 425 Acceso secuencial, 427 Inserción de registros ....427

Esquema físico de índices ....429
Acceso a registros de datos, 430 Inserción de registros, 430 Precisiones ....433
Supresión de registros ....433

Archivos secuenciales indexados en COBOL ....434
Declaración de archivos, 434 Creación de un archivo, 435 Creación de un
archivo usando una utilería, 436 Recuperación de registros, 437 Actualización
de archivos ....438

Diseño de archivos secuenciales indexados ....439

Resumen ....441
Terminología ....441
Referencias sugeridas ....441
Ejercicios de repaso ....442

CAPITULO 16 ORGANIZACIÓN DE ARCHIVOS MULTILLAVE ....446

Acceso multillave ....446
Ejemplo: la necesidad de trayectoria para múltiple acceso, 447 Manejo por
duplicación de datos, 448 Problemas causados por la duplicación, 448 Manejo por
agregación de índices ....449

Organización de archivos invertidos ....449
Conceptos básicos, 449 Ejemplo, 449 Variantes, 450 Más definiciones ....452
Indexación con direccionamiento indirecto, 452 Valores de llaves no-únicas ....453
Consultas acerca de existencia ....454

Organización de archivos multilista ....454
Conceptos básicos, 455 Ejemplo, 455 Procesamiento, 456 Variantes ....458

Archivos secuenciales indexados con llave altema ....459
Ejemplo, 459 Declaración de un archivo en COBOI 459 Creación de un archivo ....460
Recuperación de registros secuencialmente, 460 Recuperación de registros
directamente, 462 Actualización de registros ....463

Comparaciones y efectos ....463

Resumen de diseño de archivos ....464
Palabras finales ....466
Terminología ....466
Referencias sugeridas ....466
Ejercicios de repaso ....467

GLOSARIO ....469
RESPUESTAS A LOS EJERCICIOS DE REPASO ....490
APENDICE. META-LENGUA JE PARA COBOL ....507
INDICE ....509

© Biblioteca de la UOC