Структуры и алгоритмы обработки данных

       

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


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

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

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

       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;

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



Содержание раздела