Метод транспозиции

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

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

Будем использовать три указателя:

       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