Advertisement
HabKaffee

Untitled

Nov 4th, 2021
858
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ///*
  2. //#include <iostream>
  3. //#include <vector>
  4. //#include <typeinfo>
  5. //#include <string>
  6. //
  7. //// Предложить пользователю ввести последовательность целых чисел и найти среди них большее.
  8. //// Если среди последовательности было отрицательное число или вовсе не число предложить снова ввести последовательность
  9. //
  10. //int a = 0;
  11. //
  12. //struct A {
  13. //    int f;
  14. //    int j;
  15. //};
  16. //
  17. //int main() {
  18. //    std::cout << "Enter a subsequence of positive integers, enter 'exit' to stop input:" << std::endl;
  19. //    std::vector <int> sub;
  20. //    std::string x;
  21. //    unsigned max = 0;
  22. //    while (true) {
  23. //        std::cin >> x;
  24. //        if (x == "exit") {
  25. //            break;
  26. //        }
  27. //        int tmp = 0;
  28. //        try {
  29. //            tmp = std::stoi(x);
  30. //        } catch (std::invalid_argument) {
  31. //            std::cout << "Entered value isn't positive integer. Try again" << std::endl;
  32. //            std::cin.clear();
  33. //            std::cin.ignore(32767, '\n');
  34. //            sub.resize(0);
  35. //            max = -1;
  36. //        }
  37. //
  38. //        if (std::cin.fail() || tmp < 0) {
  39. //            std::cin.clear();
  40. //            std::cin.ignore(32767, '\n');
  41. //            std::cout << "Entered value isn't positive integer. Try again " << std::endl;
  42. //            sub.clear();
  43. //            max = -1;
  44. //        }
  45. //        else {
  46. //            std::cin.ignore(32767, '\n');
  47. //            sub.push_back(tmp);
  48. //            if (max < tmp) {
  49. //                max = tmp;
  50. //            }
  51. //        }
  52. //    }
  53. //    std::cout << "\nEntered subsequance is:" << std::endl;
  54. //    for (int i = 0; i < sub.size(); ++i) {
  55. //        std::cout << sub[i] << " ";
  56. //    }
  57. //    std::cout << "\nMaximum = " << max << std::endl;
  58. //    return 0;
  59. //}*/
  60. //
  61. //
  62. //#include <cstring>
  63. //#include <iostream>
  64. //#include <climits>
  65. //
  66. //class Deq {
  67. //private:
  68. //    int beg = 65536;
  69. //    int end = 65536;
  70. //    int array[131072] = {};
  71. //public:
  72. //    Deq() {
  73. //        for (unsigned i = 0; i < 131072; ++i) {
  74. //            array[i] = INT_MIN;
  75. //        }
  76. //    }
  77. //    void PushBack(int n) {
  78. //        array[++end] = n;
  79. //        std::cout << "ok" << std::endl;
  80. //    }
  81. //    void PushFront(int n) {
  82. //        array[--beg] = n;
  83. //        std::cout << "ok" << std::endl;
  84. //    }
  85. //    void PopFront() {
  86. //        if (end - beg <= 0) {
  87. //            std::cout << "error" << std::endl;
  88. //        } else {
  89. //            std::cout << array[beg] << std::endl;
  90. //            beg++;
  91. //        }
  92. //    }
  93. //    void PopBack() {
  94. //        if (end - beg <= 0) {
  95. //            std::cout << "error" << std::endl;
  96. //        } else {
  97. //            std::cout << array[end] << std::endl;
  98. //            end--;
  99. //        }
  100. //    }
  101. //    void Front() {
  102. //        if ((end - beg <= 0) || (array[beg] == INT_MIN)) {
  103. //            std::cout << "error" << std::endl;
  104. //        } else {
  105. //            std::cout << array[beg] << std::endl;
  106. //        }
  107. //    }
  108. //    void Back() {
  109. //        if ((end - beg <= 0) || (array[end] == INT_MIN)) {
  110. //            std::cout << "error" << std::endl;
  111. //        } else {
  112. //            std::cout << array[end] << std::endl;
  113. //        }
  114. //    }
  115. //    void Size() {
  116. //        std::cout << end - beg << std::endl;
  117. //    }
  118. //    void Clear() {
  119. //        beg = 65536;
  120. //        end = 65536;
  121. //        for (unsigned i = 0; i < 131072; ++i) {
  122. //            array[i] = INT_MIN;
  123. //        }
  124. //        std::cout << "ok" << std::endl;
  125. //    }
  126. //};
  127. //int main() {
  128. //    int number_of_commands = 0;
  129. //    std::cin >> number_of_commands;
  130. //    Deq A;
  131. //    int n;
  132. //    char push_f_command[] = "push_front";
  133. //    char push_b_command[] = "push_back";
  134. //    char pop_f_command[] = "pop_front";
  135. //    char pop_b_command[] = "pop_back";
  136. //    char front_command[] = "front";
  137. //    char back_command[] = "back";
  138. //    char size_command[] = "size";
  139. //    char clear_command[] = "clear";
  140. //    char exit_command[] = "exit";
  141. //    char *command = new char[11];
  142. //    for (int i = 0; i < number_of_commands; i++) {
  143. //        std::cin >> command;
  144. //        if (!strcmp(command, push_f_command)) {
  145. //            std::cin >> n;
  146. //            A.PushFront(n);
  147. //        }
  148. //        if (!strcmp(command, push_b_command)) {
  149. //            std::cin >> n;
  150. //            A.PushBack(n);
  151. //        }
  152. //        if (!strcmp(command, pop_f_command)) {
  153. //            A.PopFront();
  154. //        }
  155. //        if (!strcmp(command, pop_b_command)) {
  156. //            A.PopBack();
  157. //        }
  158. //        if (!strcmp(command, front_command)) {
  159. //            A.Front();
  160. //        }
  161. //        if (!strcmp(command, back_command)) {
  162. //            A.Back();
  163. //        }
  164. //        if (!strcmp(command, size_command)) {
  165. //            A.Size();
  166. //        }
  167. //        if (!strcmp(command, clear_command)) {
  168. //            A.Clear();
  169. //        }
  170. //        if (!strcmp(command, exit_command)) {
  171. //            std::cout << "bye";
  172. //            break;
  173. //        }
  174. //        for (size_t j = 0; j < 11; ++j) {
  175. //            command[j] = '\0';
  176. //        }
  177. //    }
  178. //    delete[] command;
  179. //    return 0;
  180. //}
  181.  
  182.  
  183. #include <iostream>
  184. #include <cmath>
  185. #include <string>
  186. #include <list>
  187. #include <vector>
  188. #include <iterator>
  189. #include <algorithm>
  190.  
  191. const short x = 263;
  192. const long long p = 1'000'000'007;
  193.  
  194. using hash_chains = std::vector<std::list<std::string>>;
  195.  
  196. long long HashingFunction(const std::string &str, int size_table) {
  197.    size_t len = str.size();
  198.    long long h = 0;
  199.    for (int i = 0; i < len; ++i) {
  200.        h = ((((long long)(static_cast<int> (str[i]) * pow(x, i))) % p) + p) % p;
  201.    }
  202.    h = ((h % size_table) + size_table) % size_table;
  203.    std::cout << h << std::endl;
  204.    return h;
  205. }
  206.  
  207. void add(hash_chains &table, const std::string &str, const int size_table) {
  208.    long long hash = HashingFunction(str, size_table);
  209.    table[hash].push_front(str);
  210. }
  211.  
  212. void del(hash_chains &table, const std::string &str, const int size_table) {
  213.    long long hash = HashingFunction(str, size_table);
  214.    auto it = std::find(table[hash].begin(), table[hash].end(), str);
  215.    // for (auto &item) { // for (it = s.begin(), it < s.end(), ++i)
  216.    //      if ()
  217.    // }
  218.    it = table[hash].erase(it);
  219.  
  220. }
  221.  
  222. void find(hash_chains &table, const std::string &str, const int size_table) {
  223.    long long hash = HashingFunction(str, size_table);
  224.    auto it = std::find(table[hash].begin(), table[hash].end(), str);
  225.    if (it != table[hash].end()) {
  226.        std::cout << "yes" << std::endl;
  227.    }
  228.    else {
  229.        std::cout << "end" << std::endl;
  230.    }
  231. }
  232.  
  233. void check(hash_chains &table, long long index) {
  234.    for (auto &item : table[index]) {
  235.        std::cout << item << " ";
  236.    }
  237.    std::cout << std::endl;
  238. }
  239.  
  240. int main() {
  241.    int size_table(0), command_amount(0);
  242.    std::cout << "Enter size_table - a size of hash table: ";
  243.    std::cin >> size_table;
  244.    std::cout << "Enter command_amount - a quantity of requests: ";
  245.    std::cin >> command_amount;
  246.  
  247.    std::vector<std::list<std::string>> table(size_table, std::list<std::string>(command_amount));
  248.    std::cout << std::endl;
  249.    const std::string command_add = "add";
  250.    const std::string command_del = "del";
  251.    const std::string command_find = "find";
  252.    const std::string command_check = "check";
  253.  
  254.    std::string entered_command;
  255.    std::string entered_str;
  256.    long long entered_val = 0;
  257.  
  258.    for (int i = 0; i < command_amount; ++i) {
  259.        std::cin >> entered_command;
  260.        if (entered_command == command_add) {
  261.            std::cin >> entered_str;
  262.            add(table, entered_str, size_table);
  263.        }
  264.        else if (entered_command == command_del) {
  265.            std::cin >> entered_str;
  266.            del(table, entered_str, size_table);
  267.        }
  268.        else if (entered_command == command_find) {
  269.            std::cin >> entered_str;
  270.            find(table, entered_str, size_table);
  271.        }
  272.        else if (entered_command == command_check) {
  273.            std::cin >> entered_val;
  274.            check(table, entered_val);
  275.            entered_val = 0;
  276.        }
  277.        entered_command.clear();
  278.        entered_str.clear();
  279.    }
  280.  
  281.    table.clear();
  282.    return 0;
  283. }
Advertisement
RAW Paste Data Copied
Advertisement