Wanna be serious
586 / 473 / 186
Регистрация: 31.07.2013
Сообщений: 1,693
1

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

23.03.2016, 16:29. Показов 1768. Ответов 6
Метки нет (Все метки)

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

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

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

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#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;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.03.2016, 16:29
Ответы с готовыми решениями:

Реализовать Двусвязный список
Реализовать Двусвязный список объектов Computer объектов этого класса, не применяя STL библиотеку....

Реализовать двусвязный список
Помогите решить) n-натурал, Х1,Х2,....,Хn (n=&gt;2) (X1+X2+Xn)(X2+X3+Xn-1)....(Xn-1+Xn+X2) Надо...

Раздельная компиляция Namespace - Реализовать двусвязный список
В книге Страуструпа описана модульность с помощью namespace: stack.c - хранит реализацию ...

Реализовать двусвязный список и операции работы с ним
Реализовать двусвязный список и операции работы с ним. В списке хранить, что пожелаете. ...

6
Wanna be serious
586 / 473 / 186
Регистрация: 31.07.2013
Сообщений: 1,693
27.03.2016, 14:46  [ТС] 2
Всё ещё актуально
0
Wanna be serious
586 / 473 / 186
Регистрация: 31.07.2013
Сообщений: 1,693
30.03.2016, 14:06  [ТС] 3
Тема всё ещё не потеряла актуальности
0
2782 / 1935 / 570
Регистрация: 05.06.2014
Сообщений: 5,600
30.03.2016, 15:33 4
Лучший ответ Сообщение было отмечено Bespridelschic как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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;
}
0
Wanna be serious
586 / 473 / 186
Регистрация: 31.07.2013
Сообщений: 1,693
30.03.2016, 15:38  [ТС] 5
Renji, не могли бы вы прокомментировать написанное? Я не совсем понял что мы этим добились
0
2782 / 1935 / 570
Регистрация: 05.06.2014
Сообщений: 5,600
30.03.2016, 15:45 6
Цитата Сообщение от Bespridelschic Посмотреть сообщение
Renji, не могли бы вы прокомментировать написанное? Я не совсем понял что мы этим добились
Кольцевой двусвязный список, начинающийся со служебного элемента-заголовка. Добились что список никогда не бывает пустым и в нем никогда не бывает nullptr ссылок. Соответственно, геморрою с кодом куда меньше.
40-41 строки - заполнение списка, 42-43 - печать списка, очистку списка я писать уже поленился (тупо, delete всех элементов).
1
Wanna be serious
586 / 473 / 186
Регистрация: 31.07.2013
Сообщений: 1,693
30.03.2016, 15:48  [ТС] 7
Renji, спасибо большое, вопрос исчерпан
0
30.03.2016, 15:48
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.03.2016, 15:48
Помогаю со студенческими работами здесь

STL: реализовать кольцевой упорядоченный двусвязный список
Добрый вечер всем кто открыл эту вкладку! Надо реализовать кольцевой упорядоченный двозвязний...

Реализовать алгоритм простой вставки через двусвязный список
Здравствуйте ! Нужно реализовать алгоритм простой вставки через двусвязный список Не понимаю как

С++ Реализовать односвязный и двусвязный список и операции работы с ними
Реализовать односвязный и двусвязный список и операции работы с ними. В списке хранятся символы....

Реализовать вывод последовательности чисел в нужном порядке (двусвязный список)
Всем привет, я написал код который считывает с файла значения и преобразует их в вид, например...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru