Отчет ЛР2 МО-
.docxФедеральное государственное бюджетное образовательное учреждение
высшего образования
Уфимский государственный авиационный технический университет
Кафедра вычислительной математики и кибернетики
Лабораторная работа №2
« Работа с Хеш-таблицей »
Выполнил:
студент группы МО-
Проверил:
Рипатти А.В.
Уфа – 2020
Задание:
Построить хеш - таблицу, содержащую последовательность из m = 64 элементов размерности n = 6. Элементы генерируются с помощью датчика случайных чисел.
Хеш - функция - f(k) = (k +7) / 41)mod t.
Метод разрешения конфликта - линейные пробы.
В программу «Построение хеш-таблицы» (лабораторная работа №1) добавить функции, позволяющие: 1. Сгенерировать или ввести в интерактивном режиме новые элементы. 2. Осуществить поиск элемента в таблице. Проверить, имеется ли такой элемент в таблице. Если есть — вывести его индекс, если нет-сообщение: «Элемент не найден». 3. Добавить элемент в таблицу. Проверить, имеется ли такой элемент в таблице. Если есть — вывести его индекс, если нет — добавить в хеш-таблицу и вывести сообщение, в какой индекс добавлен элемент. 4. Удалить элемент из таблицы. Проверить, имеется ли такой элемент в таблице. Если есть — удалить и вывести сообщение, с какого индекса удален, если нет-сообщение: «Элемент не найден». 4. Ввести в интерактивном режиме: элемент, который следует заменить на другое значение, элемент, который требуется занести в таблицу. Осуществить замену.
Разработать интерфейс, который предоставляет пользователю выбрать нужную функцию по работе с хеш-таблицей, например, cout << "\n Выберите нужный вариант : \n 1- найти элемент \n 2- удалить элемент \n 3- добавить новый элемент\n 4- Заменить элемент \n"; В результате выбора и активации нужного варианта программа должна выполнить необходимую операцию.
Реализация (язык программирования С++)
#include <iomanip>
#include <iostream>
using namespace std;
const int AllElem = 64;
const int HshElem = AllElem * 1.5;
void out(int a[], int b)
{
for (int i = 0; i < b; i++)
{
cout << setw(10) << i << setw(10) << a[i];
}
cout << endl << endl;
}
void search(int mas[]) {
int a;
int adress;
cout << "Введите число\n";
cin >> a;
adress = ((a + 7) / 41) % HshElem;
if (mas[adress] == 0) {
cout << "Элемента в таблице нет\n";
}
else {
if (a == mas[adress]) {
cout << "Элемент в таблице есть\n";
cout << "Элемент:" << a << endl;
cout << "Индекс:" << adress << endl;
}
else {
while (a != mas[adress]) {
adress = (adress + 1) % HshElem;
if (adress == 0) break;
}
if (a != mas[adress]) {
cout << "Элемента в таблице нет\n";
}
else {
cout << "Элемент в таблице есть\n";
cout << "Элемент:" << a << endl;
cout << "Индекс:" << adress << endl;
}
}
}
}
int search2(int mas[], int a, int b) {
bool f = false;
if (mas[b] == 0) {
cout << "Элемента в таблице нет\n";
}
else {
if (a == mas[b]) {
f = true;
cout << "Элемент в таблице есть\n";
cout << "Элемент:" << a << endl;
cout << "Индекс:" << b << endl;
}
else {
while (a != mas[b]) {
b = (b + 1) % HshElem;
if (b == 0) break;
}
if (a != mas[b]) {
cout << "Элемента в таблице нет\n";
}
else {
f = true;
cout << "Элемент в таблице есть\n";
cout << "Элемент:" << a << endl;
cout << "Индекс:" << b << endl;
}
}
}
return f;
}
void del(int mas[]) {
bool f;
int a;
int adress;
cout << "Введите число\n";
cin >> a;
adress = ((a + 7) / 41) % HshElem;
f = search2(mas, a, adress);
if (f) {
if (a == mas[adress]) {
mas[adress] = -1;
out(mas, HshElem);
}
else {
while (a != mas[adress]) {
adress = (adress + 1) % HshElem;
}
mas[adress] = -1;
out(mas, HshElem);
}
}
}
void add(int mas[]) {
bool f;
int a;
int adress;
cout << "Введите число\n";
cin >> a;
adress = ((a + 7) / 41) % HshElem;
f = search2(mas, a, adress);
if (f == false) {
if (mas[adress] == 0 || mas[adress] == -1) {
mas[adress] = a;
out(mas, HshElem);
}
else {
while (mas[adress]) {
adress = (adress + 1) % HshElem;
if (mas[adress] == -1)break;
}
mas[adress] = a;
out(mas, HshElem);
}
}
}
void replace(int mas[]) {
del(mas);
add(mas);
}
void Menu(int mas[],int prob, int elem) {
cout << "\n Выберите нужный вариант : \n 1- найти элемент \n 2-удалить элемент \n 3 - добавить новый элемент\n 4 - Заменить элемент \n";
bool While = true;
int a;
while (While) {
cin >> a;
switch (a)
{
case 1:
search(mas);
cout << "\n Выберите нужный вариант : \n 1- найти элемент \n 2-удалить элемент \n 3 - добавить новый элемент\n 4 - Заменить элемент \n";
break;
case 2:
del(mas);
cout << "\n Выберите нужный вариант : \n 1- найти элемент \n 2-удалить элемент \n 3 - добавить новый элемент\n 4 - Заменить элемент \n";
break;
case 3:
add(mas);
cout << "\n Выберите нужный вариант : \n 1- найти элемент \n 2-удалить элемент \n 3 - добавить новый элемент\n 4 - Заменить элемент \n";
break;
case 4:
replace(mas);
cout << "\n Выберите нужный вариант : \n 1- найти элемент \n 2-удалить элемент \n 3 - добавить новый элемент\n 4 - Заменить элемент \n";
break;
default:
cout << "error\n";
While = false;
break;
}
}
}
int main()
{
setlocale(LC_ALL, "Rus");
int mas[AllElem] = { 0 };
int hash[HshElem] = { 0 };
int adress;
for (int i = 0; i < AllElem; i++) {
int flag = 0;
int elem = (rand() % 9) * 100000 + 100000 +
(rand() % 10) * 10000 +
(rand() % 10) * 1000 +
(rand() % 10) * 100 +
(rand() % 10) * 10 +
(rand() % 10) * 1;
for (int j = 0; j < i; j++) { //чтобы не было повторяющихся
if (mas[j] == elem)
{
flag = 1;
break;
}
}
if (!flag)
{
mas[i] = elem;
}
}
cout << "Генерация неповторяющихся чисел: " << endl;
out(mas, AllElem);
int prob = 0;
int NumPr = 1;
for (int ht = 0; ht < AllElem; ht++)
{
adress = ((mas[ht] + 7) / 41) % HshElem;
prob++;
int adress0 = adress;
if (hash[adress] == 0) { //Если есть свободная ячейка
hash[adress] = mas[ht];
}
else {
while (hash[adress]) {
adress = (adress0 + NumPr) % HshElem;
NumPr++;
prob++;
}
hash[adress] = mas[ht];
}
NumPr = 1;
}
cout << "Хэш-таблица: " << endl;
out(hash, HshElem);
cout << "Коэффициент заполнения таблицы: " << double(AllElem) / double(HshElem) << endl;
cout << "Среднее число проб:" << double(prob) / double(AllElem) << endl;
int VseElem = AllElem;
Menu(hash,prob,VseElem);
return 0;
}
Результат работы программы.
Поиск
Удаление
Добавление
Замена
Вывод:
Я научилась реализовывать функции добавления, удаления, замены и поиска в хэш-таблице.