Almacenamiento aleatorio, pero la inserción y eliminación requieren mover una gran cantidad de datos

lista enlazada estática

lista circular enlazada

lista doblemente enlazada

lista única

La distribución de la memoria puede ser discontinua. Fácil de insertar y eliminar La búsqueda debe comenzar desde un extremo.

Primero en entrar, último en salir, la entrada y salida de elementos se realizan en el mismo extremo.

Primero en entrar, primero en salir, entrada al final de la cola, salida al principio de la cola

Almacenamiento secuencial y almacenamiento encadenado.

algoritmo BF

algoritmo KMP

precedencia de fila

Primera columna

Tríada

Supongamos que hay dos gráficos. Los vértices y aristas de un gráfico son un subconjunto de los vértices y aristas del otro gráfico.

Un gráfico no dirigido tiene n (n-1)/2 aristas y un gráfico dirigido tiene n (n-1) arcos.

Muy pocos bordes o arcos

Hay muchos bordes o arcos.

Valores significativos en los laterales. La comprensión personal se puede comparar con el derecho del árbol de Huffman.

Dos puntos conectados por una arista son puntos adyacentes entre sí. La arista está unida al vértice y la arista está asociada al vértice.

Para gráficos dirigidos, el punto es el grado de entrada y el punto es el grado de salida.

Un camino con los mismos puntos de inicio y fin.

Una matriz que representa la relación de adyacencia entre vértices.

Una estructura de almacenamiento vinculada de un gráfico, que establece una única lista vinculada para cada vértice del gráfico y coloca vértices adyacentes en la lista vinculada

Es otra estructura de almacenamiento en cadena de grafo dirigido.

Es otra estructura de almacenamiento en cadena de gráficos no dirigidos.

Acceso desde un vértice Encuentre el primer punto adyacente no visitado del vértice recién visitado y repita la ejecución. Devuelve el vértice visitado anteriormente que todavía tiene vértices adyacentes no visitados y encuentra el siguiente vértice adyacente no visitado.

Acceso desde un vértice Visite cada vértice adyacente no visitado de este vértice en secuencia A partir de estos puntos adyacentes, visite sus puntos adyacentes en secuencia.

algoritmo de primi

algoritmo de Kruskal

algoritmo de dijkstra

algoritmo de freud

En un gráfico dirigido, visite un vértice sin predecesor y genere Elimina este vértice. Repita las operaciones anteriores.

La ruta ponderada más larga desde un punto con grado 0 (punto de origen) hasta el punto de sumidero

una unidad independiente en el árbol

El número de subárboles que tiene un nodo se llama grado del nodo.

Los nodos con grado 0 se llaman hojas o nodos terminales.

El nivel máximo de nodos en el árbol se llama profundidad o altura del árbol.

El grado de un árbol es el valor máximo del grado de cada nodo del árbol.

Un árbol binario de profundidad k y que contiene 2∧k-1 nodos

Características

Árbol binario con profundidad k y n nodos Un árbol binario completo se denomina árbol binario completo si y sólo si cada nodo corresponde a un nodo numerado del 1 al n en un árbol binario completo de profundidad k.

Características

La lista enlazada binaria compuesta por esta estructura de nodos se utiliza como estructura de almacenamiento del árbol binario y se denomina lista enlazada de pistas. Los punteros que apuntan al predecesor y sucesor del nodo se denominan pistas. un árbol binario de pistas.

recorrido de preorden

recorrido en orden

recorrido posterior al pedido

Los llamados primero, medio y último se refieren al momento de acceder al nodo raíz. Para atravesar un árbol binario, se debe acceder a los subárboles izquierdo y derecho y a los nodos raíz en un orden determinado.

camino

longitud de la trayectoria

longitud del camino del árbol

bien

La estructura del árbol de Huffman.

Codificación Huffman

Cálculo del valor WPL

Una colección de elementos de datos del mismo tipo.

El valor de un elemento de datos en un elemento de datos.

Con base en un valor dado, determine un registro o elemento de datos en la tabla de búsqueda cuya clave sea igual al valor dado

Comenzando desde un extremo de la tabla, compárelos secuencialmente

Inicie la comparación desde el medio de la tabla. Si es mayor, realice una comparación a la mitad en la mitad que es mayor. Si es más pequeña, realice una comparación a la mitad en la mitad que es más pequeña que la tabla hasta que la búsqueda sea exitosa. no hay resultado.

Cree una tabla de índice y realice búsquedas secuenciales en los bloques de acuerdo con los bloques a los que apunta la tabla de índice.

Si el subárbol izquierdo no está vacío, debe ser más pequeño que su nodo raíz.

Si el subárbol derecho no está vacío, debe ser mayor que su nodo raíz.

Los subárboles izquierdo y derecho son árboles ordenados binariamente.

Sobre la base del árbol de clasificación binaria, existe una restricción adicional, es decir, el valor absoluto de la diferencia de profundidad entre los subárboles izquierdo y derecho no excede 1.

Es la operación de reordenar un conjunto de registros en orden no decreciente ni creciente de palabras clave.

Cuando las claves de clasificación son diferentes, el resultado obtenido al ordenar la secuencia desordenada de cualquier registro es único; de lo contrario, no es único.

Clasificación interna

clasificación externa

Al insertar el i-ésimo (i >= 1), se han ordenado los V[0], V[1],..., V[i-1] anteriores. En este momento, use el código de clasificación de V [I] para comparar el orden de los códigos de clasificación de V [i-1], V [i-2],..., encuentre la posición de inserción e inserte V [i] , y el elemento en la posición original se insertará en Mover hacia atrás

Utilice bajo, medio y alto para dividirlo en dos regiones [bajo, medio-1] y [medio 1, alto] Si el valor clave es menor que el valor medio de la secuencia, significa que el valor clave debe insertarse en el área izquierda [bajo, medio-1] y luego dividir el área repetidamente para [bajo, medio-1] hasta bajo>alto, y la inserción final La posición debe ser alta 1. Mueva los datos en la posición después de alto hacia atrás en su conjunto y luego asigne la clave a [mid 1]

Es esencialmente un método de inserción grupal que clasifica acortando continuamente la longitud de la tela.

Encuentre elementos pequeños o grandes uno por uno comparando e intercambiando posiciones de elementos adyacentes.

Es una mejora en la clasificación de burbujas. Seleccione el valor de división para dividirlo en dos partes. El lado izquierdo es menor que el lado derecho y el lado derecho es mayor.

Primero, busque el elemento más pequeño (grande) en la secuencia sin clasificar y guárdelo al comienzo de la secuencia ordenada. Luego, continúe buscando el elemento más pequeño (grande) de los elementos restantes sin clasificar y luego colóquelo al final de la secuencia. secuencia ordenada. Y así sucesivamente hasta que todos los elementos estén ordenados.

Compare los n elementos que se ordenarán en pares, saque los más pequeños y luego compare los n/2 más pequeños en pares, saque los más pequeños y repita los pasos anteriores hasta que se eliminen los elementos mínimos.

Construya la secuencia que se ordenará en un montón superior grande. Según las propiedades del montón superior grande, el nodo raíz del montón actual es el elemento más grande de la secuencia. Intercambie el elemento superior del montón con el último elemento y luego reconstruya los nodos restantes en un montón superior grande, y así sucesivamente. A partir de la primera vez que construimos el montón superior grande, podemos obtener el valor máximo de una secuencia cada vez. vez que lo construimos y luego lo colocamos al final de la pila superior. Finalmente se obtiene una secuencia ordenada.

método de máxima prioridad

método de menor prioridad