Постановка задачи: Реализация работы со справочником предметной области “Магазин”( с…
- User
Постановка задачи: Реализация работы со справочником предметной области “Магазин”( с ключами Артикул, Наименование товара, ИНН поставщика, Дата) с использованием структур данных АВЛ-дерево (по нему распределяем по ключу Наименование товара), состоящее из хеш-таблиц (по ним распределяем по ключу Дата). Общие требования: Оконный интерфейс (среда разработки WinForms) Нельзя использовать универсальные классы-коллекции в System.Collections для реализации заданных структур данных В интерфейсе отображать справочник в табличном виде и окно отладки для вывода структур данных Какой должен быть функционал: Возможность задания в интерфейсе первоначального размера ХТ Работа со справочником:
- загрузка из текстового файла / сохранение в текстовый файл
- добавление
- удаление
- поиск
- просмотр Окно отладки (печать структур данных) Реализация на C++: #include #include #include #include #include #include using namespace std;
struct VendorCode { int vendorcode;
VendorCode(int vc) : vendorcode(vc) {}}; struct ProductName { std::string productname;
ProductName(std::string pn) : productname(pn) {}}; struct TIN { long long int tin;
TIN(long long int t) { long long int n = t; int c = 0; while (n != 0) { c++; n /= 10; } if (c == 12) { tin = t; } else { std::cerr << "Invalid TIN. Setting default TIN to 100000000000" << std::endl; tin = 100000000000; } }}; struct Date { int day; int month; int year;
Date(int d, int m, int y) { bool correct = true; if (y > 2024 || y < 1900) correct = false; else { switch (m) { case 1: case 3: case 5: case 7: case 8: case 10: case 12: if (d < 1 || d > 31) correct = false; break; case 4: case 6: case 9: case 11: if (d < 1 || d > 30) correct = false; break; case 2: if (d < 1 || d > 28) correct = false; break; default: correct = false; break; } } if (correct) { day = d; month = m; year = y; } else { std::cerr << "Invalid date. Setting default date to 1.1.2000." << std::endl; day = 1; month = 1; year = 2000; } }}; struct Sorts { VendorCode vendorcodes; ProductName productnames; TIN tins; Date dates; int firstHash; Sorts(const VendorCode& vc, const ProductName& pn, const TIN& t, const Date& d) : vendorcodes(vc), productnames(pn), tins(t), dates(d), firstHash(0) {} }; struct Cell { Sorts sorts; int flag; int firstHash; Cell() : sorts(VendorCode(0), ProductName(""), TIN(100000000000), Date(1, 1, 2000)), flag(0), firstHash(0) {} }; class HashTable { private: std::vector table; std::vector readFromFile(const std::string& filename) { std::vector sorts; std::ifstream file(filename);
if (file.is_open()) { int vc; std::string pn; int t; int day; int month; int year; while (file >> vc >> pn >> t >> day >> month >> year) { VendorCode vendorcode(vc); ProductName productname(pn); TIN tin(t); Date date(day, month, year); sorts.push_back(Sorts(vendorcode, productname, tin, date)); } file.close(); } else { std::cerr << "Enable open file" << filename << std::endl; } return sorts; } int digitsCount(int n) { int c = 0; while (n != 0) { c++; n /= 10; } return c; } int hash1(int key1, int key2, int key3, int n) { int d = digitsCount(n - 1); int l = digitsCount(key1); int e = (2 * l - d) / 2; int r = pow(10, e); int h1 = (key1 * key1) / r; int mod = pow(10, d); h1 %= mod; l = digitsCount(key2); e = (2 * l - d) / 2; r = pow(10, e); int h2 = (key2 * key2) / r; mod = pow(10, d); h2 %= mod; l = digitsCount(key3); e = (2 * l - d) / 2; r = pow(10, e); int h3 = (key3 * key3) / r; mod = pow(10, d); h3 %= mod; int h = (h1 + h2 + h3) % n; return h; } int hash2(int key1, int key2, int key3, int j, int k, int n) { int hash = (hash1(key1, key2, key3, n) + j * k) % n; return hash; } int collisionInsert(int key1, int key2, int key3, int n, int hash) { int h = hash; int j = 0; int k = 3; do { if (table[h].sorts.dates.day == key1 && table[h].sorts.dates.month == key2 && table[h].sorts.dates.year == key3) return -2; if (table[h].flag != 1) { return h; } else { h = hash2(key1, key2, key3, j, k, n); ++j; } } while (j != n); return -1; } int collisionSearch(int key1, int key2, int key3, int n, int hash) { int h = hash; int j = 0; int k = 3; do { if (table[h].sorts.dates.day == key1 && table[h].sorts.dates.month == key2 && table[h].sorts.dates.year == key3) { return h; } else { h = hash2(key1, key2, key3, j, k, n); ++j; } } while (j != n); return -1; }public: bool isEmpty() { for (int i = 0; i < table.size(); i++) { if (table[i].flag == 1) return false; } return true; } int insertItem(Sorts s) { int n = table.size(); int key1 = s.dates.day; int key2 = s.dates.month; int key3 = s.dates.year; int hash = hash1(key1, key2, key3, n); s.firstHash = hash; if (table[hash].flag != 1) { table[hash].sorts = s; table[hash].firstHash = s.firstHash; table[hash].flag = 1; return 0; } else { int secondhash = collisionInsert(key1, key2, key3, n, hash); if (secondhash == -2) { std::cout << "Item is already in the table." << std::endl; return -2; } else if (secondhash == -1) { std::cout << "Can't insert, table is full." << std::endl; return -1; } else { for (int i = 0; i < table.size(); i++) { if (table[i].sorts.dates.day == key1 && table[i].sorts.dates.month == key2 && table[i].sorts.dates.year == key3) return -2; } table[secondhash].sorts = s; table[secondhash].firstHash = s.firstHash; table[secondhash].flag = 1; return 1; } } } int removeItem(int key1, int key2, int key3) { int n = table.size(); int hash = hash1(key1, key2, key3, n); if (table[hash].sorts.dates.day == key1 && table[hash].sorts.dates.month == key2 && table[hash].sorts.dates.year == key3) { table[hash].flag = 2; std::cout << "Removed" << std::endl; return 0; } else { int secondhash = collisionSearch(key1, key2, key3, n, hash); if (secondhash != -1) { if (table[secondhash].flag == 1) { table[secondhash].flag = 2; std::cout << "Removed" << std::endl; return 1; } } std::cout << "Item is not in the table." << std::endl; return -1; } } HashTable(const std::string readFile, int n) { table.resize(n); std::vector sorts = readFromFile(readFile);
for (int i = 0; i < n; i++) { if (i < sorts.size()) insertItem(sorts[i]); } } HashTable() { } void changeSize(int hashtablesize) { table.resize(hashtablesize); } ~HashTable() { table.clear(); } int searchItem(int key1, int key2, int key3, int searchsteps) { int n = table.size(); int hash = hash1(key1, key2, key3, n); searchsteps++; if (table[hash].flag == 1 && table[hash].sorts.dates.day == key1 && table[hash].sorts.dates.month == key2 && table[hash].sorts.dates.year == key3) { std::cout << "Found: " << hash << " | " << table[hash].sorts.vendorcodes.vendorcode << " " << table[hash].sorts.productnames.productname << " " << table[hash].sorts.tins.tin << " " << table[hash].sorts.dates.day << "." << table[hash].sorts.dates.month << "." << table[hash].sorts.dates.year << " | first hash: " << table[hash].firstHash << " | flag: " << table[hash].flag << std::endl; return searchsteps; } else { searchsteps++; int secondhash = collisionSearch(key1, key2, key3, n, hash); if (secondhash != -1) { if (table[secondhash].flag == 1) { std::cout << "Found: " << hash << " | " << table[hash].sorts.vendorcodes.vendorcode << " " << table[hash].sorts.productnames.productname << " " << table[hash].sorts.tins.tin << " " << table[hash].sorts.dates.day << "." << table[hash].sorts.dates.month << "." << table[hash].sorts.dates.year << " | first hash: " << table[hash].firstHash << " | flag: " << table[hash].flag << std::endl; return searchsteps; } } std::cout << "Item is not in the table." << std::endl; return -1; } } void printTable(std::string key) { std::cout << key << ": " << std::endl; for (int i = 0; i < table.size(); i++) { if (table[i].flag != 1) std::cout << i << " | flag: " << table[i].flag << std::endl; else std::cout << i << " | " << table[i].sorts.vendorcodes.vendorcode << " " << table[i].sorts.productnames.productname << " " << table[i].sorts.tins.tin << " " << table[i].sorts.dates.day << "." << table[i].sorts.dates.month << "." << table[i].sorts.dates.year << " | first hash: " << table[i].firstHash << " | flag: " << table[i].flag << std::endl; } std::cout << std::endl; } void writeFile(std::ofstream& out, std::string key) { out << key << ": " << std::endl; for (int i = 0; i < table.size(); i++) { if (table[i].flag != 1) out << i << " | flag: " << table[i].flag << std::endl; else out << i << " | " << table[i].sorts.vendorcodes.vendorcode << " " << table[i].sorts.productnames.productname << " " << table[i].sorts.tins.tin << " " << table[i].sorts.dates.day << "." << table[i].sorts.dates.month << "." << table[i].sorts.dates.year << " | first hash: " << table[i].firstHash << " | flag: " << table[i].flag << std::endl; } out << std::endl; }};
struct Node { std::string key; HashTable ht; Node* left; Node* right; int balance; };
class Tree { private: Node* root = NULL; std::vector readFromFile(const std::string& filename) { std::vector sorts; std::ifstream file(filename);
if (file.is_open()) { int vc; std::string pn; long long int t; int day; int month; int year; while (file >> vc >> pn >> t >> day >> month >> year) { VendorCode vendorcode(vc); ProductName productname(pn); TIN tin(t); Date date(day, month, year); sorts.push_back(Sorts(vendorcode, productname, tin, date)); } file.close(); } else { std::cerr << "Enable open file" << filename << std::endl; } return sorts; } void add(int vc, std::string pn, long long int t, int d, int m, int y, Node*& p, bool& h, int htsize) // поиск и добавление элемента { VendorCode vendorcode(vc); ProductName productname(pn); TIN tin(t); Date date(d, m, y); Sorts s(vendorcode, productname, tin, date); if (p == NULL) // слова нет в дереве; включить его { p = new Node; h = true; p->key = s.productnames.productname; p->ht.changeSize(htsize); p->ht.insertItem(s); p->balance = 0; p->left = NULL; p->right = NULL; } else if (pn < p->key) { add(vc, pn, t, d, m, y, p->left, h, htsize); if (h) // выросла левая ветвь { switch (p->balance) { case 1: p->balance = 0; h = false; break; case 0: p->balance = -1; break; case -1: // балансировка Node * p1 = p->left; if (p1->balance == -1) // L-поворот { p->left = p1->right; p1->right = p; p->balance = 0; p = p1; } else // LR-поворот { Node* p2 = p1->right; p1->right = p2->left; p2->left = p1; p->left = p2->right; p2->right = p; if (p2->balance == -1) p->balance = 1; else p->balance = 0; if (p2->balance == 1) p1->balance = -1; else p1->balance = 0; p = p2; } p->balance = 0; h = false; break; } } } else if (pn > p->key) { add(vc, pn, t, d, m, y, p->right, h, htsize); if (h == true) // выросла правая ветвь { switch (p->balance) { case -1: p->balance = 0; h = false; break; case 0: p->balance = 1; break; case 1: // балансировка Node * p1 = p->right; if (p1->balance == 1) //R-поворот { p->right = p1->left; p1->left = p; p->balance = 0; p = p1; } else // RL-поворот { Node* p2 = p1->left; p1->left = p2->right; p2->right = p1; p->right = p2->left; p2->left = p; if (p2->balance == 1) p->balance = -1; else p->balance = 0; if (p2->balance == -1) p1->balance = 1; else p1->balance = 0; p = p2; } p->balance = 0; h = false; break; } } } else { p->ht.insertItem(s); h = false; } } void balance1(Node* p, bool& h) { Node* p1, * p2; short b1, b2; if (p == NULL) return; switch (p->balance) { case -1: p->balance = 0; break; case 0: p->balance = 1; h = true; break; case 1: // балансировка p1 = p->right; b1 = p1->balance; if (b1 >= 0) // R-поворот { p->right = p1->left; p1->left = p; if (b1 == 0) { p->balance = 1; p1->balance = -1; h = false; } else { p->balance = 0; p1->balance = 0; } p = p1; } else // RL-поворот { p2 = p1->left; b2 = p2->balance; p1->left = p2->right; p2->right = p1; p->right = p2->left; p2->left = p; if (b2 == 1) p->balance = -1; else p->balance = 0; if (b2 == -1) p1->balance = 1; else p1->balance = 0; p = p2; p2->balance = 0; } } } void balance2(Node* p, bool& h) { Node* p1, * p2; short b1, b2; switch (p->balance) { case 1: p->balance = 0; break; case 0: p->balance = -1; h = true; break; case -1: p1 = p->left; b1 = p1->balance; if (b1 <= 0) // L-поворот { p->left = p1->right; p1->right = p; if (b1 == 0) { p->balance = -1; p1->balance = 1; h = false; } else { p->balance = 0; p1->balance = 0; } p = p1; } else // LR-поворот { p2 = p1->right; b2 = p2->balance; p1->right = p2->left; p2->left = p1; p->left = p2->right; p2->right = p; if (b2 == -1) p->balance = 1; else p->balance = 0; if (b2 == 1) p1->balance = -1; else p1->balance = 0; p = p2; p2->balance = 0; } } } void delet(std::string pn, int d, int m, int y, Node*& p, bool& h) // удаление элемента, выше вспомогательные подпрограммы { Node* q; if (p == NULL) { h = false; } else if (pn < p->key) { delet(pn, d, m, y, p->left, h); if (h) balance1(p, h); // вызов функции балансировки } else if (pn > p->key) { delet(pn, d, m, y, p->right, h); if (h) balance2(p, h); } else { if (p->left == NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { delete p; p = NULL; h = true; } } else if (p->left != NULL && p->right == NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->left; delete p; p = temp; h = true; } } else if (p->left == NULL && p->right != NULL) { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->right; delete p; p = temp; h = true; } } else { p->ht.removeItem(d, m, y); if (p->ht.isEmpty()) { Node* temp = p->left; Node* parent = p; while (temp->right != NULL) { parent = temp; temp = temp->right; } if (parent != p) parent->right = temp->left; else parent->left = temp->left; p->key = temp->key; p->ht = temp->ht; delete temp; h = true; } } if (h) balance1(p, h); // вызов функции балансировки } } void print(Node* t, short hh) // печать дерева { if (t != NULL) { print(t->right, hh + 1); for (int i = 1; i <= hh; i++) cout << " "; t->ht.printTable(t->key); std::cout << std::endl; print(t->left, hh + 1); } } void walk(Node* t, short hh, std::ofstream& out) // обход дерева справа налево и вывод в файл { if (t != NULL) { walk(t->right, hh + 1, out); t->ht.writeFile(out, t->key); walk(t->left, hh + 1, out); } } void search(std::string pn, int d, int m, int y, Node*& p, bool& h, int searchsteps) // поиск элемента { Node* q; if (p == NULL) { cout << "Haven't found." << endl; h = false; } else if (pn < p->key) { searchsteps++; search(pn, d, m, y, p->left, h, searchsteps); } else if (pn > p->key) { searchsteps++; search(pn, d, m, y, p->right, h, searchsteps); } else { searchsteps = p->ht.searchItem(d, m, y, searchsteps); if (searchsteps == -1) std::cout << "Haven't found." << std::endl; else std::cout << "Found in " << searchsteps << " steps." << std::endl; h = false; } }public: void addItem(int vc, std::string pn, long long int t, int d, int m, int y, int htsize) { bool h = false; add(vc, pn, t, d, m, y, root, h, htsize); }
void removeItem(std::string pn, int d, int m, int y) { bool h = false; delet(pn, d, m, y, root, h); } void searchItem(std::string pn, int d, int m, int y) { bool h = false; search(pn, d, m, y, root, h, 0); } void printTree() { print(root, 0); } void writeFile(std::string file) { std::ofstream out(file); walk(root, 0, out); } Tree(){} void readFile(const std::string readFile, int n, int htsize) { std::vector <Sorts> sorts = readFromFile(readFile); for (int i = 0; i < n; i++) { if (i < sorts.size()) addItem(sorts[i].vendorcodes.vendorcode, sorts[i].productnames.productname, sorts[i].tins.tin, sorts[i].dates.day, sorts[i].dates.month, sorts[i].dates.year, htsize); } }};
int main() { int htsize = 10; Tree tree; return 0; }
Проанализируй всё это и скажи, пожалуйста, в отображении справочника в интерфейсе в табличном виде, элементы должны просто идти сверху вниз в порядке добавления, или отсортированы по ключам, типа все с одинаковым наименованием находятся рядом и в том порядке, в котором они в хеш-таблице?
- Assistant
В интерфейсе справочник в табличном виде можно отображать элементы в порядке добавления или отсортированные по ключам. Если отображать элементы в порядке добавления, то они будут идти сверху вниз в порядке добавления. Если отображать отсортированные элементы по ключам, то все элементы с одинаковым наименованием будут расположены рядом и отсортированы в соответствии с ключами.
При использовании хеш-таблицы элементы могут распределяться в таблице неупорядоченно, поэтому отображение элементов в табличном виде может быть нерегулярным. Для отображения элементов отсортированными по ключам можно предварительно их отсортировать перед добавлением в таблицу или реализовать дополнительную сортировку при отображении в интерфейсе.