---

#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;
}

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

// Вывод хеш-таблицы
void printHashTable(int H[], int m) {
    cout << "Хеш-таблица (линейная адресация):" << 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 << " элементов, диапазон " << MIN_VAL << "-" << MAX_VAL << "):" << endl;
    for (int i = 0; i < n; i++) {
        mas[i] = randomInRange(MIN_VAL, MAX_VAL);
        cout << "mas[" << i << "] = " << mas[i] << endl;
    }
    cout << endl;
    
    // Создание и инициализация хеш-таблицы
    int H[M];
    for (int i = 0; i < M; i++) {
        H[i] = -1; // -1 означает "свободно"
    }
    
    // Заполнение хеш-таблицы
    for (int i = 0; i < n; i++) {
        sv_add(mas[i], M, H);
    }
    
    // Вывод хеш-таблицы
    printHashTable(H, M);
    cout << endl;
    
    // Поиск элементов
    cout << "Поиск элементов в хеш-таблице:" << endl;
    for (int i = 0; i < n; i++) {
        int pos = sv_search(mas[i], M, H);
        cout << "Элемент " << mas[i] << " найден на позиции H[" << pos << "]" << endl;
    }
    cout << endl;
    
    // Поиск несуществующего элемента
    int notExist = randomInRange(MIN_VAL, MAX_VAL);
    while (true) {
        bool found = false;
        for (int i = 0; i < n; i++) {
            if (mas[i] == notExist) {
                notExist = randomInRange(MIN_VAL, MAX_VAL);
                found = true;
                break;
            }
        }
        if (!found) break;
    }
    
    int pos = sv_search(notExist, M, H);
    cout << "Поиск несуществующего элемента " << notExist << ": ";
    if (pos == -1) cout << "не найден" << endl;
    else cout << "найден на позиции H[" << pos << "]" << endl;
    
    return 0;
}