Определения и описания структур данных

Лекция 18. Таблицы и простейшие алгоритмы поиска.

Begin

End

Begin

End

Begin

Begin

Begin

if x=0 then factorial:=1

else factorial:=x*factorial(x-1);

end;

Подобным образом можно применить рекурсию для вычисления n-го числа Фибоначчи, хотя этот способ требует много лишних действий:

function fib(n: integer): integer;

if n<=1 then fib:=1 else fib:=fib(n-1)+fib(n-2);

end;

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

Возвращаясь к деревьям, заметим, что добавление элемента является рекурсивной процедурой:

procedure InsertNode(t: tTree; key: tKey; data: tData);

if t=nil then begin

new(t);

t^.key:=key;

t^.data:=data;

else if key<t^.key then InsertNode(t^.left,key,data)

else InsertNode(t^.right,key,data);

end;

После того как дерево построено, можно выполнять поиск (также рекурсивный):

function Search(t: tree; key: tKey; var data: tData): boolean;

{возвращает значение найден / не найден}

if t=nil then Search:=false

else if key = t^.key then begin

data:=t^.data;

Search:=true;

else if key<t^.key then Search:=Search(t^.left,key,data)

else Search:=Search(t^.right,key,data);

end;

Легко заметить, что элементы данных, «уложенные» в двоичное дерево можно выводить в отсортированном порядке:

procedure Traversal(t: tTree); {обход дерева}

if t<>nil then begin

Traversal(t^.left);

writeln('Key:',t^.key,' Data:',t^.data);

Traversal(t^.right);

end;

end;

Таблицей будем называть структуру данных, пригодную для хранения набора данных, имеющих одинаковые типы. Простейшим примером такой структуры может служить массив, поскольку тип всех его элементов один и тот же. Чаще всего элемент таблицы состоит из нескольких частей, одна из которых имеет наибольшее значение (называется ключом), а остальные содержат информацию, связанную с этим ключом, или собственно данные. Если всё это изобразить графически, то получится то, что называется таблицей в обычном смысле:

Здесь ключом является фамилия, а все остальные элементы — полезная информация о человеке с такой фамилией. В случае, когда наша таблица становится довольно большой, найти данные о нужном нам человеке становится довольно сложно. Алгоритмы, предназначенные для поиска в таблице данных с указанным ключом, называются алгоритмами поиска. Поиск может быть удачным (если элемент с искомым ключом имеется в массиве) и неудачным (в противном случае).

При использовании языка Паскаль для работы с табличными данными довольно удобно использовать записи в качестве элементов данных. В нашем примере таблица будет состоять из элементов следующего типа:

type tItem {элемент} = record

surname: string[30]; {фамилия, ключевое поле}

address: string; {адрес}

phone: longint; {телефон}

birth: word; {год рождения}

end;

При рассмотрении алгоритмов поиска мы будем пользоваться более общей формой для записи типа элемента:

type tItem = record

key: tKey; {ключ}

data: tData; {данные}

end;

Типы tKey и tData зависят от конкретной задачи, которую нужно решать. В нашем примере tKey — строка до 30 символов длиной, а tData можно сделать записью из трёх полей (address, phone и birth).

Рассмотрим теперь некоторые способы реализации всей таблицы: