Цель программы
Я пытаюсь реализовать set ADT . Пока у меня есть интерфейс и некоторые функции, такие как insert () , contains () . Хотя кажется, что моя функция вставки не работает, потому что всякий раз, когда я выводю содержимое набора, он показывает пустой набор.
Чтобы реализовать вставку, я использовал вспомогательную функцию, которая рекурсивно ищет значение в наборе, а если его там нет, он вставит его и вернет истину.
Вот интерфейс класса set в set.h:
#include <iostream>
class set {
// Private type
struct treenode {
int value;
treenode* left;
treenode* right;
treenode(int val)
: value(val),
left(nullptr),
right(nullptr)
{ }
};
size_t set_size;
treenode* root;
// Recursive function that creates and returns an exact
// copy of the tree structure rooted at original
static treenode* copynodes(treenode* original);
// Recursive function that deallocates all of the
// nodes in the tree structure rooted at node
static void deallocatenodes(treenode* node);
// Recursive function called by print to output the
// values using in-order traversal
static void printhelper(std::ostream &out, treenode* node){
if (node != nullptr) {
if (node->left != nullptr) {
printhelper(out, node->left);
out << ", ";
}
out << node->value;
if (node->right != nullptr) {
out << ", ";
printhelper(out, node->right);
}
}
}
static bool containshelper(int i, treenode *node);
static bool inserthelper(int i, treenode *node);
public:
// Default constructor
set() : set_size(0), root(nullptr) { }
// Copy constructor
set(const set &s) : set_size(s.set_size), root(nullptr)
{
root = copynodes(s.root);
}
// Initializer list constructor
set(std::initializer_list<int> init) : set_size(0), root(nullptr)
{
for (auto el : init) {
insert(el);
}
}
// Copy assignment
set& operator=(const set &s) {
if (&s != this) {
deallocatenodes(root);
root = copynodes(s.root);
set_size = s.set_size;
}
return *this;
}
// Returns true if the value i is in the ordered set
bool contains(int i) const;
// If the value i is not in the set,
// insert it and return true;
bool insert(int i);
// Remove everything from the set
void clear();
// Returns the number of items in the set
size_t size() const;
// Returns whether or not the set is currently empty
bool empty() const;
// Print out the contents of the set, in order from smallest to largest
void print(std::ostream &out) const {
out << "{";
printhelper(out, root);
out << "}";
}
// Destructor
~set() {
deallocatenodes(root);
}
};
inline std::ostream& operator<<(std::ostream &out, const set &s) {
s.print(out);
return out;
}
Реализация функций
Вот что Я реализовал в наборе. cpp:
#include "set.h"
#include <iostream>
set::treenode* set::copynodes(treenode *original) {
if(original == nullptr) {
return nullptr;
}
treenode *copiedTree = new treenode(original->value);
copiedTree->left = copynodes(original->left);
copiedTree->right = copynodes(original->right);
return copiedTree;
}
void set::deallocatenodes(set::treenode *node) {
if(node != nullptr) {
deallocatenodes(node->left);
deallocatenodes(node->right);
delete node;
}
}
bool set::containshelper(int i, set::treenode *node) {
if (node == nullptr)
return false;
// i found
else if (node->value == i)
return true;
// Recursively search for i
else if (i < node->value)
return (containshelper(i, node->left));
else
return (containshelper(i, node->right));
}
bool set::inserthelper(int i, set::treenode *node) {
if(node == nullptr) {
node = new treenode(i);
return true;
} else if(i == node->value) {
return false;
} else {
if(i < node->value){
return (inserthelper(i, node->left));
} else if(i > node->value){
return (inserthelper(i, node->right));
}
return false;
}
}
bool set::contains(int i) const {
return containshelper(i, root);
}
bool set::insert(int i) {
if(inserthelper(i, root) == true) {
set_size++;
return true;
} else {
return false;
}
}
void set::clear() {
set_size = 0;
deallocatenodes(root);
}
size_t set::size() const {
return set_size;
}
bool set::empty() const {
return (set_size == 0);
}
Тестирование реализации
Тестовый файл main. cpp выглядит следующим образом:
#include "set.h"
#include <iostream>
void output(const set& s) {
std::cout << "SET OUTPUT: " << std::endl;
std::cout << s.size() << " " << s.empty() << " " << s << std::endl;
std::cout << "END OF OUTPUT." << std::endl;
}
int main() {
set s1;
output(s1);
set s2 = {44, 22, 11, 33, 55};
output(s2);
set s3(s2);
output(s3);
for (int i = 99; i > 0; i = i - 11) {
std::cout << i << " " << s2.insert(i) << " " << s2.contains(i) << "; ";
}
std::cout << std::endl;
output(s2);
for (int i = 15; i < 100; i = i + 5) {
std::cout << i << " " << s2.insert(i) << " " << s2.contains(i) << "; ";
}
std::cout << std::endl;
output(s2);
output(s3);
s1 = s2;
output(s1);
s1.clear();
output(s1);
output(s2);
output(s3);
s1.insert(123);
s1.insert(234);
s1.insert(98);
output(s1);
std::cout << "Done." << std::endl;
}
Вывод программы
Когда я компилирую и запускаю, вывод будет:
SET OUTPUT:
0 1 {}
END OF OUTPUT.
SET OUTPUT:
5 0 {}
END OF OUTPUT.
SET OUTPUT:
5 0 {}
END OF OUTPUT.
99 1 0; 88 1 0; 77 1 0; 66 1 0; 55 1 0; 44 1 0; 33 1 0; 22 1 0; 11 1 0;
SET OUTPUT:
14 0 {}
END OF OUTPUT.
15 1 0; 20 1 0; 25 1 0; 30 1 0; 35 1 0; 40 1 0; 45 1 0; 50 1 0; 55 1 0; 60 1 0; 65 1 0; 70 1 0; 75 1 0; 80 1 0; 85 1 0; 90 1 0; 95 1 0;
SET OUTPUT:
31 0 {}
END OF OUTPUT.
SET OUTPUT:
5 0 {}
END OF OUTPUT.
SET OUTPUT:
31 0 {}
END OF OUTPUT.
SET OUTPUT:
0 1 {}
END OF OUTPUT.
SET OUTPUT:
31 0 {}
END OF OUTPUT.
SET OUTPUT:
5 0 {}
END OF OUTPUT.
SET OUTPUT:
3 0 {}
END OF OUTPUT.
Done.
Program ended with exit code: 0
Видно, что наборы не имеют элементов, и размер некоторых из них неверен. Например, установите 2 после l oop с помощью функции insert () , должно быть 9 элементов, но их 14, что означает, что некоторые из них были дублированы.
Я пытался визуализировать операции, выполняемые над наборами, используя BST на бумаге, но не мог найти, в чем проблема.