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

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

for i:=1 to n
if k(i) = key then
search = i
return
endif
next i
search = 0
return

На Паскале программа будет выглядеть следующим образом:
for i:=1 to n do
if k[i] = key then
begin
search = i;
exit;
end;
search = 0;
exit;
Эффективность последовательного поиска в массиве можно определить как количество производимых сравнений М. Мmin = 1, Mmax = n. Если данные расположены равновероятно во всех ячейках массива, то Мср » (n + 1)/2.
Если элемент не найден в таблице и необходимо произвести вставку, то последние 2 оператора заменяются на
n = n + 1                                                  на Паскале
k(n) = key                                                n:=n+1;
r(n) = rec                                                 k[n]:=key;
search = n                                                r[n]:=rec;
return                                                       search:=n;
exit;

Если таблица данных задана в виде односвязного списка, то производится последовательный поиск в списке (рис. 5.2).

Варианты алгоритмов:
На псевдокоде:
q=nil
p=table
while (p <> nil) do
if k(p) = key then
search = p
return
endif
q = p
p = nxt(p)
endwhile
s = getnode
k(s) = key
r(s) = rec
nxt(s) = nil
if q = nil then
table = s
else nxt(q) = s
endif
search = s
return
На Паскале:
q:=nil;
p:=table;
while (p <> nil) do
begin
if p^.k = key then
begin
search = p;
exit;
end;
q := p;
p := p^.nxt;
end;
New(s);
s^.k:=key;
s^.r:=rec;
s.^nxt:= nil;
if q = nil then table = s
else q.^nxt = s;
search:= s;
exit

Достоинством списковой структуры является ускоренный алгоритм удаления или вставки элемента в список, причем время вставки или удаления не зависит от количества элементов, а в массиве каждая вставка или удаление требуют передвижения примерно половины элементов. Эффективность поиска в списке примерно такая же, как и в массиве.
Эффективность последовательного поиска можно увеличить.
Пусть имеется возможность накапливать запросы за день, а ночью их обрабатывать. Когда запросы собраны, происходит их сортировка.

5.2.Индексно-последовательный поиск

При таком поиске организуется две таблицы: таблица данных со своими ключами (упорядоченная по возрастанию) и таблица индексов, которая тоже состоит из ключей данных, но эти ключи взяты из основной таблицы через определенный интервал (рис. 5.3).
Сначала производится последовательный поиск в таблице индексов по заданному аргументу поиска. Как только мы проходим ключ, который оказался меньше заданного, то этим мы устанавливаем нижнюю границу поиска в основной таблице — low, а затем — верхнюю — hi , на которой ( kind > key ).
Например, key = 101.
Поиск идет не по всей таблице, а от low  до hi.

Примеры программ:

Псевдокод:
i = 1
while (i <= m) and (kind(i) <= key) do
i=i+1
endwhile
if i = 1 then low = 1
else low = pind(i-1)
endif
if i = m+1 then hi = n
else hi = pind(i)-1
endif
for j=low to hi

Страницы: 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

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