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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.79
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
#1

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

11.02.2011, 20:37. Просмотров 4490. Ответов 44
Метки нет (Все метки)

Все-таки видимо у меня всегда останутся с этим проблемы.
Само определение скидывать не буду, я пытаюсь сделать, что-то вроде 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 ничего нет. В чем мб проблема?
Хотя вообще как я понял это для однонаправленного только катит... А вот как сделать для двунаправленного - второй день догнать не могу.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.02.2011, 20:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Реализовать двунаправленный список в духе списка из STL (C++):

Двунаправленный список (добавление/удаление элементов в голову, просмотр списка, реализовать дублирование элементов с заданным значением) - C++
Здравствуйте! Помогите написать программу, обеспечивающую работу с двунаправленным нециклическим списком: добавление/удаление элементов в...

Реализовать пользовательский класс "Двунаправленный список"; реализовать добавление и удаление элементов - C++
Записи в линейном списке содержат ключевое поле типа *char(строка символов). Сформировать двунаправленный список. Удалить К элементов с...

Реализовать удаление элемента из пользовательского класса "Двунаправленный список" - C++
Программа для работы с двунаправленным списком. Пользователь вводит список с клавиатуры, программа должна выводить его в обоих...

Реализовать двухсвязный список. Каждый элемент списка может содержать один объект - C++
Здравствуйте, мне нужно было реализовать двухсвязный список. Каждый элемент списка может содержать один объект. Объект может быть трех...

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

Двунаправленный список - C++
Как в этом списке поменять ввод элементов с ручного на рандомный, помогите пожалуйста? #include <iostream.h> struct tochd { ...

44
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
11.02.2011, 20:53 #2
Ну так вы перед тем, как tail'у присваивать tmp, установите в tmp prev-указатель на tail.

Добавлено через 2 минуты
Т.е. так:
C++
1
2
3
tail->next=tmp;
tmp->prev = tail;
tail=tmp;
1
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
11.02.2011, 20:56  [ТС] #3
silent_1991, Офигеть... столько проколебался а все так просто... шок)
0
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
11.02.2011, 20:56 #4
Ссылки на предыдущий элемент нет, потому что ты её не устанавливаешь.
C++
1
2
3
tail->next = tmp;
tmp->previous = tail;
tail = tail->next;
Добавлено через 30 секунд
Опоздал...
1
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
11.02.2011, 21:01 #5
ForEveR, когда списки пишешь - очень удобно на бумажке рисовать квадратики и стрелочки, соответствующие установке связок в алгоритме. Вот так нарисовал стрелочки и увидел, что одной не хватает - сразу понятно, что надо добавить. Попробуйте)))

Не по теме:

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

0
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
11.02.2011, 22:21  [ТС] #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;
};
0
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
11.02.2011, 23:47 #7
ForEveR, если я не ошибаюсь, std::list является кольцевым двусвязным списком, и при этом даже когда он пуст, в нём присутствуют два элемента — начало и конец. А новые элементы при добавлении встраиваются между ними. Таким образом решается проблема с итераторами.
1
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
11.02.2011, 23:55  [ТС] #8
volovzi, Не очень хочется делать список кольцевым... Есть какая-то другая возможность, без переделывания списка?
0
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.02.2011, 00:00 #9
Точно не скажу, но список в стл всё-таки по-моему не кольцевой. А то, что все его элементы вставляются между start (первым элементом) и end (фиктивным элементом, следующим за последним) - это да. Собственно, я и не понимаю, как список с такими параметрами может быть кольцевым (когда есть чёткое начало и, хоть и фиктивный, но всё же конец).
1
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
12.02.2011, 00:01 #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
Список кольцевой, но дополнительный элемент там один, а не два, как я думал.
2
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.02.2011, 00:03 #11
Цитата Сообщение от volovzi Посмотреть сообщение
Список кольцевой
Да, действительно. Не знал, спасибо.
0
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
12.02.2011, 00:28  [ТС] #12
То есть, чтобы закольцевать, должен быть фиктивный элемент, при этом фиктивный элемент - элемент за последним и фикт элем->next указывает на голову списка? При этом должен ли head->prev указывать на фикт элемент?
0
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
12.02.2011, 00:29 #13
ForEveR, да, так там сделано.
1
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
12.02.2011, 00:33  [ТС] #14
volovzi, Это ответ на оба вопроса?
0
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
12.02.2011, 00:39 #15
Ага, на оба.
1
12.02.2011, 00:39
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.02.2011, 00:39
Привет! Вот еще темы с ответами:

Двунаправленный список - C++
Вопросы: Почему ругается при таком описании, говорит ; пропустил spis_fam * Create_first(char *); //формирование первого элемента ...

Двунаправленный список - C++
Вот в примере елем в список добавл в конец, а как сдел чтобы они добавл в начало ? void List_2::Insert_end_list_2(int data) { Plist...

двунаправленный список - C++
Двунаправленный список.Найти сумму первого и последнего элементарных.Заранее спасибо

Двунаправленный список - C++
Как создать двунаправленный список из целых чисел? и как заменить повторяющиеся последовательности одним числом?


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

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

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