Wondershare EdrawMind
Galería de mapas mentales Organización del mapa mental de la estructura de datos.
Organización del mapa mental de la estructura de datos.
La estructura de datos organiza la descripción general de la literatura de la dinastía Song, las letras de las canciones, la poesía de las canciones, la prosa de la dinastía Song, la gramática C11, la clasificación, los gráficos, los árboles y la comparación del plan de estudios de 935 exámenes.
Editado a las 2023-03-05 23:09:15,
- Breve historia del tiempo
Este es un mapa mental sobre una breve historia del tiempo. "Una breve historia del tiempo" es una obra de divulgación científica con una influencia de gran alcance. No sólo presenta los conceptos básicos de cosmología y relatividad, sino que también analiza los agujeros negros y la expansión. del universo. temas científicos de vanguardia como la inflación y la teoría de cuerdas.
- ¿Cuáles son los métodos de fijación de precios para los subcontratos de proyectos bajo el modelo de contratación general EPC
¿Cuáles son los métodos de fijación de precios para los subcontratos de proyectos bajo el modelo de contratación general EPC? EPC (Ingeniería, Adquisiciones, Construcción) significa que el contratista general es responsable de todo el proceso de diseño, adquisición, construcción e instalación del proyecto, y es responsable de los servicios de operación de prueba.
- Puntos de conocimiento que los ingenieros de Java deben dominar en cada etapa
Los puntos de conocimiento que los ingenieros de Java deben dominar en cada etapa se presentan en detalle y el conocimiento es completo, espero que pueda ser útil para todos.
Organización del mapa mental de la estructura de datos.
- Breve historia del tiempo
Este es un mapa mental sobre una breve historia del tiempo. "Una breve historia del tiempo" es una obra de divulgación científica con una influencia de gran alcance. No sólo presenta los conceptos básicos de cosmología y relatividad, sino que también analiza los agujeros negros y la expansión. del universo. temas científicos de vanguardia como la inflación y la teoría de cuerdas.
- ¿Cuáles son los métodos de fijación de precios para los subcontratos de proyectos bajo el modelo de contratación general EPC
¿Cuáles son los métodos de fijación de precios para los subcontratos de proyectos bajo el modelo de contratación general EPC? EPC (Ingeniería, Adquisiciones, Construcción) significa que el contratista general es responsable de todo el proceso de diseño, adquisición, construcción e instalación del proyecto, y es responsable de los servicios de operación de prueba.
- Puntos de conocimiento que los ingenieros de Java deben dominar en cada etapa
Los puntos de conocimiento que los ingenieros de Java deben dominar en cada etapa se presentan en detalle y el conocimiento es completo, espero que pueda ser útil para todos.
- Recomendados
- Resumen
estructura de datos
introducción
algoritmo
Definición de algoritmo
Descripción de los pasos para la resolución de problemas.
cinco características
finitud
certeza
factibilidad
ingresar
producción
Cálculo de complejidad
complejidad del tiempo
regla de suma
Reglas de multiplicación
Complejidades comunes del tiempo asintótico
Fórmula aritmética
complejidad espacial
Definir la relación entre el tamaño del espacio auxiliar y la cantidad de datos originales.
Trabajar en el lugar
resolver problemas
algoritmo recursivo
fórmula de recursividad
llamada recursiva
salida pública recursiva
método de ecuación de columna
datos
objeto de datos
elemento de datos
unidad básica (individual)
elemento de datos
atributos (individuales)
tipo de datos
tipo atómico
tipo de estructura
Tipo de datos abstractos (ADT)
estructura de datos
Tres elementos
estructura lógica
estructura lineal
tabla lineal general
mesa lineal restringida
pila
cola
cadena
Promoción de mesa lineal.
formación
estructura no lineal
Árbol
Árbol binario
multiárbol
bosque
Imagen/Red
gráfico dirigido
Gráfico no dirigido
recolectar
estructura de almacenamiento
almacenamiento secuencial
almacenamiento en cadena
Almacenamiento de índice
Almacenamiento de hash/almacenamiento de hash
Operaciones de datos (operaciones)
Lista linealLista lineal
Definición/Concepto
Número limitado de elementos de datos, mismo tipo de datos y ordenados
El espacio de almacenamiento es del mismo tamaño.
elemento principal; elemento posterior; orden de bits;
funcionar
Crear/destruir
asignación estática
asignación dinámica
C/C malloc, nuevo[]
Agregar, eliminar, modificar y verificar
Adquisición de propiedad
estructura de almacenamiento
mapeo secuencial almacenamiento secuencial
tabla de secuencia SqList
característica
Acceso aleatorio [el orden físico y lógico es el mismo]
La eliminación y la inserción tienen una gran complejidad temporal.
Asignación
estático
Asignación de matrices en lenguaje C
dinámica
Asignación del modo de puntero en lenguaje C
funcionar
inicialización
insertar
Implementar lógica
Juicio de robustez
mover
Modificación de propiedad
Estado de la función de retorno
complejidad del tiempo
Mejor O(1)
Peor O(n)
Promedio = Probabilidad Número de movimientos = Expectativa
borrar
Implementar lógica
Robustez
mover
Modificación de propiedad
Estado de la función de retorno
complejidad del tiempo
Mejor O(1)
Peor O(n)
promedio
Buscar por valor
Implementar lógica
buscar en orden
Orden de devolución
complejidad del tiempo
Mejor O(1)
Peor O(n)
promedio
unir
Preguntas reales
2010] 408 matriz de enteros desplazamiento circular a la izquierda
2011] 408 Encuentre la mediana de dos secuencias ascendentes de igual longitud
2013] 408 Encuentra el elemento principal en la secuencia Elemento principal: número > número total de secuencia/2.
2018】408 Encuentra el número entero más pequeño que no aparece
2020】408 Encuentra la distancia mínima de triples.
almacenamiento en cadena
lista única
definición
funcionar
insertar
Método de inserción de la cabeza
método de inserción de la cola
Complejidad del tiempo O (n)
borrar
Buscar por valor
Llámalo corto
lista doblemente enlazada
definición
funcionar
insertar
Implementar lógica
complejidad del tiempo
borrar
lista circular enlazada
Lista enlazada circular unidireccional
Lista enlazada circular bidireccional
falange
lista enlazada estática
mesa de salto
Conceptos relacionados
nodo principal
puntero de cabeza
Encabezado de lista vinculada
Primer nodo
puntero de cola
Preguntas reales
2009] 408 Encuentre el valor del nodo en la k-ésima posición desde abajo en una lista enlazada individualmente que contiene solo el nodo principal
2012】 408 Encuentre la posición inicial del sufijo común de dos listas vinculadas
2015] 408 la lista enlazada individualmente conserva el nodo con la primera posición que aparece entre todos los nodos con valores absolutos iguales.
2019】 408 reorganizar la lista enlazada individualmente
Ventajas y desventajas
orden
Acceso aleatorio, encadenado solo se puede acceder de forma secuencial
cadena
Asignación flexible, sin necesidad de ocupar espacio continuo, baja complejidad de tiempo de inserción y eliminación
estructura lógica
Pila
definición
parte superior de la pila
Abajo
Vacío
Características LIFO último en entrar, primero en salir
Propiedades matemáticas [número de Cattleya] Se colocan n elementos diferentes en la pila y el número de disposiciones diferentes de elementos que salen de la pila es
funcionar
&InicializarInit
&Destruir
Empujar(Empujar)Empujar(&S,&e)
Pop(&S,&e)
Leer la parte superior de la pila GetTop(S,&e)
Vacío está vacío
estructura de almacenamiento
orden
pila de secuencia
pila compartida
cadena
pila de cadena
funcionar
Atributos
nodo de encabezado
nodo de cola de tabla
Tipos de preguntas de aplicación
coincidencia de soportes
Evaluación de expresiones
prefijo/expresión polaca
infijo
Expresión de sufijo/pulido inverso
Método de conversión
Método de cálculo
árbol de expresión
llamada recursiva
cálculo de complejidad del tiempo
búsqueda amplia dfs
secuencia pop
secuencia imposible
Número de tipos de secuencia
Número de Cattleya:
posible secuencia
Conversión numérica
Profundidad mínima de pila
Función de almacenamiento de variables locales.
Cola/Cola
Operaciones básicas
FIFO
inicialización
destruir
Llámalo corto
Únete al equipo
quitar la cola
Leer el elemento del encabezado
concepto
Cabeza de puntero de línea
puntero de cola
nodo principal
estructura de almacenamiento
orden
cola circular
almacenamiento secuencial
cadena
deque
almacenamiento en cadena
definición
funcionar
estructura lógica
solicitud
Recorrido a nivel de árbol binario
Cálculo de secuencia de salida de cola
Al hacer las preguntas, puedes marcar la secuencia de entradas izquierda y derecha
Propiedades FIFO
Búfer del sistema operativo
asignación de recursos de CPU
Algoritmo de reemplazo de página
matriz de matriz
formación
definición
estructura de almacenamiento
precedencia de fila
Primera columna
matriz especial
matriz simétrica
Fórmula de conversión de subíndice
matriz triangular
Conversión de subíndice
matriz tridiagonal
Conversión de subíndice
matriz dispersa
Tríada
lista cruzada
matriz dispersa
matriz de adyacencia
Preguntas reales
La siguiente tabla de elementos de matriz y conversión de subíndices de matriz de un dígito
Por favor solicite la dirección del gerente del banco.
cadena
concepto basico
subcadena
cadena principal
Ubicación
estructura de almacenamiento
Almacenamiento secuencial de longitud fija
Almacenamiento asignado en montón
Almacenamiento de cadena de bloques
Operaciones relacionadas
la coincidencia de patrones
Emparejamiento de fuerza bruta
algoritmo KMP
siguientematriz
siguienteAlgoritmo manual
Juicio de igualdad
encontrar subcadena
conectar
longitud
Encontrar
índice de eficiencia
longitud media de búsqueda
Búsqueda exitosa
La búsqueda falló
concepto
Tabla de búsqueda/estructura de búsqueda
funcionar
Encuentra elementos específicos
Verifique los atributos del elemento que cumplen las condiciones.
insertar elemento
Eliminar elemento
tabla de búsqueda estática
orden
Reducir en la mitad
picadillo
tabla de búsqueda dinámica
árbol de clasificación binaria
Árbol binario balanceado AVL
árbol B
longitud media de búsqueda
conflicto/colisión
conflicto entre sinónimos
imposible de evitar
reunir/acumular
Los sinónimos entran en conflicto con los no sinónimos
Principalmente relacionado con los métodos de detección de conflictos.
estructura hash
función hash
método de direccionamiento directo
método de división dejando resto
analítica digital
Método cuadrado-medio
Manejo de conflictos
método de direccionamiento abierto
Sondeo lineal y luego hash
Segunda detección y luego hash
Sondeo pseudoaleatorio y luego hash
Método de dirección en cadena/método de cremallera
Método de refrito (hash)
longitud media de búsqueda
Búsqueda exitosa
La búsqueda falló
factor de carga
a = número de registros en la tabla/longitud de la tabla hash
estructura lineal
Búsqueda secuencial (restricción de cadena)
Búsqueda de tabla de secuencia general
Búsqueda de lista ordenada
Buscar por la mitad (dos puntos)
Adecuado para estructuras de almacenamiento secuenciales ordenadas
Árbol de decisión de media búsqueda
Tipo: árbol binario equilibrado
Altura del árbol h cuando hay n elementos
Determinar si el árbol es una regla compuesta.
La mayoría de las búsquedas
Número mínimo de búsquedas
Búsqueda bloqueada (orden de índice)
longitud ideal del bloque
búsqueda secuencial de bloques
optimización óptima
Estructura de índice/tabla de árbol
árbol B
Atributos
Orden del árbol B
estructura de nodo no hoja
El factor de equilibrio de todos los nodos es 0 [equilibrio de altura]
alto
más alto
más bajo
Número de palabras clave
mayoría
el menos
naturaleza
Número de palabras clave de nodo no raíz
Número de subárboles de nodos no raíz
Cuando el nodo raíz es un nodo no terminal, debe tener al menos dos hijos.
Árbol de búsqueda estrictamente equilibrado, todos los subárboles de nodos tienen la misma altura y las hojas están al mismo nivel y están representadas por NULL
La estructura de los nodos no hoja.
funcionar
Encontrar
insertar
Dividir
borrar
unir
Ilustración
calcular
Dado el orden, la cantidad de capas y la cantidad de palabras clave en una determinada capa, encuentre la cantidad máxima de nodos
árbol B
Ilustración
La diferencia entre árboles B y B
árbol negro rojo
definición
naturaleza
solicitud
Operaciones básicas
Descoloramiento
girar
insertar
Insertar ajustes
borrar
Eliminar ajuste
Comparación del plan de estudios 935
2022] 1. Tabla lineal (1) Definición y operaciones básicas de tabla lineal (2) Implementación de tabla lineal 1. Estructura de almacenamiento secuencial 2. Estructura de almacenamiento vinculada 3. Aplicación de tabla lineal 2. Pila, cola y matriz (1) Básico conceptos de pilas y colas (2) Estructuras de almacenamiento secuencial de pilas y colas (3) Estructuras de almacenamiento encadenado de pilas y colas (4) Aplicaciones de pilas y colas (5) [Almacenamiento de matrices multidimensionales] y almacenamiento comprimido de matrices especiales 3. Árboles y árboles binarios (1) Conceptos básicos de árboles (2) Árboles binarios 1. Definición de árboles binarios y sus principales características 2. Estructura de almacenamiento secuencial y estructura de almacenamiento en cadena de árboles binarios 3. Recorrido de árboles binarios 4. Conceptos básicos y pistas de árboles binarios Construcción (3) Árboles y bosques 1. Estructura de almacenamiento de árboles 2. Conversión entre bosques y árboles binarios 3. Recorrido de árboles y bosques (4) Aplicaciones de árboles y árboles binarios 1. Árbol de búsqueda binaria 2. Equilibrado árbol binario 3. Árbol de Huffman (Huffman) y codificación de Huffman 4. [Búsqueda de unión] 3. Gráfico (1) Concepto de gráfico (2) Almacenamiento y operaciones básicas del gráfico 1. Método de matriz de adyacencia 2. Método de lista de adyacencia (3) Recorrido del gráfico 1. Búsqueda en profundidad 2. Búsqueda en amplitud (4) Aplicaciones básicas de los gráficos 1. Árbol de expansión mínimo (costo) 2. Ruta más corta 3. Clasificación topológica 4. Ruta crítica 4. Búsqueda (1) Conceptos básicos de búsqueda (2) Método de búsqueda secuencial (3) [Método de búsqueda por bloques] (4) Método de media búsqueda (5) Árbol B y sus operaciones básicas, conceptos básicos del árbol B (6) Tabla hash (7) Análisis del algoritmo de búsqueda y aplicación 5. Clasificación (1) Conceptos básicos de clasificación (2) Clasificación por inserción 1. Clasificación por inserción directa 2. Clasificación por media inserción (3) Clasificación por burbujas (4) Clasificación por selección simple (5) Clasificación por colinas (clasificación por conchas) (6) Clasificación rápida (7) Clasificación en montón (8) Clasificación por fusión bidireccional (9) Clasificación por base (10) [Clasificación externa] (11) Comparación de varios algoritmos de clasificación (12) Aplicación de algoritmos de clasificación
2021] 1. Tabla lineal (1) Definición y operaciones básicas de tabla lineal (2) Implementación de tabla lineal 1. Estructura de almacenamiento secuencial 2. Estructura de almacenamiento vinculada 3. Aplicación de tabla lineal 2. Pila, cola y matriz (1) Básico conceptos de pilas y colas (2) Estructuras de almacenamiento secuencial de pilas y colas (3) Estructuras de almacenamiento encadenado de pilas y colas (4) Aplicaciones de pilas y colas (5) Almacenamiento comprimido de matrices especiales 3. Árboles y árboles binarios (1) Conceptos básicos de árboles (2) Árboles binarios 1. Definición y características principales de los árboles binarios 2. Estructura de almacenamiento secuencial y estructura de almacenamiento en cadena de árboles binarios 3. Recorrido de árboles binarios 4. Pistas Conceptos básicos y construcción de árboles binarios (3) Árbol , bosque 1. Estructura de almacenamiento del árbol 2. Conversión entre bosque y árbol binario 3. Recorrido de árbol y bosque (4) Aplicación de árbol y árbol binario 1. Árbol de clasificación binaria 2. Árbol binario equilibrado 3. Árbol de Huffman y codificación de Huff Mann 3. Gráfico (1) Concepto de gráfico (2) Almacenamiento y operaciones básicas del gráfico 1. Método de matriz de adyacencia 2. Método de lista de adyacencia (3) Recorrido del gráfico 1. Primera búsqueda en profundidad 2. Primera búsqueda en amplitud (4) Figura Aplicaciones básicas de 1. Árbol de expansión mínimo (costo) 2. Ruta más corta 3. Clasificación topológica 4. Ruta crítica 4. Búsqueda (1) Concepto básico de búsqueda (2) Método de búsqueda secuencial (3) Método de media búsqueda (4) B- Árbol y sus operaciones básicas, conceptos básicos de árbol B (5) Tabla hash (6) Análisis y aplicación del algoritmo de búsqueda 5. Clasificación interna (1) Concepto básico de clasificación (2) Clasificación por inserción 1. Clasificación por inserción directa 2. Clasificación por inserción a la mitad ( 3) Clasificación de burbujas (4) Clasificación de selección simple (5) Clasificación de colinas (clasificación de concha) (6) Clasificación rápida (7) Clasificación de montón (8) Clasificación de fusión bidireccional (clasificación de fusión) (9) Clasificación de base (10) Comparación de varios algoritmos de clasificación interna (11) Aplicación de algoritmos de clasificación interna
Árbol
concepto basico
alto
altura del nodo
altura del arbol
Número de capas/profundidad
profundidad del nodo
profundidad del árbol
Ancestro, descendiente, hermano, primo;
Gastar
grado de nodo
grado de arbol
Nodo
nodo de rama
nodo hoja
Árbol ordenado y árbol desordenado
Camino y longitud del camino
camino
longitud de la trayectoria
bosque
naturaleza
Nodos y grados
Número de nodos (m) = número de nodos que no son hojas número de nodos de hojas
Número de nodos = Σ grado x número 1 [raíz]
Número de nodos
Árbol m-ario con altura h hasta el número (máximo) de nodos
sp: Los nodos del árbol binario con altura h son como máximo
Para un árbol binario con un número par de nodos, el número de nodos con grado 1 debe ser un número impar.
altura minima
La altura de un árbol de orden m/árbol m-ario/árbol m-ario completo con n nodos [debe memorizar]
altura máxima
La altura máxima de un árbol con n nodos y grado m.
tipo
Árbol binario
definición
Si un nodo tiene solo un nodo hijo, debe ser el hijo izquierdo
Número de nodos, árbol ordenado que contiene subárboles izquierdo y derecho
naturaleza
Número relacionado
Número de nodos de las hojas
Número máximo de nodos en la capa k
La altura es h como máximo el número de nodos.
subíndice relacionado
controlar a los niños
Número secundario izquierdo del nodo i = 2i
Número secundario derecho del nodo i = 2i 1
Relacionado con la profundidad
La profundidad del nodo.
Árbol binario completo] Profundidad
Profundidad máxima de un árbol binario estricto
(n 1)/2
Número de punteros
El número de punteros nulos en una cadena binaria con n nodos es n 1
Orden de acceso transversal
legitimidad de secuencia
El orden de acceso determina la forma del árbol binario.
Se debe acceder a la izquierda antes que a la derecha.
Secuencia de acceso en orden frontal, medio y posterior, la secuencia de nodos hoja permanece sin cambios
Cuando la altura es igual al número de nodos, las secuencias transversales de preorden y postorden son opuestas.
tipo
árbol binario completo
Definición
árbol binario completo
definición
Todas las capas están llenas y los nodos de la capa se rellenan en orden de izquierda a derecha.
Cada nodo corresponde uno a uno a la posición del nodo numerado en el árbol binario completo con altura.
naturaleza
Si un nodo no tiene ningún hijo izquierdo, debe ser un nodo hoja.
El hermano izquierdo del padre de un nodo hoja (si existe) no debe ser un nodo hoja.
Un árbol binario completo con altura h, el número mínimo de nodos es
El último número de nodo de rama (no hoja) es
Si un árbol binario completo tiene nodos, entonces el número de nodos hoja es
calcular
Hay k nodos de hoja en la capa x. Encuentre el número máximo/mínimo de nodos.
El número mínimo de nodos es: El número máximo de nodos es:
estructura de almacenamiento
almacenamiento secuencial
almacenamiento en cadena
atravesar
Primer pedido/anterior (NLR)
Orden medio (LNR)
Postorden (LRN)
árboles y bosques
definición
Árbol de grado m árbol m-ario
bosque
estructura de almacenamiento
representación de los padres
Almacenamiento secuencial; dirección de almacenamiento = dirección lógica
representación infantil
Almacenamiento de listas de adyacencia; estructura de almacenamiento de gráficos dirigidos.
Hermanos secundarios/Notación de árbol binario
Número de nodos del bosque
Dado el número de bordes y nodos del bosque, encuentre el número de árboles que contiene el bosque.
Relación entre bosque y árbol binario.
El número de nodos cuyo puntero secundario derecho está vacío.
El número de nodos en el subárbol izquierdo del bosque = el árbol de nodos del primer árbol del bosque
Árboles transversales y ordenados.
árbol: primera raíz
Bosque: Prefacio
Árbol binario: preorden
árbol: raíz posterior
Bosque: Epílogo
Árbol binario: en orden
Transformaciones de árboles, bosques y árboles binarios.
atravesar
Primera búsqueda de amplitud BFS
Análisis de complejidad
Árboles extensos y bosques extensos
Primera búsqueda en profundidad DFS
Transversal y conectividad
Conversiones recursivas y no recursivas
recursividad = pila
recorrido de nivel
cola auxiliar
Recorre una secuencia para construir un árbol binario.
Orden medio (obligatorio) Primer pedido/Siguiente
El recorrido del árbol de pistas requiere pila
recorrido posterior al pedido
Para encontrar el camino de ancestros a descendientes, puede utilizar el recorrido de primer orden/orden
Encuentre el número heterogéneo de árboles binarios en un orden conocido
solicitud
árbol de huffman
longitud del camino ponderado
definición
El árbol binario con la longitud de ruta ponderada más pequeña (WPL) también se denomina árbol binario óptimo;
Un árbol de Huffman con grado m es un árbol m-ario estricto.
estructura
Codicioso, tome los dos nodos con el peso más pequeño cada vez como los subárboles izquierdo y derecho del nuevo nodo. El peso del nuevo nodo es la suma de los subárboles izquierdo y derecho y colóquelos en el conjunto de nodos seleccionables.
naturaleza
Los nodos iniciales son todos nodos hoja.
Cuanto menor sea el peso, más largo será el camino hasta el nodo raíz.
Se crean n-1 nuevos nodos y el número total de nodos es 2n-1
En un árbol de Huffman con grado m, el nodo hoja es n, entonces el número de nodos que no son hoja es
El número de nodos hoja es el número de códigos de diferentes símbolos.
Codificación Huffman
codificación de longitud fija
Cada carácter está representado por bits binarios de igual longitud.
codificación de prefijo
Ninguna codificación es un prefijo de otra codificación.
árbol binario de pistas
Estructura física/almacenamiento
Significado del campo de bandera
concepto
clave
señales
Preguntas relacionadas
Número de enlaces vacíos después de dar pistas
El recorrido que aún requiere soporte de pila es el árbol de pistas posterior al pedido.
No todos los nodos pueden encontrar a su predecesor y sucesor mediante pistas.
Dado el árbol binario de pistas posteriores al pedido, encontrar el sucesor posterior al pedido aún no se puede resolver por completo.
Árbol de búsqueda binaria BST
definición
funcionar
insertar
Encontrar
Implementación recursiva
Implementación no recursiva
borrar
Los nodos hoja se eliminan directamente
x tiene solo un nodo secundario del subárbol izquierdo/derecho conectado a su nodo principal
x tiene dos subárboles a la izquierda y a la derecha para complementar el predecesor y el sucesor
estructura
naturaleza
Si se elimina un nodo y luego se inserta, el árbol ordenado antes y después puede ser diferente.
Cálculo de preguntas
ASL (longitud promedio de búsqueda)
Longitud encontrada exitosamente
No se pudo encontrar la longitud
Recorrido de secuencia creciente = recorrido en orden
Secuencia de ruta de búsqueda ilegal
Árbol binario equilibrado AVL
mecanismo de equilibrio
factor de equilibrio
Principio de operación
Insertar/eliminar
girar
Puntos de giro
Ajustar el subárbol de desequilibrio mínimo
LL, RR giran una vez, LR, RL giran dos veces (primero hacia adentro y luego hacia afuera)
La rotación fuerte a la izquierda reduce la profundidad izquierda, la contrarrotación derecha reduce la profundidad derecha.
Raíz para conectar predecesor y sucesor [Comparar conexiones basadas en valores numéricos]
Método de rotación
LL (subárbol izquierdo hijo izquierdo)
El subárbol izquierdo se rota y se equilibra bajando un nivel.
RR (subárbol derecho hijo derecho)
LR (subárbol derecho hijo izquierdo)
RL (subárbol derecho hijo izquierdo)
calcular
El número mínimo de nodos necesarios para construir un AVL con altura h
Dado un AVL con n nodos en total, encuentre su profundidad máxima
Se sabe que la altura de AVL es n y el factor de equilibrio de todos los nodos que no son hojas es 1. Encuentre el número total de nodos.
Y busca en la colección.
funcionar
Fusionar Unión
Encuentra ancestros Encuentra(S,x)
Inicializar inicio(s)
imagen
Conceptos relacionados
gráfico dirigido
Cabeza de arco (vértice)
Cola de arco (vértice)
Gráfico no dirigido
Gráfico simple, gráfico múltiple
Gráfico simple: sin bucles automáticos, sin bordes repetidos
Múltiples gráficos: bucles automáticos y aristas repetidas
grafico completo
El número de aristas en un gráfico simple alcanza el límite superior
subtrama
Los bordes y los vértices son subconjuntos y pueden formar un gráfico.
Conectividad, gráficos conectados y componentes conectados
Conectividad: hay un camino entre u y v
Gráfico conectado: dos puntos cualesquiera del gráfico están conectados
Componentes conectados: subgrafos conectados máximos en gráficos no dirigidos
Componente fuertemente conectado, fuertemente conectado
Fuertemente conectado: u y v en el gráfico dirigido son accesibles entre sí
Gráfico fuertemente conectado: dos puntos cualesquiera en el gráfico dirigido son alcanzables entre sí.
Componentes fuertemente conectados: subgrafos conectados a paredes máximas en gráficos dirigidos
Árbol de expansión, bosque de expansión
Árbol de expansión: un subgrafo mínimo conectado que contiene todos los vértices del gráfico.
Bosque de expansión: los árboles de expansión de componentes conectados en un gráfico no conectado constituyen un bosque de expansión.
Subgrafo mínimamente conectado: mantenga la conectividad del gráfico y mantenga el número de aristas lo más pequeño posible
Grado de vértice, grado interno y grado externo
Grado de vértice: el número de aristas conectadas a un vértice en un gráfico no dirigido
Bian's Quanhe.com
Neto: Imagen con autoridad
Gráfico denso, gráfico disperso
Caminos, longitudes de caminos y bucles
Ruta: Secuencia de vértices [secuencia formada por aristas compuestas por vértices y vértices adyacentes]
Bucle/Bucle: el primer y el último vértice del camino son iguales
Camino simple, bucle simple
distancia
árbol dirigido
bosque de gráficos no dirigidos
El número de árboles forestales de gráficos no dirigidos con n vértices y e aristas
estructura de almacenamiento
matriz dispersa
lista cruzada
método de lista de adyacencia
lista múltiple de adyacencia
matriz densa
matriz de adyacencia
gráfico dirigido
Gráfico no dirigido
naturaleza
atravesar
novios guangsou
búsqueda profunda dfs
solicitud
árbol de expansión mínimo
algoritmo de primi
algoritmo de Kruskal
camino más corto
Dijkstra
floyd
expresión de gráfico acíclico dirigido
clasificación topológica
red AOV
Número de secuencias ordenadas
Camino critico
Red AOE
La primera vez que ocurrió el evento.
Última hora de aparición del evento
El evento de inicio más temprano de la actividad.
La última hora de inicio del evento.
margen de tiempo
clasificar
concepto basico
proceso ordenado por palabras clave
estabilidad
Se desconocen los elementos específicos, al menos el número de comparaciones.
viaje
Durante el proceso de clasificación se procesan una vez todos los elementos cuya posición final aún no se ha determinado.
Clasificación interna
Tipos comunes
tipo de inserción
insertar directamente
Complejidad del tiempo
clasificación estable
Características
Después de cada clasificación, los primeros i bits están en orden y puede haber valores después de i bit que cambien los i bits originales.
Insertar por la mitad
Utilice una media búsqueda en la parte de búsqueda de secuencia ordenada
almacenamiento secuencial
Complejidad del tiempo
clasificación estable
clasificación de colinas
Descripción del algoritmo: seleccione el incremento d, divida la secuencia original en varias partes y luego realice la clasificación por inserción en cada parte.
Complejidad del tiempo
complejidad del espacio
Clasificación inestable [motivo de la agrupación]
tipo de intercambio
Ordenamiento de burbuja
Descripción del algoritmo [Aparece la burbuja máxima] Cada vez que se clasifica, se coloca el elemento más pequeño/más grande al final de la secuencia/la posición final al principio de la cola mediante recorrido secuencial, comparación e intercambio.
Complejidad del tiempo
complejidad del espacio
clasificación estable
Características
Los primeros i dígitos o los últimos i dígitos (según el orden o el orden inverso) son el orden ordenado final.
Ordenación rápida
Basado en la idea de divide y vencerás [dos puntos]
Complejidad del tiempo [relacionada con la profundidad de la pila recursiva]
Complejidad del espacio [profundidad de la pila]
Características
El lado izquierdo de un valor es un valor menor que él y el lado derecho es un valor mayor que él.
Cuando la secuencia está básicamente en orden o en orden inverso, la eficiencia es más baja: afectada por la partición desequilibrada
Preguntas reales
2014) Para realizar una clasificación rápida de 15 elementos, el número mínimo de veces para comparar elementos es
clasificación de selección
elección sencilla
Descripción del algoritmo: busque el elemento con la palabra clave más pequeña entre los siguientes n-i elementos en cada pasada e intercámbielo con el i-ésimo elemento.
Complejidad del tiempo
complejidad del espacio
Clasificación inestable [múltiples mínimos toman la última posición atravesada]
Características
Los primeros i dígitos o los últimos i dígitos (según el orden o el orden inverso) son el orden ordenado final.
clasificación de montón
Descripción del algoritmo Montón binario: árbol binario completo, los subárboles izquierdo y derecho son más pequeños/más grandes que el nodo raíz [montón superior pequeño/grande]
Complejidad del tiempo
complejidad del espacio
Tiempo de construcción del montón 【Suplemento de cálculo】
Características
La posición del último nodo no hoja es len/2 [el subíndice del nodo raíz es 1]
Clasificación inestable [la posición trasera puede ajustarse a la raíz durante el ajuste]
fusionar ordenar
Descripción del algoritmo: Algoritmo de fusión bidireccional: inicialmente, la longitud de cada subtabla es 1, luego las fusiona y clasifica continuamente en pares, y finalmente las fusiona y crece en una secuencia ordenada de n
Complejidad del tiempo [independiente del estado inicial de la secuencia]
complejidad del espacio
clasificación estable
Características
Cuando hay archivos que son lo suficientemente grandes como para caber en la memoria, se utiliza una clasificación de combinación de divide y vencerás.
Ordenación por base
La descripción del algoritmo se ordena una por una según el tamaño de los números en las posiciones clave.
Complejidad del tiempo
complejidad del espacio
Clasificación de palabras clave comunes
MSD endian más significativo
Primer LSD menos significativo
clasificación estable
ordenar comparación
complejidad del tiempo
en orden
Inserción directa, clasificación por burbujas
clasificación rápida
En caso de desorden [promedio]
Selección simple, inserción directa, clasificación por burbujas
Ordenar por apilado, ordenar rápidamente, fusionar
complejidad espacial
Selección simple, inserción, burbujeo, colina, clasificación por pila.
clasificación rápida
fusionar
Estabilidad del algoritmo
clasificación estable
Clasificación inestable
Impacto de la estructura de almacenamiento
almacenamiento secuencial
almacenamiento en cadena
Características del proceso algorítmico.
[Cada operación de clasificación puede obtener al menos un pedido final]
Clasificación en montón, clasificación rápida, selección simple, clasificación por burbuja
[Tiempos de comparación y secuencia inicial]
Clasificación por fusión bidireccional no relacionada, clasificación por selección simple, clasificación por base
Acerca de la clasificación rápida, la clasificación por inserción directa, la clasificación por burbujas, la clasificación por montón y la clasificación Hill
[Número de pasadas de clasificación y secuencia inicial]
Clasificación por inserción directa independiente, clasificación por inserción a la mitad, clasificación Hill, clasificación por selección simple, clasificación por fusión, clasificación por base
Acerca de la clasificación por burbujas y la clasificación rápida
clasificación externa
concepto basico
Método general método de clasificación por fusión
Tiempo total de clasificación externa = tiempo de clasificación de la memoria, tiempo de lectura y escritura de información del almacenamiento externo, tiempo de fusión interna
Número de camas fusionadas = altura del árbol =
Número total de comparaciones de fusiones ==
Número de operaciones de E/S leídas en el segmento fusionado y escritas en el segmento fusionado (en bloques)
Ilustración
La secuencia inicial es de 12 datos desordenados.
Divida los datos de la memoria en varios bloques, primero ordene los bloques para formar una cadena ordenada
Fusionar dos subbloques ordenados en un bloque más grande [fusión bidireccional]
Continuar fusionando pequeños segmentos fusionados en segmentos fusionados más grandes
Árbol perdedor y fusión equilibrado multidireccional
fusión equilibrada de k-way
Como máximo k segmentos se pueden fusionar en uno
En cada pasada, si se combinan m bloques, se obtendrán bloques en una sola pasada.
árbol ganador/árbol perdedor
árbol ganador
árbol perdedor
Utilice árboles perdedores para acelerar la clasificación
clasificación por selección de permutación
principio
Diagrama de creación de segmento inicial
Cada grupo se divide en 6 elementos y el número inicial de grupos se divide en al menos 4 grupos.
ELIGE TU PRIMER MINIMAX 29
Elige un MINIMAX 38 más grande que en el segmento inicial
Misma razón
Hasta que no se seleccione ningún MINIMAX, el segmento inicial se considera completado.
Utilización del árbol perdedor
mejor árbol de fusión
principio
El árbol de fusión óptimo con short virtual adicional
Número adicional suplementario de descansos virtuales
sintaxis C11
palabra clave typedef
estructura estructura
gramática
Sin etiqueta typedef
con etiqueta typedef
Mala sintaxis
Anidamiento de estructuras
autorreferencia
Referencia cruzada
La diferencia entre estructura en C y C.
Puntero T*t
dirección y valor
& Obtener dirección/referencia (alias)