Автор работы: Пользователь скрыл имя, 30 Мая 2012 в 16:39, курсовая работа
В теоретической части курсовой работы предоставлен материал исследования на тему: «Хеширование с цепочками». С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором (таблица символов). По словам Брайана Кернигана, это «одно из величайших изобретений информатики». Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочение по алфавиту является не чем иным, как хешированием.
1.3.1 Реализация основных процедур и функций для работы с хеш-таблицами (Паскаль).
1) Структура данных для хеш-таблицы с внешними цепочками может быть описана следующим образом:
Type
Chain=^Item;
Item=record
Key:Tkey;
Info: Tinfo;
Next: chain
End;
CHTable=array[0..M-1] of Chain;
2)
Операция инициализации хеш-
Procedure TableInit (var T:CHTable);
Var i:integer;
Begin
For i:=0 to M-1 do T[i]:=nil;
End;
3) Операция поиска x в хеш-таблице Т реализована как последовательный поиск в списке с адресом T[h(x)]. Функция CHSearch возвращает указатель на элемент, содержащий ключ х, или nil, в случае неудачного поиска:
Function CHSearch(x: Tkey; var T:CHTable): chain;
Var P: chain;
Begin
P:=T[h(x)];
While (P< >nil) and (P^.key< >x) do P:=P^.next;
CHSearch:=P;
End;
4) Операция вставки ключа х основана на неудачном поиске в списке, начинающемся с адреса T[h(x)]? После чего реализуется вставка в начало списка:
Procedure CHInsert(x: Tkey; var T: CHTable);
Var P: chain; i:integer;
Begin
I:=h(x);
P:=T[i];
While (P< >nil) and (P^.key< >x) do P:=P^.next;
If P=nil then
Begin
P:=T[i];
New(T[i]);
T[i]^.key:=x;
T[i]^.next:=P;
End;
End;
5) При удалении элемента x определённое неудобство доставляет односвязность списка, поэтому при поиске х следует использовать второй указатель – на предшествующий элемент (заметим, что этого можно было бы избежать, если пожертвовать памятью и хранить цепочки в виде двухсвязных списков). Особо рассматривается случай, когда x находится в первой ячейке списка:
Procedure CHDelete (x: Tkey; var T: CHTable);
Var P,Q: chain; i: integer;
Begin
I:=h(x);
If T[i]<>nil then
Begin
If T[i]^.key=x then
Begin Q:=T[i]; T[i]:=T[i]^.next; Dispose(Q) end
Else
Begin
P:=T[
While (Q<>nil) and (Q^.key<>x) do
Begin P:=Q; Q:=Q^.next end;
If Q<>nil then
Begin P^.next:=Q^.next; Dispose(Q) end
End;
End;
End;
1.3.2 Оценка времени работы операций для хеширования с цепочками.
В худшем случае на поиск будет тратится время O(N) , когда все хеш-адреса одинаковы, все элементы таблицы попадают в один список длины N и операция поиска сводится к последовательному поиску в списке.
Среднее время поиска зависит от того, насколько равномерно хеш-функция распределяет хеш-адреса. Предположим, что хеширование равномерно, то есть каждый из элементов может попасть в любую из М позиций таблицы с равной вероятностью. Определим величину q=N/M, равную средней длине цепочек, тогда время выполнения операций оценивается в терминах коэффициента q. Справедливо следующее утверждение:
Практическая часть. Демонстрационная программа.
2.1 Описание.
Практичееская часть представляет собой демонстрационную программу, включающая хеш-таблицу, поле для ввода ключа, счетчик коллизий, необходимые управляющие элементы и пояснения. Программа реализует процедуру записи ключа в таблицу и процедуру его поиска.
2.2 Техническое описание программы.
Среда программирования-Delphi;
Требуемая операционная система: Windows xp,7,Vista;
Используемая дисковая память: 460 КБ
Требования к компьютеру: процессор(Intel Pentium 233 МГц и выше), оперативная память(64 Мбайт (рекомендуется 128 Мбайт)), монитор(SVGA или выше).
2.3 Скриншот демонстрационной программы.
procedure TForm1.btn1Click(Sender:
TObject);
var ch:integer;
begin
ch:=strtoint(Edt1.Text);
AddElem(ch,20);
end;
procedure TForm1.btn2Click(Sender: TObject);
begin
FindElem(strtoint(Edt2.Text),
end;
procedure
AddElem(key:integer;c:integer)
var position:integer;
p,cur:pElem;
begin
position:=HF(key,c);
GetMem(p,sizeof(Elem));
p^.key := key;
p^.next:=nil;
cur:=HT[position];
if cur=nil then HT[position]:=p
else
begin
while cur^.next<>nil do
begin
cur := cur^.next;
end;
cur^.next := p;
end;
if(Form1.strngrd1.Cells[2,
Form1.strngrd1.Cells[2,
else Form1.strngrd1.Cells[2,
if Form1.strngrd1.Cells[3,
Form1.strngrd1.Cells[3,
else Form1.strngrd1.Cells[3,
end;
procedure
FindElem(key:integer;c:
var position:integer;
cur:pElem;
find:boolean;
begin
find:=false;
position:=HF(key,c);
cur := HT[position];
while (not find) and (cur<>nil) do
begin
if cur^.key = key then
find:=true;
cur:=cur^.next;
end;
if not find then Form1.Lbl1.Caption:='Ничего не найдено'
else Form1.lbl1.Caption:= 'Найдено в строке '+ inttostr(position);
end;
function
HF(t:integer;cm:integer):
var A,B,C:Mnog;
begin
InitMnog(A);
InitMnog(B);
InitMnog(C);
From2(t,A);
From2(cm,B);
DivMnog(A,B,C);
HF := trunc(To2(C));
end;
Заключение
Основным недостатком хеширования по сравнению другими методами, основанными на динамическом размещении, - это фиксированный размер таблиц и невозможность настройки на реальные требования, поэтому нужно научиться достаточно хорошо заранее оценивать число классифицируемых элементов. Другой недостаток методов, основанных на хешировании, становится сразу же очевидным, как только заходит речь о том, что ключи нужно не только вставлять в таблицу и отыскивать, но и исключать из таблицы. Изъятие строки из хеш-таблицы – вещь крайне трудная, если только не используются явные списки в отдельной области переполнения.
Однако,
хеширование, которое родилось еще в середине
прошлого века, активно используется в
наши дни везде, где требуется произвести
быструю выборку данных.
Список литературы