Пусть каждая ячейка массива является указателем на связный список (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии приводят к тому, что появляются цепочки длиной более одного элемента.
| Задание
| Краткие теоретические сведения
|
| 1. Пункты 1, 2, 3 содержат программный код проекта, в котором реализована хэш-таблица с цепочками.
В правой части записан в левом столбце заголовочный файл Hash_ Twin_Chain.h, а в правом - заголовочный файл Lists.h.
Написать комментарии к программному коду.
| | #pragma once
#include "Lists.h"
namespace hashTC
{ struct Object
{ int Size;
int (*FunKey)(void*);
listx::Object* Hash;
Object(int size, int (*f)(void*))
{ Size=size; FunKey=f;
Hash=new listx::Object[Size];
};
int HashFunction(void* data);
bool Insert(void* data);
listx::Element* Search(void* data);
bool Delete(void* data);
void Scan();
};
Object Create(int size, int (*f)(void*));
}
| #pragma once
#define LISTNIL (Element*)-1
namespace listx
{ struct Element
{ Element* Prev; Element* Next; void* Data;
Element(Element* prev, void* data, Element* next)
{ Prev = prev; Data = data; Next = next; }
Element* GetNext(){return Next;};
Element* GetPrev(){return Prev;}; };
static Element* NIL=NULL;
struct Object
{Element* Head; Object() { Head = NIL; };
Element* GetFirst() { return Head;};
Element* GetLast(); Element* Search(void* data);
bool Insert(void* data); bool Delete(Element* e);
bool Delete(void* data); void Scan(); };
Object Create();
}
#undef LISTNIL
| |
| 2. В правой части данной строки таблицы записан в левом столбце заголовочный файл Hash_Twin_ Chain.h, а в правом - заголовочный файл Lists.h.
Написать комментарии к программному коду.
| | #pragma once
#include "Lists.h"
namespace hashTC
{
struct Object
{ int Size;
int (*FunKey)(void*);
listx::Object* Hash;
Object(int size, int (*f)(void*))
{ Size=size; FunKey=f;
Hash=new listx::Object[Size];
};
int HashFunction(void* data);
bool Insert(void* data);
listx::Element* Search(void* data);
bool Delete(void* data);
void Scan();
};
Object Create(int size, int (*f)(void*));
}
| #pragma once
#define LISTNIL (Element*)-1
namespace listx
{ struct Element
{ Element* Prev; Element* Next;
void* Data;
Element(Element* prev, void* data, Element* next)
{ Prev = prev; Data = data; Next = next; }
Element* GetNext(){return Next;};
Element* GetPrev(){return Prev;};
};
static Element* NIL=NULL;
struct Object
{Element* Head; Object()
{Head = NIL; };
Element* GetFirst() {return Head;};
Element* GetLast();
Element* Search(void* data);
bool Insert(void* data);
bool Delete(Element* e);
bool Delete(void* data);
void Scan(); };
Object Create();
}
#undef LISTNIL
| |
| 1. В правой части данного пункта записаны две вспомогательные функции проекта и фрагмент главной функции.
Дописать главную функцию, в которой должна демонстрироваться работа с основными операциями манипулирования данными в хэш-таблице с цепочками с использованием меню.
Выполнить проект и проанализировать результаты.
| | #include "stdafx.h"
#include "Hash_Twin_Chain.h"
#include <iostream>
using namespace std;
struct AAA
{ int key;
char *mas;
AAA(int k, char*z)
{ key = k; mas = z; }
AAA() { key = 0; mas = ""; }
};
int hf(void* d)
{ AAA* f = (AAA*)d;
return f->key;
}
void AAA_print(listx::Element* e)
{ cout<<((AAA*)e->Data)->key<<'-' <<((AAA*)e->Data)->mas<<" / ";
}
| int _tmain(int argc, _TCHAR* argv[])
{setlocale(LC_ALL, "rus");
int current_size;
int choise; int k;
cout<<"Введите размер хэш-таблицы" <<endl;
cin>>current_size;
hashTC::Object H = hashTC::Create (current_size, hf);
for(;;)
{
.............
}
return 0;
}
| |
4. Провести исследование построения хэш-таблиц разного размера с коллизиями. Исследовать время поиска в построенных в соответствии со своим вариантом хэш-таблицах.
Для вариантов с 1 по 8 вычисление хэш-функции произвести по методу универсального хеширования. Для вариантов с 9 по 16 при вычислении хэш-функции использовать не ключ int key, а алгоритм на основе исключающего ИЛИ для поля строки данных (mas).
5. Изменить проект таким образом, чтобы реализовать конкретную задачу: создать телефонную книжку, словарь и т. п.
В начало практикума
