---

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

using namespace std;

// Структура узла списка
struct tstk {
    int inf;      // Данные
    tstk *next;   // Указатель на следующий элемент
};

// Создание хеш-таблицы
tstk** sv_create(int m) {
    tstk **H = new tstk*[m];
    for (int i = 0; i < m; i++) {
        H[i] = NULL;
    }
    return H;
}

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

// Добавление элемента
void sv_add(int inf, int m, tstk **H) {
    tstk *spt = new tstk;
    spt->inf = inf;
    int i = hashFunc(inf, m);
    
    if (H[i] == NULL) {
        H[i] = spt;
        spt->next = NULL;
    } else {
        spt->next = H[i];
        H[i] = spt;
    }
}

// Поиск элемента (возвращает указатель на узел)
tstk* sv_search(int inf, int m, tstk **H) {
    int i = hashFunc(inf, m);
    tstk *spt = H[i];
    
    while (spt != NULL) {
        if (spt->inf == inf) return spt;
        spt = spt->next;
    }
    return NULL;
}

// Поиск с возвратом индекса списка
int search_get_index(int inf, int m, tstk **H) {
    return hashFunc(inf, m);
}

// Очистка памяти
void sv_delete(int m, tstk **H) {
    tstk *spt, *sp;
    for (int i = 0; i < m; i++) {
        sp = H[i];
        while (sp != NULL) {
            spt = sp;
            sp = sp->next;
            delete spt;
        }
    }
    delete[] H;
}

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

// Вывод хеш-таблицы
void printHashTable(tstk **H, int m) {
    cout << "\n=== Хеш-таблица (связанные списки) ===" << endl;
    for (int i = 0; i < m; i++) {
        cout << "H[" << setw(2) << i << "] -> ";
        tstk *current = H[i];
        if (current == NULL) {
            cout << "NULL" << endl;
        } else {
            while (current != NULL) {
                cout << current->inf;
                if (current->next != NULL) cout << " -> ";
                current = current->next;
            }
            cout << " -> NULL" << endl;
        }
    }
}

int main() {
    srand(time(NULL));
    
    // Параметры варианта А4
    const int n = 9;            // Количество элементов
    const int M = 10;           // Размер хеш-таблицы
    const int MIN_VAL = 11000;
    const int MAX_VAL = 53000;
    
    // Генерация исходного массива
    int mas[n];
    cout << "=== ВАРИАНТ А4: Связанные списки ===" << endl;
    cout << "Сгенерированный массив (" << n << " элементов):" << endl;
    for (int i = 0; i < n; i++) {
        mas[i] = randomInRange(MIN_VAL, MAX_VAL);
        cout << "mas[" << i << "] = " << mas[i] << " (hash = " << (mas[i] % M) << ")" << endl;
    }
    
    // Создание и заполнение хеш-таблицы
    tstk **H = sv_create(M);
    for (int i = 0; i < n; i++) {
        sv_add(mas[i], M, H);
    }
    
    // Вывод хеш-таблицы
    printHashTable(H, M);
    
    // === ОСНОВНАЯ ЧАСТЬ: ручной поиск ===
    cout << "\n=== ПОИСК ЭЛЕМЕНТА ===" << endl;
    int searchKey;
    cout << "Введите число для поиска: ";
    cin >> searchKey;
    
    tstk *found = sv_search(searchKey, M, H);
    int listIndex = search_get_index(searchKey, M, H);
    
    if (found != NULL) {
        cout << "\n✅ Элемент " << searchKey << " НАЙДЕН!" << endl;
        cout << "Он находится в списке H[" << listIndex << "]" << endl;
        
        // Дополнительно: показываем позицию в списке
        int position = 1;
        tstk *current = H[listIndex];
        while (current != NULL && current->inf != searchKey) {
            position++;
            current = current->next;
        }
        cout << "Это " << position << "-й элемент в этом списке" << endl;
    } else {
        cout << "\n❌ Элемент " << searchKey << " НЕ НАЙДЕН в хеш-таблице!" << endl;
    }
    
    // Очистка памяти
    sv_delete(M, H);
    
    return 0;
}