Программа для реализации раздельной цепочки в C ++ STL без использования указателей
Предварительные требования: отдельная цепочка, STL в C ++
В этой статье реализована раздельная цепочка при хешировании с помощью STL на C ++ без использования указателей.
Подход: создайте массив векторов для получения динамического (изменяемого размера) массива для каждого хэш-индекса, а не используйте связанный список для того же. Теперь стало проще работать с набором данных без использования связного списка. Этот простой трюк намного проще реализовать и он более эффективен. В этом подходе:
- Размер хэша инициализируется конструктором класса.
- Элементы вставляются в хэш согласно выражению:
Вектор [i% n] .push_back (i); где: Вектор = массив векторов, используемых для хеширования i = текущий элемент для хеширования n = размер хеша
Алгоритм: Алгоритм подхода приведен ниже:
- Инициализируйте размер (скажем, n ) векторов.
- При добавлении элемента выполните следующие действия:
- Получить значение x = "[значение] MOD n ".
- Верните значение этого элемента в v [x].
- Для удаления мы выполняем следующие шаги:
- Получить значение x = "[значение] MOD n ".
- Найдите элемент, который нужно удалить, в v [x].
- Если найден, удалите элемент с помощью метода erase ().
- Если удаляемый элемент не найден, выведите «Элемент не найден!»
- Распечатайте хеш.
Выполнение
// 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.