Метод транспозиции при оптимизированном поиске (для переупорядочивания таблицы поиска

В данном методе найденный элемент переставляется на один элемент к голове списка. И если к этому элементу обращаются часто, то, перемещаясь к голове списка, он скоро окажется на первом месте.

p – рабочий указатель;

q – вспомогательный указатель, отстает на один шаг от p;

s – вспомогательный указатель, отстает на два шага от q.

Алгоритм метода транспозиции:

s = nil

q = nil

p = table

while (p <> nil) do

if key = k(p) then ‘ нашли, транспонируем

if q = nil then ‘ переставлять не надо

return

endif

nxt(q)= nxt(p)

nxt(p) = q

if s = nil then

table = p

else

nxt(s) = p

search = p

endif

return

endif

s =q

q = p

p = nxt(p)

endwhile

search = nil

return

Этот метод удобен при поиске не только в списках, но и в массивах (так как меняются два стоящих рядом элемента).