The task is to make a doubly linked list in which class methods add / remove a list item, sort the list, display list items from the beginning / end, search for an item in the list. In the code below, the implementation of this, without a search, I can not get to how to implement it.

#include "stdafx.h" #include <iostream> using namespace std; #include <algorithm> #include <vector> #include <list> #include <locale.h> #include <iterator> #include <stack> struct Node //Структура являющаяся звеном списка { int x; //Значение x будет передаваться в список Node *Next, *Prev; //Указатели на адреса следующего и предыдущего элементов списка }; class List { Node *Head, *Tail, *cur; Node *Next, *Prev;//Указатели на адреса начала списка и его конца public: List() :Head(NULL), Tail(NULL) {}; //Инициализируем адреса как пустые ~List(); void Show(); void Delete_end(); void empty() { if (Head == NULL) cout << "Список пуст" << endl; else cout << "Список не пуст" << endl; } void Delete_first(); void Add(); }; class iterator : public List { friend Node; public: iterator() {}; iterator& operator++() { Node*temp; // Node=Node->Next; return *this; } }; List::~List() { while (Head) //Пока по адресу на начало списка что-то есть { Tail = Head->Next; //Резервная копия адреса следующего звена списка delete Head; //Очистка памяти от первого звена Head = Tail; //Смена адреса начала на адрес следующего элемента } } void List::Delete_first() { } void List::Delete_end() { Node *temp; Node *current = Tail; current = Head; temp = Head->Next; delete current; Head = temp; temp->Prev = NULL; } void List::Add() { int x = 0; cout << "Введите элемент списка: "; cin >> x; Node *temp = new Node; //Выделение памяти под новый элемент структуры temp->Next = NULL; //Указываем, что изначально по следующему адресу пусто temp->x = x;//Записываем значение в структуру if (Head != NULL) //Если список не пуст { temp->Prev = Tail; //Указываем адрес на предыдущий элемент в соотв. поле Tail->Next = temp; //Указываем адрес следующего за хвостом элемента Tail = temp; //Меняем адрес хвоста } else //Если список пустой { temp->Prev = NULL; //Предыдущий элемент указывает в пустоту Head = Tail = temp; //Голова=Хвост=тот элемент, что сейчас добавили } } void List::Show() { //ВЫВОДИМ СПИСОК С КОНЦА Node *temp = Tail; //Временный указатель на адрес последнего элемента while (temp != NULL) //Пока не встретится пустое значение { cout << temp->x << " "; //Выводить значение на экран temp = temp->Prev; //Указываем, что нужен адрес предыдущего элемента } cout << "\n"; //ВЫВОДИМ СПИСОК С НАЧАЛА temp = Head; //Временно указываем на адрес первого элемента while (temp != NULL) //Пока не встретим пустое значение { cout << temp->x << " "; //Выводим каждое считанное значение на экран temp = temp->Next; //Смена адреса на адрес следующего элемента } cout << "\n"; } int main() { system("CLS"); setlocale(LC_ALL, "Russian"); List lst; lst.empty(); lst.Add(); lst.empty(); lst.Add(); lst.Add(); lst.empty(); lst.Add(); lst.Delete_first(); lst.Delete_end(); lst.Show(); lst.Delete_end(); lst.Add(); lst.Delete_first(); lst.Show(); system("PAUSE"); }
  • one
    Why does your iterator inherit from List? Why does the list contain next / prev? - free_ze Nov.
  • Well, I am learning the first day with ++, and that is not the under-code)) - Jurtchak
  • Inheritance is not needed here. Take next / prev in the iterator to logic. - free_ze Nov.
  • Search is not much different from Show - vp_arth
  • Oh, this @ Spirit community, I feel like a necromancer) - vp_arth

2 answers 2

To begin with, the Node structure should be declared as an internal structure of the List class. It is not intended to be used outside the List class, and therefore it should not be made open to the outside world.

The iterator class should also be defined inside the list class. It must have access to the start and end nodes of the list.

A doubly linked list is defined by its head and tail nodes. Therefore, to keep these variables in the list definition like cur , Next and Prev does not make sense. Instead of ad data

 Node *Head, *Tail, *cur; Node *Next, *Prev;//Указатели на адреса начала списка и его конца

should write this announcement

 Node *Head, *Tail;

The empty function should use the return value to tell the client code whether the list is empty or not. Therefore, its definition should look like this.

 bool empty() const { return Head == nullptr; }

No messages should be included in this function.

The Delete_end function Delete_end incorrect. It must delete the tail node, and instead the function tries to remove the head node.

 current = Head; //... delete current;

Moreover, if the list before deleting a node contained one element, then the Tail node after removing this single node will have an incorrect value instead of nullptr

The function can be defined, for example, as follows.

 void List::Delete_end() { if ( Tail != nullptr ) { Node *tmp = Tail; Tail = Tail->prev; delete tmp; if ( Tail == nullptr ) Head = Tail; else Tail->next = nullptr; } }

Since you have a doubly linked list, this means that new items in the list can be added both to the top of the list and to the end of the list, and therefore you should have not one Add method declared, but two methods, one of which adds a new item to the top of the list, and another to the end of the list.

And both methods must have one parameter that specifies an integer value to be inserted into the list. You should not request this value inside the methods themselves.

The Show method must also be split into two methods: one lists in the forward direction and the other method goes in the opposite direction.

So when all this is fixed, you can ask about the search function of the element in the list. :)

  • Fixed as it was written by you above, now after I enter the elements, after entering the last one, the program crashes with the error "Unhandled exception thrown: read access violation. Temp was 0x1." - Jurtchak
  • @Jurtchak Your item entry function may not be correct. I had a typo in the function of deleting the last element, I corrected it. It must set the next field to nullptr. - Vlad from Moscow
  • Instead of "Tail"? - Jurtchak
  • @Jurtchak I wrote that I corrected the function. - Vlad from Moscow
  • "Next" is undeclared identifier, although the next one is announced - Jurtchak

I did some refactoring and did a desirable search for items using the iterator class. But I renamed it (this class) in order to avoid name conflicts.

Here is the finished program.

Main.cpp file

 #include "stdafx.h" #include <iostream> #include <locale.h> #include "List.h" #include"iterat.h" using std::cout; using std::cin; using std::endl; int main() { system("CLS"); setlocale(LC_ALL, "Russian"); List lst; lst.Add(); lst.Add(); lst.Add(); lst.Add(); lst.Add(); lst.Add(); iterat it; cout << "====================================" << endl; for (it = lst.begin(); it != lst.end(); ++it) { cout << it << ' '; } cout << endl; cout << endl; int key; cout << "Введите элемент поиска: "; cin >> key; cout << endl; for (it = lst.begin(); it != lst.end(); ++it) { if (it == key) { std::cout << "Элемент " << key << " найден."; break; } } cout << endl << endl; lst.Show(); cout << endl; lst.Add(); lst.Show(); system("PAUSE"); return 0; }

iterat.h

 #pragma once #include "List.h" #include <iostream> class iterat : public List { public: Node* iter; iterat() {} iterat* operator=(Node*); iterat* operator++(); bool operator!=(Node*); friend std::ostream& operator<<(std::ostream&, const iterat&); bool operator==(int); bool operator==(Node*); };

iterat.cpp

 #include "stdafx.h" #include "iterat.h" iterat* iterat::operator=(Node *pv) { iter = pv; return this; } iterat* iterat::operator++() { iter = iter->Next; return this; } bool iterat::operator!=(Node * temp) { if (this->iter != temp) return true; return false; } std::ostream& operator<<(std::ostream& os, const iterat& it) { os << it.iter->x; return os; } bool iterat::operator==(int key) { if (iter->x == key) return true; return false; } bool iterat::operator==(Node *pv) { if (iter == pv) return true; return false; }

List.h

 #pragma once class List { public: class Node { public: int x; Node *Next, *Prev; Node(int dat = 0) { x = dat; Next = 0; Prev = 0; } }; Node *Head, *Tail; List() :Head(NULL), Tail(NULL) {}; Node* begin() { return Head; } Node* end() { return Tail->Next; } void Show(); void Delete_end(); void Delete_first(); void Add(); };

List.cpp

 #include "stdafx.h" #include "List.h" #include <iostream> using std::cout; using std::cin; using std::endl; void List::Add() { int x = 0; cout << "Введите элемент списка: "; cin >> x; Node* pv = new Node(x); if (Head == 0) { Head = Tail = pv; } else { pv->Prev = Tail; Tail->Next = pv; Tail = pv; } } void List::Show() { //ВЫВОДИМ СПИСОК С КОНЦА Node *temp = Tail; //Временный указатель на адрес последнего элемента while (temp != NULL) //Пока не встретится пустое значение { cout << temp->x << " "; //Выводить значение на экран temp = temp->Prev; //Указываем, что нужен адрес предыдущего элемента } cout << "\n"; //ВЫВОДИМ СПИСОК С НАЧАЛА temp = Head; //Временно указываем на адрес первого элемента while (temp != NULL) //Пока не встретим пустое значение { cout << temp->x << " "; //Выводим каждое считанное значение на экран temp = temp->Next; //Смена адреса на адрес следующего элемента } cout << "\n"; }