---

#include <iostream>
#include <cstdlib>
#include <ctime>

const int N = 12;          // количество элементов
const int M = 15;          // размер хеш-таблицы
const int LOW = 23000;     // нижняя граница диапазона
const int HIGH = 45000;    // верхняя граница диапазона

// Функция добавления элемента в хеш-таблицу с линейной адресацией
void sv_add(int value, int m, int* H) {
    int i = value % m;
    // линейное пробирование: ищем свободную ячейку
    while (H[i] != -1) {
        i = (i + 1) % m;
    }
    H[i] = value;
}

// Функция поиска элемента в хеш-таблице
int sv_search(int value, int m, const int* H) {
    int i = value % m;
    int start = i;
    do {
        if (H[i] == value) return i;       // элемент найден
        if (H[i] == -1) return -1;         // свободная ячейка – элемент отсутствует
        i = (i + 1) % m;
    } while (i != start);                  // обошли всю таблицу
    return -1;                             // элемент не найден
}

int main() {
    // 1. Генерация исходного массива
    std::srand(static_cast<unsigned>(std::time(nullptr)));
    int mas[N];
    std::cout << "Исходный массив (" << N << " элементов, диапазон [" << LOW << ", " << HIGH << "]):\n";
    for (int i = 0; i < N; ++i) {
        mas[i] = LOW + std::rand() % (HIGH - LOW + 1);
        std::cout << mas[i] << " ";
    }
    std::cout << std::endl;

    // 2. Создание хеш-таблицы и инициализация (-1 означает свободно)
    int H[M];
    for (int i = 0; i < M; ++i) {
        H[i] = -1;
    }

    // 3. Заполнение хеш-таблицы
    for (int i = 0; i < N; ++i) {
        sv_add(mas[i], M, H);
    }

    // 4. Вывод хеш-таблицы
    std::cout << "\nХеш-таблица (размер " << M << ", хеш-функция key % " << M << "):\n";
    for (int i = 0; i < M; ++i) {
        std::cout << "H[" << i << "] = " << H[i] << std::endl;
    }

    // 5. Поиск элементов по запросу пользователя
    std::cout << "\nПоиск элемента в хеш-таблице (для выхода введите -1):\n";
    int key;
    while (true) {
        std::cout << "Введите ключ: ";
        std::cin >> key;
        if (key == -1) break;
        int idx = sv_search(key, M, H);
        if (idx == -1) {
            std::cout << "Net elementa" << std::endl;
        } else {
            std::cout << "Элемент " << H[idx] << " найден в позиции " << idx << std::endl;
        }
    }

    return 0;
}