diff options
Diffstat (limited to '02-data_structures/03-hash_tables/02-hash_chains')
7 files changed, 136 insertions, 0 deletions
diff --git a/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp b/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp new file mode 100644 index 0000000..8af47d2 --- /dev/null +++ b/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp @@ -0,0 +1,81 @@ +#include <iostream> +#include <string> +#include <vector> +#include <algorithm> + +using std::string; +using std::vector; +using std::cin; + +struct Query { + string type, s; + size_t ind; +}; + +class QueryProcessor { + int bucket_count; + // store all strings in one vector + vector<string> elems; + size_t hash_func(const string& s) const { + static const size_t multiplier = 263; + static const size_t prime = 1000000007; + unsigned long long hash = 0; + for (int i = static_cast<int> (s.size()) - 1; i >= 0; --i) + hash = (hash * multiplier + s[i]) % prime; + return hash % bucket_count; + } + +public: + explicit QueryProcessor(int bucket_count): bucket_count(bucket_count) {} + + Query readQuery() const { + Query query; + cin >> query.type; + if (query.type != "check") + cin >> query.s; + else + cin >> query.ind; + return query; + } + + void writeSearchResult(bool was_found) const { + std::cout << (was_found ? "yes\n" : "no\n"); + } + + void processQuery(const Query& query) { + if (query.type == "check") { + // use reverse order, because we append strings to the end + for (int i = static_cast<int>(elems.size()) - 1; i >= 0; --i) + if (hash_func(elems[i]) == query.ind) + std::cout << elems[i] << " "; + std::cout << "\n"; + } else { + vector<string>::iterator it = std::find(elems.begin(), elems.end(), query.s); + if (query.type == "find") + writeSearchResult(it != elems.end()); + else if (query.type == "add") { + if (it == elems.end()) + elems.push_back(query.s); + } else if (query.type == "del") { + if (it != elems.end()) + elems.erase(it); + } + } + } + + void processQueries() { + int n; + cin >> n; + for (int i = 0; i < n; ++i) + processQuery(readQuery()); + } +}; + +int main() { + std::ios_base::sync_with_stdio(false); + int bucket_count; + cin >> bucket_count; + QueryProcessor proc(bucket_count); + proc.processQueries(); + return 0; +} diff --git a/02-data_structures/03-hash_tables/02-hash_chains/tests/01 b/02-data_structures/03-hash_tables/02-hash_chains/tests/01 new file mode 100644 index 0000000..543e44b --- /dev/null +++ b/02-data_structures/03-hash_tables/02-hash_chains/tests/01 @@ -0,0 +1,14 @@ +5 +12 +add world +add HellO +check 4 +find World +find world +del world +check 4 +del HellO +add luck +add GooD +check 2 +del good diff --git a/02-data_structures/03-hash_tables/02-hash_chains/tests/01.a b/02-data_structures/03-hash_tables/02-hash_chains/tests/01.a new file mode 100644 index 0000000..2089645 --- /dev/null +++ b/02-data_structures/03-hash_tables/02-hash_chains/tests/01.a @@ -0,0 +1,5 @@ +HellO world +no +yes +HellO +GooD luck diff --git a/02-data_structures/03-hash_tables/02-hash_chains/tests/02 b/02-data_structures/03-hash_tables/02-hash_chains/tests/02 new file mode 100644 index 0000000..3ebfc0e --- /dev/null +++ b/02-data_structures/03-hash_tables/02-hash_chains/tests/02 @@ -0,0 +1,10 @@ +4 +8 +add test +add test +find test +del test +find test +find Test +add Test +find Test diff --git a/02-data_structures/03-hash_tables/02-hash_chains/tests/02.a b/02-data_structures/03-hash_tables/02-hash_chains/tests/02.a new file mode 100644 index 0000000..95b2d9a --- /dev/null +++ b/02-data_structures/03-hash_tables/02-hash_chains/tests/02.a @@ -0,0 +1,4 @@ +yes +no +no +yes diff --git a/02-data_structures/03-hash_tables/02-hash_chains/tests/03 b/02-data_structures/03-hash_tables/02-hash_chains/tests/03 new file mode 100644 index 0000000..0893cf3 --- /dev/null +++ b/02-data_structures/03-hash_tables/02-hash_chains/tests/03 @@ -0,0 +1,14 @@ +3 +12 +check 0 +find help +add help +add del +add add +find add +find del +del del +find del +check 0 +check 1 +check 2 diff --git a/02-data_structures/03-hash_tables/02-hash_chains/tests/03.a b/02-data_structures/03-hash_tables/02-hash_chains/tests/03.a new file mode 100644 index 0000000..8f5237c --- /dev/null +++ b/02-data_structures/03-hash_tables/02-hash_chains/tests/03.a @@ -0,0 +1,8 @@ + +no +yes +yes +no + +add help + |