Реализация различных методов доступа к данным в таблицах по имени
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
авку и поиск элементов, даже если элементов в таблице много. Но производительность некоторых методов хеширования сильно падает, если таблица практически заполнена.
Удалить элемент из связанной таблицы также очень просто. Для этого достаточно удалить ячейку элемента из соответствующего связанного списка, в то время как в некоторых схемах хеширования удалить элемент трудно или даже невозможно.
Один из недостатков связывания в том, что если число связанных списков относительно невелико, то размер списков может стать огромным. Чтобы добавить или найти элемент, придется исследовать большое число элементов списка. Если хеш-таблица содержит 10 связанных списков и вы добавляете к таблице 10 000 элементов, средняя длина связанного списка составит 1000. Всякий раз, когда вам нужно будет найти элемент в таблице, потребуется исследовать 1000 или более ячеек.
Можно ускорить процесс поиска, отсортировав связанные списки. Это позволяет прекратить поиск, если программа находит элемент со значением больше искомого. В среднем потребуется проверить только половину списка, чтобы найти элемент или определить, что его нет в списке.
cell : PChainCell;
begin
// Определение цепи, содержащей значение.
cell := ListTops* [value mod NumChains].NextCell;
// Поиск элемента.
while (cellonil) do(се11Л.Value >= value) then break;:= се!1Л.NextCell;;(cellonil) then
if (cell.Value = value) then
begin
// Какие-либо действия с ячейкой.
,
end;;
Использование упорядоченных списков ускоряет поиск, но не устраняет саму проблему переполнения таблиц. Лучшим решением будет создание хеш-таблицы большего размера и повторное хеширование элементов в новой таблице так, чтобы связанные списки в ней имели меньший размер. Но эта операция может занять много времени, особенно в том случае, если списки сохранены на жестком диске или каком-либо другом медленном устройстве, а не в оперативной памяти.
Бинарный (двоичный) поиск
Пусть имеется N записей в виде линейного массива, упорядоченных по ключам так, что k1 < k2 <...< kN (ki =a[i].key). В дальнейшем будем вместо a[i].key использовать обозначения ki и вместо x - key.
Определить запись, имеющую ключ key, можно при помощи последовательного поиска, но если учесть специфику массива, то поиск можно существенно сократить. Для этого обратимся к середине массива и определим ключ ki. Если ki = key, то нужная запись найдена. Если ki>key, то key должен находиться в части массива, предшествующей ki,и если ki < key, то во второй части. Теперь для поиска нужного элемента достаточно рассматривать половину массива с ключами k1 ,...., ki или ki ,...., kN. Повторяя эту процедуру, после каждого неудачного сравнения key с ki будем исключать приблизительно половину непросмотренной части. Это и представляет суть двоичного (бинарного) поиска, алгоритм которого можно записать следующим образом:
Algorithm BSEARCH [Бинарный поиск.]
Шаг B0. [ Инициализация. ] First:=1; Last:=N;
{ First, Last - указатели первого и последнего ключей. }
Шаг B1. [ Основной цикл. ] While LastFirst do
Шаг B2. [Определение центрального ключа.]i:=(Fist+Last) div 2;
Шаг B3. [Проверка.]if key=ki then Stop;
Шаг B4. [Сравнение.]if key<ki then Last:=i-1 else First:=i+1;
ШагB5. [Конец. ] End do (B1)
Блок схема алгоритма бинарного поиска приведена на рисунке 2.
На рисунке 3 приведен пример определения key=42.
Crt; {Реализация алгоритма бинарного поиска.}
Constn=1000; key=100;Arr=Array[1..n] of Integer;a: Arr; key, i, n: Integer;BSEARCH(n,key: Integer; a: Arr; Var i: Integer); F, L: Integer;Label LL;F:=1; L:=n;(L>=F) doi:=(F+L) div 2; If key=a[i] then Goto LL;key<a[i] then L:=i-1 else F:=i+1;:END;{BSEARCH}ClrScr; {Начало.}i:=1 to n do a[i]:=i; {Ввод данных.}(n,key,a,i);{Сортировка.}( Число элементов=,n:5, Key=,key:4); {Вывод.}(a(i)=,a[i]:4; i=,i:4);
END.
Метод бинарного поиска можно применять для того, чтобы представить упорядоченный массив в виде двоичного дерева. Значение ключа k(8)=53 является корнем дерева. Интервалы ключей (1-7) и (9-16) помещаются в память. Затем на втором шаге в первой и второй половинах определяются средние элементы. Средние же элементы определяются в каждой четверти и т.д. Для данного массива получим следующее бинарное дерево поиска (см. рисунок 4).
Пусть N=2k-1 -число записей в массиве и двоичное дерево массива является полным, т.е. у каждой вершины есть как левый, так и правый преемники. Дерево имеет высоту k-1, а число вершин на уровне i равно 2 i (i=0,...,k-1).
Рассмотрим наихудший вариант работы алгоритма BSEARCH. Число сравнений M, необходимых для отыскания заданного ключа, max(M)=k {(k-1)- уровень вершины и k = log2 (N+1) N=2 k -1}.
Пусть все записи равновероятны и NCOMP (i) -1 уровень ключа k i