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
Valoraciones
No hay valoraciones aún.