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

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

Наиболее часто применяется второй способ.
Ниже приведены рекурсивные алгоритмы прохождения бинарных деревьев.

subroutine pretrave (tree) ‘сверху вниз
if tree <> nil then
print info(tree)
pretrave(left(tree))
pretrave(right(tree))
endif
return

subroutine intrave (tree) ‘симметричный
if tree <> nil then
intrave(left(tree))
print info(tree)
intrave(right(tree))
endif
return

Procedure pretrave (tree: tnode)
Begin
if tree <> nil then
begin
WriteLn(Tree^.Info);
Pretrave(Tree^.left);
Pretrave(Tree^.right);
End;
end;

procedure intrave (tree: tnode)
begin
if tree <> nil then
begin
intrave(Tree^.left);
writeLn(Tree^.info);
intrave(Tree^.right);
end;
end;

Поясним подробнее рекурсию алгоритма обхода дерева слева направо.
Пронумеруем строки алгоритма intrave (tree):

1if tree <> nil
2   then intrave (left(tree))
3         print info (tree)
4        intrave (right (tree))
5   endif
6return

Обозначим указатели: t ? tree;  l ? left;  r ? right
На приведенном рис. 4.11 проиллюстрирована последовательность вызова процедуры intrave (tree) по мере обхода узлов простейшего дерева, изображенного на рис. 4. 10.

5. Поиск

Поиск является одной из основных операций при обработке информации в ЭВМ. Ее назначение — по заданному аргументу найти среди массива данных те данные, которые соответствуют этому аргументу.
Набор данных (любых) будем называть таблицей или файлом. Любое данное (или элемент структуры) отличается каким-то признаком от других данных. Этот признак называется ключом. Ключ может быть уникальным, т. е. в таблице существует только одно данное с этим ключом. Такой уникальный ключ называется первичным. Вторичный ключ в одной таблице может повторяться, но по нему тоже можно организовать поиск. Ключи данных могут быть собраны в одном месте (в другой таблице) или представлять собой запись, в которой одно из полей — это ключ. Ключи, которые выделены из таблицы данных и организованы в свой файл, называются внешними ключами. Если ключ находится в записи, то он называется внутренним.
Поиском по заданному аргументу называется алгоритм, определяющий соответствие ключа с заданным аргументом. Результатом работы алгоритма поиска может быть нахождение этого данного или отсутствие его в таблице. В случае отсутствия данного возможны две операции:
1. индикация того, что данного нет
2. вставка данного в таблицу.
Пусть k — массив ключей. Для каждого k(i) существует r(i) — данное. Key — аргумент поиска. Ему соответствует информационная запись rec. В зависимости от того, какова структура данных в таблице, различают несколько видов поиска.
5.1Последовательный поиск

Применяется в том случае, если неизвестна организация данных или данные неупорядочены. Тогда производится последовательный просмотр по всей таблице начиная от младшего адреса в оперативной памяти и кончая самым старшим.
Последовательный поиск в массиве (переменная search хранит номер найденного элемента).

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

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