---

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

using namespace std;

// Хеш-функция: i = key % M
int hashFunc(int key, int M) {
    return key % M;
}

// Добавление элемента с линейным разрешением коллизий
void sv_add(int inf, int m, int H[]) {
    int i = hashFunc(inf, m);
    
    while (H[i] != -1) {
        i++;
        if (i == m) i = 0;
    }
    H[i] = inf;
}

// Поиск элемента в хеш-таблице (возвращает позицию)
int sv_search(int inf, int m, int H[]) {
    int i = hashFunc(inf, m);
    int start = i;
    
    while (H[i] != -1) {
        if (H[i] == inf) return i;  // Нашли - вернули индекс
        i++;
        if (i == m) i = 0;
        if (i == start) break;
    }
    return -1;  // Не нашли
}

// Генерация случайного числа
int randomInRange(int minVal, int maxVal) {
    return minVal + rand() % (maxVal - minVal + 1);
}

// Вывод хеш-таблицы
void printHashTable(int H[], int m) {
    cout << "\nХеш-таблица (линейная адресация):" << endl;
    for (int i = 0; i < m; i++) {
        if (H[i] != -1)
            cout << "H[" << setw(2) << i << "] = " << H[i] << endl;
        else
            cout << "H[" << setw(2) << i << "] = --" << endl;
    }
}

int main() {
    srand(time(NULL));
    
    // Параметры варианта А3
    const int n = 15;
    const int M = 20;
    const int MIN_VAL = 12000;
    const int MAX_VAL = 34000;
    
    // Исходный массив со случайными числами
    int mas[n];
    cout << "=== ВАРИАНТ А3: Линейная адресация ===" << endl;
    cout << "Сгенерированный массив (" << n << " элементов):" << endl;
    for (int i = 0; i < n; i++) {
        mas[i] = randomInRange(MIN_VAL, MAX_VAL);
        cout << "mas[" << i << "] = " << mas[i] << endl;
    }
    
    // Создание и заполнение хеш-таблицы
    int H[M];
    for (int i = 0; i < M; i++) H[i] = -1;
    
    for (int i = 0; i < n; i++) {
        sv_add(mas[i], M, H);
    }
    
    // Вывод хеш-таблицы
    printHashTable(H, M);
    
    // ПОИСК С ВВОДОМ ОТ ПОЛЬЗОВАТЕЛЯ
    cout << "\n=== ПОИСК ЭЛЕМЕНТА ===" << endl;
    int searchKey;
    cout << "Введите число для поиска: ";
    cin >> searchKey;
    
    int position = sv_search(searchKey, M, H);
    
    if (position != -1) {
        cout << "\nРезультат: Элемент " << searchKey << " НАЙДЕН!" << endl;
        cout << "Он находится в ячейке H[" << position << "]" << endl;
    } else {
        cout << "\nРезультат: Элемент " << searchKey << " НЕ НАЙДЕН в хеш-таблице" << endl;
    }
    
    return 0;
}