Программирование на языке Турбо Паскаль )
Реферат - Компьютеры, программирование
Другие рефераты по предмету Компьютеры, программирование
p>
Этот вариант более экономичен в плане расхода памяти, так как всегда будет занято ровно столько места, сколько нужно под данные. В отличие от массива, мы не можем легко просматривать данные произвольного элемента, для перехода от одного элемента к другому нужно долго двигаться по цепочке указателей; это является недостатком списка.
Как выглядит такая таблица на Паскале нам уже известно:
type tItemPtr = ^tItem; {указатель на элемент списка}
tItem = record {элемент списка}
key: tKey;
data: tData;
next: tItemPtr;
end;
tList: tItemPtr; {задаётся указателем на первый элемент}
var Table: tList {таблица является списком}
3. Дерево
Как хранить и искать данные в двоичном дереве, мы уже знаем, а таблицу можно задать так:
type tItemPtr = ^tItem; {указатель на элемент}
tItem = record {элемент}
key: tKey;
data: tData;
left, right: tItemPtr;
end;
tTree = tItemPtr;
var Table: tTree; {таблица является деревом}
2. Алгоритмы
1. Линейный поиск в массиве
Пусть таблица представлена в виде массива. Тогда первое, что приходит в голову по поводу поиска элемента это обход всех элементов, начиная с первого, до тех пор, пока не будет найден элемент с искомым ключом, или пока массив не кончится. Такой способ называется линейным поиском в неупорядоченном массиве. Оформим его на Паскале в виде процедуры:
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;
В таком варианте становится значительно меньше сравнений, следовательно, алгоритм работает быстрее предыдущего.
2. Двоичный поиск
Следующий алгоритм также применяется для таблицы, представленной в виде массива, кроме того, массив должен быть отсортированным по значениям ключа (для определённости по возрастанию). Тогда при поиске можно использовать следующие соображения: возьмём элемент, находящийся в середине массива, если его ключ равен искомому ключу, то мы нашли нужный элемент, если меньше продолжаем поиск в первой половине массива, если меньше то во второй. Под продолжением понимаем аналогичный процесс: вновь берём средний элемент из выбранной половины массива, сравниваем его ключ с искомым ключом, и т. д. Этот цикл закончится, когда часть массива, в которой производится поиск, не будет содержать ни одного элемента. Так как этот алгоритм многократно разбивает массив на две части, то он называется алгоритмом двоичного поиска. Ниже приведена соответствующая процедура на Паскале.
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.
3. Линейный поиск в списке
Пусть теперь данные таблицы содержатся в списке. В этом случае можно использовать для поиска алгоритм, очень похожий на алгоритм линейного поиска в массиве. Отличие лишь в том, что изменение номера текущего элемента заменяется переходом к указателю на следующий элемент списка:
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, если поиск неудачен.
Сокращать число проверок в цикле с помощью б