Advertisement
Sanlover

Напишите программу, которая вставляет N случайных целых чисел в таблицу размером N/100 с цепочками п

Jun 28th, 2021
251
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.17 KB | None | 0 0
  1. //Напишите программу, которая вставляет N случайных целых чисел в таблицу
  2. //размером N/100 с цепочками переполнения, а затем определяет длину самого короткого и
  3. //самого длинного списков, при N = 103
  4.  
  5.  
  6.  
  7. #include <iostream>
  8. #include <vector>
  9. #include <cmath>
  10. #include <time.h>
  11. #include <random>
  12. #include <iomanip>
  13. using namespace std;
  14.  
  15. static const int kLeftRandomBorder = -600;
  16. static const int kRightRandomBorder = 300;
  17.  
  18. typedef int data_t;
  19.  
  20. class HashTable
  21. {
  22.     size_t size_;
  23.     size_t amount_;
  24.     vector<vector<data_t>> table_;
  25.  
  26. public:
  27.     HashTable(const size_t& N)
  28.     {
  29.         amount_ = 0;
  30.         size_ = N;
  31.         table_.resize(N);
  32.     }
  33.     size_t getHash(const int& number)
  34.     {
  35.         return static_cast<size_t>(abs(static_cast<int>(number % size_)));
  36.     }
  37.  
  38.     void add(const int& number)
  39.     {
  40.         table_[getHash(number)].push_back(number);
  41.         amount_++;
  42.     }
  43.     void getTheLongest()
  44.     {
  45.         int maxSize = -1;
  46.         size_t id = 0;
  47.         for (size_t i = 0 ; i < table_.size() ; i++)
  48.         {
  49.             int temp = table_[i].size();
  50.             if (temp > maxSize)
  51.             {
  52.                 maxSize = table_[i].size(), id = i;
  53.             }
  54.         }
  55.         cout << "Max size = " << maxSize << endl << "collisions: ";
  56.             for (int i = 0; i < table_[id].size(); i++)
  57.                 cout << setw(5) << table_[id][i];
  58.     }
  59.     void getTheShortest()
  60.     {
  61.         int minSize = size_*100;
  62.         size_t id = 0;
  63.         for (size_t i = 0; i < table_.size(); i++)
  64.         {
  65.             int temp = table_[i].size();
  66.             if (table_[i].size() < minSize)
  67.             {
  68.                 minSize = table_[i].size(), id = i;
  69.             }
  70.         }
  71.         if (minSize == size_ * 100)
  72.             cout << "Table is empty";
  73.         else
  74.         {
  75.             cout << "Min size = " << minSize << endl << "collisions: ";
  76.             for (int i = 0; i < table_[id].size(); i++)
  77.                 cout << table_[id][i] << " ";
  78.         }
  79.     }
  80. };
  81. int main()
  82. {
  83.     size_t N;
  84.     cout << "Enter N: ";
  85.     cin >> N;
  86.  
  87.     HashTable table(N/100);
  88.  
  89.     srand(unsigned(time(NULL)));
  90.     for(size_t i = 0 ; i < N; i++)
  91.     {
  92.         int temp = kRightRandomBorder + rand() % kLeftRandomBorder;
  93.         table.add(temp);
  94.     }
  95.  
  96.     table.getTheLongest();
  97.     cout << endl << endl;
  98.     table.getTheShortest();
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement