Pascal de clasificación de hash de puntero
Tabla hash
El método de búsqueda mencionado anteriormente se basa en la comparación y la eficiencia de la búsqueda depende del número de comparaciones. De hecho, la esperanza de búsqueda ideal se puede obtener en un solo acceso. sin comparación Para que se busque el registro, se debe establecer una cierta correspondencia f entre la ubicación de almacenamiento del registro y su palabra clave. De esta manera, al buscar k, solo necesitamos encontrar la imagen f (k) del. valor dado k basado en esta correspondencia f. Esta correspondencia f se llama función hash. La tabla creada en base a esta idea se llama tabla hash (también llamada tabla hash). Las tablas hash son de fácil acceso pero propensas a colisiones durante el almacenamiento: es decir, diferentes palabras clave pueden corresponder a la misma dirección hash. La clave es cómo determinar la función hash y resolver conflictos.
1. Método de construcción de la función hash
Método de direccionamiento directo: H(k)=k
o H(k)=a*k+b ( Función lineal)
Por ejemplo: tabla de estadísticas de población
Dirección
1
2
3< / p>
...
100
Edad
1
2
3
p>...
100
Número de personas
67
3533
244
...
4
Método de análisis numérico: tome varios dígitos de la palabra clave para formar una dirección hash
Por ejemplo: la palabra clave es la siguiente: si la longitud de la tabla hash es 100, los dos números decimales del medio se pueden utilizar como dirección hash.
81346532
81372242
81387422
81301367
81322817
81338967 p>
81354157
81368537
Método de cuadrar el medio: después de elevar al cuadrado la palabra clave, tome los pocos dígitos del medio para formar la dirección hash
Método de plegado: el número de clave se divide en varias partes con el mismo número de dígitos (el número de dígitos en la última parte puede ser diferente) y luego la suma de superposición de las partes (realización) se toma como dirección hash.
Método de división con resto: toma el resto obtenido después de dividir la palabra clave por un número p no mayor que la longitud de la tabla m como dirección hash.
H(k)=k
mod
p
p<=m
Método de números aleatorios :H(k)=aleatorio(k).
2. Método de manejo de conflictos
Supongamos que la dirección establecida es 0..n-1 y la dirección hash obtenida de la palabra clave es j (0<=j<= n- Ya existe un registro en la ubicación de 1), y manejar el conflicto es encontrar otra dirección hash "vacía" para el registro de esta palabra clave. Durante el procesamiento, se puede obtener una secuencia de direcciones Hi
i=1, 2,...k
0<=Hi<=n-1), es decir, si If otra dirección hash H1 obtenida aún entra en conflicto, luego busque la siguiente dirección H2. Si todavía hay un conflicto, busque H3... ¿Cómo llegar Hola?
Método de direccionamiento abierto: Hi=(H(k)+di)
mod
m
(H(k) es Función hash; m es la longitud de la tabla hash; di es la secuencia incremental)
Cuando di=1, 2, 3,...
m-1
se llama sondeo lineal y luego hash.
Cuando di=12, -12, 22, -22, 32, -32,..., k2, -k2, se llama detección secundaria y luego hash.
Cuando di=random(m), se denomina secuencia de detección pseudoaleatoria.
Ejemplo: Las claves de la tabla hash con longitud 11 son 17, 60, 29 respectivamente, y la función hash es H(k)=k
mod
11, la palabra clave del cuarto registro es 38 y las direcciones agregadas a la tabla hash según el método anterior son 8, 4 y 3 (número aleatorio = 9).
Método de repetición: Hi=RHi(key)
i=1,2,...,k, donde RHi son funciones hash diferentes.
Método de dirección en cadena: este método es muy similar a la clasificación por base. Los valores de palabras clave de la misma dirección se vinculan en la lista vinculada correspondiente.
Establezca un método de área de bienestar público: configure otra tabla de desbordamiento Independientemente de la dirección hash obtenida, una vez que ocurre un conflicto, la tabla de desbordamiento se completará.
3. Buscar en tabla hash
Ejemplo: el siguiente conjunto de palabras clave se calcula según la función hash H(k)=k
mod
La tabla hash a[0..15] obtenida por 13 y el procesamiento de colisiones de detección lineal:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
14
01
68
27
55
19
20
p>84
79
23
11
10
Cuándo se da el valor k = 84, luego compárelo primero con a [6] y luego compárelo con a [7] y a [8]. El resultado es a [8] = 84 y la búsqueda es exitosa.
Cuando el valor dado k = 38, primero se compara con a[12] y luego con a[13]. Dado que a[13] no existe, la búsqueda no tiene éxito y el resultado. La palabra clave no existe en la tabla.
5.5
Encontrar el k-ésimo elemento pequeño
Encontrar el k-ésimo elemento pequeño significa encontrar el k-ésimo elemento pequeño entre n elementos (no ordenados). El método es el mismo que el de clasificación rápida, utilizando recursividad.
El programa es el siguiente:
program
kspv;
const
n=7;
tipo
arr=matriz[1..n]
de
entero;
var
b:arr;
i,k:entero;
función
p(s,t:entero):entero;
var
i,j,t1,x:integer;
comenzar
i:=s;j:=t;x: =b[ i];
repetir
mientras
(b[j]>=x)
y
(j>i)
hacer
j:=j-1;
si
j>i
luego
comenzar
t1:=b[i];
b[i]:=b[j];b[j ]:= t1;fin;
mientras
(b[i]<=x)
y
(i hacer i:=i+1; si i entonces comienzo t1:=b[j];b[j]:=b[i];b[i]:=t1; fin hasta i=j; b[i]:=x; p:=i; end ; función find(s,t,k:integer):integer; var p1,q :entero; comenzar si s=t entonces buscar:=b[s ] otro comenzar p1:=p(s,t); q:=p1-s+1; si k<=q entonces buscar:=buscar(s,p1,k) else buscar:=buscar(p1+1,t,k-q); fin; fin; comenzar escribir('entrada datos:'); para i:=1 para n hacer read(b[i]);readln; escribir('entrada k: ');leer(k); escribir('salida datos:'); escribir('kthsmall:=',buscar (1, n,k)); fin.