Реализовать двусвязный список

@Bespridelschic · Регистрация: 31.07.2013

Author24 — интернет-сервис помощи студентам

Доброго времени суток. Я получил задание в университете реализовать двусвязный список. В общем то с пониманием общей концепции списка / стека проблем не возникает, а вот в реализации появились некоторые проблемы.

Среди методов класса присутствуют: Push - добавление нового элемента; Pop - удаление элемента списка, значение которого равно запрашиваемому; is_empty - проверка на наличие элементов в очереди; size - размер списка; show - вывод в консоль значения всех членов списка.

Поля класса представлены следующими членами: Node - класс содержащий в себе хранимое значение, а так же указатели на следующий/предыдущий элемент списка; items - количество членов списка; Указатели head/tail соответствуют голове/хвосту списка. Нарастание в списке происходит от хвоста до головы.

Собственно о проблемах возникающих при отладке: вылетает ошибка в работе деструктора, якобы он не может получить доступ к закрытым членам. Так же возникает ошибка в методе show: цикл вывода в консоль уходит в бесконечность при выводе последнего элемента. Исходный код прилагается. Заранее благодарен всем откликнувшимся.

C++

#include <iostream>
 
typedef int Item;
 
class List
{
private:
    class Node
    {
    public:
        Item item;
        Node *prev;
        Node *next;
    };
    unsigned items;
    Node *tail;
    Node *head;
public:
    List()
    {
        tail = head = nullptr;
        items = 0;
    }
 
    ~List()
    {
        while (head)
        {
            Node *temp = head;
            head = head->next;
            delete temp;
        }
    }
 
    bool push(Item & item)
    {
        items++;
        Node *temp = new Node;
        temp->item = item;
        if (is_empty())
        {
            head = tail = temp;
            head->prev = tail->next = nullptr;
        }
        else
        {
            head->next = temp;
            temp->prev = head;
            head = temp;
            head->prev = nullptr;
        }
        std::cout << temp->item << " was added\n";
        return true;
    }
 
    bool pop(Item & item)
    {
        if (is_empty())
        {
            std::cout << "List is empty";
            return false;
        }
        else
        {
            for (Node *temp = head; tail != nullptr; temp = temp->next)
            {
                if (temp == head && temp == tail)
                {
                    if (temp->item == item)
                    {
                        items--;
                        std::cout << head->item << " was deleted" << std::endl;
                        delete head;
                        delete tail;
                        return true;
                    }
                    else return false;
                }
                if (temp == head)
                {
                    if (temp->item == item)
                    {
                        items--;
                        std::cout << head->item << " was deleted" << std::endl;
                        Node *temp = head;
                        head = head->next;
                        delete temp;
                        return true;
                    }
                    else continue;
                }
                if (temp->item == item)
                {
                    items--;
                    Node *for_prev = temp->prev;
                    Node *for_next = temp->next;
                    std::cout << temp->item << " was deleted\n";
                    delete temp;
                    for_prev->next = for_next;
                    for_next->prev = for_prev;
                    return true;
                }
                else continue;
            }
        }
        std::cout << "Not found\n";
        return false;
    }
 
    bool is_empty()
    {
        if (head == nullptr || tail == nullptr) return true;
        else return false;
    }
 
    unsigned size()
    {
        return items;
    }
 
    void show()
    {
        if (is_empty())
        {
            std::cout << "List is empty";
        }
        else
        {
            for (Node *temp = head; temp != nullptr; temp = temp->next)
            {
                std::cout << temp->item << std::endl;
            }
        }
    }
};
 
int main()
{
    List list;
    int n;
    std::cout << "Enter value: ";
    std::cin >> n;
    list.push(n);
 
    std::cout << "Enter value: ";
    std::cin >> n;
    list.push(n);
 
    std::cout << "Enter value: ";
    std::cin >> n;
    list.push(n);
 
    std::cout << "Size = " << list.size() << std::endl;
 
    std::cout << "Enter value: ";
    std::cin >> n;
    list.pop(n);
    std::cout << "Size = " << list.size() << std::endl;
 
    std::cout << "Enter value: ";
    std::cin >> n;
    list.pop(n);
    std::cout << "Size = " << list.size() << std::endl;
 
    std::cout << "Enter value: ";
    std::cin >> n;
    list.pop(n);
    std::cout << "Size = " << list.size() << std::endl;
 
    std::cout << "Enter value: ";
    std::cin >> n;
    list.pop(n);
    std::cout << "Size = " << list.size() << std::endl;
 
    list.show();
 
    system("Pause >> 0");
    return 0;
}

@Bespridelschic · 27.03.2016, 14:46 **[ТС]**

Всё ещё актуально

@Bespridelschic · 30.03.2016, 14:06 **[ТС]**

Тема всё ещё не потеряла актуальности

@Renji · 30.03.2016, 15:33

C++

#include<iostream>
 
class list_value;
class list_header
{
public:
    list_header():_prev(this),_next(this){}
    list_header(list_header*next):_prev(next->_prev),_next(next){_prev->_next=_next->_prev=this;}
    ~list_header(){
        _prev->_next=_next;
        _next->_prev=_prev;
    }
 
    inline const list_value*prev()const;
    inline const list_value*next()const;
 
private:
    list_header*_prev;
    list_header*_next;
};
 
class list_value:public list_header
{
public:
    list_value(list_header*next,int value):list_header(next),_value(value){}
    int value()const{return _value;}
 
private:
    int _value;
};
 
inline const list_value*list_header::prev()const{return static_cast<list_value*>(_prev);}
inline const list_value*list_header::next()const{return static_cast<list_value*>(_next);}
 
using namespace std;
 
int main()
{
    list_header header;
    for(int i=0;i<10;++i)
        new list_value(&header,i);
    for(const list_value*pos=header.next();pos!=&header;pos=pos->next())
        std::cout<<pos->value()<<std::endl;
    return 0;
}

@Bespridelschic · 30.03.2016, 15:38 **[ТС]**

Renji, не могли бы вы прокомментировать написанное? Я не совсем понял что мы этим добились

@Renji · 30.03.2016, 15:45

Сообщение от Bespridelschic

Renji, не могли бы вы прокомментировать написанное? Я не совсем понял что мы этим добились

Кольцевой двусвязный список, начинающийся со служебного элемента-заголовка. Добились что список никогда не бывает пустым и в нем никогда не бывает nullptr ссылок. Соответственно, геморрою с кодом куда меньше.
40-41 строки - заполнение списка, 42-43 - печать списка, очистку списка я писать уже поленился (тупо, delete всех элементов).

@Bespridelschic · 30.03.2016, 15:48 **[ТС]**

Renji, спасибо большое, вопрос исчерпан

@Bespridelschic Wanna be serious 586 / 473 / 186 Регистрация: 31.07.2013 Сообщений: 1,693
	27.03.2016, 14:46 [ТС]	2
	Всё ещё актуально 0

@Bespridelschic Wanna be serious 586 / 473 / 186 Регистрация: 31.07.2013 Сообщений: 1,693
	30.03.2016, 14:06 [ТС]	3
	Тема всё ещё не потеряла актуальности 0

@Bespridelschic Wanna be serious 586 / 473 / 186 Регистрация: 31.07.2013 Сообщений: 1,693
	30.03.2016, 15:38 [ТС]	5
	Renji, не могли бы вы прокомментировать написанное? Я не совсем понял что мы этим добились 0

@Renji 2782 / 1935 / 570 Регистрация: 05.06.2014 Сообщений: 5,600
	30.03.2016, 15:45	6
	Сообщение от Bespridelschic Renji, не могли бы вы прокомментировать написанное? Я не совсем понял что мы этим добились Кольцевой двусвязный список, начинающийся со служебного элемента-заголовка. Добились что список никогда не бывает пустым и в нем никогда не бывает nullptr ссылок. Соответственно, геморрою с кодом куда меньше. 40-41 строки - заполнение списка, 42-43 - печать списка, очистку списка я писать уже поленился (тупо, delete всех элементов). 1

@Bespridelschic Wanna be serious 586 / 473 / 186 Регистрация: 31.07.2013 Сообщений: 1,693
	30.03.2016, 15:48 [ТС]	7
	Renji, спасибо большое, вопрос исчерпан 0

Реализовать двусвязный список

Решение