Estructura datos

Algoritmos y Estructuras de Datos










































Índice

1. Nociones básicas de programación. pág 4
o Datos pág 4
o Instrucciones Elementales pág 4
o Instrucciones Compuestas pág 5
o Ejemplos de programas iterativos pág 10
o Diagramas de Estados pág 15
oRecursividad pág 18
o "Dividir para reinar" pág 19
o Recursividad y Tabulación (Programación Dinámica) pág 20
o Conceptos de Programación Orientada al Objeto (OOP) pág 23


2. Estructuras de datos básicas. pág 32
o Arreglos. pág 32
o Punteros y variables de referencia. pág 33
o Listas enlazadas. pág 34
oÁrboles. pág 37
▪ Árboles binarios. pág 39
▪ Árboles generales. pág 42


3. Tipos de datos abstractos. pág 43
o TDA lista. pág 43
o TDA pila. pág 44
o TDA cola. pág 50
o TDA cola de prioridad pág 52


4. TDA diccionario. pág 53
o Implementaciones sencillas. pág 55
▪Búsqueda binaria. pág 55
▪ Búsqueda secuencial con probabilidades de acceso no uniforme. pág 57
o Arboles de búsqueda binaria. pág 58
o Arboles AVL. pág 63
o Arboles 2-3. pág 68
o Arboles B. pág 71
o Arboles digitales. pág 72
o Arboles de búsqueda digital. pág 73
o Skip lists. pág 74o ABB óptimos. pág 76
o Splay Trees. pág 78
o Hashing. pág 81
▪ Encadenamiento. pág 82
▪ Direccionamiento abierto. pág 84
▪ Hashing en memoria secundaria. pág 86




5. Compresión de Datos. pág 89
o Codificación de mensajes pág 89
o Entropía de Shannon pág 91
o Algoritmo deHuffman pág 92
o Lempel Ziv pág 94


6. Ordenamiento. pág 96
o Cota inferior pág 96
o Quicksort pág 97
o Heapsort pág 101
o Bucketsort pág 104
o Mergesort y Ordenamiento Externo pág 106


7. Búsqueda en Texto. pág 108
o Algoritmo de fuerza bruta. pág 108
o AlgoritmoKnuth-Morris-Pratt (KMP). pág 109
o Algoritmo Boyer-Moore. pág 112
▪ Boyer-Moore-Horspool (BMH). pág 112
▪ Boyer-Moore-Sunday (BMS). pág 112


8. Grafos. pág 115
o Definiciones Básicas pág 115
o Recorridos de Grafos pág 116
o Árbol Cobertor Mínimo pág 118
o Distancias Mínimas en un Grafo Dirigidopág 120


9. Algoritmos probabilísticos. pág 124



















Nociones básicas de programación

En esta sección se revisarán los elementos básicos que se van a utilizar para escribir programas. Esto supone que los alumnos ya saben programar, y es sólo un resumen y una ordenación de conceptos. La notación utilizada es la del lenguaje Java, pero los conceptosson más generales y se aplican a muchos otros lenguajes similares.

Datos

Los programas representan la información que manejan mediante valores llamados "constantes", y dichos valores se almacenan en "variables".

Variables

int k; // entero
float x; // real
double prom; // real de doble precisión
boolean condicion; // verdadero o falso
char c; // un carácter
String nombre; //secuencia de caracteres
Nótese que la secuencia "//" indica el comienzo de un comentario, el cual se extiende hasta el final de la línea.

Constantes

3 // int
4.50 // float
1e-6 // float
'a' // char
"hola" // String

Instrucciones Elementales


Asignación

Esta es la instrucción más simple, que permite modificar el valor de una variable:
a = E; // asigna a la variable 'a' el valor...