Estructuras de datos y algoritmos
20 pasos en 6 series de C.
Estructuras de datos escritas a mano, porque en C es la única forma de tenerlas. Ordenamiento y búsqueda, listas enlazadas y pilas, árboles, tablas hash y heaps, y después grafos.
La última serie es manipulación de bits, que está más cerca del metal que cualquier otra cosa aquí y aun así aparece en código real más de lo que esperarías. Veinte pasos, y de paso sirve como repaso de algoritmos.
Ordenamiento y búsqueda
- Ordenamiento burbujaEl ordenamiento que nadie debería usar y que todos deberían haber escrito una vez.
- Ordenamiento por inserciónOrdenar en el lugar haciendo crecer un prefijo ordenado.
- Búsqueda binariaDivide el rango a la mitad en cada paso; mil elementos toman diez comparaciones.
- QuicksortParticionar alrededor de un pivote y luego ordenar las dos mitades.
- Ordenamiento por mezclaDividir, ordenar cada mitad y luego mezclar las dos corridas ordenadas.
Listas y pilas
- Nodos de lista enlazadaEl struct autorreferencial detrás de una lista enlazada.
- Una lista doblemente enlazadaDos punteros por nodo: insertar y quitar no requieren recorrido.
- Invertir una lista en el lugarTres punteros recorren la lista una vez, volteando cada enlace al pasar.
- Una pila sobre un arregloUna pila de capacidad fija con push y pop.
- Una cola sobre un arregloDos índices se persiguen alrededor de un búfer fijo.
Árboles, tablas y heaps
- Un árbol binario de búsquedaInsertar desciende a izquierda o derecha; buscar sigue el mismo camino.
- Recorrer un árbolEn orden, profundidad y liberación: tres recursiones con la misma forma.
- Una tabla hash con encadenamientoUn arreglo de buckets con nodos enlazados: hashear a un bucket y recorrer su cadena corta.
- Un heap binarioEl arreglo es el árbol: los hijos de i viven en 2i+1 y 2i+2.
Grafos
- Búsqueda en anchuraUna matriz de adyacencia, una cola de nodos frontera y un arreglo de visitados.
- Búsqueda en profundidadEl mismo grafo, un recorrido recursivo y otro orden de visita.
Manipulación de bits
- Flags de bitsEncender, apagar y probar bits individuales.
- Trucos para contar bitsTrucos de bits clásicos con & y resta.
Bis
- matrix.cMultiplicar dos matrices enteras de 3x3 e imprimir el resultado.
- hash_index.cUn índice de palabras sobre una tabla hash encadenada, con conteos y cierre limpio.