Программа для реализации раздельной цепочки в C ++ STL без использования указателей

Опубликовано: 1 Декабря, 2021

Предварительные требования: отдельная цепочка, STL в C ++

В этой статье реализована раздельная цепочка при хешировании с помощью STL на C ++ без использования указателей.

Подход: создайте массив векторов для получения динамического (изменяемого размера) массива для каждого хэш-индекса, а не используйте связанный список для того же. Теперь стало проще работать с набором данных без использования связного списка. Этот простой трюк намного проще реализовать и он более эффективен. В этом подходе:

  1. Размер хэша инициализируется конструктором класса.
  2. Элементы вставляются в хэш согласно выражению:
    Вектор [i% n] .push_back (i);
    где:
        Вектор = массив векторов, используемых для хеширования
        i = текущий элемент для хеширования
        n = размер хеша
    

    Раздельное связывание с использованием STL

    Алгоритм: Алгоритм подхода приведен ниже:

    1. Инициализируйте размер (скажем, n ) векторов.
    2. При добавлении элемента выполните следующие действия:
      1. Получить значение x = "[значение] MOD n ".
      2. Верните значение этого элемента в v [x].
    3. Для удаления мы выполняем следующие шаги:
      1. Получить значение x = "[значение] MOD n ".
      2. Найдите элемент, который нужно удалить, в v [x].
      3. Если найден, удалите элемент с помощью метода erase ().
      4. Если удаляемый элемент не найден, выведите «Элемент не найден!»
    4. Распечатайте хеш.

    Выполнение

    // C++ Program to implement Separate
    // Chaining in C++ STL without
    // the use of pointers
    #include <bits/stdc++.h>
    using namespace std;
    // Container for our data-set
    class SeperateHash {
    // Data members are kept private
    // since they are accessed using methods
    private :
    int n;
    vector<vector< int > > v;
    // Methods are kept public
    public :
    // Initialising constructors as the
    // minimum required memory will be
    // allocated after which compiler
    // will not report flag error
    SeperateHash( int n)
    {
    // Constructor to initialize
    // the vector of vectors
    v = vector<vector< int > >(n);
    // Here, we will allocate
    // memory of the unnamed_memory
    // to the object. This snippet
    // of code won't work for now.
    // Program will work whenever
    // constructor gets initialized
    this ->n = n;
    }
    int getHashIndex( int x)
    {
    return x % n;
    }
    void add( int x)
    {
    // Adding the element according
    // to hash index
    v[getHashIndex(x)].push_back(x);
    }
    void del( int x)
    {
    int i = getHashIndex(x);
    // Scan for the element to be removed
    for ( int j = 0; j < v[i].size(); j++) {
    // Erase if present otherwise
    // print no element found!
    if (v[i][j] == x) {
    v[i].erase(v[i].begin() + j);
    cout << x << " deleted!" << endl;
    return ;
    }
    }
    cout << "No Element Found!" << endl;
    }
    void displayHash()
    {
    // Display the contents
    for ( int i = 0; i < v.size(); i++) {
    cout << i;
    for ( int j = 0; j < v[i].size(); j++)
    cout << " -> " << v[i][j];
    cout << endl;
    }
    }
    };
    // Driver Code
    int main()
    {
    // Array to be used
    int arr[] = { 12, 3, 23, 4, 11,
    32, 26, 33, 17, 19 };
    // Sending the size
    // for separate chaining
    SeperateHash obj(10);
    // Inserting elements in
    // the container accordingly
    for ( int i = 0; i < 10; i++)
    obj.add(arr[i]);
    // Display the initial hash
    cout << "Initial Hash: " ;
    obj.displayHash();
    // Removing the element
    // from the container
    cout << " Removing 23 from Hash: " ;
    obj.del(23);
    cout << endl;
    // Display the final hash
    cout << "Final Hash: " ;
    obj.displayHash();
    return 0;
    }
    Выход:
    Начальный хеш:
    0
    1 -> 11
    2 -> 12 -> 32
    3 -> 3 -> 23 -> 33
    4 -> 4
    5
    6 -> 26
    7 -> 17
    8
    9 -> 19
    
    Удаление 23 из хэша: 23 удалено!
    
    Окончательный хеш:
    0
    1 -> 11
    2 -> 12 -> 32
    3 -> 3 -> 33
    4 -> 4
    5
    6 -> 26
    7 -> 17
    8
    9 -> 19
    

    Преимущества использования этого подхода:

    1. Нам не нужно перебирать записи, как это нужно со связанными списками.
    2. Более легкая отладка кода.
    3. Проще реализовать, поскольку традиционный подход имеет шансы пометить ошибку сегментации с помощью незначительных логических ошибок.
    4. Возможность применения методов STL к данным дает преимущество в конкурентном программировании.

    Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

    Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.