Cada vez más, noto que las personas modernas autodidactas realmente carecen de material. Todo el mundo sabe idiomas, pero pequeños conceptos básicos como los tipos de datos o algoritmos. Un poco sobre los tipos de datos.
En 1976, el científico suizo
Nicklaus Wirth escribió el libro
Algoritmos + estructuras de datos = programas.Más de 40 años después, esta ecuación sigue siendo cierta. Y si eres una persona autodidacta y repasas el artículo durante mucho tiempo en la programación, puedes hacerlo en diagonal. Puedes codificar el café.
El artículo también tendrá preguntas que puede escuchar en la entrevista.
¿Qué es una estructura de datos?
Una estructura de datos es un contenedor que almacena datos en un diseño específico. Este "diseño" permite que la estructura de datos sea efectiva en algunas operaciones e ineficaz en otras.
Cuales hay
Lineal , los elementos forman una secuencia o lista lineal, sin pasar por los nodos es lineal. Ejemplos: matrices. Lista vinculada, pilas y colas.
No lineal , si el bypass de nodos no es lineal y los datos no son consistentes. Ejemplo: gráfico y árboles.
Estructuras de datos básicos.
- Matrices
- Pilas
- Colas
- Listas Relacionadas
- Cuenta
- Arboles
- Árboles de prefijo
- Tabla hash
Matrices
Una matriz es la estructura de datos más simple y más utilizada. Otras estructuras de datos, como pilas y colas, se derivan de matrices.
Imagen de una matriz simple de tamaño 4 que contiene elementos (1, 2, 3 y 4).
A cada elemento de datos se le asigna un valor numérico positivo (índice), que corresponde a la posición del elemento en la matriz. La mayoría de los idiomas definen el índice inicial de una matriz como 0.
Hay
Unidimensional , como se muestra arriba.
Multidimensionales , matrices dentro de matrices.
Operaciones básicas
- Insertar-inserta un elemento en un índice dado
- Get-devuelve un elemento en un índice dado
- Eliminar-eliminar un elemento en un índice dado
- Tamaño: obtenga el número total de elementos en la matriz
Preguntas
- Encuentra el segundo elemento mínimo de la matriz
- Los primeros enteros no repetitivos en una matriz
- Combina dos matrices ordenadas
- Reordenación de valores positivos y negativos en una matriz
Pilas
Una pila es un tipo de datos abstractos, que es una lista de elementos organizados según el principio de LIFO (último último - primero en salir, último en llegar - primero en ir)
Estos no son matrices. Este es el turno.
Inventado por Alan Thuring.Un ejemplo de una pila sería un montón de libros dispuestos verticalmente. Para obtener el libro, que está en algún lugar en el medio, deberá eliminar todos los libros colocados en él. Así es como funciona el método LIFO (Last In First Out). La función "Cancelar" en las aplicaciones funciona en LIFO.
La imagen de la pila, en tres elementos (1, 2 y 3), donde 3 está en la parte superior y se eliminará primero.
Operaciones básicas
- Push inserta un elemento en la parte superior
- Pop-devuelve el elemento superior después de eliminarlo de la pila
- isEmpty-devuelve verdadero si la pila está vacía
- Top: devuelve el elemento superior sin eliminarlo de la pila.
Preguntas
- Implemente una cola usando la pila
- Ordenar valores en la pila
- Implementando dos pilas en una matriz
- Invierte una cadena usando una pila
Colas
Al igual que las pilas, una cola almacena un elemento de forma secuencial. Una diferencia significativa de la pila es el uso de FIFO (Primero en entrar, primero en salir) en lugar de LIFO.
Un ejemplo de una línea es una línea de personas. El último tomó el último y tú lo harás, y el primero la dejará primero.
La imagen de la cola, en cuatro elementos (1, 2, 3 y 4), donde 1 está en la parte superior y se eliminará primero
Operaciones básicas
- Enqueue—): inserta un elemento al final de la cola
- Dequeue (): elimina un elemento del comienzo de la cola
- isEmpty (): devuelve verdadero si la cola está vacía
- Top (): devuelve el primer elemento de la cola
Preguntas
- Implementar una pila usando una cola
- Invierte los primeros N elementos de una cola
- Generando números binarios del 1 al N usando una cola
Lista vinculada
Una lista vinculada es una matriz donde cada elemento es un objeto separado y consta de dos elementos: datos y un enlace al siguiente nodo.
La principal ventaja sobre la matriz es la flexibilidad estructural: el orden de los elementos de la lista vinculada puede no coincidir con el orden de la ubicación de los elementos de datos en la memoria de la computadora, y el orden de recorrido de la lista siempre está explícitamente determinado por sus relaciones internas.
Hay
Unidireccional , cada nodo almacena la dirección o enlace al siguiente nodo en la lista y el último nodo tiene la siguiente dirección o enlace como NULL.
1-> 2-> 3-> 4-> NULL
Bidireccional , dos enlaces asociados con cada nodo, uno de los puntos fuertes para el siguiente nodo y otro para el nodo anterior.
NULL <-1 <-> 2 <-> 3-> NULL
Circular , todos los nodos están conectados para formar un círculo. Al final no hay NULL. Una lista enlazada cíclica puede ser una lista enlazada cíclica simple o doble.
1-> 2-> 3-> 1
La lista unidireccional lineal más común. Un ejemplo es un sistema de archivos.
Operaciones básicas
- InsertAtEnd: inserta el elemento especificado al final de la lista.
- InsertAtHead: inserta un elemento en la parte superior de la lista
- Eliminar: elimina el elemento especificado de la lista.
- DeleteAtHead: elimina el primer elemento de la lista
- Buscar: devuelve el elemento especificado de la lista
- isEmpty: devuelve True si la lista vinculada está vacía
Preguntas
- Lista reversa inversa
- Definir un bucle en una lista vinculada
- Devolver N artículo desde el final en la lista vinculada
- Eliminar duplicados de una lista vinculada
Cuenta
Un gráfico es un conjunto de nodos (vértices) que están conectados entre sí en forma de red por aristas (arcos).
Hay
Orientado , las costillas son direccionales, es decir solo hay una dirección disponible entre dos vértices conectados.
Desorientado , a cada una de las costillas puede ir en ambas direcciones.
Mezclado
Encontrado en formas como
- Matriz de adyacencia
- Lista de adyacencia
Algoritmos transversales de gráficos generales
- Búsqueda de ancho: rastreo de nivel
- Búsqueda de profundidad: atravesando los picos
Preguntas
- Implementar búsqueda en ancho y profundidad
- Comprueba si el gráfico es un árbol o no
- Cuenta el número de aristas en un gráfico
- Encuentra el camino más corto entre dos picos
Arboles
Un árbol es una estructura de datos jerárquica que consta de nodos (vértices) y aristas (arcos). Los árboles son esencialmente gráficos conectados sin bucles.
Estructuras de árboles en todas partes. Todos conocen el árbol de habilidades en los juegos.
Árbol simple
Tipos de árboles
El árbol binario es el más común.
“Un árbol binario es una estructura de datos jerárquica en la que cada nodo tiene un valor (también es la clave en este caso) y referencias a los descendientes izquierdo y derecho. »- ProcsTres formas de moverse por un árbol
- En orden directo (de arriba a abajo): el formulario de prefijo.
- En orden simétrico (de izquierda a derecha) - forma infija.
- En el orden inverso (de abajo hacia arriba) - formulario postfix.
Preguntas
- Encuentra la altura de un árbol binario
- Encuentra el N elemento más pequeño en un árbol de búsqueda binario
- Encuentra nodos a una distancia N de la raíz
- Encuentra antepasados del nodo N en árbol binario
Trie (árbol de prefijos)
Una especie de árbol para cuerdas, búsqueda rápida. Diccionarios T9
Así es como dicho árbol almacena las palabras "top", "so" y "su".
Las palabras se almacenan de arriba a abajo, los nodos de color verde "p", "s" y "r" apuntan al final de "arriba", "así" y "su", respectivamente.
Preguntas
- Cuenta el número total de palabras
- Imprime todas las palabras
- Ordenar elementos de matriz del árbol de prefijos
- Crear diccionario T9
Tabla hash
El hash es un proceso que se utiliza para identificar objetos de forma exclusiva y almacenar cada objeto en un índice (clave) único precalculado.
Un objeto se almacena como un par clave-valor, y una colección de dichos elementos se denomina diccionario. Cada objeto se puede encontrar usando esta clave.
En esencia, esta es una matriz en la que la clave se representa como una función hash.
El rendimiento del hash depende de
- Funciones hash
- Tamaño de tabla hash
- Métodos de manejo de colisiones
Un ejemplo de coincidencia de hash en una matriz. El índice de esta matriz se calcula mediante una función hash.
Preguntas
- Encuentra pares simétricos en una matriz
- Averigua si una matriz es un subconjunto de otra matriz
- Describir hashing abierto
Listado de recursos
En lugar de una conclusión
El material es tan interesante como los idiomas mismos. Quizás alguien verá las estructuras básicas que le son familiares y se interesará.
Gracias por leer Espero no perder el tiempo =)
PD: Pido disculpas, resultó que la traducción del artículo ya estaba aquí y, muy recientemente, la pasé por alto.
Si está interesado,
aquí está , gracias
Hokum , tendré más cuidado.