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

Реализовать двунаправленный список в духе списка из STL - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.79
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
11.02.2011, 20:37     Реализовать двунаправленный список в духе списка из STL #1
Все-таки видимо у меня всегда останутся с этим проблемы.
Само определение скидывать не буду, я пытаюсь сделать, что-то вроде STL-ного списка.
Спросить хочу только одно.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
    void push_back(const T& el)
    {
        Node* tmp=new Node(el);
        if(empty())
        {
            head=tmp;
            tail=tmp;
            ++sz;
            return;
        }
        tail->next=tmp;
        tail=tmp;
        ++sz;
    }
После этого список можно прогонять только в одну сторону. С головы в хвост. В хвосте же только последний элемент и в prev ничего нет. В чем мб проблема?
Хотя вообще как я понял это для однонаправленного только катит... А вот как сделать для двунаправленного - второй день догнать не могу.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.02.2011, 20:37     Реализовать двунаправленный список в духе списка из STL
Посмотрите здесь:

Двунаправленный список C++
C++ Двунаправленный список
C++ Двунаправленный список!
Двунаправленный список C++
Реализовать двухсвязный список. Каждый элемент списка может содержать один объект C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.02.2011, 20:53     Реализовать двунаправленный список в духе списка из STL #2
Ну так вы перед тем, как tail'у присваивать tmp, установите в tmp prev-указатель на tail.

Добавлено через 2 минуты
Т.е. так:
C++
1
2
3
tail->next=tmp;
tmp->prev = tail;
tail=tmp;
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
11.02.2011, 20:56  [ТС]     Реализовать двунаправленный список в духе списка из STL #3
silent_1991, Офигеть... столько проколебался а все так просто... шок)
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
11.02.2011, 20:56     Реализовать двунаправленный список в духе списка из STL #4
Ссылки на предыдущий элемент нет, потому что ты её не устанавливаешь.
C++
1
2
3
tail->next = tmp;
tmp->previous = tail;
tail = tail->next;
Добавлено через 30 секунд
Опоздал...
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
11.02.2011, 21:01     Реализовать двунаправленный список в духе списка из STL #5
ForEveR, когда списки пишешь - очень удобно на бумажке рисовать квадратики и стрелочки, соответствующие установке связок в алгоритме. Вот так нарисовал стрелочки и увидел, что одной не хватает - сразу понятно, что надо добавить. Попробуйте)))

Не по теме:

С "Ну так вы перед..." как-то грубовато вышло, извиняюсь)))

ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
11.02.2011, 22:21  [ТС]     Реализовать двунаправленный список в духе списка из STL #6
Ниже код. Есть несколько вопросов.
Не могу понять как сделать push_back/front через итераторы. Не получается. Хотелось бы увидеть простой пример на одну из данных функций.
функция back() - выдает ошибку, ибо end() у меня указывает на элемент за последним, то есть tail->next. Так как tail->next == 0 то --end() не выходит, ибо curr=curr->prev где curr == tail->next, вследствие чего - ошибка. Как исправить?
Ну и плоховато дело с erase. Буду благодарен за помощь.


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
struct bidirectional_iterator_tag:public std::forward_iterator_tag
{
};
 
template<class T>
class List
{
public:
    class Iterator;
    struct Node;
    typedef Iterator iterator;
    typedef T& reference;
    typedef const T& const_reference;
 
    List():head(0), tail(0), sz(0)
    {
    }
    size_t size() const {return sz;}
    bool empty() const {return sz == 0;}
    iterator begin() {return iterator(head);}
    iterator end() {return iterator(tail->next);}
    void push_back(const_reference el)
    {
        Node* tmp=new Node(el);
        if(empty())
        {
            head=tmp;
            tail=tmp;
            ++sz;
            return;
        }
        tail->next=tmp;
        tmp->prev=tail;
        tail=tmp;
        ++sz;
    }
    void push_front(const_reference el)
    {
        Node* tmp=new Node(el);
        if(empty())
        {
            head=tmp;
            tail=tmp;
            ++sz;
            return;
        }
        head->prev=tmp;
        tmp->next=head;
        head=tmp;
        ++sz;
    }
    reference front()
    {
        return *begin();
    }
    reference back()
    {
        return *(--end());
    }
    const_reference front() const
    {
        return *begin();
    }
    const_reference back() const
    {
        return *(--end());
    }
    void erase(iterator Where)
    {
        if(Where == begin())
        {
            Node* tmp=head;
            head=head->next;
            delete tmp;
            return;
        }
        for(Node* tmp=head; tmp; tmp=tmp->next)
        {
            if(tmp == Where.MyNode())
            {
                Node* ts=tmp;
                tmp=tmp->next;
                delete ts;
            }
        }
    }
private:
    struct Node
    {
        Node(T elem_=T(), Node* next_=0, Node* prev_=0)
            :next(next_),  elem(elem_), prev(prev_)
        {
        }
        Node* next;
        Node* prev;
        T elem;
    };
    Node* head;
    Node* tail;
    size_t sz;
};
 
template<class T> class List<T>::Iterator
{
public:
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef size_t difference_type;
    typedef T* pointer;
    typedef T& reference;
 
    Iterator(Node* t):
      curr(t)
      {
      }
    Iterator& operator ++()
    {
        curr=curr->next;
        return *this;
    }
    Iterator& operator --()
    {
        curr=curr->prev;
        return *this;
    }
    T& operator *()
    {
        return curr->elem;
    }
    Iterator& operator +(size_t idx)
    {
        for(size_t i=0; i<idx; ++i)
        {
            curr=curr->next;
        }
        return *this;
    }
    bool operator == (const Iterator& other) const 
    {
        return curr == other.curr;
    }
    bool operator != (const Iterator& other) const
    {
        return curr != other.curr;
    }
    Node* MyNode()
    {
        return curr;
    }
private:
    Node* curr;
};
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
11.02.2011, 23:47     Реализовать двунаправленный список в духе списка из STL #7
ForEveR, если я не ошибаюсь, std::list является кольцевым двусвязным списком, и при этом даже когда он пуст, в нём присутствуют два элемента — начало и конец. А новые элементы при добавлении встраиваются между ними. Таким образом решается проблема с итераторами.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
11.02.2011, 23:55  [ТС]     Реализовать двунаправленный список в духе списка из STL #8
volovzi, Не очень хочется делать список кольцевым... Есть какая-то другая возможность, без переделывания списка?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
12.02.2011, 00:00     Реализовать двунаправленный список в духе списка из STL #9
Точно не скажу, но список в стл всё-таки по-моему не кольцевой. А то, что все его элементы вставляются между start (первым элементом) и end (фиктивным элементом, следующим за последним) - это да. Собственно, я и не понимаю, как список с такими параметрами может быть кольцевым (когда есть чёткое начало и, хоть и фиктивный, но всё же конец).
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
12.02.2011, 00:01     Реализовать двунаправленный список в духе списка из STL #10
ForEveR, как сделать без зацикливания так сходу не соображу, надо подумать.

Добавлено через 1 минуту
Вот цитата из СБШ:
Код
a %list conceptually represented as
   *  @code
   *    A <---> B <---> C <---> D
   *  @endcode
   *  is actually circular; a link exists between A and D.  The %list
   *  class holds (as its only data member) a private list::iterator
   *  pointing to @e D, not to @e A!  To get to the head of the %list,
   *  we start at the tail and move forward by one.  When this member
   *  iterator's next/previous pointers refer to itself, the %list is
   *  %empty.  @endif
Список кольцевой, но дополнительный элемент там один, а не два, как я думал.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
12.02.2011, 00:03     Реализовать двунаправленный список в духе списка из STL #11
Цитата Сообщение от volovzi Посмотреть сообщение
Список кольцевой
Да, действительно. Не знал, спасибо.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.02.2011, 00:28  [ТС]     Реализовать двунаправленный список в духе списка из STL #12
То есть, чтобы закольцевать, должен быть фиктивный элемент, при этом фиктивный элемент - элемент за последним и фикт элем->next указывает на голову списка? При этом должен ли head->prev указывать на фикт элемент?
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
12.02.2011, 00:29     Реализовать двунаправленный список в духе списка из STL #13
ForEveR, да, так там сделано.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.02.2011, 00:33  [ТС]     Реализовать двунаправленный список в духе списка из STL #14
volovzi, Это ответ на оба вопроса?
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
12.02.2011, 00:39     Реализовать двунаправленный список в духе списка из STL #15
Ага, на оба.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.02.2011, 00:42  [ТС]     Реализовать двунаправленный список в духе списка из STL #16
Можешь приблизительно показать реализацию и использование такого фиктивного элемента? А то у меня что-то совсем туго...
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
12.02.2011, 13:50     Реализовать двунаправленный список в духе списка из STL #17
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Если совсем приблизительно, то будет выглядеть примерно так:
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
template <typename Value>
class circle_list {
 
// ---- Определения -------------------------------------------------------------------------------
 
public:
    typedef Value value_type;
 
// ---- Узел списка -------------------------------------------------------------------------------
 
private:
    struct node {
        explicit node (const value_type & value) : value(value), next(0), previous(0) {}
        ~node () { delete next; }
    
        value_type value;
        
        node * next;
        node * previous;
    };
 
// ---- Итераторы ---------------------------------------------------------------------------------
 
public:
    struct iterator {
        iterator () : m_node(0) {}
        explicit iterator (node * n) : m_node(n) {}
        
        value_type & operator * () { return m_node->value; }
        value_type * const operator -> () { return &m_node->value; }
        
        iterator & operator ++ () { return *this = iterator(m_node->next); }
        iterator & operator -- () { return *this = iterator(m_node->previous); }
        
        bool operator == (const iterator & i) const { return m_node == i.m_node; }
        bool operator != (const iterator & i) const { return m_node != i.m_node; }
    
        node * m_node;
    };
 
// ---- Создание и уничтожение --------------------------------------------------------------------
    
public:
    circle_list () : m_last(new node(value_type())), m_size(0) { m_last->previous = m_last->next = m_last; }
 
    ~circle_list () {
        if (m_last != 0) m_last->previous->next = 0;
        
        delete m_last;
    }
 
// ---- Модификации -------------------------------------------------------------------------------
    
    void push_back (const value_type & value) {
        node * new_node = new node(value);
        
        new_node->previous = m_last->previous;
        new_node->next = m_last;
        
        m_last->previous->next = new_node;
        m_last->previous = new_node;
        
        if (is_empty()) m_last->next = new_node;
        
        ++m_size;
    }
    
    iterator erase (iterator & position) {
        node * node_to_delete = position.m_node;
        node * result = node_to_delete->next;
        
        node_to_delete->previous->next = node_to_delete->next;
        node_to_delete->next->previous = node_to_delete->previous;
        
        node_to_delete->next = 0;
        delete node_to_delete;
        
        return position = iterator(result);
    }
 
// ---- Последовательный доступ -------------------------------------------------------------------
 
    iterator begin () { return ++iterator(m_last); }
    iterator end () { return iterator(m_last); }
 
// ---- Информация --------------------------------------------------------------------------------
    
    bool is_empty () const { return m_size == 0; }
    int size () const { return m_size; }
 
// ---- Переменные --------------------------------------------------------------------------------
    
private:
    node * m_last;
    
    int m_size;
};
Здесь многое упрощено, в частности, функция «erase», которая в оригинале работает немного не так.

Добавлено через 11 часов 36 минут
Хм, я erase неправильно написал. Так будет неправильно работать.

Добавлено через 43 минуты
Сложность в том, что, функция «erase» удаляет узел, на который в данный момент ссылается итератор, и из-за этого итератор в дальнейшем не может быть изменён из-за того, что его узел ссылается на нули.
Как это реализовано в СБШ пока не понял. Видимо, там какой-то небольшой сборщик мусора, который удаляет уже неиспользуемые узлы.

Добавлено через 19 минут
Придумал, как мне кажется, приемлимое решение: итератор запоминает указатели на следующий и предыдущий узлы на стадии инициализации, и поэтому удаление текущего узла на работа не сказывается:
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
template <typename Value>
class circle_list {
 
// ---- Определения -------------------------------------------------------------------------------
 
public:
    typedef Value value_type;
 
// ---- Узел списка -------------------------------------------------------------------------------
 
private:
    struct node {
        explicit node (const value_type & value) : value(value), next(0), previous(0) {}
        ~node () { delete next; }
    
        value_type value;
        
        node * next;
        node * previous;
    };
 
// ---- Итераторы ---------------------------------------------------------------------------------
 
public:
    struct iterator {
        iterator () : current(0), next(0), previous(0) {}
        explicit iterator (node * n) : current(n), next(n->next), previous(n->previous) {}
        
        value_type & operator * () { return current->value; }
        value_type * const operator -> () { return &current->value; }
        
        iterator & operator ++ () { return *this = iterator(next); }
        iterator & operator -- () { return *this = iterator(previous); }
        
        bool operator == (const iterator & i) const { return current == i.current; }
        bool operator != (const iterator & i) const { return current != i.current; }
    
        node * current;
        node * next;
        node * previous;
    };
 
// ---- Создание и уничтожение --------------------------------------------------------------------
    
public:
    circle_list () : m_last(new node(value_type())), m_size(0) { m_last->previous = m_last->next = m_last; }
 
    ~circle_list () {
        m_last->previous->next = 0;
        
        delete m_last;
    }
 
// ---- Модификации -------------------------------------------------------------------------------
    
    void push_back (const value_type & value) {
        node * new_node = new node(value);
        
        new_node->previous = m_last->previous;
        new_node->next = m_last;
        
        m_last->previous->next = new_node;
        m_last->previous = new_node;
        
        ++m_size;
    }
    
    void push_front (const value_type & value) {
        node * new_node = new node(value);
        
        new_node->previous = m_last;
        new_node->next = m_last->next;
        
        m_last->next->previous = new_node;
        m_last->next = new_node;
        
        ++m_size;
    }
    
    void pop_front () {
        node * node_to_delete = m_last->next;
    
        m_last->next = node_to_delete->next;
        node_to_delete->next->previous = m_last;
        
        node_to_delete->next = 0;
        delete node_to_delete;
    }
    
    void pop_back () {
        node * node_to_delete = m_last->previous;
        
        m_last->previous = node_to_delete->previous;
        node_to_delete->previous->next = m_last;
        
        node_to_delete->next = 0;
        delete node_to_delete;
    }
    
    iterator insert (iterator position, const value_type & value) {
        node * new_node = new node(value);
        node * current_node = position.current;
        
        new_node->next = current_node->next;
        new_node->previous = current_node;
        
        current_node->next->previous = new_node;
        current_node->next = new_node;
        
        return iterator(new_node);
    }
    
    iterator erase (iterator position) {
        node * node_to_delete = position.current;
        node * result = node_to_delete->next;
        
        node_to_delete->previous->next = node_to_delete->next;
        node_to_delete->next->previous = node_to_delete->previous;
        
        node_to_delete->next = 0;
        delete node_to_delete;
        
        return iterator(result);
    }
    
    void clear () {
        m_last->previous->next = 0;
        delete m_last->next;
        
        m_last->previous = m_last->next = m_last;
        m_size = 0;
    }
    
// ---- Доступ к элементам ------------------------------------------------------------------------
 
    value_type & front () { return m_last->next->value; }
    const value_type & front () const { return m_last->next->value; }
    
    value_type & back () { return m_last->previous->value; }
    const value_type & back () const { return m_last->previous->value; }
 
// ---- Последовательный доступ -------------------------------------------------------------------
 
    iterator begin () { return ++iterator(m_last); }
    iterator end () { return iterator(m_last); }
 
// ---- Информация --------------------------------------------------------------------------------
    
    bool is_empty () const { return m_size == 0; }
    int size () const { return m_size; }
 
// ---- Переменные --------------------------------------------------------------------------------
    
private:
    node * m_last;
    
    int m_size;
};
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
13.02.2011, 00:59  [ТС]     Реализовать двунаправленный список в духе списка из STL #18
volovzi, Однако действительно красиво. Попробую, спасибо

Добавлено через 34 минуты
Очень сильно помогло. Спасибо! Даже с алгоритмами пашет. Прекрасно. Буду доделывать дальше. Буду спрашивать, если не смогу справится. Спасибо огромное)
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
13.02.2011, 01:06     Реализовать двунаправленный список в духе списка из STL #19
Да не за что, самому интересно.

Добавлено через 4 минуты
Только нужно в удаления и добавлениях исправить корректировку размера списка, я там в нескольких местах забыл это сделать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.02.2011, 01:50     Реализовать двунаправленный список в духе списка из STL
Еще ссылки по теме:

C++ двунаправленный список
C++ Двунаправленный список

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

Или воспользуйтесь поиском по форуму:
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
13.02.2011, 01:50  [ТС]     Реализовать двунаправленный список в духе списка из STL #20
volovzi, Я пока с конструкторами занимаюсь. Ща разберусь и дальше продолжу) Спасибо огромное за помощь

Добавлено через 13 минут
Не могу понять вот такой фигни...
Есть два конструктора.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
    explicit List(size_t n, const T& value=T()):sz(0),head(new Node(T()))
    {
        head->prev=head->next=head;
        for(size_t i=0; i<n; ++i)
            push_back(value);
    }
    template<class iterator_>
    List(iterator_ first, iterator_ last):head(new Node(T())), sz(0)
    {
        head->prev=head->next=head;
        for(iterator_ beg=first; beg != last; ++beg)
            push_back(*beg);
    }
Почему он при вызове
C++
1
    List<int> Lst(5, 3);
Упорно пытается вызвать мне второй конструктор? Я прям-таки в шоке. Соответственно не работает, ибо *int ничего не выйдет.

Добавлено через 6 минут
Решилось все вот таким способом

C++
1
    List<int> Lst(static_cast<size_t>(5), 3);
Но все же это дико криво... Как-то ведь можно обойтись без такого чуда?
Yandex
Объявления
13.02.2011, 01:50     Реализовать двунаправленный список в духе списка из STL
Ответ Создать тему
Опции темы

Текущее время: 20:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru