Estructura de Datos

Descripción

Libro digital para leer en línea o en app móvil

Descripción:
Este libro tiene como objetivo presentar las estructuras de datos, así como los algoritmos necesarios para tratarlas. El lenguaje utilizado es algorítmico, escrito en seudo código, independiente de cualquier lenguaje comercial de programación. Esta característica es muy importante, ya que permite al lector comprender las estructuras de datos y los algoritmos asociados a ellas sin relacionarlos con lenguajes de programación particulares. Se considera que una vez que el lector domine estos conceptos, los podrá implementar fácilmente en cualquier lenguaje.

Tabla de contenidos:

Front Matter
   PRESENTACIÓN
   OBJETIVO
   LENGUAJE UTILIZADO
   ORGANIZACIÓN
   Capítulo 1: Estructuras fundamentales
   Capítulo 2: Arreglos multidimensionales representados en arreglos unidimensionales
   Capítulo 3: Pilas y colas
   Capítulo 4: Recursión
   Capítulo 5: Listas
   Capítulo 6: Árboles
   Capítulo 7: Gráficas
   Capítulo 8: Métodos de ordenación
   Capítulo 9: Métodos de búsqueda
   AGRADECIMIENTOS
Capítulo 1: ESTRUCTURAS FUNDAMENTALES DE DATOS
   1.1: INTRODUCCIÓN
   FIGURA 1.1
   1.2: ARREGLOS
   Ejemplo 1.1
   Algoritmo 1.1: Doble_lectura
   Doble_lectura
   Algoritmo 1.2: Muchas_variables
   Muchas_variables
   FIGURA 1.2
   FIGURA 1.3
   1.2.1: Declaración de arreglos unidimensionales
   Ejemplo 1.2
   FIGURA 1.4
   Ejemplo 1.3
   FIGURA 1.5
   Ejemplo 1.4
   FIGURA 1.6
   1.2.2: Operaciones con arreglos unidimensionales
   Lectura
   FIGURA 1.7
   FIGURA 1.8
   Escritura
   Asignación
   FIGURA 1.9
   Actualización
   Algoritmo 1.3: Busca_secuencial_desordenado
   Busca_secuencial_desordenado
   a): Arreglos desordenados
   FIGURA 1.10
   Algoritmo 1.4: Inserta_desordenado
   Inserta_desordenado (V, N, Y)
   FIGURA 1.10a
   Algoritmo 1.5: Elimina_desordenado
   Elimina_desordenado (V, N, X)
   FIGURA 1.10b
   Algoritmo 1.6: Modifica_desordenado
   Modifica_desordenado (V, N, X, Y)
   FIGURA 1.10c
   b): Arreglos ordenados
   FIGURA 1.11
   Algoritmo 1.7: Busca_secuencial_ordenado
   Busca_secuencial_ordenado (V, N, X, POS)
   Algoritmo 1.8: Inserta_ordenado
   Inserta_ordenado (V, N, Y)
   FIGURA 1.11a
   Algoritmo 1.9: Elimina_ordenado
   Elimina_ordenado (V, N, X)
   FIGURA 1.11b
   Algoritmo 1.10: Con_arreglos
   Con_arreglos (CAL)
   1.3: ARREGLOS BIDIMENSIONALES
   Ejemplo 1.5
   TABLA 1.1: Costos mensuales por departamentos
   FIGURA 1.12
   FIGURA 1.13
   FIGURA 1.14
   1.3.1: Declaración de arreglos bidimensionales
   Ejemplo 1.6
   FIGURA 1.15
   Ejemplo 1.7
   FIGURA 1.16
   Ejemplo 1.8
   FIGURA 1.17
   Ejemplo 1.9
   FIGURA 1.18
   1.3.2. Operaciones con arreglos bidimensionales
   Lectura
   Escritura
   Asignación
   FIGURA 1.19
   FIGURA 1.20
   1.4: ARREGLOS DE MÁS DE DOS DIMENSIONES
   FIGURA 1.21
   FIGURA 1.22
   Ejemplo 1.10
   FIGURA 1.23
   1.5: LA CLASE ARREGLO
   FIGURA 1.24
   1.6: REGISTROS
   Ejemplo 1.11
   1.6.1: Declaración de registros
   Ejemplo 1.12
   FIGURA 1.25
   Ejemplo 1.13
   FIGURA 1.26
   Ejemplo 1.14
   FIGURA 1.27
   1.6.2: Acceso a los campos de un registro
   1.6.3: Diferencias entre registros y arreglos
   1.6.4: Combinaciones entre arreglos y registros
   Arreglos de registros
   Ejemplo 1.15
   FIGURA 1.28
   Registros anidados
   Ejemplo 1.16
   FIGURA 1.29
   Registros con arreglos
   Ejemplo 1.17
   FIGURA 1.30
   1.6.5: Arreglos paralelos
   Uso de arreglos paralelos
   FIGURA 1.31
   Algoritmo 1.11: Arreglos_paralelos
   Arreglos_paralelos
   Uso de arreglos de registros
   FIGURA 1.32
   Algoritmo 1.12: Arreglo_de_registros
   Arreglo_de_registros
   1.7: REGISTROS Y CLASES
   FIGURA 1.33
   EJERCICIOS
   Arreglos de una dimensión y arreglos paralelos
   Arreglos multidimensionales
   Combinaciones entre arreglos y registros
   Problemas interesantes
Capítulo 2: ARREGLOS MULTIDIMENSIONALES REPRESENTADOS EN ARREGLOS UNIDIMENSIONALES
   2.1: INTRODUCCIÓN
   2.2: ARREGLOS BIDIMENSIONALES
   FIGURA 2.1
   Ejemplo 2.1
   Ejemplo 2.2
   2.3: ARREGLOS DE MÁS DE DOS DIMENSIONES
   FIGURA 2.2
   Ejemplo 2.3
   Ejemplo 2.4
   2.4: MATRICES POCO DENSAS
   FIGURA 2.3
   Arreglo de registros
   TABLA 2.1
   Algoritmo 2.1: Almacena_matriz_poco_densa
   Almacena_matriz_poco_densa (MAT)
   Arreglo de listas
   FIGURA 2.4
   2.4.1: Matrices cuadradas poco densas
   FIGURA 2.5
   2.4.2: Matriz triangular inferior
   FIGURA 2.6
   2.4.3: Matriz triangular superior
   FIGURA 2.7
   Ejemplo 2.5
   Ejemplo 2.6
   2.4.4: Matriz tridiagonal
   FIGURA 2.8
   FIGURA 2.9
   Ejemplo 2.7
   2.4.5: Matrices simétricas y antisimétricas
   FIGURA 2.10
   FIGURA 2.11
   FIGURA 2.12
   FIGURA 2.13
   EJERCICIOS
   Arreglos multidimensionales
   Matrices poco densas
   Matrices simétricas y antisimétricas
Capítulo 3: PILAS Y COLAS
   3.1: INTRODUCCIÓN
   3.2: PILAS
   FIGURA 3.1
   3.2.1: Representación de pilas
   FIGURA 3.2
   FIGURA 3.3
   FIGURA 3.4
   FIGURA 3.5
   3.2.2: Operaciones con pilas
   Algoritmo 3.1: Pila_vacía
   Pila_vacía (PILA, TOPE, BAND)
   Algoritmo 3.2: Pila_llena
   Pila_llena (PILA, TOPE, MAX, BAND)
   Algoritmo 3.3: Pone
   Pone (PILA, TOPE, MAX, DATO)
   Algoritmo 3.4: Quita
   Quita (PILA, TOPE, DATO)
   Ejemplo 3.1
   FIGURA 3.6
   FIGURA 3.7
   3.2.3: Aplicaciones de pilas
   Llamadas a subprogramas
   FIGURA 3.8
   FIGURA 3.9
   Recursividad
   Tratamiento de expresiones aritméticas
   Ejemplo 3.2
   TABLA 3.1: Traducción de infija a posfija
   TABLA 3.2: Traducción de expresión infija a posfija.
   Algoritmo 3.5: Conv_postfija
   Conv_postfija (El, EPOS)
   Ejemplo 3.3
   TABLA 3.3: Traducción de expresión infija a posfija
   TABLA 3.4: Traducción de expresión infija a postfija
   Ejemplo 3.4
   TABLA 3.5: Traducción de expresión infija a prefija
   TABLA 3.6: Traducción de expresión infija a prefija
   Algoritmo 3.6: Conv_prefija
   Conv_prefija (El, EPRE)
   Ejemplo 3.5
   TABLA 3.7: Traducción de expresión infija a prefija
   TABLA 3.8: Traducción de expresión infija a prefija
   Ordenación
   3.2.4: La clase Pila
   FIGURA 3.10
   3.3: COLAS
   FIGURA 3.11
   3.3.1: Representación de colas
   FIGURA 3.12
   FIGURA 3.13
   3.3.2: Operaciones con colas
   Algoritmo 3.7: Inserta_cola
   Inserta_cola (COLA, MAX, FRENTE, FINAL, DATO)
   Algoritmo 3.8: Elimina_cola
   Elimina_cola (COLA, FRENTE, FINAL, DATO)
   Algoritmo 3.9: Cola_vacía
   Cola_vacía (COLA, FRENTE, BAND)
   Algoritmo 3.10: Cola_llena
   Cola_llena (COLA, FINAL, MAX, BAND)
   Ejemplo 3.6
   FIGURA 3.14
   FIGURA 3.15
   FIGURA 3.16
   3.3.3: Colas circulares
   FIGURA 3.17
   Algoritmo 3.11: Inserta_circular
   Inserta_circular (COLACIR, MAX, FRENTE, FINAL, DATO)
   Algoritmo 3.12: Elimina_circular
   Elimina_circular (COLACIR, MAX, FRENTE, FINAL, DATO)
   Ejemplo 3.7
   FIGURA 3.18
   FIGURA 3.19
   FIGURA 3.20
   FIGURA 3.21
   3.3.4: Doble cola
   FIGURA 3.22
   FIGURA 3.23
   FIGURA 3.24
   3.3.5: Aplicaciones de colas
   3.3.6: La clase Cola
   FIGURA 3.25
   EJERCICIOS
   Pilas
   Colas
Capítulo 4: RECURSIÓN
   4.1: INTRODUCCIÓN
   FIGURA 4.1
   FIGURA 4.2
   Ejemplo 4.1: Factorial de un número
   Algoritmo 4.1: Factorial_rec
   Factorial_rec (N)
   FIGURA 4.3
   Algoritmo 4.2: Factorial_ite
   Factorial_ite (N)
   TABLA 4.1: Cálculo del factorial en forma iterative
   Ejemplo 4.2
   Algoritmo 4.3: Fibonacci_rec
   Fibonacci_rec (N)
   FIGURA 4.4
   Algoritmo 4.4: Fibonacci_ite
   Fibonacci_ite (N)
   TABLA 4.2: Cálculo de los números Fibonacci en forma iterativa
   Ejemplo 4.3: Impresión de un arreglo
   Algoritmo 4.5: Arreglo_imp
   Arreglo_imp (A, N)
   FIGURA 4.5
   Ejemplo 4.4: Impresión de un arreglo
   Algoritmo 4.6: Arreglo_imp
   Arreglo_imp (A, N)
   Ejemplo 4.5: Suma de un arreglo
   Algoritmo 4.7: Arreglo_sum
   Arreglo_sum (A, N)
   FIGURA 4.6
   Ejemplo 4.6: Euclides
   Algoritmo 4.8: Euclides
   Euclides (M, N)
   FIGURA 4.7
   Ejemplo 4.7: Ackermann
   TABLA 4.3: Ackermann y valores de M y N
   Algoritmo 4.9: Ackermann
   Ackermann (M, N)
   FIGURA 4.8
   Ejemplo 4.8: Algoritmo de partición
   Algoritmo 4.10: Partición
   Partición (M, N)
   FIGURA 4.9
   Ejemplo 4.9: Los números de Catalan
   Algoritmo 4.11: Catalan
   Catalan (N)
   FIGURA 4.10
   Ejemplo 4.10: Coeficientes binomiales
   FIGURA 4.11
   Algoritmo 4.12: CB
   CB (N, K)
   FIGURA 4.12
   4.2: EL PROBLEMA DE LAS TORRES DE HANOI
   FIGURA 4.13
   FIGURA 4.14
   FIGURA 4.15
   Algoritmo 4.13: Hanoi
   Hanoi (N, ORIGEN, DESTINO, AUXILIAR)
   FIGURA 4.16
   Algoritmo 4.14: Hanoi_ite
   Hanoi_ite (N, ORIGEN, DESTINO, AUXILIAR)
   FIGURA 4.17.
   4.3: RECURSIVIDAD EN ÁRBOLES
   4.4: RECURSIVIDAD EN ORDENACIÓN Y BÚSQUEDA
   EJERCICIOS
   P1 (X)
Capítulo 5: LISTAS
   5.1: INTRODUCCIÓN
   5.2: LISTAS SIMPLEMENTE LIGADAS
   FIGURA 5.1
   FIGURA 5.2
   5.2.1: Operaciones con listas simplemente ligadas
   Algoritmo 5.1: Crea_inicio
   Crea_inicio
   Ejemplo 5.1
   FIGURA 5.3
   Algoritmo 5.2: Crea_final
   Crea_final
   Ejemplo 5.2
   FIGURA 5.4
   5.2.2: Recorrido de una lista simplemente ligada
   Algoritmo 5.3: Recorre_iterativo
   Recorre_iterativo (P)
   Algoritmo 5.4: Recorre_recursivo
   Recorre_recursivo (P)
   5.2.3: Inserción en listas simplemente ligadas
   a): Inserción al inicio de una lista simplemente ligada
   Algoritmo 5.5: Inserta_inicio
   Inserta_inicio (P, DATO)
   Ejemplo 5.3
   FIGURA 5.5
   b): Inserción al final de una lista simplemente ligada
   Algoritmo 5.6: Inserta_final
   Inserta_final (P, DATO)
   Ejemplo 5.4
   FIGURA 5.6
   FIGURA 5.7
   c): Inserción de un nodo antes que otro en una lista simplemente ligada
   Algoritmo 5.7: Inserta_antes_X
   Inserta_antes_X (P, DATO, X)
   Ejemplo 5.5
   FIGURA 5.8
   d): Inserción de un nodo después de otro en una lista simplemente ligada
   Algoritmo 5.8: Inserta_después_X
   Inserta_después_X (P, DATO, X)
   Ejemplo 5.6
   FIGURA 5.9
   5.2.4: Eliminación en listas simplemente ligadas
   a): Eliminar el primer nodo de una lista simplemente ligada
   Algoritmo 5.9: Elimina_inicio
   Elimina_inicio (P)
   Ejemplo 5.7
   FIGURA 5.10
   b): Eliminar el último nodo de una lista simplemente ligada
   Algoritmo 5.10: Elimina_último
   Elimina_último (P)
   Ejemplo 5.8
   FIGURA 5.11
   c): Eliminar un nodo con información X de una lista simplemente ligada
   Algoritmo 5.11: Elimina_X
   Elimina_X (P, X)
   Ejemplo 5.9
   FIGURA 5.12
   d): Eliminar el nodo anterior al nodo con información X en una lista simplemente ligada
   Algoritmo 5.12: Elimina_antes_X
   Elimina_antes_X (P, X)
   Ejemplo 5.10
   FIGURA 5.13
   5.2.5: Búsqueda en listas simplemente ligadas
   Algoritmo 5.13: Búsqueda_desordenada
   Búsqueda_desordenada (P, X)
   Algoritmo 5.14: Búsqueda_ordenada
   Búsqueda_ordenada (P, X)
   Algoritmo 5.15: Búsqueda_recursivo
   Búsqueda_recursivo (P, X)
   5.3: LISTAS CIRCULARES
   FIGURA 5.14
   FIGURA 5.15
   5.4: LISTAS DOBLEMENTE LIGADAS
   5.4.1: Operaciones con listas doblemente ligadas
   FIGURA 5.16
   5.4.2: Recorrido de una lista doblemente ligada
   5.4.3: Inserción en listas doblemente ligadas
   a): Inserción al inicio de la lista doblemente ligada
   Algoritmo 5.16: Inserta_principio
   Inserta_principio (P, DATO)
   Ejemplo 5.11
   FIGURA 5.17
   b): Inserción al final de una lista doblemente ligada
   Algoritmo 5.17: Inserta_final
   Inserta_final (F, DATO)
   Ejemplo 5.12
   FIGURA 5.18
   c): Inserción de un nodo antes que otro en una lista doblemente ligada
   Algoritmo 5.18: Inserta_antes_X
   Inserta_antes_X (P, DATO, X)
   Ejemplo 5.13
   FIGURA 5.19
   5.4.4: Eliminación en listas doblemente ligadas
   a): Eliminar el primer nodo de una lista doblemente ligada
   Algoritmo 5.19: Elimina_inicio
   Elimina_inicio (P, F)
   Ejemplo 5.14
   FIGURA 5.20
   b): Eliminar el último nodo de una lista doblemente ligada
   Algoritmo 5.20: Elirnina_último
   Elimina_último (P, F)
   Ejemplo 5.15
   FIGURA 5.21
   c): Eliminar un nodo con información X
   Algoritmo 5.21: Elimina_X
   Elimina_X (P, F, X)
   Ejemplo 5.16
   FIGURA 5.22
   d): Eliminar el nodo anterior al nodo con información X
   Algoritmo 5.22: Elimina_antes_X
   Elimina_antes_X (P, X)
   Ejemplo 5.17
   FIGURA 5.23
   5.5: LlSTAS DOBLEMENTE LIGADAS CIRCULARES
   FIGURA 5.24
   FIGURA 5.25
   FIGURA 5.26
   5.6: APLICACIONES DE LISTAS
   5.6.1: Representación de polinomios
   FIGURA 5.27
   5.6.2: Solución de colisiones (hash)
   5.7: LA CLASE LISTA
   FIGURA 5.28
   FIGURA 5.29
   EJERCICIOS
Capítulo 6: ÁRBOLES
   6.1: INTRODUCCIÓN
   TABLA 6.1: Estructuras de datos estáticas y dinámicas
   TABLA 6.2: Estructuras de datos lineales y no lineales
   6.2: ÁRBOLES EN GENERAL
   FIGURA 6.1
   6.2.1: Características y propiedades de los árboles
   Ejemplo 6.1
   FIGURA 6.2
   6.2.2: Longitud de camino interno y externo
   Longitud de camino interno
   Longitud de camino externo
   FIGURA 6.3
   Ejemplo 6.2
   FIGURA 6.4
   FIGURA 6.5
   6.3: Árboles binarios
   FIGURA 6.6
   6.3.1: Árboles binarios distintos, similares y equivalentes
   FIGURA 6.7
   FIGURA 6.8
   FIGURA 6.9
   Ejemplo 6.3
   FIGURA 6.10
   6.3.2: Árboles binarios completos
   FIGURA 6.11
   6.3.3: Representación de árboles generales como binarios
   FIGURA 6.12
   Ejemplo 6.4
   FIGURA 6.13
   FIGURA 6.14
   FIGURA 6.15
   6.3.4: Representación de un bosque como árbol binario
   FIGURA 6.16
   FIGURA 6.17
   Ejemplo 6.5
   FIGURA 6.18
   6.3.5: Representación de árboles binarios en memoria
   Ejemplo 6.6
   FIGURA 6.19
   6.3.6: Operaciones en árboles binarios
   Algoritmo 6.1: Crea_árbol
   Crea_árbol (APNODO)
   FIGURA 6.20
   Algoritmo 6.2: Preorden
   Preorden (APNODO)
   Ejemplo 6.7
   TABLA 6.3: Recorrido preorden
   Algoritmo 6.3: Inorden
   Inorden (APNODO)
   Ejemplo 6.8
   TABLA 6.4: Recorrido inorden
   TABLA 6.5: Recorrido posorden
   Algoritmo 6.4: Posorden
   Posorden (APNODO)
   Ejemplo 6.9
   6.3.7: Árboles binarios de búsqueda
   Ejemplo 6.10
   FIGURA 6.21
   Búsqueda
   Algoritmo 6.5: Búsqueda_ABB
   Búsqueda_ABB (APNODO, INFOR)
   Ejemplo 6.11
   TABLA 6.6: Localización de la clave 93 (INFOR ← 93)
   TABLA 6.7: Localización de la clave 123 (INFOR ← 123)
   Algoritmo 6.6: Búsqueda_v1_ABB
   Búsqueda_v1_ABB (APNODO, INFOR)
   Inserción en un árbol binario de búsqueda
   Ejemplo 6.12
   FIGURA 6.22
   Algoritmo 6.7: Inserción_ABB
   Inserción_ABB (APNODO, INFOR)
   Ejemplo 6.13
   TABLA 6.8: Inserción de la clave 93 (INFOR ← 93)
   TABLA 6.9: Inserción de la clave 135 (INFOR ← 135)
   FIGURA 6.23
   Algoritmo 6.8: Inserción_v1_ABB
   Inserción_v1_ABB (APNODO, INFOR)
   Eliminación en un árbol binario de búsqueda
   Ejemplo 6.14
   FIGURA 6.24
   Algoritmo 6.9: Eliminación_ABB
   Eliminación_ABB (APNODO, INFOR)
   Ejemplo 6.15
   FIGURA 6.25
   6.4: ÁRBOLES BALANCEADOS
   FIGURA 6.26
   FIGURA 6.27
   Ejemplo 6.16
   6.4.1: Inserción en árboles balanceados
   FIGURA 6.28
   FIGURA 6.29
   6.4.2: Reestructuración del árbol balanceado
   Ejemplo 6.17
   FIGURA 6.30
   Ejemplo 6.18
   TABLA 6.10: Factores de equilibrio en la rotación DI
   TABLA 6.11: Factores de equilibrio en la rotación ID
   Ejemplo 6.19
   FIGURA 6.31
   Algoritmo 6.10: Inserta_balanceado
   Inserta_balanceado (NODO, BO, INFOR)
   Eliminación en árboles balanceados
   Ejemplo 6.20
   FIGURA 6.32
   a) ELIMINACIÓN: CLAVE 82
   b) ELIMINACIÓN: CLAVE 10
   c) ELIMINACIÓN: CLAVE 39
   d) ELIMINACIÓN: CLAVE 65
   e) ELIMINACIÓN: CLAVES 70, 23 Y 50
   f) ELIMINACIÓN: CLAVE 43
   Ejemplo 6.21
   FIGURA 6.33
   Algoritmo 6.11: Reestructura_izq
   Reestructura_izq (NODO, BO)
   Algoritmo 6.12: Reestructura_der
   Reestructura_der
   Algoritmo 6.13: Elimina_balanceado
   Elimina_balanceado (NODO, BO, INFOR)
   Ejemplo 6.22
   FIGURA 6.34
   6.5: ÁRBOLES MULTICAMINOS
   6.5.1: Árboles-B
   FIGURA 6.35
   FIGURA 6.36
   Ejemplo 6.23
   FIGURA 6.37
   Búsqueda en árboles-B
   Inserción en árboles-B
   FIGURA 6.38
   FIGURA 6.39
   FIGURA 6.40
   Ejemplo 6.24
   FIGURA 6.41
   Ejemplo 6.25
   FIGURA 6.42
   Eliminación en árboles-B
   FIGURA 6.43
   FIGURA 6.44
   FIGURA 6.45
   FIGURA 6.46
   FIGURA 6.47
   Ejemplo 6.26
   FIGURA 6.48
   FIGURA 6.49
   Ejemplo 6.27
   FIGURA 6.50
   Ejemplo 6.28
   FIGURA 6.51
   6.5.2: Árboles-B+
   FIGURA 6.52
   Búsqueda en árboles-B+
   Inserción en árboles-B+
   FIGURA 6.53
   FIGURA 6.54
   Ejemplo 6.29
   FIGURA 6.55
   Ejemplo 6.30
   FIGURA 6.56
   Eliminación en árboles-B+
   FIGURA 6.57
   FIGURA 6.58
   FIGURA 6.59
   Ejemplo 6.31
   FIGURA 6.60
   FIGURA 6.61
   Ejemplo 6.32
   FIGURA 6.62
   6.5.3: Árboles 2-4
   6.6: LA CLASE ÁRBOL
   FIGURA 6.63
   EJERCICIOS
   Árboles en general
   Árboles binarios
   Representación de árboles generales como árboles binarios
   Árboles binarios de búsqueda
   Ejercicios de programación en árboles binarios
   Árboles balanceados
   Árboles-B y árboles-B+
   Ejercicios de programación de árboles-B y árboles-B+
Capítulo 7: GRÁFICAS
   7.1: INTRODUCCIÓN
   FIGURA 7.1
   FIGURA 7.2
   7.2: DEFINICIÓN DE GRÁFICAS
   7.3: CONCEPTOS BÁSICOS DE GRÁFICAS
   FIGURA 7.3
   FIGURA 7.4
   7.4: GRÁFICAS DIRIGIDAS
   FIGURA 7.5
   7.4.1: Representación de gráficas dirigidas
   Matriz de adyacencia
   FIGURA 7.6
   FIGURA 7.7
   Lista de adyacencia
   FIGURA 7.8
   7.4.2: Obtención de caminos dentro de una digráfica
   7.4.3: Algoritmo de Dijkstra
   Algoritmo 7.1: Dijkstra
   Dijkstra (N)
   Ejemplo 7.1
   TABLA 7.1: Aplicación del algoritmo de Dijkstra
   FIGURA 7.9
   Ejemplo 7.2
   FIGURA 7.10
   TABLA 7.2: Aplicación del algoritmo de Dijkstra
   7.4.4: Algoritmo de Floyd
   Algoritmo 7.2: Floyd
   Floyd (N)
   Ejemplo 7.3
   FIGURA 7.11
   Algoritmo 7.3: Floyd_guarda_vértices
   Floyd_guarda_vértices (N)
   Ejemplo 7.4
   FIGURA 7.12
   7.4.5: Algoritmo de Warshall
   Algoritmo 7.4: Warshall
   Warshall (N)
   Ejemplo 7.5
   FIGURA 7.13
   7.5: GRÁFICAS NO DIRIGIDAS
   7.5.1: Representación de gráficas no dirigidas
   FIGURA 7.14
   FIGURA 7.15
   7.5.2: Construcción del árbol abarcador de costo mínimo
   7.5.3: Algoritmo de Prim
   Algoritmo 7.5: Prim
   Prim (N)
   Ejemplo 7.6
   FIGURA 7.16
   FIGURA 7.17
   TABLA 7.3: Aplicación del algoritmo de Prim
   7.5.4: Algoritmo de Kruskal
   Algoritmo 7.6: Kruskal
   Kruskal (N)
   Ejemplo 7.7
   FIGURA 7.18
   FIGURA 7.19
   TABLA 7.4: Aplicación del algoritmo de Kruskal
   7.6: RESOLUCIÓN DE PROBLEMAS
   FIGURA 7.20
   TABLA 7.5: Puzzle-8
   TABLA 7.6: Puzzle de 4 × 4
   FIGURA 7.21
   FIGURA 7.22
   7.6.1: Espacio-estado
   7.6.2: Métodos de búsqueda en espacio-estado
   7.6.3: Método de búsqueda breadth-first
   Algoritmo 7.7: Breadth-first
   Breadth_first
   Ejemplo 7.8
   FIGURA 7.23
   FIGURA 7.24
   Ejemplo 7.9
   FIGURA 7.25
   Ejemplo 7.10
   FIGURA 7.26
   Ejemplo 7.11
   TABLA 7.7: Operadores para el problema de la jarra
   FIGURA 7.27
   Complejidad del método breadth-first
   TABLA 7.8: Complejidad breadth-first O(bd)
   7.6.4: Método de búsqueda depth-first
   Algoritmo 7.8: Depth-first
   Depth-First
   Ejemplo 7.12
   FIGURA 7.28
   7.7: LA CLASE GRÁFICA
   EJERCICIOS
   FIGURA 7.29
   FIGURA 7.30
   FIGURA 7.31
   FIGURA 7.32
   FIGURA 7.33
   FIGURA 7.34
   FIGURA 7.35
Capítulo 8: MÉTODOSDE ORDENACIÓN
   8.1: INTRODUCCIÓN
   FIGURA 8.1
   FIGURA 8.2
   8.2: ORDENACIÓN INTERNA
   8.2.1: Ordenación por intercambio directo (burbuja)
   Ejemplo 8.1
   TABLA 8.1
   Algoritmo 8.1: Burbuja_menor
   Burbuja_menor (A, N)
   Ejemplo 8.2
   TABLA 8.2
   Algoritmo 8.2: Burbuja_mayor
   Burbuja_mayor (A, N)
   Análisis de eficiencia del métoclo de intercambio directo
   8.2.2: Ordenación por el método de intercambio directo con señal
   Algoritmo 8.3: Burbuja_señal
   Burbuja_señal (A, N)
   8.2.3: Ordenación por el método de la sacudida (shaker sort)
   Ejemplo 8.3
   Algoritmo 8.4: Sacudida
   Sacudida (A, N)
   Análisis de eficiencia del método de la sacudida
   8.2.4: Ordenación por inserción directa
   Ejemplo 8.4
   TABLA 8.3
   Algoritmo 8.5: Inserción
   Inserción (A, N)
   Análisis de eficiencia del método de inserción directa
   Ejemplo 8.5
   Ejemplo 8.6
   8.2.5: Ordenación por el método de inserción binaria
   Ejemplo 8.7
   Algoritmo 8.6: Inserción_binaria
   Inserción_binaria (A, N)
   Análisis de eficiencia del método de inserción binaria
   8.2.6: Ordenación por selección directa
   Ejemplo 8.8
   TABLA 8.4
   Algoritmo 8.7: Selección
   Selección (A, N)
   Análisis de eficiencia del método de selección directa
   8.2.7: Análisis de eficiencia de los métodos directos
   TABLA 8.5
   TABLA 8.6
   8.2.8: Ordenación por el método de Shell
   Ejemplo 8.9
   Algoritmo 8.8: Shell
   Shell (A, N)
   Análisis de eficiencia del método de Shell
   TABLA 8.7
   TABLA 8.8
   Ejemplo 8.10
   TABLA 8.9
   8.2.9: Ordenación por el método quicksort
   Ejemplo 8.11
   TABLA 8.10
   Algoritmo 8.9: Rápido_recursivo
   Rápido_recursivo (A, N)
   Algoritmo 8.10: Reduce_recursivo
   Reduce_recursivo (INI, FIN)
   FIGURA 8.3
   Algoritmo 8.11: Rápido_iterativo
   Rápido_iterativo (A, N)
   Algoritmo 8.12: Reduce_iterativo
   Reduce_iterativo (INI, FIN, POS)
   Ejemplo 8.12
   TABLA 8.11
   Análisis de eficiencia del método quicksort
   8.2.10: Ordenación por el método heapsort (montículo)
   Ejemplo 8.13
   FIGURA 8.4
   FIGURA 8.5
   Inserción de un elemento en un montículo
   Ejemplo 8.14
   FIGURA 8.6
   FIGURA 8.7
   Ejemplo 8.15
   FIGURA 8.8
   Ejemplo 8.16
   FIGURA 8.9
   Algoritmo 8.13: Inserta_montículo
   Inserta_montículo (A, N)
   Eliminación de un montículo
   Ejemplo 8.17
   FIGURA 8.10
   FIGURA 8.11
   Ejemplo 8.18
   FIGURA 8.12
   TABLA 8.12
   Algoritmo 8.14: Elirnina_montículo
   Elimina_montículo (A, N)
   Algoritmo 8.15: Montículo
   Montículo (A, N)
   Análisis de eficiencia del método del montículo
   8.3: ORDENACIÓN EXTERNA
   8.3.1: Intercalación de archivos
   Ejemplo 8.19
   Algoritmo 8.16: Intercalación
   Intercalación (F1, F2, F3)
   8.3.2: Ordenación de archivos
   8.3.3: Ordenación por mezcla directa
   Ejemplo 8.20
   Algoritmo 8.17: Mezcla_directa
   Mezcla_directa (F, F1, F2, N)
   Algoritmo 8.18: Particiona
   Particiona (F, F1, F2, PART)
   Algoritmo 8.19: Fusiona
   Fusiona (F, F1, F2, PART)
   Ejemplo 8.21
   8.3.4: Ordenación por el método de mezcla equilibrada
   Ejemplo 8.22
   Algoritmo 8.20: Mezcla_equilibrada
   Mezcla_equilibrada (F, F1, F2, F3)
   Algoritmo 8.21: Partición_inicial
   Partición_inicial (F, F2, F3)
   Algoritmo 8.22: Partición_fusión
   Partición_fusión (FA, FB, FC, FD)
   Ejemplo 8.23
   EJERCICIOS
   Ordenación interna
   Ordenación externa
Capítulo 9: MÉTODOS DE BÚSQUEDA
   9.1: INTRODUCCIÓN
   FIGURA 9.1
   FIGURA 9.2
   9.2: BÚSQUEDA INTERNA
   9.2.1: Búsqueda secuencial
   Algoritmo 9.1: Secuencial_desordenado
   Secuencial_desordenado (V, N, X)
   Algoritmo 9.2: Secuencial_desordenado_recursivo
   Secuencial_desordenado_recursivo (V, N, X, I)
   Algoritmo 9.3: Secuencial_ordenado
   Secuencial_ordenado (V, N, X)
   Algoritmo 9.4: Secuencial_ordenado_recursivo
   Secuencial_ordenado_recursivo (V, N, X, I)
   Algoritmo 9.5: Secuencial_lista_desordenada
   Secuencial_lista_desordenada (P, X)
   Algoritmo 9.6: Secuencial_lista_desordenada_recursivo
   Secuencial_lista_desordenada_recursivo (P, X)
   Análisis de la búsqueda secuencial
   TABLA 9.1: Complejidad del método de búsqueda secuencial
   9.2.2: Búsqueda binaria
   Algoritmo 9.7: Binaria
   Binaria (V, N, X)
   Ejemplo 9.1
   FIGURA 9.3
   TABLA 9.2: Búsqueda binaria
   FIGURA 9.4
   TABLA 9.3: Búsqueda binaria
   FIGURA 9.5
   Algoritmo 9.8: Binaria_sin_bandera
   Binaria_sin_bandera (V, N, X)
   Algoritmo 9.9: Binaria_recursivo
   Binaria_recursivo (V, IZQ, DER, X)
   Análisis de la búsqueda binaria
   TABLA 9.4: Complejidad del método de búsqueda binaria
   9.2.3: Búsqueda por transformación de claves
   9.2.4: Función hash por módulo: división
   Ejemplo 9.2
   9.2.5: Función hash cuadrado
   Ejemplo 9.3
   9.2.6: Función hash por plegamiento
   Ejemplo 9.4
   9.2.7: Función hash por truncamiento
   Ejemplo 9.5
   9.2.8: Solución de colisiones
   9.2.9: Reasignación
   Prueba lineal
   Algoritmo 9.10: Prueba_lineal
   Pruebajineal (V, N, K)
   Ejemplo 9.6
   FIGURA 9.6
   TABLA 9.5: Solución de colisiones por la prueba lineal. K = 35
   TABLA 9.6: Solución de colisiones por la prueba lineal. K = 13
   Prueba cuadrática
   Algoritmo 9.11: Prueba_cuadrática
   Prueba_cuadrática (V, N, K)
   Ejemplo 9.7
   FIGURA 9.7
   TABLA 9.7: Solución de colisiones por la prueba cuadrática. K = 35
   TABLA 9.8: Solución de colisiones por la prueba cuadrática. K = 55
   Doble dirección hash
   Algoritmo 9.12: Doble_dirección
   Doble_dirección (V, N, K)
   Ejemplo 9.8
   FIGURA 9.8
   TABLA 9.9: Solución de colisiones por el método de doble dirección hash. K = 13
   9.2.10: Arreglos anidados
   Ejemplo 9.9
   FIGURA 9.9
   9.2.11: Encadenamiento
   FIGURA 9.10
   Algoritmo 9.13: Encadenamiento
   Encadenamiento (V, N, K)
   Ejemplo 9.10
   FIGURA 9.11
   Ejemplo 9.11
   TABLA 9.10
   FIGURA 9.12
   Análisis del método por transformación de claves
   9.2.12: Árboles de búsqueda
   FIGURA 9.13
   FIGURA 9.14
   FIGURA 9.15
   FIGURA 9.16
   9.3: BÚSQUEDA EXTERNA
   9.3.1: Búsqueda en archivos secuenciales
   9.3.2: Búsqueda secuencial
   Algoritmo 9.14: Archivo_secuencial_desordenado
   Archivo_secuencial_desordenado (FA, K)
   Algoritmo 9.15: Archivo_secuencial_ordenado
   Archivo_secuencial_ordenado (FA, K)
   9.3.3: Búsqueda secuencial mediante bloques
   Algoritmo 9.16: Archivo_secuencial_bloques
   Archivo_secuencial_bloques (FA, N, K)
   Ejemplo 9.12
   TABLA 9.11: Búsqueda secuencial con bloque
   9.3.4: Búsqueda secuencial con índices
   FIGURA 9.17
   Determinación del tamaño del bloque
   9.3.5: Búsqueda binaria
   9.3.6: Búsqueda por transformación de claves (hash)
   FIGURA 9.18
   Funciones hash
   Conversiones de bases
   Ejemplo 9.13
   9.3.7: Solución de colisiones
   FIGURA 9.19
   Uso de áreas independientes para colisiones
   FIGURA 9.20
   FIGURA 9.21
   Uso de áreas de colisiones entre los bloques de almacenamiento primario
   FIGURA 9.22
   9.3.8: Hashing dinámico: búsqueda dinámica por transformación de claves
   9.3.9: Método de las expansiones totales
   Ejemplo 9.14
   FIGURA 9.23
   FIGURA 9.24
   FIGURA 9.25
   FIGURA 9.26
   FIGURA 9.27
   Ejemplo 9.15
   FIGURA 9.28
   Ejemplo 9.16
   FIGURA 9.29
   FIGURA 9.30
   Ejemplo 9.17
   FIGURA 9.31
   9.3.10: Método de las expansiones parciales
   Ejemplo 9.18
   FIGURA 9.32
   FIGURA 9.33
   FIGURA 9.34
   Ejemplo 9.19
   FIGURA 9.35
   Ejemplo 9.20
   FIGURA 9.36
   Ejemplo 9.21
   FIGURA 9.37
   9.3.11: Listas invertidas
   Ejemplo 9.22
   Ejemplo 9.23
   Ejemplo 9.24
   Ejemplo 9.25
   9.3.12: Multilistas
   Ejemplo 9.26
   FIGURA 9.38
   EJERCICIOS
   Búsqueda interna
   Búsqueda externa
Back Matter
   BIBLIOGRAFÍA
   GLOSARIO
   ÍNDICE ANALÍTICO