Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Guy Kawasaki
2 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 42
#1

Итератор двусвязного списка - C++

16.11.2013, 20:22. Просмотров 1039. Ответов 6
Метки нет (Все метки)

Добрый день.
Проблема: Есть итератор для двусвязного списка. Реализован метод вывода списка с головы, но не получается реализовать метод вывода с хвоста. Класс итератор отказывается видеть указатель tail(хвост).
Что было сделано для решения проблемы: Пытался получить tail с помощью функции get_tail, которая должна была вернуть указатель на хвост. Пытался делать указатель на структуру Node из private в public или protected.
Просьба: Помочь с разрешением этой проблемы, и, если есть желание, указать на ее источник.
Среда разработки: Code::Bloks 12.11

P.S. Заранее спасибо всем откликнувшимся!

Код заголовка iterator.h

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
#ifndef ITERATOR_H_INCLUDED
#define ITERATOR_H_INCLUDED
#include "list.h"
 
class Iterator
{
public:
    friend class List;
 
    Iterator();
    Iterator(List::Node* p);
    Iterator operator ++ ();
    Iterator operator -- ();
    int &operator * ()
    {
        if(ptr)
            return ptr->core;
        //else
            //throw exeption(); Кидает написанное мной исключение
    }
    int &operator -> ()
    {
        if(ptr)
            return ptr->core;
        //else
            //throw exeption(); Кидает написанное мной исключение
    }
    bool operator != (Iterator &right); //Реализовать этот оеператор гораздо важнее
    bool operator == (Iterator &right)
    {
        return ptr == right.ptr;
    }
private:
   List::Node *ptr;
};
#endif
Код заголовка list.h

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
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
 
class Iterator;
 
class List
{
private:
    struct Node
    {
        Node();
        Node(const Node &original);
        ~Node();
 
        int core;
        Node *next, *previous;
    };
 
    int meter;
    Node *head, *tail;
public:
    friend class Iterator;
 
    List();
    List(const List &original) {};
    List &operator = (const List &rhs);
    ~List();
 
    Node* get_tail_for_iterator();
 
    void show_from_the_beginning();
    void show_from_the_end();
    void add_head(int value);
    void add_tail(int value);
    void insert_node(int pos, int data);
    void delete_node(int pos);
    void insertSubList(List &original, int pos);
    void cutSubList(int pos_first, int pos_end);
    void clearList();
    int get_list_size();
    void changeMeter (int i);
    Iterator begin_iterator();
    Iterator end_iterator();
};
#endif
Код файла iterator.cpp

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
#include "iterator.h"
 
Iterator List::begin_iterator()
{
    return Iterator(head);
}
 
Iterator List::end_iterator()
{
    return Iterator(0);
}
 
Iterator::Iterator():
    ptr(0)
{}
 
Iterator::Iterator(List::Node* p):
    ptr(p)
{}
 
Iterator Iterator::operator ++ ()
{
    if(ptr)
    {
        ptr = ptr -> next; //Может быть еще и здесь кинуть исключение
        return *this;
    }
    else return 0;
}
 
Iterator Iterator::operator -- ()
{
    if(ptr)
    {
        ptr = ptr -> previous; //Может быть еще и здесь кинуть исключение
        return *this;
    }
    else
    {
         ptr = List::get_tail_for_iterator();
        return *this;
    }
}
Код файла list.cpp

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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
#include <iostream>
#include <locale.h>
#include "list.h"
using namespace std;
 
List::Node::Node():
    core(0),
    next(0),
    previous(0)
{}
 
List::Node::Node(const Node &original):
    core(original.core),
    next(0),
    previous(0)
{
    next = original.next;
    previous = original.previous;
}
 
List::Node::~Node()
{}
 
List::List():
    meter(0),
    head(0),
    tail(0)
{}
 
/* Исправить оператор присваивания для списка
List& List::operator = (const List &rhs)
{
    if (this != &rhs) // защита от неправильного самоприсваивания
    {
 
    }
    return *this;
}
*/
 
List::~List()
{
    delete head;
    delete tail;
}
 
void List::changeMeter(int i)
{
    if(i == 1)
        ++meter;
    else
        --meter;
}
 
// Оставляем этот метод как пример прошлой лабы
/*
void List::show_from_the_beginning()
{
    Node *temp = tail;
    temp = head;
 
    cout << "\nВывод элементов двусвязного списка с начала:\n\n";
    while (temp != 0)
    {
        cout << temp -> core << " ";
        temp = temp -> next;
    }
    cout << endl;
}
*/
 
// Оставляем этот метод как пример прошлой лабы
/*
void List::show_from_the_end()
{
    Node *temp = tail;
 
    cout << "\nВывод элементов двусвязного списка с конца:\n\n";
    while (temp != 0)
    {
        cout << temp -> core << " ";
        temp = temp -> previous;
    }
    cout << endl;
}
*/
 
int List::get_list_size()
{
    meter = 0;
    Node *temp = tail;
    temp = head;
 
    while (temp != 0)
    {
        changeMeter(1);
        temp = temp -> next;
    }
 
    return meter;
}
 
void List::add_head(int value)
{
    Node *temp = new Node;
 
    temp -> previous = 0;
    temp -> core = value;
    temp -> next = head;
 
    if (head != 0)
        head -> previous = temp;
 
    if (meter == 0)
        head = tail = temp;
    else
        head = temp;
 
    changeMeter(1);
}
 
void List::add_tail(int value)
{
    Node *temp = new Node;
 
    temp -> next = 0;
    temp -> core = value;
    temp -> previous = tail;
 
    if (tail != 0)
        tail -> next = temp;
 
    if (meter == 0)
        head = tail = temp;
    else
        tail = temp;
 
    changeMeter(1);
}
 
void List::insert_node(int pos, int data)
{
    if(pos == meter + 1)
    {
        add_tail(data);
        return;
    }
    else if(pos == 1)
    {
        add_head(data);
        return;
    }
 
    int i = 1; //Счетчик
 
    Node *elem_insert = head;
 
    while(i < pos) //Ввести итератор
    {
        elem_insert = elem_insert -> next;
        ++i;
    }
 
    Node *prev_elem_insert = elem_insert -> previous;
    Node *temp = new Node;
 
    temp -> core = data;
 
    if(prev_elem_insert != 0 && meter != 1) //Настройка связей
        prev_elem_insert -> next = temp;
 
    temp -> next = elem_insert;
    temp -> previous = prev_elem_insert;
    elem_insert -> previous = temp;
 
    changeMeter(1);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////
void List::delete_node(int pos)
{
    cout << "\nУдаление узла, находящегося на позиции " << pos;
    if (pos == 0)
    {
        cout << "Введите позицию удаляемого элемента: ";
        cin >> pos;
    }
 
    if (pos < 1 || pos > meter)
    {
        cout << "\nНеверная позиция\n";
        return;
    }
 
    int i = 1; //Счетчик
 
    Node *Del = head;
 
    while (i < pos)
    {
        Del = Del -> next;
        ++i;
    }
 
    Node *PrevDel = Del -> previous;
    Node *AfterDel = Del -> next;
 
    if (PrevDel != 0 && meter != 1)
        PrevDel -> next = AfterDel;
 
    if (AfterDel != 0 && meter != 1)
        AfterDel -> previous = PrevDel;
 
    if (pos == 1)
        head = AfterDel;
    if (pos == meter)
        tail = PrevDel;
 
    changeMeter(0);
}
 
void List::insertSubList(List &original, int pos)
{
    cout << "\nВставка подцепи в начальный список на позицию " << pos;
 
    if (pos < 1 || pos > original.meter + 1)
    {
        cout << "\nНеверная позиция!\n";
        return;
    }
 
    if(pos == original.meter + 1)
    {
        original.tail -> next = head;
        head -> previous = original.tail;
        return;
    }
    else if(pos == 1)
    {
        tail -> next = original.head;
        original.head -> previous = tail;
        original.head = head;
        return;
    }
 
    int i = 1; //Счетчик
 
    Node *before = original.head;
 
    while(i < pos)
    {
        before = before -> next;
        ++i;
    }
 
    Node *x = before -> next;
 
    before -> next = head;
    head -> previous = before;
 
    tail -> next = x;
    x -> previous = tail;
 
    for(int i = 0; i < meter; ++i)
    original.changeMeter(1);
}
 
void List::cutSubList(int pos_first, int pos_end)
{
    if(pos_first < 1 || pos_end > meter)
    {
        cout << "\nВыбрана неверная позиция. Выход из функции.\n";
        return;
    }
 
    Node *before = head, *after = head;
 
    int i = 1;
    while(i < pos_first)
    {
        before = before -> next;
        ++i;
    }
 
    i = 1;
    while(i < pos_end + 1)
    {
        after = after -> next;
        ++i;
    }
    /*
        while(before -> next != after -> previous)
        {
            delete before;
        }
    */
    before -> next = after -> previous;
 
    for(int i = 0; i < (pos_end - pos_first); ++i)
    changeMeter(0);
}
 
List::Node* List::get_tail_for_iterator()
{
    return tail;
}
Код файла main.cpp

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
#include <iostream>
#include <locale.h>
#include "list.h"
#include "iterator.h"
using namespace std;
 
void input_list(List &myList)
{
 
}
 
void output_begin(List &myList)
{
    cout << "\nВывод двусвязного списка с головы:\n";
    Iterator iter = myList.begin_iterator();
    Iterator end = myList.end_iterator();
    for (; !(iter == end); ++iter)
    {
        cout << *iter << " ";
    }
}
 
void output_end(List &myList)
{
    cout << "\n\nВывод двусвязного списка с хвоста:\n";
    Iterator iter = myList.end_iterator();
    Iterator beg = myList.begin_iterator();
    for (; !(iter == beg); --iter)
    {
        if(iter)
        cout << *iter << " ";
    }
}
 
void insert_node(List &myList)
{
    int data, pos;
 
    cout << "\nВставка нового узла на вашу позицию.\n";
    cout << "\nВведите позицию нового узла: ";
    cin >> pos;
    cout << "\nВведите значение нового узла: ";
    cin >> data;
 
    if(pos < 1 || pos > myList.get_list_size() + 1)
    {
        while(pos < 1 || pos > myList.get_list_size() + 1)
        {
            cout << "Неверная позиция. Введите корректное значение позиции: ";
            cin >> pos;
        }
    }
 
    myList.insert_node(pos, data);
}
 
int main()
{
    setlocale(LC_CTYPE,"Russian");
 
    List abc;
    int value, pos_first, pos_end;
 
    cout << "Введите значения узлов списка типа <int>:\n";
    do
    {
        cin >> value;
        abc.add_tail(value);
    }while(/*(sizeof(value) >= 2) && (sizeof(value) <= 4)*/value);
 
    output_begin(abc);
    output_end(abc);
 
    cout << "\nКоличество элементов в списке равно: " << abc.get_list_size() << endl;
 
    cout << "\nВставка узла в начало списка.";
    abc.add_head(111);
    output_begin(abc);
 
    cout << "\nВставка узла в конец списка.";
    abc.add_tail(222);
    output_begin(abc);
 
    insert_node(abc);
    output_begin(abc);
 
    abc.delete_node(5); // Переделать на итераторах
    output_begin(abc);
 
 
/*
    List subABC;
 
    cout << "Введите значения узлов ПОДсписка типа <int>:\n";
    do
    {
        cin >> value;
        subABC.add_tail(value);
    }while(value);
 
    cout << "\nПодцепь для вставки в начальный список.";
    subABC.show_from_the_beginning();
    subABC.get_list_size();
    subABC.insertSubList(abc, 3); //передаем в подсписок ОРИГИНАЛЬНЫЙ список
    abc.show_from_the_beginning();
    abc.get_list_size(); //Получение количества элементов списка после вставки
 
    abc.cutSubList(3, 8); //нельзя вырезать подсписок, выходящий за пределы оригинального списка
    abc.get_list_size();
    cout << "\nПосле удаления.";
    abc.show_from_the_beginning();
*/
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.11.2013, 20:22
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Итератор двусвязного списка (C++):

Реализовать двусвязный список (list), итератор (iterator) и константный итератор (сonst_iterator) для списка - C++
не могу понять что должно быть результатом. может подскажете примеры? пожалуйста. Задание: Реализовать двусвязный список (list),...

Разработать класс Итератор, методы которого: переход в начало списка, в конец, к текущему элементу списка, к с - C++
Разработать класс Итератор, методы которого: переход в начало списка, в конец, к текущему элементу списка, к следующему элементу, к...

"Сортировка двусвязного списка путем исключения элемента с минимальным значением и включения его в начало нового списка - C++
Здравствуйте! Возникла проблема с программой. Тема: &quot;Сортировка двусвязного списка путем исключения элемента с минимальным значением и...

Реверс двусвязного списка - C++
Столкнулся с задачей написать функцию реверса двусвязного списка. Часа 3 сушил себе мозг с копиями указателей, получилось что надо хранить...

Cортировка двусвязного списка - C++
Ну, в общем задание в названии. Нужно отсортировать двусвязный список, методом пузырька. Сортировку-то я эту знаю. Но вот проблема, я не...

Создание двусвязного списка - C++
Не понимаю как его создать. И как сделать стандартные операции над списком(удаление, добавление и т.д). Сколько сайтов переползал, все...

6
stima
487 / 339 / 39
Регистрация: 22.03.2011
Сообщений: 1,084
Завершенные тесты: 2
16.11.2013, 20:49 #2
Вы не совсем понимаете, что пишите. У вас итератор это wrapper на указатель типа Node. Node не имеет поля tail.
0
Guy Kawasaki
2 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 42
16.11.2013, 20:56  [ТС] #3
Да. Дружественность идет от класса, но почему указателем на структуру head мы можем пользоваться, а tail - нет?
Получается метод end_iterator(); зануляет наш iter, и for (; !(iter == end); ++iter) условие уже ложно. Подскажите, как разрешить эту проблему?
0
stima
487 / 339 / 39
Регистрация: 22.03.2011
Сообщений: 1,084
Завершенные тесты: 2
16.11.2013, 21:23 #4
Цитата Сообщение от Guy Kawasaki Посмотреть сообщение
Дружественность идет от класса, но почему указателем на структуру head мы можем пользоваться, а tail - нет?
Вы используете head в методе класса List, но не методах класса Iterator.
0
Guy Kawasaki
2 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 42
16.11.2013, 21:38  [ТС] #5
Да. Старый код, уже подзабыл особенности.
У нас есть два публичных метода класса:

C++
1
2
    Iterator begin_iterator();
    Iterator end_iterator();
Теперь у меня их реализация выглядит так:

C++
1
2
3
4
5
6
7
8
9
Iterator List::begin_iterator()
{
    return Iterator(head);
}
 
Iterator List::end_iterator()
{
    return Iterator(tail);
}
Есть еще перегруженные префиксные операторы:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Iterator Iterator::operator ++ ()
{
    if(ptr)
    {
        ptr = ptr -> next;
        return *this;
    }
    else return 0;
}
 
Iterator Iterator::operator -- ()
{
    if(ptr)
    {
        ptr = ptr -> previous;
        return *this;
    }
    else return 0;
}
Так почему же эта функция не работает?

C++
1
2
3
4
5
6
7
8
9
10
11
void output_end(List &myList)
{
    cout << "\n\nВывод двусвязного списка с хвоста:\n";
    Iterator iter = myList.end_iterator();
    Iterator beg = myList.begin_iterator();
    for (; !(iter == beg); --iter)
    {
        if(iter)
            cout << *iter << " ";
    }
}
0
stima
487 / 339 / 39
Регистрация: 22.03.2011
Сообщений: 1,084
Завершенные тесты: 2
16.11.2013, 21:45 #6
Во первых как понять не работает? Во вторых не зная текущее состояние List сложно угадать, из чего сосоят итераторы. В третьих реализуйте список без итераторов, доведите его до идеально рабочего состояния и реализовав все методы, добавте итераторы.
0
Guy Kawasaki
2 / 1 / 0
Регистрация: 07.11.2013
Сообщений: 42
16.11.2013, 21:55  [ТС] #7
Если убрать проверку if(iter), то функция заработает:

C++
1
2
3
4
5
6
7
8
void output_end(List &myList)
{
    cout << "\n\nВывод двусвязного списка с хвоста:\n";
    Iterator iter = myList.end_iterator();
    Iterator beg = myList.begin_iterator();
    for (; !(iter == beg); --iter)
            cout << *iter << " ";
}
НО есть одно НО:

При введение значений узлов списка: 1 2 3 4 5 6 7 8 9 10 11 12, последний введенный 0 указывает на то, что ввод завершен.

Функция void output_begin(List &myList) выдает нам: 1 2 3 4 5 6 7 8 9 10 11 12,
а функция void output_end(List &myList) нечто вроде этого: 0 12 11 10 9 8 7 6 5 4 3 2 1

Как грамотно пофиксить этот ноль?

Добавлено через 4 минуты
Цитата Сообщение от stima Посмотреть сообщение
Во первых как понять не работает? Во вторых не зная текущее состояние List сложно угадать, из чего сосоят итераторы. В третьих реализуйте список без итераторов, доведите его до идеально рабочего состояния и реализовав все методы, добавте итераторы.
В комментариях кода есть старые методы, которые отлично работают. Задание было переписать программу, используя Iterator и NVI, про NVI я пока забуду, хочу переписать все бывшие методы на новые с итераторами.

А вот и старые методы отвечающие за вывод с головы и хвоста:

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
void List::show_from_the_beginning()
{
    Node *temp = tail;
    temp = head;
 
    cout << "\nВывод элементов двусвязного списка с начала:\n\n";
    while (temp != 0)
    {
        cout << temp -> core << " ";
        temp = temp -> next;
    }
    cout << endl;
}
 
void List::show_from_the_end()
{
    Node *temp = tail;
 
    cout << "\nВывод элементов двусвязного списка с конца:\n\n";
    while (temp != 0)
    {
        cout << temp -> core << " ";
        temp = temp -> previous;
    }
    cout << endl;
}
0
16.11.2013, 21:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.11.2013, 21:55
Привет! Вот еще темы с ответами:

Итератор списка не распознаётся - C++
class personel : public user { public: personel():user() { post = new char; } ~personel(){} bool...

Итератор для списка - C++
#include &lt;iostream&gt; using namespace std; template &lt;class T&gt; class Link { public: T value; Link *nextLink; Link( T v,...

Шейкерная сортировка двусвязного списка - C++
Здравствуйте! У меня возникла проблема с сортировкой двусвязного списка. Получилось реализовать двусвязный список и отдельно...

Быстрая сортировка двусвязного списка - C++
что не так?? void newsort(Offender_Node*first,Offender_Node*last) { Offender_Node*cur=first,*Prev=cur; ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru