Preste atención al juicio final de si las dos mesas están vacías o no.

complejidad del tiempo:

complejidad del tiempo:

complejidad del tiempo:

Intercambie continuamente los elementos frontal y final de una lista lineal

Presta atención al orden del código.

Presta atención al orden del código.

Constantemente eliminando e insertando cabezas.

La pila es una lista lineal especial (primero en entrar, último en salir, último en entrar, primero en salir)

No se puede sacar una pila vacía y no se puede ingresar a una pila llena.

La pila se implementa con una tabla lineal. El puntero superior (en realidad un número) de la pila es -1, que significa una pila vacía, y top=MAX-1, que significa una pila llena.

Cuando la pila está llena, se convierte en un desbordamiento; cuando la pila está vacía, se convierte en un desbordamiento.

La cola solo se puede eliminar al principio de la cola (frente) y solo se puede insertar al final de la cola (posterior).

Frente inicial=trasero=-1

Falso desbordamiento de cola

Juicio de colas llenas y vacías: delantero = trasero

Estructura de almacenamiento de la cadena de colas

matriz triangular superior e inferior

matriz simétrica

matriz tridiagonal

almacenamiento de mesa triple

almacenamiento en cadena

Al utilizar una cola, cada vez que se visita un nodo, sus hijos izquierdo y derecho se ponen en cola.

Regulación: si hay un subárbol izquierdo, entonces lchild apunta a su subárbol izquierdo; de lo contrario, apunta a su predecesor. Si hay un subárbol derecho, entonces rchild apunta a su subárbol derecho; de lo contrario, apunta a su sucesor.

Un árbol de clasificación binaria es un árbol vacío o tiene las siguientes propiedades: si su subárbol izquierdo no está vacío, entonces todos los valores de los nodos en el subárbol izquierdo son menores que el valor del nodo raíz. Entonces el subárbol derecho Los valores de todos los nodos en el subárbol son mayores que el valor del nodo raíz. Los subárboles izquierdo y derecho son árboles binarios ordenados.

Encontrar

estructura

borrar

Buscar análisis de rendimiento

Un árbol binario equilibrado es, ante todo, un árbol binario ordenado. Sus subárboles izquierdo y derecho son árboles binarios equilibrados y la diferencia de profundidad entre los subárboles izquierdo y derecho no supera 1.

Los árboles binarios equilibrados se construyen utilizando técnicas de rotación equilibrada.

El árbol con la longitud de camino ponderada más corta.

Algoritmo codicioso para construir el árbol de Huffman

Cuatro pasos para transmitir mensajes

Un árbol apilado es un árbol binario completo. El valor del nodo padre de un montón superior grande es mayor que su nodo hijo, y el valor del nodo padre de un montón superior pequeño es menor que su nodo hijo.

peinando la pila

clasificación de montón

Problema TopK de elementos masivos.

Gráfico completo dirigido (un gráfico dirigido con n (n-1) aristas)

Los enlaces se llaman arcos.

Gráfico completo no dirigido (el número de aristas es la mitad que el del gráfico completo dirigido)

los enlaces se convierten en bordes

componentes conectados

Un gráfico cuyo conjunto de vértices es un subconjunto del gráfico principal y cuyo conjunto de aristas también es un subconjunto del gráfico principal se convierte en un subgrafo del gráfico principal.

Para un gráfico con n vértices, su árbol de expansión es un subgrafo conectado con n vértices y n-1 aristas.

Si hay una arista que conecta dos vértices en un gráfico no dirigido, entonces los dos vértices son adyacentes entre sí.

Si hay un arco en el gráfico dirigido, el receptor está adyacente al remitente

Es fácil encontrar el grado de salida, pero es difícil encontrar el grado de entrada.

Es fácil encontrar el grado de entrada de la lista de adyacencia inversa, pero es difícil encontrar el grado.

lista cruzada

algoritmo de primi

algoritmo de Kruskal

Eliminar continuamente vértices con grado 0

La clasificación topológica no puede continuar, lo que indica que el gráfico contiene ciclos.

Método de etiquetado, la suma máxima en la dirección hacia adelante, la diferencia mínima en la dirección inversa, el nodo con direcciones iguales hacia adelante y hacia atrás es el nodo clave

Algoritmo de la unidad Dijikstra

Algoritmo Floyd de todas las fuentes

Comparación promedio requerida al verificar aciertos

Si la verificación falla, es necesario compararla n veces.

Cuando la búsqueda falla, los valores altos y bajos se entrelazan.

Se registra el número máximo de comprobaciones exitosas y el número mínimo es 1.

Si la verificación falla, es necesario comparar los tiempos de registro.

El proceso de búsqueda se divide en dos partes: búsqueda secuencial entre bloques y búsqueda secuencial dentro de bloques.

Suponiendo que n es la longitud de la tabla y que cada bloque contiene s datos, la longitud de búsqueda promedio es

método de función hash directa

analítica digital

Método cuadrado-medio

método de plegado

método dividir y dejar resto

método de números aleatorios

ley de direcciones abiertas

refrito

método de dirección de cadena

método de desbordamiento del área pública

El ASL de una tabla hash es una función del factor de relleno en lugar de una función de n

Media búsqueda en secuencia ordenada

La complejidad del tiempo está entre

Seleccione el más pequeño de los datos desordenados y agréguelo a la secuencia ordenada cada vez

Utilice un montón superior grande, elimine continuamente los elementos superiores y fíltrelos

División rápida de una sola vez: busque un registro como pivote, mueva todo lo que sea más pequeño al frente y mueva todo lo que sea más grande hacia atrás

Quicksort es un programa recursivo

Mejora de la clasificación rápida, seleccione el del medio entre el primer elemento, el último elemento y el elemento del medio como pivote para evitar el deterioro del rendimiento.

La complejidad del espacio se refleja principalmente en la recursividad.

Clasificación en montón, clasificación rápida, clasificación Hill, clasificación por selección simple

Clasificación por burbujas, clasificación por inserción directa, clasificación por media inserción, clasificación por combinación bidireccional