Реализация. Шаг 1. Генерируем элементы исходного массива заданной размерности с помощью датчика случайных чисел

Шаг 1. Генерируем элементы исходного массива заданной размерности с помощью датчика случайных чисел. Одновременно проверяем элементов на уникальность. Выводим последовательноссть на экран.

 

cout << "SourceMas: \n";

int SourceMas [ N ]; // исходный массив генерируемых чисел

srand (time (NULL));

for (k = 0; k < N; ++k) // k - индекс массива SourceMas

{

int flag=0;

while (flag==0)

{

SourceMas [ k ] = rand ()% 99999 + 100000 * (rand () % 9 + 1);

flag=1;

for(int j=0;j<k;++j)

if (SourceMas [k]== SourceMas [j]) flag=0;

cout << SourceMas [ k ] << "\t"; // вывод на экран

 

 

Шаг 2. Начинаем работу с хеш-таблицей, занулив её.

 

for (ht = 0; ht < t; ++ht) // зануляем хеш-таблицу

HashTabl [ ht ] = 0;

 

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

 

for (ht = 0; ht < N; ++ht) // заполняем хеш-таблицу

{

adres = ((SourceMas [ht] + 18)/ 61) % t; // вычисляем непосредственно хеш функцию

int adres0 = adres;

if (HashTabl [adres] == 0) // если ячейка хеш таблицы пустая

{

HashTabl [adres] = SourceMas [ht]; // то записываем в неё значение из исхтаблицы непосредственно по адресу=ключу

kz++;

}

else // иначе

{

while (HashTabl [ adres ]!= NULL) // пока не найдётся пустая ячейка

{

adres = (adres0 + np*np) % t; // применяем метод квадратичной пробы, где np-№ пробы, adres0-нач значение ключа

++np;

}

chp++;

HashTabl [ adres ] = SourceMas [ ht ];

kz++;

}

}

 

 

Шаг 3. Выведем на экран полученную хеш-таблицу, а также коэффициент заполненности таблицы(отношение числа заполненных ячеек таблицы к общему их числу) и среднее число проб (отношение количества всех проб к числу заполненных ячеек).

 

cout << "\nHashTabl: \n";

for (ht = 0; ht < t; ++ ht)

printf("%i: %i\t",ht,HashTabl [ ht ]);

printf("Koeff.zapoln.tabl: %f \n",float(kz)/float(t));

printf("Srednee chislo prob:%f\n",float(chp)/float(kz));

 

Шаг 4. В результате работы программы получим следующий результат:

Вывод

 

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