Как на основе кольцевого однонаправленного списка сделать двусвязный?
Написал код где можно работать с данными из файла (что-то похожее на БД) на основе кольцевого однонаправленного списка, но нужно использовать двунаправленный, не пойму как это сделать в моем коде. Понимаю, что вопрос звучит глупо, но на лекции мы рассматривали первый вид списков, а второй мне тяжело реализовать в этом коде.
Надеюсь на чью-либо помощь
List::List() {
head = nullptr;
tail = nullptr;
Size = 0;
}
List::~List() {
Node* temp{};
std::ofstream f;
f.open("Data.txt");
if (f.is_open())
{
if (head != nullptr)
{
std::string buf{};
temp = head;
for (int i{ 0 }; i < Size; i++)
{
Combine(temp, &buf);
f << buf << std::endl;
temp = temp->pNext;
}
std::cout << "Данные успешно загружены в файл" << std::endl;
}
else
{
std::cout << "Список пуст, нечего записывать" << std::endl;
}
}
else
{
std::cout << "Не удалось записать данные в файл" << std::endl;
}
f.close();
while (Size)
{
pop_front();
}
std::cout << "Список успешно очищен" << std::endl;
}
void List::Combine(Node* node, std::string* buf) {
*buf = node->name + node->offers + node->all_offers;
}
void List::Separate(std::string str, std::string data[]) { //разделитель
int j{ 0 };
for (int i{ 0 }; i < str.size(); i++)
{
if (str[i] != ';' && str[i] != '\t')
{
if (j != 0 and str[i] == ' ')
{
continue;
}
data[j] += str[i];
}
else if (str[i] == ';')
{
j++;
}
}
}
void List::Add_Data(std::string data[]) {
Node* add = new Node;
add->name = data[0] + "; ";
data[0] = "";
add->offers = data[1] + "; ";
data[1] = "";
add->all_offers = data[2];
data[2] = "";
if (head == nullptr)
{
head = tail = add;
add->pNext = head;
}
else
{
add->pNext = head;
tail->pNext = add;
tail = add;
}
Size++;
}
void List::List_input() {
std::ifstream f;
f.open("Data.txt");
if (f.is_open())
{
std::string str{};
std::string data[3]{};
while (!f.eof())
{
getline(f, str);
if (str == "")
{
continue;
}
Separate(str, data);
Add_Data(data);
}
f.close();
}
else
{
std::cout << "Не удалось загрузить список" << std::endl;
exit(-1);
}
}
void List::Show() {
if (head != nullptr)
{
std::string buf{};
Node* temp{ head };
for (int i{ 0 }; i < Size; i++)
{
Combine(temp, &buf);
std::cout << buf << std::endl;
temp = temp->pNext;
}
std::cout << "\n";
}
else
{
std::cout << "Пусто )=" << std::endl;
}
}
void List::pop_front() {
Node* temp{ head };
head = head->pNext;
delete temp;
Size--;
}
void List::Set_default() {
Node* temp{ head };
for (int i{ 0 }; i < Size; i++)
{
temp->name = "Name; "; temp->offers = "0; "; temp->all_offers = "0";
temp = temp->pNext;
}
std::cout << "Сброс данных успешно выполнен." << std::endl;
}
int List::DeleteElement() {
if (Size == 0) {
std::cout << "Список пуст." << std::endl;
return 0;
}
int n;
std::cout << "Какой элемент хотите удалить?(Всего элементов " << Size << ").\n";
while (!(std::cin >> n) || std::cin.peek() != '\n' || n == 0 || n > Size)
{
std::cin.clear();
while (std::cin.get() != '\n');
std::cout << "Ошибка ввода\n" << std::endl;
}
n--;
Node* temp = head, * helping = head;
for (int i = 0; i < n; i++)
{
helping = temp; // предыдущее значение temp
temp = temp->pNext;
}
if (temp == head) // если элемент который надо удалить первый
{
head = temp->pNext;
}
else
{
helping->pNext = temp->pNext;
}
std::cout << "Элемент был удалён." << std::endl;
free(temp);
Size--; // уменьшаем размер списка
return 0;
}
Ответы (1 шт):
У вас есть класс узла, в нем есть указатель на следующий элемент списка. Нужно добавить указатель на предыдущий элемент списка. И при всех операциях в списке, менять оба указателя. Из class List поле Node* tail можно убрать - в двунаправленном списке можно двигаться в оба направления, достаточно одного указателя на начало. Тогда указатель на конец будет head->pPrev.
class Node
{ public:
Node *pNext;
Node *pPrev; // нужно добавить
... // какие-то данные
}