6. Текст программы
Kursovaya_4s.cpp (основная программа) #include <fstream>
#include <vector>
#include <clocale>
#include "RBST.h"
using namespace std;
void bubblesort(std::vector<Newspaper>& arr) {
size_t n = arr.size();
for (size_t i = 0; i < n - 1; ++i) {
for (size_t j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
void selectionsort(std::vector<Newspaper>& arr) {
size_t n = arr.size();
for (size_t i = 0; i < n - 1; ++i) {
size_t minIndex = i;
for (size_t j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
std::swap(arr[i], arr[minIndex]);
}
}
void insertsort(std::vector<Newspaper>& np)
{
for (size_t i = 1; i < np.size(); i++)
for (size_t j = i; j > 0 && np[j - 1] > np[j]; j--)
std::swap(np[j - 1], np[j]);
}
//-----------------------------------------------------------------------------------------------------------------------------------------//
int main() {
setlocale(LC_ALL, "Russian"); // на всякий
std::vector<Newspaper> newspapers;
// Чтение данных из текстового файла
std::ifstream inputFile("newspapers.txt");
if (!inputFile) {
std::cout << "Ошибка открытия файла." << std::endl;
return 1;
}
for (int i = 0; i < 5; i++) { //input to temp file
Newspaper temp;
inputFile >> temp;
newspapers.push_back(temp);
}
RBS_Tree *tree = nullptr;
for (Newspaper np : newspapers)
tree = RBST::insert(tree, np);
if (RBST::find(tree, newspapers[0]))
std::cout << "Found!\n";
else
std::cout << "That sucks :(\n";
cout << "choose 1, 2 or 3. 1 is Bubble Sort, 2 is Selection Sort, 3 is Insertion Sort. Your choice: ";
int x;
cin >> x;
switch (x)
{
case 1:
bubblesort(newspapers);
break;
case 2:
selectionsort(newspapers);
break;
case 3:
insertsort(newspapers);
break;
default:
cout << "choose 1, 2 or 3";
break;
}
for (Newspaper np : newspapers) { // console output
std::cout << np << "\n";
}
return 0;
}
RBST.cpp #include "RBST.h"
namespace RBST
{
int getsize(RBS_Tree* p)
{
if (!p) return 0;
return p->size;
}
void fixsize(RBS_Tree* p)
{
p->size = getsize(p->left) + getsize(p->right) + 1;
}
RBS_Tree* find(RBS_Tree* p, Newspaper& k)
{
if (!p) return 0;
if (k == p->key)
return p;
if (k < p->key)
return find(p->left, k);
else
return find(p->right, k);
}
RBS_Tree* insert(RBS_Tree* p, Newspaper& k)
{
if (!p) return new RBS_Tree(k);
if (rand() % (p->size + 1) == 0)
return insertroot(p, k);
if (p->key > k)
p->left = insert(p->left, k);
else
p->right = insert(p->right, k);
fixsize(p);
return p;
}
RBS_Tree* rotateright(RBS_Tree* p)
{
RBS_Tree* q = p->left;
if (!q) return p;
p->left = q->right;
q->right = p;
q->size = p->size;
fixsize(p);
return q;
}
RBS_Tree* rotateleft(RBS_Tree* q)
{
RBS_Tree* p = q->right;
if (!p) return q;
q->right = p->left;
p->left = q;
p->size = q->size;
fixsize(q);
return p;
}
RBS_Tree* insertroot(RBS_Tree* p, Newspaper& k)
{
if (!p) return new RBS_Tree(k);
if (k < p->key)
{
p->left = insertroot(p->left, k);
return rotateright(p);
}
else
{
p->right = insertroot(p->right, k);
return rotateleft(p);
}
}
RBS_Tree* join(RBS_Tree* p, RBS_Tree* q)
{
if (!p) return q;
if (!q) return p;
if (rand() % (p->size + q->size) < p->size)
{
p->right = join(p->right, q);
fixsize(p);
return p;
}
else
{
q->left = join(p, q->left);
fixsize(q);
return q;
}
}
RBS_Tree* remove(RBS_Tree* p, Newspaper& k)
{
if (!p) return p;
if (p->key == k)
{
RBS_Tree* q = join(p->left, p->right);
delete p;
return q;
}
else if (k < p->key)
p->left = remove(p->left, k);
else
p->right = remove(p->right, k);
return p;
}
}
Newspaper.h
#include <iostream>
using namespace std;
struct Newspaper {
string name{}; // Название газеты
int index{}; // Индекс издания
string editor{}; // ФИО редактора
int price{}; // Цена экземпляра газеты
bool operator>(Newspaper& np)
{
return name > np.name;
}
bool operator<(Newspaper& np)
{
return name < np.name;
}
bool operator==(Newspaper& np)
{
if (name == np.name && index == np.index && editor == np.editor && price == np.price)
return true;
return false;
}
bool operator>=(Newspaper& np)
{
return name >= np.name;
}
};
RBST.h
#pragma once
#include <iostream>
#include <string>
struct Newspaper {
std::string name{}; // Название газеты
int index{}; // Индекс издания
std::string editor{}; // ФИО редактора
int price{}; // Цена экземпляра газеты
bool operator>(Newspaper& np)
{
return name > np.name;
}
bool operator<(Newspaper& np)
{
return name < np.name;
}
bool operator==(Newspaper& np)
{
if (name == np.name && index == np.index && editor == np.editor && price == np.price)
return true;
return false;
}
bool operator>=(Newspaper& np)
{
return name >= np.name;
}
};
inline std::ostream& operator<<(std::ostream& out, Newspaper& np)
{
return out
<< "Newspaper name: " << np.name << '\n'
<< "Newspaper index: " << np.index << '\n'
<< "Newspaper editor: " << np.editor << '\n'
<< "Newspaper price: " << np.price << '\n';
}
inline std::istream& operator>>(std::istream& in, Newspaper& np)
{
std::getline(in >> std::ws, np.name);
in >> np.index;
std::getline(in >> std::ws, np.editor);
return in >> np.price;
}
struct RBS_Tree // структура дерева
{
Newspaper key;
int size;
RBS_Tree* left;
RBS_Tree* right;
RBS_Tree(Newspaper k) : key(k), left(0), right(0), size(1) {}
};
namespace RBST
{
RBS_Tree* find(RBS_Tree*, Newspaper&);
RBS_Tree* insert(RBS_Tree*, Newspaper&);
int getsize(RBS_Tree*);
RBS_Tree* insertroot(RBS_Tree*, Newspaper&);
RBS_Tree* join(RBS_Tree*, RBS_Tree*);
RBS_Tree* remove(RBS_Tree*, Newspaper&);
}