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

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

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

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

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

Размер хэша инициализируется конструктором класса.

Элементы вставляются в хэш согласно выражению:

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

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

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

Инициализируйте размер (скажем, n ) векторов.
При добавлении элемента выполните следующие действия:
1. Получить значение x = "[значение] MOD n ".
2. Верните значение этого элемента в v [x].
Для удаления мы выполняем следующие шаги:
1. Получить значение x = "[значение] MOD n ".
2. Найдите элемент, который нужно удалить, в v [x].
3. Если найден, удалите элемент с помощью метода erase ().
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

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

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

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

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

Technical Scripter Алгоритмы

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ