Программирование на языке Турбо Паскаль )
Реферат - Компьютеры, программирование
Другие рефераты по предмету Компьютеры, программирование
арьера было бы неразумно: каждый раз барьер придётся ставить в хвост списка, а для этого нужно сначала обойти весь список, начиная с головы, затрачивая при этом много времени.
Лекция 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
else if t[h].key = empty then index:= notfound
else h:=hash2(h,key);
until index<>сontinue;
end;
Процедура выдаёт ответ о результатах поиска через параметр-переменную index. При удачном поиске там будет лежать номер найденного элемента, при неудачном константа notfound. Константа continue означает пока не найден и используется только внутри процедуры. При поиске сначала вычисляется значение первичной хэш-функции, а в index заносится значение continue Затем выполняется проверка на равенство ключей, если оно выполняется, то ячейка массива найдена, и мы записываем её номер в index, иначе, если ячейка пуста, то элемент не найден (в index записываем notfound), в третьем случае находим значение вторичной функции. Эти действия