Colección de citas famosas - Libros antiguos - Ocho características de la estructura de datos

Ocho características de la estructura de datos

Estructuras de datos: la forma en que las computadoras almacenan y organizan datos. El objetivo del programador es elegir la mejor estructura de datos para el problema en cuestión.

Ocho estructuras de datos: matriz, pila, lista vinculada, cola, montón, gráfico, árbol y tabla hash; cada estructura tiene su propio modo de almacenamiento especial.

Concepto:

Matriz unidimensional: elemento de matriz + índice de matriz

Matriz multidimensional: los elementos de la matriz también son matrices.

Operaciones básicas: insertar, obtener, eliminar (eliminar la matriz en el índice), cambiar tamaño (obtener la longitud de la matriz)

Título:

Buscar en la matriz El segundo elemento más pequeño.

Encuentre el primer elemento de matriz no duplicado.

Combina datos de dos números ordenados.

Reorganiza los números positivos y negativos en la matriz.

Características: Stack es una mesa lineal especial que solo se puede operar en un extremo de la mesa lineal. Se permiten operaciones en la parte superior pero no en la inferior. Las características de la pila son: primero en entrar, último en salir o último en entrar, primero en salir. Los elementos de la pila utilizan el método último en entrar, primero en salir (LIFO), es decir, el método último en entrar, primero en salir.

Operaciones básicas: Push (insertar elementos en la parte superior de la pila), Pop (devolver los elementos en la parte superior de la pila y eliminarlos), isEmpty (consultar si la pila está vacía) y Top ( devolver los elementos en la parte superior sin eliminarlos)).

Tema: Usar pilas para evaluar expresiones postfijas, usar pilas para ordenar elementos en la pila y verificar que los corchetes en las cadenas coincidan correctamente.

Escenarios de uso: las pilas se utilizan a menudo para implementar funciones recursivas, como la secuencia de Fibonacci. Deshacer, también conocido como Ctrl+Z, es una de nuestras operaciones más utilizadas y la mayoría de las aplicaciones admitirán esta función. ¿Sabes cómo se consigue? La respuesta es esta: mantenga los estados anteriores de la aplicación (una cantidad limitada) en la memoria y coloque el estado más reciente primero. En este momento necesitamos una pila para implementar esta función.

Concepto: Una cola es similar a una pila y utiliza una estructura lineal para almacenar datos. La diferencia entre ellos es que la pila usa el modo LIFO, mientras que la cola usa FIFO (primero en entrar, primero en salir).

Escenarios de uso: debido a la naturaleza de primero en entrar, primero en salir de la cola, es muy adecuada para la gestión de colas de bloqueo de subprocesos múltiples.

Operaciones básicas: Poner en cola: insertar un elemento al final de la cola, Quitar de la cola: eliminar el primer elemento I de la cola, vacío: consultar si la cola está vacía, Arriba: devolver el primer elemento de la cola. cola .

Ejercicio: use una cola para implementar una pila, invierta los primeros k elementos de la cola y use la cola para convertir 1 an a binario.

El concepto de "lista enlazada" también es una estructura lineal que se parece mucho a una matriz, pero su asignación de memoria, estructura interna y operaciones de inserción y eliminación son diferentes. Una lista enlazada es una cadena de nodos, cada nodo contiene datos y un puntero al siguiente nodo. El puntero principal de la lista vinculada apunta al primer nodo. Si la lista vinculada está vacía, el puntero principal está vacío. Las listas enlazadas se dividen en listas enlazadas unidireccionalmente y listas doblemente enlazadas.

Escenarios de uso: las listas enlazadas se pueden utilizar para implementar sistemas de archivos, tablas hash y listas de adyacencia.

Operaciones básicas: InsertAtEnd - inserta un elemento al final de la lista enlazada, InsertAtHead - inserta un elemento al principio de la lista enlazada, eliminar - elimina el elemento especificado de la lista enlazada, elimina el primero elemento de la lista vinculada, Buscar - -Consulta el elemento especificado en la lista vinculada, está vacío - Consulta si la lista vinculada está vacía.

Título: Invertir una lista vinculada, verificar si hay un ciclo en la lista vinculada, devolver el enésimo elemento del último en la lista vinculada y eliminar elementos duplicados en la lista vinculada.

Concepto: Un gráfico consta de muchos vértices que están conectados entre sí para formar una red. (X,Y) representa un borde, lo que significa que los nodos X e Y están conectados. Los bordes pueden tener pesos/costos.

Clasificación: gráfico no dirigido, gráfico dirigido

Representación: matriz de adyacencia, lista de adyacencia.

Dos algoritmos para el recorrido de gráficos: búsqueda en amplitud y búsqueda en profundidad.

Preguntas frecuentes:

Implemente la búsqueda en amplitud, implemente la búsqueda en profundidad, verifique si el gráfico es un árbol, cuente el número de aristas en el gráfico y use el algoritmo de Dijkstra para Encuentre la conexión entre dos nodos a la distancia más corta.

Un árbol es una estructura de datos jerárquica que consta de nodos y bordes que conectan los nodos. Un árbol es un tipo especial de gráfico y su mayor diferencia con un gráfico es que no tiene ciclos. Los árboles se utilizan ampliamente en inteligencia artificial y en algunos algoritmos complejos para proporcionar estructuras de almacenamiento eficientes.

Árboles comunes: árbol N-ario, árbol balanceado, árbol binario, árbol binario de búsqueda, árbol binario balanceado, árbol rojo-negro y árbol 2-3.

Título: Calcule la altura del árbol, encuentre los k elementos más grandes en el árbol binario equilibrado, encuentre el nodo con una distancia k desde el nodo raíz en el árbol y encuentre todos los ancestros de un nodo en el nodo del árbol binario.

Hash convierte un objeto en un identificador único, que suele estar representado por una corta cadena aleatoria de letras y números. Los hashes se pueden utilizar para implementar varias estructuras de datos, la más utilizada de las cuales son las tablas hash.

Las tablas hash generalmente se implementan como matrices.

El rendimiento de la tabla hash depende de tres indicadores:

Cómo lidiar con el tamaño de la colisión hash de la tabla hash de la función hash

Título: Encuentre el matriz Combinaciones simétricas en, confirma si los elementos de una matriz son un subconjunto de los elementos de otra matriz, confirma si las matrices dadas son mutuamente excluyentes.

Un árbol de prefijos (árbol de prefijos o Trie) es similar a un árbol y es muy eficaz cuando se trata de problemas relacionados con cadenas. Puede lograr una recuperación rápida y se utiliza a menudo para consultas de palabras en diccionarios, finalización automática de motores de búsqueda e incluso enrutamiento IP.

Materiales de referencia:

blogs.com/williamjie/p/9558015.html