Advertisement
Bibodui

ЯМП Лаба 2 2023 (хэш-таблица)

May 30th, 2023 (edited)
984
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.21 KB | None | 0 0
  1. //Source.cpp
  2.  
  3. //Входной текст разбивается на слова, очищается от знаков препинания и
  4. //помещается в хеш - таблицу.
  5. //Каждый элемент хеш - таблицы – это слово и полесчетчик,
  6. //содержащее количество раз, которое данное слово встретилось в тексте.
  7. //При вставке нового элемента в таблицу, если данный элемент уже
  8. //присутствует в ней, необходимо увеличить соответствующий счетчик.В
  9. //противном случае, создается новый элемент.
  10. //Программа должна выдавать 10 слов,
  11. //которые встречаются чаще всего во входном тексте.
  12.  
  13. //Вариант 11. Хен-функция: метод деления. Метод разрешения коллизий: открытой адресации
  14.  
  15. #include "Hash.h"
  16.  
  17. int main()
  18. {
  19.     SetConsoleOutputCP(1251);
  20.     SetConsoleCP(1251);
  21.  
  22.     int q;
  23.  
  24.     do
  25.     {
  26.         const size_t N = 1000;
  27.         Hash table1(N);
  28.  
  29.         ifstream input_file_1("input_text_1.txt");
  30.         string tmp;
  31.         while (!input_file_1.eof())
  32.         {
  33.             input_file_1 >> tmp;
  34.             tmp = remove_punctuation(tmp);
  35.             table1.insert(tmp);
  36.         }
  37.         input_file_1.close();
  38.  
  39.         ofstream output_file_1("output_file_1.txt");
  40.         table1.most_frequent_words(output_file_1);
  41.         output_file_1.close();
  42.  
  43.         ///////////////////////////////////////////////////////////////
  44.         ///////////////////////////////////////////////////////////////
  45.  
  46.         Hash table2(N);
  47.         string tmp2;
  48.         ifstream input_file_2("input_text_2.txt");
  49.  
  50.         while (!input_file_2.eof())
  51.         {
  52.             input_file_2 >> tmp2;
  53.             tmp2 = remove_punctuation(tmp2);
  54.             table2.insert(tmp2);
  55.         }
  56.         input_file_2.close();
  57.  
  58.         ofstream output_file_2("output_file_2.txt");
  59.         table2.most_frequent_words(output_file_2);
  60.         output_file_2.close();
  61.  
  62.         ///////////////////////////////////////////////////////////////
  63.         ///////////////////////////////////////////////////////////////
  64.  
  65.         Hash table3(N);
  66.  
  67.         ifstream input_file_3("input_text_3.txt");
  68.  
  69.         while (!input_file_3.eof())
  70.         {
  71.             input_file_3 >> tmp;
  72.             tmp = remove_punctuation(tmp);
  73.             table3.insert(tmp);
  74.         }
  75.         input_file_3.close();
  76.  
  77.         ofstream output_file_3("output_file_3.txt");
  78.         table3.most_frequent_words(output_file_3);
  79.         output_file_3.close();
  80.  
  81.         cout << "\n0. Выход" << endl;
  82.         cin >> q;
  83.     } while (q != 0);
  84. }
  85.  
  86. //Hash.h
  87.  
  88. #pragma once
  89. #include <iostream>
  90. #include <string>
  91. #include <Windows.h>
  92. #include <fstream>
  93. #include <vector>
  94.  
  95. using namespace std;
  96.  
  97. struct node
  98. {
  99.     string word;
  100.     int count;
  101.     node()
  102.     {
  103.         word = '\0';
  104.         count = 0;
  105.     }
  106. };
  107.  
  108. class Hash
  109. {
  110.     node* table;
  111.     size_t size;
  112.     size_t fullness;
  113.  
  114. public:
  115.     int collision;
  116.     Hash(size_t);
  117.     ~Hash();
  118.     int division_function(string, size_t);
  119.     void insert(string);
  120.     void new_table();
  121.     void most_frequent_words(ofstream&);
  122. };
  123.  
  124. string remove_punctuation(string);
  125.  
  126. //Hash.cpp
  127.  
  128. #include "Hash.h"
  129.  
  130. Hash::Hash(size_t n)
  131. {
  132.     table = new node[n];
  133.     size = n;
  134.     collision = 0;
  135.     fullness = 0;
  136. }
  137. Hash::~Hash()
  138. {
  139.     delete[] table;
  140. }
  141. int Hash::division_function(string word, size_t size)
  142. {
  143.     int hash = 0;
  144.     for (char c : word)
  145.     {
  146.         hash += static_cast<int>(c);
  147.     }
  148.     return (hash % size);
  149. }
  150. string remove_punctuation(string word)
  151. {
  152.     string result;
  153.     for (char c : word)
  154.     {
  155.         if (isalpha(c))
  156.             result += tolower(c);
  157.     }
  158.  
  159.     return result;
  160. }
  161. void Hash::insert(string word)
  162. {
  163.  
  164.     int index = division_function(word, size);
  165.  
  166.     if (table[index].count > 0 && table[index].word != word) //разрешение коллизий открытой адресацией
  167.     {
  168.         collision++;
  169.         while (table[index].count > 0 && table[index].word != word)
  170.         {
  171.             index = (index + 1) % size;
  172.         }
  173.     }
  174.  
  175.     if (table[index].word == word)
  176.         table[index].count++;
  177.     else
  178.     {
  179.         table[index].word = word;
  180.         table[index].count = 1;
  181.     }
  182.  
  183.     fullness++;
  184.  
  185.     if (fullness == size)
  186.         new_table();
  187. }
  188. void Hash::new_table()
  189. {
  190.     size_t old_size = size;
  191.     size *= 2;
  192.     node* tmp = new node[size];
  193.     swap(tmp, table);
  194.     for (size_t i = 0; i < old_size; i++)
  195.     {
  196.         table[i].word = tmp[i].word;
  197.         table[i].count = tmp[i].count;
  198.     }
  199.     delete[] tmp;
  200. }
  201. void Hash::most_frequent_words(ofstream& file)
  202. {
  203.     vector <node> tmp_arr;
  204.     for (size_t i = 0; i < size; i++)
  205.         if (table[i].word != "\0")
  206.             tmp_arr.push_back(table[i]);
  207.  
  208.     for (size_t i = 0; i < tmp_arr.size() - 1; i++)
  209.     {
  210.         int max = i;
  211.         for (size_t j = i + 1; j < tmp_arr.size(); j++)
  212.         {
  213.             if (tmp_arr[j].count > tmp_arr[max].count)
  214.                 max = j;
  215.         }
  216.  
  217.         if (max != i)
  218.         {
  219.             int tmp = tmp_arr[i].count;
  220.             string word = tmp_arr[i].word;
  221.             tmp_arr[i].word = tmp_arr[max].word;
  222.             tmp_arr[i].count = tmp_arr[max].count;
  223.             tmp_arr[max].word = word;
  224.             tmp_arr[max].count = tmp;
  225.         }
  226.     }
  227.  
  228.     size_t top_ten = 10;
  229.     if (top_ten > tmp_arr.size())
  230.         top_ten = tmp_arr.size();
  231.  
  232.     for (size_t i = 0; i < top_ten; i++)
  233.     {
  234.         file << tmp_arr[i].word << " = " << tmp_arr[i].count << endl;
  235.     }
  236.  
  237.     file << "\nКоличество коллизий = " << collision << endl;
  238. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement