Galería de mapas mentales Mapa mental de estructura de datos
Este es un mapa mental sobre la estructura de datos. Los símbolos físicos almacenados en un medio determinado que pueden reconocerse son portadores de información. Estos símbolos pueden ser números, símbolos, etc. u otras personas,
Editado a las 2023-12-02 14:20:48,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? 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.
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.
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? 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.
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.
estructura de datos
introducción
datos
definición
Los símbolos físicos almacenados en un determinado medio que puede ser reconocido son los portadores de información. Estos símbolos pueden ser números, símbolos u otros.
constituir:
datos
elemento de datos
elemento de datos
La unidad más pequeña que compone los datos.
unidad básica de datos
estructura lógica
Relaciones entre elementos de datos
Establecer estructura
Pertenecen a la misma colección.
estructura lineal
Cara a cara
Lista lineal, montón, pila
estructura de árbol
uno a muchos
estructura grafica
muchos a muchos
estructura de almacenamiento
estructura de almacenamiento secuencial
estructura de almacenamiento en cadena
Estructura de almacenamiento de índice
Estructura de almacenamiento de hash
algoritmo
definición
Una descripción de pasos específicos para resolver un problema particular, una secuencia finita de instrucciones.
cinco propiedades básicas
finitud
Debe finalizar después de ejecutar un número limitado de pasos.
certeza
factibilidad
Cualquier paso computacional se puede dividir en pasos operativos ejecutables básicos, cada paso se puede completar en un tiempo limitado.
ingresar
Un algoritmo puede tener 0 o más entradas.
producción
Un algoritmo tiene 1 o más salidas.
Reglas generales de diseño.
exactitud
legibilidad
Robustez
Responder apropiadamente a entradas incorrectas
Alta eficiencia y bajo volumen de almacenamiento
la complejidad
estructura lineal
mesa lineal
complejidad del tiempo
Búsqueda de tabla de secuencia por valor
norte 1/2
Inserción de tabla de secuencia
En)
borrar
En)
pila
último en entrar primero en salir
definición
parte superior de la pila
Terminal de operación
parte inferior de la pila
Extremo fijo
pila de secuencia
top=-1 es una pila vacía
top=MAXSIZE-1 significa pila completa
almacenamiento en cadena apilada
Similar a la lista enlazada individualmente
cola
primero en entrar primero en salir
definición
cola de la cola
Permitir inserción
Jefe de equipo
Permitir eliminación
cola secuencial
cola circular
Deja un espacio sin usar
la frase esta llena
(trasero 1)%MAXQUEUE==frente
delantero == trasero
Llámalo corto
lista enlazada
Lista enlazada única sin nodo principal
Las operaciones que involucran el nodo principal requieren un manejo especial.
Lista enlazada individualmente con nodo principal
El puntero principal no es nulo
Lista circular individualmente enlazada
El campo de puntero del último nodo almacena la dirección del primer nodo, formando un anillo.
La operación de cancelación en la operación determina si es el puntero principal
lista doblemente enlazada
Hay predecesores y sucesores.
formación
Cálculo de la dirección de almacenamiento.
Dirección base (i 1)*n (j-1)
encontrar método
búsqueda secuencial
atravesar
Longitud media de búsqueda=n 1/2
Búsqueda de índice
Crear entrada de índice
Elementos de palabras clave
Bloquear
elemento de puntero
Longitud media de búsqueda = (n/s s)/2 1
n es la longitud de la tabla, dividida uniformemente en b bloques, cada bloque contiene s registros
Búsqueda de hash
Método de construcción de la función hash
función hash directa
Tome la palabra clave en sí o una función lineal de la palabra clave como dirección
Tamaño del conjunto de direcciones == tamaño del conjunto de palabras clave
Función hash de análisis numérico
Encuentra el centro del cuadrado.
método de plegado
pliegue desplazado
colapso fronterizo
Excepto por el resto
H=clave mod p
tomar numero primo
método de números aleatorios
Análisis del rendimiento de la búsqueda de hash
factor
Función hash
Básicamente no lo consideres
Métodos de manejo de conflictos
ley de direcciones abiertas
Sondeo lineal y luego hash
1, 2, 3,. . posponer
(1 1/1-α )/2
Segunda detección y luego hash
Retraso al cuadrado de números positivos y negativos
ln(1-α)/α
Sondeo pseudoaleatorio y luego hash
secuencia pseudoaleatoria
ln(1-α)/α
refrito
ln(1-α)/α
método de dirección de cadena
Los registros en conflicto se almacenan en la misma lista enlazada lineal
1 α/2
área de desbordamiento público
Sea otro vector la tabla de desbordamiento.
Factor de relleno de la tabla hash
α=número de registros completados en la tabla/longitud de la tabla hash
La longitud de búsqueda promedio de una tabla hash es una función de α, no una función de n
Requisito previo: los datos se cargan de manera uniforme
clasificar
clasificación estable
La posición relativa de los datos de las palabras clave permanece sin cambios antes y después de la clasificación.
insertar directamente
Dividido en dos partes, el lado izquierdo está ordenado y el lado derecho está desordenado. El primer elemento del lado derecho ingresa a la posición apropiada en el lado izquierdo.
O (cuadrado)
Estabilizar
clasificación de colinas
Según un intervalo fijo, d se divide en el mismo grupo y se utiliza inserción o clasificación binaria dentro del mismo grupo.
Completado por primera vez, reduzca el intervalo para agrupar y luego ordene
hasta que el intervalo sea 1
inestable
Ordenamiento de burbuja
Compare n-i 1 elementos en secuencia de izquierda a derecha
Estabilizar
cuadrado/2
elección sencilla
Tome el valor máximo de la secuencia desordenada y agréguelo al final de la secuencia ordenada
cuadrado
Estabilizar
Ordenación por base
Clasificación de varias palabras clave
Orden de palabras clave múltiples
alta prioridad
pequeño endian
Ordenación rápida
Divida la secuencia en dos partes (requerido para garantizar la relación de tamaño relativo)
Recurrir a dos subsecuencias para una clasificación rápida
No es necesario fusionar, porque la matriz está completamente ordenada en este momento.
nlogn
Pero cuando la secuencia en sí está ordenada, degenera en cuadrado.
fusionar ordenar
Divida la secuencia que se va a ordenar en varias subsecuencias, y cada subsecuencia es una secuencia ordenada. Luego combine las subsecuencias ordenadas en la secuencia ordenada general
Un árbol es un conjunto finito de n (n>=0) nodos. Cuando n = 0, se denomina árbol vacío. En cualquier árbol que no esté vacío, hay un solo nodo específico llamado raíz. Cuando n>1, los nodos restantes se pueden dividir en m (m>0) conjuntos finitos disjuntos, cada uno de los cuales es en sí mismo un árbol y se denomina subárbol de la raíz (SubTree).
Los árboles tienen las siguientes propiedades:
1. Los subárboles están separados.
2. Excepto el nodo raíz, cada nodo tiene solo un nodo principal.
3. Un árbol con N nodos tiene N-1 aristas.
El grado de un árbol se refiere al grado máximo entre todos los nodos del árbol, y el nodo hoja se refiere al nodo con grado 0. La profundidad de un árbol se refiere al nivel más grande entre todos los nodos del árbol. Hay como máximo 2^(i-1) nodos (i≥1) en el i-ésimo nivel del árbol binario, y el árbol binario con profundidad k tiene como máximo 2^k-1 nodos (k≥1).
Recursión y divide y conquistarás
recursividad
definición
Llámese a sí mismo directa o indirectamente
escenas a utilizar
La definición es recursiva.
Factorial de n, secuencia de Fibonacci
Las estructuras de datos son recursivas.
lista enlazada
divide y conquistaras
divide y conquistaras
escenas a utilizar
Pequeña escala, fácil de resolver
El problema se puede descomponer en subproblemas del mismo tipo, con subestructura óptima.
La solución al problema original se puede obtener fusionando subproblemas.
los subproblemas son independientes
Complejidad del tiempo del algoritmo
método iterativo
Expandir directamente
método de árbol recursivo
método principal
Árbol
Árbol binario
concepto
Gastar
El número de subárboles propiedad del nodo.
hoja
nodo con grado 0
niño
La raíz del subárbol de nodos.
padres
El nodo superior del nodo hijo.
antepasado
Todos los nodos en las ramas desde el nodo raíz hasta este nodo
Nivel de nodo
A partir del nodo raíz, la raíz es el primer nivel.
grado de árbol binario
Grado máximo de nodo
Profundidad del árbol binario
El número máximo de capas de nodos.
especial
árbol binario completo
Todos los nodos de rama tienen subárbol izquierdo y subárbol derecho.
Todas las hojas y todos los nodos de las hojas están en la misma capa.
árbol binario completo
Un árbol binario en el que todos los niveles, excepto el último, están completamente llenos. Los nodos de la última capa se concentran continuamente a la izquierda.
Un árbol binario completo debe ser un árbol binario completo, y un árbol binario completo puede no ser un árbol binario completo.
naturaleza
1. En un árbol binario no vacío, el número total de nodos en el i-ésimo nivel no excede i>=1.
2. Un árbol binario con profundidad h tiene como máximo 2^h - 1 nodos (h>=1) y al menos h nodos.
3. Para cualquier árbol binario, si el número de nodos de hoja es N0 y el número total de nodos con grado 2 es N2, entonces N0=N2 1.
4. La profundidad de un árbol binario completo con n nodos es logn 1
atravesar
El recorrido del árbol binario se refiere a visitar cada nodo del árbol binario de acuerdo con ciertas reglas, de modo que cada nodo se visite y solo se visite una vez. Hay tres formas principales de atravesar un árbol binario: recorrido de preorden, recorrido de orden y recorrido de postorden.
1. Recorrido de pedidos anticipados:
* Acceder al nodo raíz
* Recorrido de preorden del subárbol izquierdo
* Preorder atraviesa el subárbol derecho
2. Recorrido en orden:
* Recorrido en orden del subárbol izquierdo
* Acceder al nodo raíz
* En orden recorre el subárbol derecho
3. Recorrido posterior al pedido:
* Recorrido posterior al pedido del subárbol izquierdo
* Recorrido posterior al pedido del subárbol derecho
* Acceder al nodo raíz
Recorrer la aplicación
Construya un árbol binario a partir de secuencias transversales en orden y en orden previo
El pedido anticipado y posterior no pueden construir un árbol binario
Encuentra la profundidad de un árbol binario
El siguiente es un ejemplo de pseudocódigo que utiliza la recursividad para encontrar la profundidad de un árbol binario:
```
función árbolProfundidad(raíz):
si la raíz es nula:
regresar 0
demás:
profundidadizquierda = profundidaddelárbol(raíz.izquierda)
profundidadderecha = profundidad del árbol(raíz.derecha)
devolver max(profundidad izquierda, profundidad derecha) 1
```
En este pseudocódigo, "root" representa el nodo raíz del árbol binario. Si el nodo raíz está vacío, la profundidad devuelta es 0; de lo contrario, la profundidad del subárbol izquierdo y del subárbol derecho se calcula de forma recursiva, el mayor de los dos más 1 se toma como la profundidad del subárbol actual y la profundidad máxima. se devuelve como resultado.
árbol de clasificación binaria
insertar
árbol binario equilibrado
La diferencia de profundidad entre los subárboles izquierdo y derecho de cada nodo no supera 1
Convertir un árbol binario ordenado en un árbol binario equilibrado
RR de rotación única izquierda
Insertar un nodo en el subárbol derecho del hijo derecho del nodo
Rotación única derecha LL
Insertar un nodo en el subárbol izquierdo del hijo izquierdo del nodo
Gire LR en ambas direcciones, primero hacia la izquierda y luego hacia la derecha.
Insertar un nodo en el subárbol derecho del hijo izquierdo del nodo
Gire RL en ambas direcciones, primero a la derecha y luego a la izquierda.
Insertar un nodo en el subárbol izquierdo del hijo derecho del nodo
Árbol binario óptimo (árbol de Huffman)
Árbol binario con la longitud de ruta ponderada más corta
Construcción del árbol Huffman
Seleccione la combinación más pequeña de pesos del nodo raíz para generar una nueva raíz.
Codificación Huffman
Izquierda 0 Derecha 1
conversión de árbol a árbol binario
Añadir línea
Los nodos hermanos están conectados por líneas.
Ir en línea
Mantenga la conexión entre los padres y el niño más a la izquierda y elimine los demás.
montón
1. Montón máximo: un montón en el que cada nodo es mayor o igual que sus nodos secundarios se denomina montón máximo.
2. Montón mínimo: un montón en el que cada nodo es menor o igual que sus nodos secundarios se denomina montón mínimo.
inserción de montón
imagen
grafico completo
Para un gráfico dirigido con n vértices
Número de aristas n(n-1)
Gráfico completo dirigido
Número de aristas n(n-1)/2
gráfico completo no dirigido
concepto basico
Gastar
grado
grado
Número de lados == suma de grados/2
camino
camino sencillo
Pase cualquier vértice no más de una vez
La longitud de un camino es el número de aristas que contiene.
anillo (bucle)
gráfico conectado
Gráfico fuertemente conectado
Hay un camino entre dos vértices cualesquiera en un gráfico dirigido
Componentes fuertemente conectados
estructura de almacenamiento secuencial
matriz de adyacencia
matriz de correlación
estructura de almacenamiento en cadena
lista de adyacencia
lista de adyacencia inversa
lista cruzada
tialvex
cabezavex
enlace
tintineo
lista múltiple de adyacencia
Gráfico no dirigido
Ivértice
enlace
Jvertex
jlink
atravesar
profundidad primero
amplitud primero
árbol de expansión
Características
Un gráfico completo con n vértices tiene n (n-2) árboles de expansión diferentes.
árbol de expansión mínimo
algoritmo de primi
Elige un lado
Elija el borde nuevo más pequeño para los componentes conectados conocidos
algoritmo de Kruskal
Seleccionar bordes según el peso de los bordes
Si cierto borde forma un bucle, deséchelo
algoritmo codicioso
camino más corto ponderado
algoritmo de dijkstra
Dividido en dos conjuntos de puntos.
El camino más corto ha sido encontrado.
Indeterminado
clasificación topológica
No debe haber ningún bucle
Camino critico
La hora de inicio más temprana del punto en la ruta == la hora de inicio más tardía
programación dinámica