Структуры и алгоритмы обработки данных
Метод транспозиции
В данном методе найденный элемент переставляется на один элемент к голове списка. Если к этому элементу обращаются часто, то постепенно перемещаясь к началу списка, он скоро окажется в его голове.
Этот метод удобен тем, что он эффективен не только в списковых структурах, но и в неупорядоченных массивах, т.к. меняются местами только два рядом стоящих элемента.
Будем использовать три указателя:
p - рабочий указатель, указывает на элемент.
q - вспомогательный указатель, отстает на один шаг от p.
s - вспомогательный указатель, отстает на два шага от p.
Найденный нами третий элемент передвигается на один шаг к голове списка (т.е. становится вторым). Указатель первого элемента перемещается на третий элемент, указатель второго элемента на четвертый, таким образом третий элемент перемещается на второе место. Если к данному элементу обратиться еще раз, то он окажется в голове списка.
s=nil
q=nil
p=nil
while (p<>nil) do
if key=k(p) then search=p
if q=nil then return
else next(q)=next(p)
next(p)=q
if s=nil then table
else next(s)=p
end if
search=p
end if
end if
return
end while
search=nil return
