Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
4 / 1 / 0
Регистрация: 09.10.2015
Сообщений: 204
1

Реализовать указанные функции-члены для пользовательского класса "Кольцевой двусвязный список"

15.10.2016, 02:07. Показов 1004. Ответов 29
Метки нет (Все метки)

Сообственно сабж.
У списка два закрытых поля:
tail-это узел следующий за "последним"(условно,ибо список -кольцо. в tail-е лежит мусор)
tail->prev-это начало списка
tail->next -его конец
и sz-это размер списка. если список пустой-то там есть только tail и sz=0
Нужно реализовать несколько функций. Я определила их,но все равно есть сомнения в работоспособности некоторых,хотя может быть я плохо тестю. Посмотрите пож-та и укажите,если что не так.
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
#include <iostream>
using namespace std; 
struct Double_node
{
    Double_node *next;
    Double_node *prev;
    int val;
    Double_node() {}
    Double_node(int x) { val = x; };
    Double_node(int a, Double_node* b, Double_node* c) { val = a; next = b; prev = c; };
};
class Double_list
{
private:
    Double_node *tail;
    int sz;
public:
    Double_list() { tail = new Double_node; sz = 0; };
 
    Double_list(int x) { tail = new Double_node(x);  tail->next = tail; tail->prev = tail; sz = 1; };
 
    ~Double_list() { while (!tail) { Double_node* tmp; tmp = tail->next; delete tail->next; tmp = tmp->next; } delete tail->prev; sz = 0; }
 
    bool is_empty() { return sz == 0; };
 
    void add_front(int x) { tail->prev = new Double_node(x, tail->prev, tail); sz++; };
 
    void add_rear(int x) { tail->next = new Double_node(x, tail->next, tail); sz++; };
 
    void insert_after(int n, int x) { Double_node* tmp = tail->prev; for (int i = 0; i < n - 2; i++) tmp = tmp->next; Double_node* mem1 = tmp->next; Double_node* mem2 = tmp; tmp->next = new Double_node(x, mem1, mem2); sz++; }
 
    int remove(int x) { Double_node* tmp = tail->prev; for (tmp; tmp != tail; tmp = tmp->next) { if (tmp->val == x) { int mem = tmp->val; tmp->prev->next = tmp->next; delete tmp; sz--; return mem; } } };
 
    int remove_front() { int memory = tail->prev->val; Double_node* mem = tail->prev; mem->prev = tail; tail = mem->next; delete mem; sz--; return memory;  }
 
    int remove_rear() { int memory = tail->next->val; Double_node* mem = tail->next; tail->next = mem->next; mem->next->prev = tail; delete mem; sz--; return memory; }
 
    bool find(int x) { Double_node* tmp = tail->prev; for (tmp;tmp!=tail; tmp = tmp->next) { if (tmp->val == x) return true; }return false; };
 
    int get_nth(int n) { Double_node* tmp = tail->prev; for (int i = 0; i < n-2; i++) tmp = tmp->next; return tmp->val; };
 
    int size() { return sz; }
 
    };
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.10.2016, 02:07
Ответы с готовыми решениями:

На основе заданных прототипов реализовать функции-члены для пользовательского класса "Односвязный список"
Извиняюсь,забыла принт опреедлить Преподаватель дал прототипы функций ,которые надо определить для...

Написать конструктор для пользовательского класса "Двусвязный список"
Попытался построить двусвязный список. Как написать этот конструктор ? Может быть правильно будет...

Перегрузить указанные операторы для пользовательского типа "Однонаправленый список"
Помогите, ваще не понимаю в классах и перегрузке, нужна помощь, завтра сдавать лабу ...

Реализовать пользовательский класс "Список" и функции-члены для создания, просмотра и удаления списка
Добрый день. Имеются несколько функций для работы с однонаправленным списком. Не получается...

29
4 / 1 / 0
Регистрация: 09.10.2015
Сообщений: 204
15.10.2016, 02:19  [ТС] 2
вот схематично нарисовано,на данном примере sz=3
Миниатюры
Реализовать указанные функции-члены для пользовательского класса "Кольцевой двусвязный список"  
0
Заблокирован
Эксперт C
15.10.2016, 08:14 3
Получаю в личку
Цитата Сообщение от Kristina_S
Здравствуйте,судя по вашим ответам вы хорошо понимаете c++ .
Не могли бы вы помочь мою проблемы решить,а то мне никто не отвечает
Реализовать указанные функции-члены для пользовательского класса "Кольцевой двусвязный список"
Что я вам могу сказать.
Читайте правила. п.4.6. Уверяю вас, он придуман не напрасно
Тему вашу я видел. Если не ответил - значит нет охоты или возможности.
3
Эксперт CЭксперт С++
5068 / 2253 / 331
Регистрация: 20.02.2013
Сообщений: 5,595
Записей в блоге: 19
15.10.2016, 10:52 4
Цитата Сообщение от Байт Посмотреть сообщение
Получаю в личку
Байт, там в личке специальная треугольная кнопочка есть.
Миниатюры
Реализовать указанные функции-члены для пользовательского класса "Кольцевой двусвязный список"  
0
Заблокирован
Эксперт C
15.10.2016, 13:09 5
Цитата Сообщение от gru74ik Посмотреть сообщение
специальная треугольная кнопочка
Спасибо, но я как-то жаловаться не привык. Предпочитаю свои проблемы решать самостоятельно.
0
252 / 158 / 118
Регистрация: 26.11.2012
Сообщений: 384
15.10.2016, 15:08 6
Вся проблема в том, что посмотрев на ваш код написанный в строчку все желание его смотреть пропадает.
Вам удобно его читать? И почему бы всю программу не написать одной строкой?
0
Любитель чаепитий
3623 / 1710 / 532
Регистрация: 24.08.2014
Сообщений: 5,783
Записей в блоге: 1
15.10.2016, 15:21 7
Цитата Сообщение от Apostol584 Посмотреть сообщение
И почему бы всю программу не написать одной строкой?
Вот почему:
C++
1
#include <iostream>using namespace std; struct Double_node{Double_node *next;Double_node *prev;int val;Double_node() {}Double_node(int x) { val = x; };Double_node(int a, Double_node* b, Double_node* c) { val = a; next = b; prev = c; };};class Double_list{private:Double_node *tail;int sz;public:Double_list() {tail = new Double_node; sz = 0; }; Double_list(int x) { tail = new Double_node(x);  tail->next = tail; tail->prev = tail; sz = 1; };~Double_list() { while (!tail) { Double_node* tmp; tmp = tail->next; delete tail->next; tmp = tmp->next; } delete tail->prev; sz = 0; } bool is_empty() { eturn sz == 0; };void add_front(int x) { tail->prev = new Double_node(x, tail->prev, tail); sz++; };void add_rear(int x) { tail->next = new Double_node(x, tail->next, tail); sz++; };void insert_after(int n, int x) { Double_node* tmp = tail->prev; for (int i = 0; i < n - 2; i++) tmp = tmp->next; Double_node* mem1 = tmp->next; Double_node* mem2 = tmp; tmp->next = new Double_node(x, mem1, mem2); sz++; }int remove(int x) { Double_node* tmp = tail->prev; for (tmp; tmp != tail; tmp = tmp->next) { if (tmp->val == x) { int mem = tmp->val; tmp->prev->next = tmp->next; delete tmp; sz--; return mem; } } };int remove_front() { int memory = tail->prev->val; Double_node* mem = tail->prev; mem->prev = tail; tail = mem->next; delete mem; sz--; return memory;  }int remove_rear() { int memory = tail->next->val; Double_node* mem = tail->next; tail->next = mem->next; mem->next->prev = tail; delete mem; sz--; return memory; }bool find(int x) { Double_node* tmp = tail->prev; for (tmp;tmp!=tail; tmp = tmp->next) { if (tmp->val == x) return true; }return false; };int get_nth(int n) { Double_node* tmp = tail->prev; for (int i = 0; i < n-2; i++) tmp = tmp->next; return tmp->val; };int size() { return sz; }};
http://rextester.com/UQY99324
1
252 / 158 / 118
Регистрация: 26.11.2012
Сообщений: 384
16.10.2016, 02:03 8
вот пример
Кликните здесь для просмотра всего текста
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
    #include <iostream>
    #include <ctime>
    #include <iostream>
    using namespace std;
     
    struct Node{
        Node *next;
        Node *prev;
        int val;
        Node(int a = 0, Node* b = nullptr, Node* c = nullptr)
            : val(a), next(b), prev(c) {}
    };
     
    class List{
    private:
        Node *first, *last;
        int count;
     
        void clear() {
            for (int i = 0; i < count; i++) {
                last = first;
                first = first->next;
                delete last;
            }
            count = 0;
            first = last = nullptr;
        }
    public:
        List() 
            : first(nullptr), last(nullptr), count(0) {};
     
        List(const List &l)
            : first(nullptr), last(nullptr), count(0)
        {
            Node*tmp = l.first;
            for (int i = 0; i < l.count; i++) {
                push_back(tmp->val);
                tmp = tmp->next;
            }
        };
     
        List(List &&l)
            : first(l.first), last(l.last), count(count)
        {
            l.last = l.first = nullptr;
            l.count = 0;
        };
     
        List& operator = (const List &l) {
            if (this == &l) return *this;
            clear();
            Node*tmp = l.first;
            for (int i = 0; i < l.count; i++) {
                push_back(tmp->val);
                tmp = tmp->next;
            }
            return *this;
        }
     
        List& operator = (List &&l) {
            if (this == &l) return *this;
            first = l.first;
            last = l.last;
            count = l.count;
     
            l.first = l.last = nullptr;
            l.count = 0;
        }
     
     
        ~List() {
            clear();
        };
     
        void push_back(const int& x) {
            Node *tmp = new Node(x);
     
            if(!first){
                first = last = tmp;
            }
            else{
                last->next = tmp;
                tmp->prev = last;
                tmp->next = first;
                
                last = tmp;
            }
            count++;
        }
     
        void push_front(const int& x) {
            first = new Node(x, first, last);
     
            if (!last) {
                last = first;
                last->prev = first;
            }
     
            if (count == 1) {
                first->prev = last;
                last->next = first;
            }
            count++;
        }
     
        int pop_back() {
            Node * tmp = last;
            last = tmp->prev;
            last->next = first;
            first->prev = last;
     
            int x = tmp->val;
            delete tmp;
            count--;
            return x;
        }
     
        int pop_front() {
            Node * tmp = first;
            first = tmp->next;
     
            last->next = first;
            first->prev = last;
            int x = tmp->val;
            delete tmp;
            count--;
            return x;
        }
     
        int find(int x)const {
            Node *tmp = first;
            for (int i = 0; i < count; i++) {
                if (tmp->val == x) return i;
                tmp = tmp->next;
            }
            return -1;
        }
     
        bool is_empty()const { return !count; }
        int size()const { return count; }
     
     
     
        friend std::ostream& operator << (std::ostream &out, const List &l) {
            if (l.is_empty()) return out;
            Node *tmp = l.first;
            for (int i = 0; i < l.count - 1; i++) {
                out << tmp->val << "->";
                tmp = tmp->next;
            }
            out << tmp->val;
            return out;
        }
    };
     
     
    int main() {
    //  setlocale(LC_ALL, "russian");
        List l1, l2;
        for (int i = 0; i < 10; i++) {
            l1.push_back(i);
            l2.push_front(i);
        }
     
        std::cout << l1 << std::endl;
        std::cout << l2 << std::endl;
        
        
        std::cout << l1.pop_back() << std::endl;
        std::cout << l2.pop_front() << std::endl;
        
        std::cout << l1 << std::endl;
        std::cout << l2 << std::endl;
        
        std::cout << l1.find(5)  << std::endl;
        std::cout << l2.find(9)  << std::endl;
        
        
        //system("pause");
        return 0;
    }


Добавлено через 2 минуты

Не по теме:

GbaLog-, я имел в виду без деректив.

0
180 / 46 / 33
Регистрация: 27.02.2016
Сообщений: 259
16.10.2016, 10:17 9
Kristina_S, когда-то писал шаблонный класс подобный тому, что реализован в библиотеке STL. Всё, что действительно необходимо здесь есть, остальное можете добавить сами:
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
//LinkedList.hpp
 
#pragma once
 
template <typename T>
class LinkedList
{
private:
    struct ListItem
    {
        ListItem() : Prev(this), Next(this) {}
 
        ListItem(const T &value, ListItem *prev, ListItem *next) : Value(value), Prev(prev), Next(next) {}
 
        ~ListItem() 
        {
            Prev->Next = Next;
            Next->Prev = Prev;
        } 
 
        T Value;
        ListItem *Prev;
        ListItem *Next;
    };
public:
    class iterator
    {
    public:
        bool operator==(const iterator &other) const
        {
            return _position == other._position;
        }
 
        bool operator!=(const iterator &other) const
        {
            return _position != other._position;
        }
 
        T &operator*() const
        {
            return _position->Value;
        }
 
        T *operator->() const
        {
            return &(_position->Value);
        }
 
        iterator &operator++()
        {
            _position = _position->Next;
            
            return *this;
        }
 
        iterator operator++(int)
        {
            iterator temp = *this;
 
            _position = _position->Next;
 
            return temp;
        }
 
        iterator operator--()
        {
            _position = _position->Prev;
            
            return *this;
        }
 
        iterator operator--(int)
        {
            iterator temp = *this;
 
            _position = _position->Prev;
 
            return temp;
        }
 
        iterator &operator=(const iterator &other)
        {
            if (this != &other)
                _position = other._position;
 
            return *this;
        }
 
        friend class LinkedList;
    private:
        iterator(ListItem *position) : _position(position) {}
 
        ListItem *_position;
    };
public:
    LinkedList()
    {
        _head = new ListItem();
    }
 
    ~LinkedList() 
    {
        if (!empty())
        {
            iterator last = end(), it = begin();
 
            while (it != last)
                remove(it++);
 
            remove(it);
        }
    };
 
    LinkedList(const LinkedList &other)
    {
        _head = new ListItem();
 
        InitializeFrom(other);
    }
 
    LinkedList &operator=(const LinkedList &other)
    {
        if (this != &other)
            InitializeFrom(other);
 
        return *this;
    }
 
    iterator begin() const
    {
        return iterator(_head->Next);
    }
 
    iterator end() const
    {
        return iterator(_head);
    }
 
    void remove(iterator what)
    {
        delete what._position;
    }
 
    bool empty() const
    {
        return end() == begin();
    }
 
    void insert(iterator where, T value)
    {
        ListItem *wherePtr = where._position, *prevPtr = (--where)._position;
        ListItem *insertItemPtr = new ListItem(value, prevPtr, wherePtr);
 
        prevPtr->Next = insertItemPtr;
        wherePtr->Prev = insertItemPtr;
    }
 
    void push_back(T value)
    {
        insert(end(), value);
    }
 
    void push_front(T value)
    {
        insert(begin(), value);
    }
 
private:
    void InitializeFrom(const LinkedList &other)
    {
        if (other.empty())
            return;
 
        iterator it = begin(), another = other.begin();
 
        while (another != other.end())
        {
            if (it == end())
                push_back(*another);
            else
            {
                *it = *another;
                ++it;
            }
 
            ++another;
        }
    }
 
    ListItem *_head;
};
P.S.: Итератор очень полезная вещь, стоит ее активно использовать.
0
4 / 1 / 0
Регистрация: 09.10.2015
Сообщений: 204
16.10.2016, 16:00  [ТС] 10
я совсем не понимаю эти чертовы итераторы.
можете пожалуйста пофиксить например эту функцию
она вставляет элемент после данного итератора.
C++
1
2
3
4
5
6
7
8
9
void insert(iterator it, T x)
    {
        Double_node* mem = it;
        Double_node* added = new Double_node(x);
        mem->next->prev = added;
        mem->next = added;
        added->prev = mem;
        added->next = mem->next;
    }
0
180 / 46 / 33
Регистрация: 27.02.2016
Сообщений: 259
16.10.2016, 16:16 11
Kristina_S, для понимания итераторов лучше почитать литературу.
Если постараться объяснить на пальцах, то итератор это некая оболочка для указателя. Если мы имеем указатель на элемент списка, то чтобы перейти к следующему мы пишем: "указатель_на_текущий_элемент"->next. Гораздо удобнее эту инструкцию представить в виде ++"итератор"(итератор - это объект класса, он знает "указатель_на_текущий_элемент", и поэтому может выполнить "указатель_на_текущий_элемент"->next, а после вернуть вновь созданный итератор соответствующий след. элементу). Я старался объяснить, чтобы была понятна суть.
0
4 / 1 / 0
Регистрация: 09.10.2015
Сообщений: 204
16.10.2016, 16:18  [ТС] 12
ну это то я понимаю)
код,что выше почему-то не работает,хотя сделано все верно вроде,но выходит ошибка.
я даже на листочке пошагово программу написала,но не работает.
0
180 / 46 / 33
Регистрация: 27.02.2016
Сообщений: 259
16.10.2016, 16:27 13
Kristina_S, в строке 3 (если я правильно понимаю, то Double_node* - указатель на элемент списка) указателю на элемент списка присваиваете итератор. Это разные типы. Вместо итератора it нужно присваивать указатель в нем содержащийся(получить его можно it.position)
P.S.: Может у Вас это будет не position.
0
4 / 1 / 0
Регистрация: 09.10.2015
Сообщений: 204
16.10.2016, 16:32  [ТС] 14
Готово.
Но теперь компилятор ругается на строку №5
мол указатель был 0xCDCDCDCD
Причем это какая-то принципиальная ошибка у меня во многих функциях в этом классе такая ошибка выходит
что можно сделать с этим?(
0
180 / 46 / 33
Регистрация: 27.02.2016
Сообщений: 259
16.10.2016, 16:36 15
Kristina_S, дайте весь код который Вы компилируете.
0
4 / 1 / 0
Регистрация: 09.10.2015
Сообщений: 204
16.10.2016, 16:41  [ТС] 16
Вот.мне кажется тут не много ошибок,но они повторяются почти во всех функциях
посмотрите пож-та ,а то второй день ломаю голову уже
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include "d_list.h"
using namespace std;
 
int main()
{
    Double_list<int> list;
    for (int i = 0; i < 10; i++)
    {       
        list.add_rear(i); 
    }
    for (Double_list<int>::iterator p = list.rbegin(); p != list.rend(); p++) cout << *p<<' ';
    cout << endl;
    
 
 
    system("pause");
    return 0;
}
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
#include <iostream>
using namespace std; 
 
template <class T>
class Double_list
{
public: 
    struct Double_node
    {
        Double_node *next;
        Double_node *prev;
        int val;
        Double_node(){}
        Double_node(T x)
        { 
            val = x;
        }
        Double_node(T a, Double_node* b, Double_node* c) 
        {
            val = a;
            next = b; 
            prev = c;
        }
    };
    class iterator
    {
    public:
        Double_node* node;
    public:
        iterator(Double_node* tmp)
        {
            node = tmp; 
        }
        T& operator*() const 
        {
            return node->val;
        }
        iterator& operator++(int)
        {
            node = node->next;  
            return *this;
        }
        iterator& operator--(int) 
        { 
            node = node->prev; 
            return *this; 
        }
        iterator operator++()   
        {
            iterator it(node);  
            node = node->next;
            return it;
        }
        iterator operator--() 
        { 
            iterator it(node);
            node = node->prev; 
            return it; 
        }
        bool operator==(const iterator& it)const
        {
            return it.node == this->node;
        }
        bool operator!=(const iterator& it)const
        {
            return it.node != this->node;
        }
        iterator& operator+(const int n) 
        {
            for(int i = 0; i<n; i++)
                node = node->next;
            return *this;
        }
        int operator-(const iterator* const q)const
        {
            int counter = 0;
            for(const Double_list::iterator* p = this; p != q; p++)
                counter++;
            return counter;
        }
    };
public:
    Double_node *tail;
    int sz;
public:
    iterator rbegin() 
    { 
        return iterator(tail->prev);
    }
    iterator rend() 
    {
        return iterator(tail);
    }
    Double_list();
    Double_list(T);
    ~Double_list();
    bool is_empty();
    void add_front(T);
    void add_rear(T);
    void insert_after(int, T);
    T remove(int);
    T remove_front();
    T remove_rear();
    bool find(T );
    T get_nth(int);
    int size();
    void sort()
    {
 
    }
    void insert(iterator it, T x)
    {
        Double_node* mem = it.node;
        Double_node* added = new Double_node(x);
        mem->next->prev = added;
        mem->next = added;
        added->prev = mem;
        added->next = mem->next;
    }
    void remove_other(iterator it)
    {
        Double_node* mem = it.node;
        mem->prev->next = mem->next;
        mem->next->prev = mem->prev;
        delete mem;
    }
    void print()
    {
        Double_node* tmp = tail->prev;
        for (int i = 0; i < sz; i++, tmp = tmp->next)
            cout << tmp->val << ' ';
        cout << endl;
    }
    };
 
template<class T> Double_list<T>::Double_list()
{
    tail = new Double_node; sz = 0;
}
 
template<class T>  Double_list<T>::Double_list(T x)
{
    tail = new Double_node(x, tail, tail);  sz = 1;
}
 
template<class T>  Double_list<T>::~Double_list()
{
     while (!tail) 
     {
     Double_node* tmp=tail->next;
     delete tail;
     tail = tmp;
     } 
     delete tail;
     sz = 0; 
}
 
template<class T>  int Double_list<T>::size()
{
    return sz;
}
 
template<class T>  bool Double_list<T>::is_empty()
{
    return sz == 0;
}
 
template<class T>  void Double_list<T>::add_front(T x)
{
    if (is_empty())
    {
        tail->prev = new Double_node(x, tail, tail);
    }
    else
    {
        Double_node* mem = tail->prev;
        tail->prev = new Double_node(x, mem, tail);
        mem->prev = tail->prev;
    }
    sz++;
}
 
template<class T>  void Double_list<T>::add_rear(T x)
{
    insert(rend(), x);
    /*if (size() == 0)
    {
        tail->next = new Double_node(x,tail, tail);
        sz++;
    }
    else
    {
        Double_node* mem = tail->next;
        Double_node* added = new Double_node(x);
        tail->next->prev = added;
        added->prev = tail;
        tail->next = added;
        added->next = mem;
        sz++;
    }*/
}
template<class T>  void Double_list<T>::insert_after(int n, T x)
{
    if (size() >= n)
    {
        Double_node* mem = tail;
        for (int i = 0; i < n; i++)
            mem = mem->prev;
        Double_node* new_next = mem->next;
        Double_node* added = new Double_node(x);
        mem->next = added;
        new_next->prev = added;
        added->next = new_next;
        added->prev = mem;
        sz++;
    }
}
 
template<class T>  T Double_list<T>::remove(int n)
{
    Double_node* mem = tail;
    for (int i = 0; i < n; i++, mem = mem->prev);
    mem->prev->next = mem->next;
    mem->next->prev = mem->prev;
    T memory = mem->val;
    delete mem;
    sz--;
    return memory;
}
 
template<class T>  T Double_list<T>::remove_front()
{
    T memory = tail->prev->val;
    Double_node* mem = tail->prev;
    tail->prev = tail->prev->next;
    tail->prev->next = tail;
    delete mem;
    sz--;
    return memory;
}
 
template<class T>  T Double_list<T>::remove_rear()
{
    T memory = tail->next->val;
    Double_node* mem = tail->next;
    tail->next = tail->next->next;
    tail->next->next->prev = tail;
    delete mem;
    sz--;
    return memory;
}
 
template<class T>  bool Double_list<T>::find(T x)
{
     Double_node* tmp = tail->prev;
     for (tmp; tmp != tail; tmp = tmp->next)
     { 
         if (tmp->val == x) 
             return true; 
     }
     return false; 
}
 
template<class T>  T Double_list<T>::get_nth(int n)
{
    Double_node* mem = tail;
    for (int i = 0; i < n; i++, mem = mem->next);
    return mem->val;
}
0
180 / 46 / 33
Регистрация: 27.02.2016
Сообщений: 259
16.10.2016, 16:53 17
Kristina_S, общие замечания:
1. Шаблонные функции, классы рекомендовано реализовывать в .hpp файлах(тогда и методы шаблонного класса спокойно реализуются, без создания для каждого шаблонной функции)
2. Обратите внимание на класс элемента списка в моем примере. Конструкторы и деструкторы сами настраивают связи, это очень сильно упрощает написание программы.
0
4 / 1 / 0
Регистрация: 09.10.2015
Сообщений: 204
16.10.2016, 17:14  [ТС] 18
1) нам препод сказал опредение функций в .h файл поместить после класса
может как-то нерпавильно просить вас это,но можете реализовать одну функцию add_rear(T); чтобы я сам принцип поняла
0
180 / 46 / 33
Регистрация: 27.02.2016
Сообщений: 259
16.10.2016, 17:54 19
Kristina_S, в целом у вас эта функция должна выглядеть так:
C++
1
2
3
4
    void add_rear(T value)
    {
        insert(end(), value);
    }
1
4 / 1 / 0
Регистрация: 09.10.2015
Сообщений: 204
16.10.2016, 18:28  [ТС] 20
Ага,получается все функции почти можно так реализовать через итераторы
а сама функция вставки должна выглядить так?
C++
1
2
3
4
5
6
7
8
9
void insert(iterator it, T x)
    {
        Double_node* mem = it.node;
        Double_node* new_next = it.node->next;
        Double_node* inserted = new Double_node(x, it.node->next, it.node);
        it.node->next = inserted;
        new_next->prev = inserted;
        sz++;
    }
Добавлено через 6 минут
------
Ага,получается все функции почти можно так реализовать через итераторы
а сама функция вставки должна выглядить так?
вставляет узел со значением "x" типа "T" после узлы на который указывает итератор it
по вашему прототипу сделал
C++
1
2
3
4
5
6
7
8
9
void insert(iterator it, T x)
    {
        Double_node* mem = it.node;
        Double_node* mem_next = (++it).node;
        Double_node* added = new Double_node(x, mem_next, mem);
        mem_next->prev = added;
        mem->next = added;
        sz++;
    }
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.10.2016, 18:28

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

Иерархия классов "Структура - Список - Кольцевой Двусвязный список"
Неделю назад получил задание и срок выполнения до конца мая. Разработка иерархии классов....

Обработка пользовательского класса "Односвязный линейный список"
Доброго времени суток. Хочу написать программу для обработки односвязного линейного списка (ОЛС)...

Реализовать класс "Книжный магазин", используя двусвязный список (ошибка с покупкой книги)
Доброго времени суток,мне нужно реализовать класс BookShop используя двусязный список,все методы...


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

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

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