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

Алгоритмы

Дерево

Список

Массив

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

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

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;