Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Реализация. Шаг 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. В результате работы программы получим следующий результат:

Вывод

 

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







Дата добавления: 2015-06-15; просмотров: 548. Нарушение авторских прав; Мы поможем в написании вашей работы!




Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...


Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...


Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...


Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

ТЕОРИЯ ЗАЩИТНЫХ МЕХАНИЗМОВ ЛИЧНОСТИ В современной психологической литературе встречаются различные термины, касающиеся феноменов защиты...

Этические проблемы проведения экспериментов на человеке и животных В настоящее время четко определены новые подходы и требования к биомедицинским исследованиям...

Классификация потерь населения в очагах поражения в военное время Ядерное, химическое и бактериологическое (биологическое) оружие является оружием массового поражения...

Эндоскопическая диагностика язвенной болезни желудка, гастрита, опухоли Хронический гастрит - понятие клинико-анатомическое, характеризующееся определенными патоморфологическими изменениями слизистой оболочки желудка - неспецифическим воспалительным процессом...

Признаки классификации безопасности Можно выделить следующие признаки классификации безопасности. 1. По признаку масштабности принято различать следующие относительно самостоятельные геополитические уровни и виды безопасности. 1.1. Международная безопасность (глобальная и...

Прием и регистрация больных Пути госпитализации больных в стационар могут быть различны. В цен­тральное приемное отделение больные могут быть доставлены: 1) машиной скорой медицинской помощи в случае возникновения остро­го или обострения хронического заболевания...

Studopedia.info - Студопедия - 2014-2025 год . (0.008 сек.) русская версия | украинская версия