Двусвязный циклический список. Не могу переделать из функционального в ООП стиль
Написал двусвязный циклический список с "барьерным" элементом. Требуется переделать в ООП стиль. Появились проблемы с доступом к данным. Также я не уверен, что делаю без "костылей". Мои мысли: правильно ли, что я разделил на два класса (1 - одна запись с функциями без управления памятью, 2 - барьерный элемент, функции управления памятью)?; как сделать так, чтобы не использовать гетеры и сетеры?; Можно закинуть в паблик, но тогда пользователь может изменять данные сам; нет ли у меня утечки памяти?. Прошу помочь! Вот мой код в функциональном виде:
#include <iostream>
using namespace std;
struct Node;
void print(Node *list);
void print_back(Node *list);
void print_dbg(Node *list);
void insert(Node *p, Node *t);
void insert_before(Node *q, Node *t);
void init(Node *list);
void list_remove(Node *t);
bool list_empty(Node *list);
Node* push_front(Node *list, int d);
Node * push_back(Node *list, int d);
int list_delete(Node *t);
int pop_front(Node *list);
int pop_back(Node *list);
void clear(Node *list);
struct Node {
int data;
struct Node *prev;
struct Node *next;
};
void print(Node *list) {
for (Node *p = list->next; p != list ;p=p->next) {
cout << p->data << " ";
}
cout << endl;
}
void print_back(Node *list) {
for (Node *p = list->prev; p != list ;p=p->prev) {
cout << p->data << " ";
}
cout << "\n---------------" << endl;
}
void print_dbg(Node *list) {
Node *p = list;
cout << "list: prev=" << p->prev << " " << p << " next=" << p->next << endl;
for (p = list->prev; p != list ;p=p->prev) {
cout << p->data << " prev=" << p->prev << " " << p << " next=" << p->next << endl;
}
}
void insert(Node *p, Node *t) {
Node *q = p->next;
t->prev = p;
t->next = q;
p->next = t;
q->prev = t;
}
void insert_before(Node *q, Node *t) {
insert(q->prev, t);
}
void init(Node *list) {
list->prev = list;
list->next = list;
}
void list_remove(Node *t) {
t->prev->next = t->next;
t->next->prev = t->prev;
}
bool list_empty(Node *list) {
return (list->prev == list && list->next == list);
}
Node* push_front(Node *list, int d) {
Node *pr = (Node *)malloc(sizeof(Node));
pr->data = d;
insert(list, pr);
return pr;
}
Node * push_back(Node *list, int d) {
return push_front(list->prev, d);
}
int list_delete(Node *t) {
list_remove(t);
int d = t->data;
free(t);
return d;
}
int pop_front(Node *list) {
return list_delete(list->next);
}
int pop_back(Node *list) {
return list_delete(list->prev);
}
void clear(Node *list) {
while (!list_empty(list)) {
pop_front(list);
}
}
void test_alloc() {
Node z{};
Node *list = &z;
int test_data1[] = {21, 17, 3};
int test_data2[] = {10, 8};
init(list);
cout << "Empty ";
list_empty(list) ? cout << "YES" << endl : cout << "NO" << endl;
Node *t;
for (auto x : test_data1) {
t = push_front(list, x);
print(list);
cout << "pushed: " << t->data << endl;
} // 3 17 21
for (auto x : test_data2) {
t = push_back(list, x);
print(list);
cout << "pushed: " << t->data << endl;
} // 3 17 21 10 8
cout << "Empty ";
list_empty(list) ? cout << "YES" << endl : cout << "NO" << endl;
t = list->next->next; // 17
int res;
res = list_delete(t);
print(list); // 3 21 10 8
cout << "deleted: " << res << endl; // 17
res = pop_front(list);
print(list); // 21 10 8
cout << "pop front: " << res << endl; // 3
res = pop_back(list);
print(list); // 21 10
cout << "pop back: " << res << endl; // 8
clear(list);
cout << "Empty ";
list_empty(list) ? cout << "YES" << endl : cout << "NO" << endl;
}
void test() {
Node z{}, a{}, b{}, c{}, u{}, w{};
a.data = 3;
b.data = 17;
c.data = 21;
u.data = 10;
w.data = 8;
Node *list = &z;
init(list);
list_empty(list)? cout << "YES" << endl : cout << "NO" << endl; //YES
insert(list, &c);
list_empty(list)? cout << "YES" << endl : cout << "NO" << endl; //NO
print(list); // 21
insert(list, &b);
print(list); // 17 21
insert(list, &a);
print(list); // 3 17 21
print(list); //3 17 21
print_back(list); // 21 17 3
print_dbg(list);
insert(&a, &u);
print(list); //3 10 17 21
print_back(list); // 21 17 10 3
insert_before(&u, &w);
print(list); //3 8 10 17 21
print_back(list); // 21 17 10 8 3
list_remove(&u);
print(list); //3 8 17 21
print_back(list); // 21 17 8 3
list_remove(&w);
print(list); //3 17 21
print_back(list); // 21 17 3
}
int main() {
// test();
test_alloc();
return 0;
}
Вот до чего я дошёл в ООП стиле:
-----
Node.h
-----
class Node {
protected:
Node *prev;
int data;
Node *next;
public:
Node(): data{0}, prev{nullptr}, next{nullptr} {};
explicit Node(int d): data{d}, prev{nullptr}, next{nullptr} {};
[[nodiscard]] int GetData() const;
void setData(int a) {data = a;}
virtual void print(Node *list);
virtual void print_back(Node *list);
virtual void insert(Node *p, Node *t);
virtual void insert_before(Node *q, Node *t);
virtual void init(Node *list);
virtual void list_remove(Node *t);
virtual bool list_empty(Node *list);
};
-----
NodesList.h
-----
#include "Node.h"
class NodesList : public Node {
private:
Node z{};
Node *list = &z;
public:
NodesList* push_front(int d) {
Node *pr = (Node *) malloc(sizeof(Node));
pr->setData(d);
insert(this->list, pr);
return this;
}
NodesList* push_back(int d) {
Node *pr = (Node *) malloc(sizeof(Node));
pr->setData(d);
insert_before(this->list, pr);
return this;
}
NodesList() {
Node::init(this->list);
}
explicit NodesList(int a) {
Node::init(this->list);
push_front(a);
}
void print() {
Node::print(this->list);
}
int list_delete(Node *t) {
list_remove(t);
int d = t->GetData();
free(t);
return d;
}
int pop_front() {
return list_delete(list->next);
}
int pop_back(Node *list) {
return list_delete(list->prev);
}
void clear(Node *list) {
while (!list_empty(list)) {
pop_front(list);
}
}
};
Ответы (1 шт):
Автор решения: Swift - Friday Pie
→ Ссылка
Класс узла Node переусложнен. Ему вообще лучше быть тривиальным.
Переусложненное наследование, классическая путаница между is-a и has-a. Список функционально не является узлом, поэтому не является потомком узла, он является контейнером для того что хранится в узле, а узел - либо внутренний класс, либо интерфейс для "итератора".
И все в итоге можно превратить в шаблон где Т вместо int.
Строго говоря простейший список с барьерным элементом не является циклическим, это вариант двухсвязного списка. Барьерный элемент - фиктивен и перейти от последнего к первому нельзя, как и "разыменовать" его. Зато у нас есть метки начала и конца. Простейший пример:
#include <iostream>
class NodeList {
private:
class Node {
public:
friend NodeList;
using value_type = int;
Node() = default;
Node(const Node&) = default;
Node(Node&&) = default;
Node& operator=(const Node&) = default;
Node& operator=(Node&&) = default;
bool operator !=(const Node& o) const
{ return std::tie(next, prev) != std::tie(o.next,o.prev); }
bool operator ==(const Node& o) const
{ return std::tie(next, prev) == std::tie(o.next,o.prev); }
[[nodiscard]] value_type operator*() { return *value; }
Node operator++(int) { if(!next) throw; Node n = *this; *this = *next; return n; }
Node operator--(int) { if(!prev) throw; Node n = *this; *this = *prev; return n; }
Node& operator++() { if(!next) throw; return *this = *next; }
Node& operator--() { if(!prev) throw; return *this = *prev; }
private:
Node *next, *prev;
value_type* value;
Node(Node * p, Node * n, value_type* v) : next(n), prev(p), value(v) {
p->next = this; n->prev = this;
}
};
Node z = { &z, &z, nullptr };
Node * root = &z;
public:
using value_type = Node::value_type;
using iterator = Node;
iterator begin() { if(!z.next) throw; return *(z.next); }
iterator end() { return z; }
iterator push_back(value_type v) {
iterator *node = new iterator(z.prev, &z, new value_type(v));
return *node;
}
iterator push_front(value_type v) {
iterator *node = new iterator(&z, z.next, new value_type(v));
return *node;
}
};
int main()
{
NodeList r;
r.push_back(3);
r.push_front(2);
r.push_front(1);
for(int i : r) {
std::cout << i << std::endl;
}
}
Тут нужно что-то делать по поводу фрагментации памяти и поддержки аллокаторов. Интерфейс итератора лучше отделить от узла и в нем хранить только указатель на узел. Таким образом не будем копировать весь узел.