Xreferat.com » Рефераты по информатике и программированию » Программирование на языке Турбо Паскаль

Программирование на языке Турбо Паскаль

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

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

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

p:=p^.next;

end;

end;

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

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

Лекция 19. Перемешанные таблицы

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

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

const empty = '';

nmax = 1000;

type tKey = string;

tData = .....;

tItem = record

key: tKey;

data: tData;

end;

tTable = array[0..nmax-1] of tItem;

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

Реализованная описанным способом таблица называется перемешанной (или hash-таблицей), а функция — функцией расстановки ключей (hash-функцией). Такие названия связаны с тем, что данные беспорядочно разбросаны по массиву.

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

function hash(key: tKey): integer;

var i: integer;

begin

sum:=0;

for i:=1 to length(key) do sum:=sum+ord(key[i]);

hash := sum mod nmax;

end;

Процедура добавления элемента в таблицу в предварительном варианте будет выглядеть так:

procedure AddItem(var t: tTable; item: tItem);

var h: integer;

begin

h:=hash(item.key);

t[h]:=item.key;

end;

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

Наиболее простая хэш-функция будет добавлять к номеру занятой ячейки какое-нибудь постоянное число:

const HC = 7;


function hash2(n: integer, key: tKey): integer;

begin

hash2 := (n + HC) mod nmax;

end;

Остаток от деления на nmax понадобилось вычислять по той же причине, что и в первичной хэш-функции.

Сейчас можно написать окончательный вариант процедуры добавления элемента данных в таблицу:

procedure AddItem(var t: tTable; item: tItem);

var h: integer;

begin

h:=hash(item.key);

while t[h].key<>empty do h:=hash2(h,item.key);

t[h].key:=item.key;

t[h].data:=item.data;

end;

Пусть в хэш-таблицу занесены все необходимые данные и требуется отыскать данные с некоторым ключом. Для этого будем действовать по такой схеме: вычисляем значение хэш-функции на данном ключе, если ячейка с полученным номером свободна, то элемент не найден, если занята, то сравниваем её ключ с искомым. В случае совпадения мы нашли нужный элемент, иначе — находим значение вторичной функции и смотрим на ключ в ячейке с полученным номером. Если он равен «пустому» значению, то поиск неудачен, если равен искомому ключу — то удачен, иначе — вновь находим значение вторичной хэш функции и т. д. На Паскале всё это выглядит так:

const notfound = -1;

continue = -2;

procedure Search(var t: tTable; key: tKey; var index: integer);

var h: integer;

begin

h:=hash(key);

index:=continue;

repeat

if t[h].key = key then index:=h

elseif t[h].key = empty then index:= notfound

else h:=hash2(h,key);

until index<>сontinue;

end;

Процедура выдаёт ответ о результатах поиска через параметр-переменную index. При удачном поиске там будет лежать номер найденного элемента, при неудачном — константа notfound. Константа continue означает «пока не найден» и используется только внутри процедуры. При поиске сначала вычисляется значение первичной хэш-функции, а в index заносится значение continue Затем выполняется проверка на равенство ключей, если оно выполняется, то ячейка массива найдена, и мы записываем её номер в index, иначе, если ячейка пуста, то элемент не найден (в index записываем notfound), в третьем случае находим значение вторичной функции. Эти действия продолжаются до тех пор, пока index не перестанет быть равным continue.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: