Galería de mapas mentales Estructura de datos Capítulo 1 Introducción
Capítulo 1 de "Estructura de datos": revisión de conocimientos introductorios, incluidos los conceptos básicos de estructura de datos, algoritmos y evaluación de algoritmos.
Editado a las 2022-11-23 16:05:51,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.
introducción
Conceptos básicos de estructuras de datos.
1. Conceptos básicos y terminología.
datos
El portador de información, el número que describe los atributos de las cosas objetivas.
elemento de datos
La unidad básica de datos, que consta de varios elementos de datos.
Elemento de datos: la unidad más pequeña que constituye un elemento de datos.
objeto de datos
Una colección de elementos de datos con las mismas propiedades.
tipo de datos
tipo atómico
tipo de estructura
tipo de datos abstractos
Organización de datos abstractos y operaciones relacionadas con ellos.
estructura de datos
Una colección de elementos de datos que tienen una o más relaciones específicas entre sí.
2. Tres elementos de la estructura de datos.
Estructura lógica: las relaciones lógicas entre elementos de datos.
estructura lineal
recolectar
estructura de árbol
Estructura gráfica (estructura de malla)
Estructura de almacenamiento: la representación de la estructura de datos en la computadora (también llamada imagen), también llamada estructura física.
Almacenamiento secuencial: almacene elementos lógicamente adyacentes en unidades de almacenamiento físicamente adyacentes
Ventajas: se puede lograr acceso aleatorio y ocupa menos espacio de almacenamiento
Desventajas: solo se puede utilizar un bloque adyacente de unidades de almacenamiento, lo que puede provocar fragmentación externa
Almacenamiento encadenado: representa la relación lógica entre elementos con la ayuda de punteros que indican las direcciones de almacenamiento de los elementos.
Ventajas: Sin fragmentación, uso completo de todas las unidades de almacenamiento.
Desventajas: los punteros ocupan espacio adicional y solo pueden lograr un acceso secuencial.
Almacenamiento de índice: mientras se almacena información de elementos, también se crean tablas de índice adicionales.
Ventajas: velocidad de recuperación rápida
Desventajas: la tabla de índice ocupa espacio adicional al agregar o eliminar datos y es necesario modificar la tabla de índice, lo que requiere más tiempo.
Almacenamiento hash (almacenamiento hash): calcule directamente la dirección de almacenamiento del elemento en función de la palabra clave del elemento
Ventajas: recuperar, agregar y eliminar nodos es muy rápido
Desventajas: si la función hash no es buena, pueden producirse conflictos en la unidad de almacenamiento de elementos, lo que provocará una sobrecarga de tiempo y espacio adicional.
Operaciones de datos
Definición de operaciones
Para la estructura lógica, señale la función de la operación.
Implementación de operaciones
Para la estructura de almacenamiento, señale los pasos operativos específicos de la operación.
Algoritmos y evaluación de algoritmos
concepto
Definición: Un algoritmo es una descripción de los pasos para resolver un problema específico y es una secuencia finita de instrucciones.
característica
finitud
certeza
factibilidad
ingresar
producción
Objetivo
exactitud
legibilidad
Robustez
Eficiencia y bajos requisitos de almacenamiento.
Una medida de la eficiencia del algoritmo.
complejidad del tiempo
Fórmula básica:
T(n)——La suma de las frecuencias de todas las declaraciones en el algoritmo
f (n) —— la frecuencia de las operaciones básicas en el algoritmo
O——Orden de magnitud
Definición de fórmula: si T(n) y f(n) son dos funciones definidas en el conjunto de números enteros positivos, entonces existen constantes positivas C y n0, de modo que cuando n>=n0, ambas satisfacen 0=<T(n) =<Cf(n)
Clasificación
Peor complejidad del tiempo
complejidad del tiempo promedio
mejor complejidad del tiempo
reglas aritméticas
a. regla de suma
b. regla de multiplicación
Complejidad del tiempo asintótico común
complejidad espacial
Definición: el espacio de almacenamiento consumido por el algoritmo.
fórmula:
El algoritmo funciona in situ significa que el espacio auxiliar requerido por el algoritmo es constante, es decir, O (1)