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

Переупорядочивание таблицы поиска путем перестановки найденного элемента в начало списка


Суть этого метода заключается в том, что элемент списка с ключом, равным заданному, становится первым элементом списка, а все остальные сдвигаются.

Этот алгоритм применим как для списков, так и для массивов. Однако не рекомендуется применять его для массивов, так как на перестановку элементов массива затрачивается гораздо больше времени, чем на перестановку указателей.

Алгоритм переупорядочивания в начало списка:

Псевдокод:

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) = table

    table = p

    search = p

    return

  endif

  q = p

  p = nxt(p)

endwhile

search = nil

return

Паскаль:

q:=nil;

p:=table;

while (p <> nil) do

  begin

    if key = p^.k then

      begin

if q = nil

      then 'перестановка не нужна'

        search := p;

 exit;

 end;

        q^.nxt := p^.nxt;

        p^.nxt := table;

        table := p;

        exit;

      end;

    q := p;

    p := p^.nxt;

  end;

search := nil;

exit;

 



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