Понедельник, Июль 5th, 2010

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

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

Этот алгоритм применим как для списков, так и для массивов. Однако не рекомендуется применять его для массивов, так как на перестановку элементов массива затрачивается гораздо больше времени, чем на перестановку указателей.
Алгоритм переупорядочивания в начало списка:
Псевдокод:
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;

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

р — рабочий указатель
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;

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

5.5.3. Дерево оптимального поиска
Если извлекаемые элементы сформировали некоторое постоянное множество, то может быть выгодным настроить дерево бинарного поиска для большей эффективности последующего поиска.
Рассмотрим деревья бинарного поиска, приведенные на рисунках a и b.Оба дерева содержат три элемента — к1, к2, к3, где к1<к2<к3. Поиск элемента к3 требует двух сравнений для рисунка 5.6 a), и только одного — для рисунка 5.6 б).
Число сравнений ключей, которые необходимо сделать для извлечения некоторой записи, равно уровню этой записи в дереве бинарного поиска плюс 1.
Предположим, что:
p1 — вероятность того, что аргумент поиска key = к1
р2 — вероятность того, что аргумент поиска key = к2

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники