Лабораторная 2
.pdfПриложение 2
Программа для построения хэш-таблицы, двоичного дерева, поиска
элементов в них и вывода их статистик:
Файл main.c:
#include <iostream> #include <fstream> #include <list> #include "hash.h" #include "binary_tree.h"
Using namespace std; int main() {
tree *Tree = new tree;
Node *hash = new Node[hash_number];
CreateHash(hash);
ifstream file(R"( C:\Users\monst\Desktop\аисд\ ads_lab2.dat)");
if (!file.is_open()) {
cout << "File is not opened!" << endl; return 1;
}
int art[100000], creator[100000], article; float price[100000], s_price;
for (int i = 0; i < 100000; i++) {
file >> art[i] >> price[i] >> creator[i]; if (i == 0) {
CreateTree(Tree, price[i], art[i], creator[i]);
AddToHash(hash, art[i], price[i], creator[i]);
} else {
AddToTree(Tree, price[i], art[i], creator[i]);
AddToHash(hash, art[i], price[i], creator[i]);
}
}
int result[39]{0}; stats(Tree, result);
cout << "Enter the price of the element you want to find in a tree: " << endl;
cin >> s_price; SearchInTree(Tree, s_price);
cout << "Enter the article of an element you want to find in hash: " << endl;
cin >> article;
if (SearchInHash(hash, article) == 1) {
cout << "There isn't any product with this article" <<
endl;
}
int results[6]{0}; stats(hash,results); stats(Tree,result);
cout<<"Statistics of hash: "<< endl; for(int i: results){
cout<<i<< endl;
}
cout<<"Statistics of a tree: "<< endl; cout<< endl;
for(int i: result){ cout<<i<< endl;
}
return 0;
}
Файл binary_tree.c:
#include <iostream> #include "binary_tree.h"
tree* CreateTree(tree* Tree,float key,int art,int creator){ Tree->left= nullptr;
Tree->right=nullptr;
Tree->key=key;
Tree->creator=creator;
Tree->atr=art;
Tree->height=1;
return Tree;
}
tree* AddToTree(tree* Tree,float key,int art,int creator){ tree* Tree1=new tree();
Tree1->key=key; Tree1->creator=creator; Tree1->atr=art; if(Tree!=nullptr){
if(Tree1->key<Tree->key) {
if (Tree->left == nullptr) { Tree->left = Tree1; Tree1->height=Tree->height+1;
}
else(AddToTree(Tree->left,key,art,creator));
}
if(Tree1->key>Tree->key){
if (Tree->right == nullptr) { Tree->right = Tree1; Tree1->height=Tree->height+1;
}
else(AddToTree(Tree->right,key,art,creator));
}
if(Tree1->key==Tree->key){
// cout<<Tree->key<<" "<<key<< endl; Tree->middle.push_back(Tree1);
}
}
Tree1->left=nullptr; Tree1->right=nullptr; return Tree;
} |
|
tree* SearchInTree(tree* |
Tree,float key) { |
if (Tree == nullptr) |
{ |
return Tree; |
|
} else { |
|
if (Tree->key == |
key) { |
cout << Tree->atr << " " << Tree->key << " " << Tree->creator << "\n";
if (!Tree->middle.empty()) {
for (tree *i: Tree->middle){
cout << i->atr << " " << i->key << " " <<
i->creator << "\n";
}
}
}
if (key > Tree->key) { if(Tree->right==nullptr){
cout<<"There is no such element with this
price"<< endl;
}
else return SearchInTree(Tree->right, key);
}
if (key < Tree->key) { if(Tree->left==nullptr){
cout<<"There is no such element with this
price"<< endl;
}
else return SearchInTree(Tree->left, key);
}
return Tree;
}
}
int* stats(tree* Tree,int result[40]) {
if (Tree->left != nullptr && Tree->right != nullptr) { result[Tree->height]++;
stats(Tree->left,result); stats(Tree->right,result);
}
else {
if (Tree->left != nullptr) {
{
result[Tree->height]++;
stats(Tree->left,result);
}
}
if (Tree->right != nullptr) {
{
result[Tree->height]++; stats(Tree->right, result);
}
}
}
return result;
}
Файл binary_tree.h:
#ifndef NEW_LAB_2_AISD_BINARY_TREE_H #define NEW_LAB_2_AISD_BINARY_TREE_H #include <list>
#include <iostream> using namespace std; struct tree{
tree* left; tree* right;
list<tree*> middle; float key;
int atr;
int creator; int height;
};
tree* CreateTree(tree* Tree,float key,int art,int creator); tree* AddToTree(tree* Tree,float key,int art,int creator); tree* SearchInTree(tree* Tree,float key);
int* stats(tree* Tree,int result[40]); #endif //NEW_LAB_2_AISD_BINARY_TREE_H
Файл hash.c:
#include "hash.h" #include <iostream>
Node* CreateHash(Node n[hash_number]) {
for (int i = 0; i < hash_number; i++) { n[i].article = 0;
n[i].owner = 0; n[i].price = 0; n[i].current=nullptr; n[i].next=nullptr;
}
return n;
}
Node* AddToHash(Node n[hash_number],int article,float price,int owner) {
int index = article % hash_number; Node* temp=new Node();
if (n[index].list.empty()) { n[index].article = article; n[index].owner = owner; n[index].list.push_back(&n[index]); n[index].current=n[index].list.front(); n[index].next=n[index].current;
}
if (!n[index].list.empty()) { temp->article = article; temp->owner = owner; temp->price = price; n[index].list.push_back(temp);
temp->current=n[index].list.back(); for (Node *i: n[index].list) {
if ((i + 1) != nullptr) { i->next = i + 1;
}
else{
i->next = i;
}
}
}
return n;
}
int SearchInHash(Node n[hash_number], int article) { int index = article%hash_number; if(n[index].current!=nullptr){
for(Node* i:n[index].list) {
if (i->article == article) { cout<<i->article<<" "<<i->price<<" "<<i-
>owner<< endl;
}
if(i==n[index].list.back()&&i->article!=article){ cout<<"There is no such article!";
}
}
return 0;
}
else{
return 1;
}
}
int* stats(Node n[hash_number],int result[6]) { cout<< endl;
for(int i=0;i<hash_number;i++){ result[n[i].list.size()]++;
}
return result;
}
Файл hash.h:
#ifndef NEW_LAB_2_AISD_HASH_H
#define NEW_LAB_2_AISD_HASH_H #define hash_number 35129 #include <list>
struct Node{
int article; float price; int owner;
list<Node*> list; Node* current; Node* next;
};
Node* CreateHash(Node n[hash_number]);
int* stats(Node n[hash_number],int result[6]);
Node* AddToHash(Node n[hash_number],int article,float price,int owner);
int SearchInHash(Node n[hash_number], int article); #endif //NEW_LAB_2_AISD_HASH_H
Вывод
Проведя лабораторную работу, мы ознакомились с алгоритмами поиска в линейных структурах: двоичный (бинарный) поиск, двоичное дерево поиска и хеш-таблицы.