La búsqueda se divide en búsqueda estática y búsqueda dinámica. Una búsqueda estática simplemente encuentra y devuelve la ubicación de búsqueda. La búsqueda dinámica, por otro lado, es diferente. Si la búsqueda tiene éxito, se devolverá la posición; si la búsqueda no tiene éxito, se devolverá la posición donde se insertó el nuevo registro. En otras palabras, una búsqueda estática no cambia la tabla de búsqueda, mientras que una búsqueda dinámica tiene una operación de inserción, que cambia la tabla de búsqueda.
Diferentes búsquedas utilizan diferentes estructuras de almacenamiento. La búsqueda estática utiliza tablas secuenciales, mientras que la búsqueda dinámica utiliza árboles de clasificación binarios, árboles binarios equilibrados, B- y B debido a cambios frecuentes.
La búsqueda estática incluye búsqueda secuencial, semibúsqueda y búsqueda de bloques (búsqueda secuencial de índice). ) ).
La búsqueda secuencial es el método de búsqueda más sencillo.
Pensamiento algorítmico
Establezca el valor dado en k, y en la tabla (r1r2...Rn), comenzando desde el último elemento rn, busque el registro con clave = k , si la clave de un registro Ri (l≤i≤n) es k, la búsqueda es exitosa y se devuelve el número de secuencia del registro I; de lo contrario, la búsqueda falla y se devuelve 0;
Descripción del algoritmo
Intsqsearch (SQLIST R, tipo de clave K)//Algoritmo para la tabla de búsqueda secuencial R//
{ int I;
r.datos[0]. key = k; //k se almacena en la publicación de monitoreo //
i = r.len//Obtener la longitud de la tabla //
while(r.data[i] .Clave! =k)
I-;//Búsqueda secuencial//
Retorno (1);
}
El El algoritmo utiliza un pequeño consejo: primero, K se almacena en el centinela. Si hay r.data[i]. key=k Para una i (≠0), la búsqueda es exitosa y se devuelve I; si reduzco de n a 1, no hay ningún registro de la clave K. Si reduzco de 1 a 0, debe haber r.data. [0]. key=k significa que la búsqueda falla y se devuelve i=0.
La duración promedio de una búsqueda exitosa es ASL=. Cuando la búsqueda falla, el número de búsquedas es igual a n L.
Algoritmo y análisis de semibúsqueda
Cuando las claves registradas se ordenan según la relación ≤ o ≥, ya sea creciente o decreciente, solo es necesario ordenarlas y almacenarlas en orden.
Descripción del algoritmo
Int Binsearch (SQLIST R, tipo de clave K)//Algoritmo de lista ordenada de semibúsqueda R//
{ int low, high , medio;
Bajo = 1; alto = r.len//Valores iniciales de los límites superior e inferior//
mientras(bajo lt;=alto) //Cuando el espacio de tabla existe //
{ mid=(low high)/2 //Encuentra el mid actual//
if (k==r.data[mid]) . key)
Return (mid); //Buscar exitosamente, mid//
If (k
Alto = mid 1; //Ajustar el límite superior , hacia Mirar a la izquierda //
Otros
Low = mid 1; //Ajustar el límite inferior, mirar a la derecha//
}
return (0); // Bajo gt, alto, no encontrado //
}
Árbol de decisión: un árbol binario con n nodos utilizado para describir el proceso de búsqueda binaria. La profundidad de es la misma que la de un árbol binario completo con n nodos. Sin embargo, un árbol de decisión no es necesariamente un árbol binario completo cuyos niveles de nodos hoja difieren en no más de 1. Por lo tanto, cuando la búsqueda tiene éxito, el La clave es comparar con el valor dado. El número máximo de palabras es
ASL=
Algoritmo y análisis de búsqueda de bloques
Búsqueda de bloques, también llamada secuencia de índice. La búsqueda es un tipo de método de búsqueda secuencial. Mejoras destinadas a mejorar la eficiencia de la búsqueda.
1.
Supongamos que la longitud de la tabla de registros es n, divida los n registros de la tabla en b = bloques, cada bloque tiene s registros (el número de registros en la tabla El último bloque puede ser menor que s), es decir:
Y la tabla está particionada secuencialmente, es decir, las claves de todos los registros en el bloque i (1 ≤ i ≤ b-1) son más pequeñas que las claves de los registros en el bloque i 1, pero los registros en un bloque pueden estar desordenados.
Indexación
Cada bloque corresponde a una entrada de índice:
KeymaxLink
donde Keymax es la clave más grande registrada en el bloque;Enlace es el número de secuencia (o puntero) del primer registro del bloque.
3. El algoritmo se divide en dos pasos:
(1) Determinar el bloque donde se encuentra el registro a encontrar a través de la tabla de índice (Se puede buscar por la mitad o por la mitad; en secuencia, porque la tabla de índice es secuencial)
(2) Buscar secuencialmente en el bloque. (Solo puede buscar en orden y los bloques no están ordenados).
Si tiene preguntas sobre el examen de ingreso de posgrado, no sabe cómo resumir el contenido del centro de examen de ingreso de posgrado o no Si no conoce las políticas locales para el registro de exámenes de ingreso de posgrado, haga clic en la parte inferior para consultar el sitio web oficial y obtenga materiales de revisión de forma gratuita: /xl/