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

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

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

 

Ф. И. О.	Адрес	Телефон	Год рождения
Петров Ф. М.	Северная 99-88	29-29-29	1962
Иванов П. С.	Мира 111-222	77-88-99	1976
Козлов Н. В.	Октябрьская 135-246	45-67-89	1970
.................

 

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

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

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).

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

Массив

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

Для того чтобы хранить таблицу, нам потребуется запись из двух полей: сам массив и целочисленное поле, обозначающее текущий размер массива:

const maxsize = 2000; {максимальный размер таблицы}

type tTable = record

   a: array [1..maxsize] of tItem; { это сам массив}

   n: integer; {а это - реальное число элементов}

end;

var Table: tTable;

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

Список

Этот вариант более экономичен в плане расхода памяти, так как всегда будет занято ровно столько места, сколько нужно под данные. В отличие от массива, мы не можем легко просматривать данные произвольного элемента, для перехода от одного элемента к другому нужно долго двигаться по цепочке указателей; это является недостатком списка.

Как выглядит такая таблица на Паскале нам уже известно:

type tItemPtr = ^tItem; {указатель на элемент списка}

tItem = record { элемент списка}

  key: tKey;

  data: tData;

  next: tItemPtr;

end;

tList: tItemPtr; {задаётся указателем на первый элемент}

var Table: tList {таблица является списком}

Дерево

Как хранить и искать данные в двоичном дереве, мы уже знаем, а таблицу можно задать так:

type tItemPtr = ^tItem; {указатель на элемент}

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

  key:    tKey;

  data:   tData;

  left, right: tItemPtr;

end;

tTree = tItemPtr;

var Table: tTree;       { таблица является деревом}

Алгоритмы

Линейный поиск в массиве

Пусть таблица представлена в виде массива. Тогда первое, что приходит в голову по поводу поиска элемента — это обход всех элементов, начиная с первого, до тех пор, пока не будет найден элемент с искомым ключом, или пока массив не кончится. Такой способ называется линейным поиском в неупорядоченном массиве. Оформим его на Паскале в виде процедуры:

procedure LinearSearch(var T:tTable; k:tKey; var index:integer);

var i: integer;

Begin

i:=1; index:=0;

while (i<=T.n) and (index=0) do begin

if T.a[i].key=k then index:=i;

i:=i+1;

end;

end;

Рассмотрим подробнее части этой процедуры. Параметрами процедуры являются таблица (T), в которой нужно искать элемент, искомое значение ключа (k) и выходной параметр (index), в котором процедура должна указать номер элемента, если он найден, и 0 в противном случае. В списке параметров таблица T описана как параметр переменная, хотя процедура и не должна менять какие-либо данные из таблицы. Это нужно для того, чтобы не создавать копию таблицы в стеке при передаче параметра процедуре, поскольку таблица может иметь большой размер.

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

procedure LinearSearch2(var T:tTable; k:tKey; var index:integer);

var i: integer;

Begin

T.a[0]:=k;

index:=T.n; index:=0;

while T.a[index]<>k do index:=index-1;

end;

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

Двоичный поиск

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

procedure BinarySearch(var T:tTable; k:tKey; var index:integer);

var l,c,r: integer;

Begin

index:=0;

l:=1; r:=T.n;

while (index=0) and (l<=r) do begin

c:=(l+r) div 2;

if T.a[c].key=k then index:=c

else if T.a[c].key>k then r:=c-1

else l:=c+1;

end;

end;

Переменные l, r и c обозначают соответственно номер левого края, центра и правого края части массива, в которой мы ищем элемент с заданным ключом. Поиск прекращается либо если элемент найден (index <> 0), либо если часть массива, в которой нужно искать, была исчерпана (то есть номер левого края превысил номер правого). Внутри цикла находим номер середины части массива (c), затем сравниваем ключ этого среднего элемента с искомым ключом. Если выполнилось равенство, то элемент найден, если средний больше искомого, то устанавливаем правую границу части массива равной c-1, если больше — меняем левую границу на c+1.

Линейный поиск в списке

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

procedure SearchInList(T: tTable; k: tKey; var p: tItemPtr);

var notfound: boolean;

Begin

notfound:=true;

p:=T;

while (p<> nil) and (notfound) do begin

if p^.key=k then notfound:=false;

p:=p^.next;

end;

end;

Параметр T в этом случае не нужно делать параметром-переменной, поскольку он является только указателем на начало таблицы, а сама таблица лежит в динамической памяти. Вместо номера найденного элемента будем возвращать пользователю нашей процедуры указатель на него (если поиск был удачным) или nil, если поиск неудачен.

Сокращать число проверок в цикле с помощью барьера было бы неразумно: каждый раз барьер придётся ставить в «хвост» списка, а для этого нужно сначала обойти весь список, начиная с головы, затрачивая при этом много времени.