Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Напишите программу, которая вставляет N случайных целых чисел в таблицу
- //размером N/100 с цепочками переполнения, а затем определяет длину самого короткого и
- //самого длинного списков, при N = 103
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <time.h>
- #include <random>
- #include <iomanip>
- using namespace std;
- static const int kLeftRandomBorder = -600;
- static const int kRightRandomBorder = 300;
- typedef int data_t;
- class HashTable
- {
- size_t size_;
- size_t amount_;
- vector<vector<data_t>> table_;
- public:
- HashTable(const size_t& N)
- {
- amount_ = 0;
- size_ = N;
- table_.resize(N);
- }
- size_t getHash(const int& number)
- {
- return static_cast<size_t>(abs(static_cast<int>(number % size_)));
- }
- void add(const int& number)
- {
- table_[getHash(number)].push_back(number);
- amount_++;
- }
- void getTheLongest()
- {
- int maxSize = -1;
- size_t id = 0;
- for (size_t i = 0 ; i < table_.size() ; i++)
- {
- int temp = table_[i].size();
- if (temp > maxSize)
- {
- maxSize = table_[i].size(), id = i;
- }
- }
- cout << "Max size = " << maxSize << endl << "collisions: ";
- for (int i = 0; i < table_[id].size(); i++)
- cout << setw(5) << table_[id][i];
- }
- void getTheShortest()
- {
- int minSize = size_*100;
- size_t id = 0;
- for (size_t i = 0; i < table_.size(); i++)
- {
- int temp = table_[i].size();
- if (table_[i].size() < minSize)
- {
- minSize = table_[i].size(), id = i;
- }
- }
- if (minSize == size_ * 100)
- cout << "Table is empty";
- else
- {
- cout << "Min size = " << minSize << endl << "collisions: ";
- for (int i = 0; i < table_[id].size(); i++)
- cout << table_[id][i] << " ";
- }
- }
- };
- int main()
- {
- size_t N;
- cout << "Enter N: ";
- cin >> N;
- HashTable table(N/100);
- srand(unsigned(time(NULL)));
- for(size_t i = 0 ; i < N; i++)
- {
- int temp = kRightRandomBorder + rand() % kLeftRandomBorder;
- table.add(temp);
- }
- table.getTheLongest();
- cout << endl << endl;
- table.getTheShortest();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement