---

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

struct tstk {
    int inf;
    tstk* a;
};

const int N = 9;
const int M = 10;
const int LOW = 11000;
const int HIGH = 53000;

tstk** sv_create(int m) {
    tstk** H = new tstk*[m];
    for (int i = 0; i < m; i++) H[i] = NULL;
    return H;
}

void sv_add(int inf, int m, tstk** H) {
    tstk* spt = new tstk;
    spt->inf = inf;
    int i = inf % m;
    if (H[i] == NULL) {
        H[i] = spt;
        spt->a = NULL;
    } else {
        spt->a = H[i];
        H[i] = spt;
    }
}

tstk* sv_search(int inf, int m, tstk** H) {
    int i = inf % m;
    tstk* spt = H[i];
    while (spt != NULL) {
        if (spt->inf == inf) return spt;
        spt = spt->a;
    }
    return NULL;
}

void sv_delete_all(int m, tstk** H) {
    tstk* spt;
    tstk* sp;
    for (int i = 0; i < m; i++) {
        sp = H[i];
        while (sp != NULL) {
            spt = sp;
            sp = sp->a;
            delete spt;
        }
    }
    delete[] H;
}

int main() {
    std::srand(static_cast<unsigned>(std::time(NULL)));
    int mas[N];
    std::cout << "Ishodnyy massiv:" << std::endl;
    for (int i = 0; i < N; i++) {
        mas[i] = LOW + std::rand() % (HIGH - LOW + 1);
        std::cout << mas[i] << " ";
    }
    std::cout << std::endl;

    tstk** H = sv_create(M);

    for (int i = 0; i < N; i++) {
        sv_add(mas[i], M, H);
    }

    std::cout << std::endl << "Hesh-tablitsa (na osnove svyazannykh spiskov):" << std::endl;
    for (int i = 0; i < M; i++) {
        std::cout << "H[" << i << "] -> ";
        tstk* p = H[i];
        while (p != NULL) {
            std::cout << p->inf << " ";
            p = p->a;
        }
        std::cout << "NULL" << std::endl;
    }

    std::cout << std::endl << "Poisk elementa (dlya vykhoda vvedite -1):" << std::endl;
    int key;
    while (true) {
        std::cout << "Vvedite klyuch: ";
        if (!(std::cin >> key)) {
            std::cin.clear();
            std::cin.ignore(10000, '\n');
            std::cout << "Oshibka vvoda. Vvedite celoe chislo." << std::endl;
            continue;
        }
        if (key == -1) break;
        tstk* res = sv_search(key, M, H);
        if (res == NULL) {
            std::cout << "Net elementa" << std::endl;
        } else {
            std::cout << "Element " << res->inf << " naiden" << std::endl;
        }
    }

    sv_delete_all(M, H);
    return 0;
}