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

Поиск

Пример рекурсивной программы построения снежинки

Рекурсивная программа построения снежинки

рис. 25 – построение снежинок

Как видно из рисунка, здесь опять повторяются одни и те же фрагменты. Построение выполняется так: на окружности заданного радиуса r берется 6 равноотстоящих точек (начиная от угла в 0 0, с шагом ?/3), из каждой точки к центру окружности проводятся радиусы. Затем каждая из этих точек выступает центром новой, меньшей окружности с радиусом r=2 r/5. На каждой меньшей окружности вновь берется 6 равноотстоящих точек, из которых строятся радиусы к центру, и т.д., пока радиус не станет меньше или равен 1.

program sneg;

uses graph, crt;

var

x,y,r,d,m:integer;

procedure ris(x,y,r:integer);

var

x1,y1,t:integer;

begin

if r<=1 then begin putpixel(x,y,15);exit end;

for t:=0 to 6 do

begin

x1:=x+trunc(r*cos(t*pi/3));

y1:=y+trunc(r*sin(t*pi/3));

line(x,y,x1,y1);

ris(x1,y1,r*2 div 5);

delay(500);

end;

end;

begin

d:=detect;

initgraph(d,m,'e:\bp\bgi');

x:=320;

y:=240;

r:=80;

ris(x,y,r);

readln;

end.

Поиск является одной из основных операций при обра­ботке информации в ЭВМ. Ее назначение - по заданному ар­гументу найти среди массива те данные, которые со­ответствуют этому аргументу.

Признак, по которому элемент структуры отличается от других данных называется ключом.

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

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

Ключи данных могут быть собраны в од­ном месте (в другой таблице) или представлять собой запись, в которой одно из полей - это ключ.

Внешний ключ (и) -это Ключ (и), который выделе­н из таблицы данных и организован в свой файл, называ­ются

Внутренний ключ –это ключ, который находится в записи

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

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

1. индикация того, что данного нет

2. вставка данного в таблицу.

Пусть k - массив ключей. Для каждого k(i) существует r(i) - данное. Key - аргумент поиска. Ему соответствует ин­формационная запись геc. В зависимости от того, какова структура данных в таблице, различают несколько видов по­иска.

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

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

Последовательный поиск в массиве осуществляется с помощью переменной search, котораяхранит номер найденного элемента.

Рис. 26 - Последовательный поиск в массиве

for i:=l to n

if k(i) = key then

search = i

return

end if

next i

search = 0

return

На Паскале программа будет выглядеть следующим обра­зом:

for i:=l to n do

if k[i] = key then

begin

search = i;

exit;

end;

search = 0;

exit;

Эффективность последовательного поиска в массиве можно определить как количество производимых сравнений М.

M_min = 1, M_max = n. Если данные расположены равноверо­ятно во всех ячейках массива, то М_ср ≈ (п + 1)/2.

Если элемент не найден в таблице и необходимо произвести вставку, то последние 2 оператора заменяются на n = n + 1

на Паскале

n:=n+l n:=n+l;

k(n) = key k[n]:=key;

r(n) = rec r[n]:=rec;

search = n search :=n;

return exit;

Если таблица данных задана в виде односвязного спи­ска, то производится последовательный поиск в списке (рис. 5.2).

table

Рис. – Поиск в списке