Метод транспозиции
В данном методе найденный элемент переставляется на один элемент к голове списка. Если к этому элементу обращаются часто, то постепенно перемещаясь к началу списка, он скоро окажется в его голове.
Этот метод удобен тем, что он эффективен не только в списковых структурах, но и в неупорядоченных массивах, т.к. меняются местами только два рядом стоящих элемента.
Будем использовать три указателя:
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
В данном методе найденный элемент переставляется на один элемент к голове списка. И если к этому элементу обращаются часто, то, перемещаясь к голове списка, он скоро окажется на первом месте.
р - рабочий указатель
q - вспомогательный указатель, отстает на один шаг от р
s - вспомогательный указатель, отстает на два шага от q
Алгоритм метода транспозиции:
| Псевдокод:
s=nil q=nil p=table while (p <> nil) do if key = k(p) then ‘ нашли, транспонируем if q = nil then ‘ переставлять не надо search=p return endif nxt(q)=nxt(p) nxt(p)=q if s = nil then table = p else nxt(s)=p endif search=p return endif endwhile search=nil return | Паскаль:
s:=nil; q:=nil; p:=table; while (p <> nil) do begin if key = p^.k then ‘ нашли, транспонируем begin if q = nil then begin ‘переставлять не на- до search:=p; exit; end; q^.nxt:=p^.nxt; p^.nxt:=q; if s = nil then table := p; else begin s^.nxt := p; end; search:=p; exit; end; end; search:=nil; exit; |
Этот метод удобен при поиске не только в списках, но и в массивах (так как меняются только два стоящих рядом элемента).
