Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
2 из 3 « 1 2 3 »
 
Рейтинг 4.86/413: Рейтинг темы: голосов - 413, средняя оценка - 4.86
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
1

Списки, стеки, очереди

19.10.2010, 12:11. Показов 77531. Ответов 53
Метки нет (Все метки)
Author24 — интернет-сервис помощи студентам
В процессе разбора этой темы появились программки на список. Сделанные через класс, не идеал конечно, но вроде бы и не самый плохой вариант. Выложу, вдруг кому пригодится. Конструктивная критика приветствуется.
Двунаправленный список и очередь будет чуть позже. С двунаправленным возникли некоторые трудности.

Однонаправленный список
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

#ifndef _LISTNODE_H_
#define _LISTNODE_H_
 
#include <iostream>
#include <string>
 
template<class T>
class List
{
public:
    List():head(0), tail(0)
    {
    }
    
    ~List()
    {
        delete head;
        delete tail;
    }
 
    void push_back(T val)
    {
        Node* Temp;
        Temp=new Node;
        Temp->elem=val;
        if(head==0)
        {
            head=Temp;
            tail=Temp;
            return;
        }
        tail->next=Temp;
        tail=Temp;
    }
 
    void print()
    {
        if(head==0)
        {
            throw std::string("List is empty!");
        }
        for(Node* ptr=head; ptr!=0; ptr=ptr->next)
        {
            std::cout<<ptr->elem<<' ';
        }
        std::cout<<'\n';
    }
 
    void push_front(T val)
    {
        Node* Temp;
        Temp=new Node;
        Temp->elem=val;
        Temp->next=head;
        head=Temp;
    }
 
    void erase()
    {
        if(head==0)
        {
            throw std::string("List is empty!\n");
        }
        Node* delptr=head->next;
        head=head->next;
        delete delptr;
    }
    
    void erase(T val)
    {
        Node* ptrPrev;
        ptrPrev=new Node;
        if(head==0)
        {
            throw std::string("List is empty\n");
        }
        for(Node* ptr=head; ptr!=0; ptr=ptr->next)
        {
            if(ptr->elem==val)
            {
                ptrPrev->next=ptr->next;
                delete ptr;
                break;
            }
            ptrPrev=ptr;
        }
        if(ptrPrev->next==0)
            std::cout<<"There are no elements in list equal to "<< val <<'\n';
    }
 
    void clear()
    {
        while(head!=0)
            erase();
    }
 
    void find(T val)
    {
        if(head==0)
        {
            throw std::string("List is empty!\n");
        }
        for(Node* ptr=head; ptr!=0; ptr=ptr->next)
        {
            if(ptr->elem=val)
                std::cout<<"Element "<< val <<" is finded\n";
            return;
        }
        std::cout<<"Element "<< val <<" is not finded\n";
    }
    
    void insert(T val)
    {
        if(head==0)
        {
            push_front(val);
            return;
        }
        Node* Temp=new Node;
        Temp->elem=val;
        Node* founded=head;
        for(founded; founded!=0; founded=founded->next)
        {
            if(founded->elem<val)
                break;
        }
        if(founded==0)
        {
            push_front(val);
            return;
        }
        Temp->next=founded->next;
        founded->next=Temp;
    }
private:
    struct Node
    {
                Node():next(0), elem(0)
                {
                }
        Node* next;
        T elem;
    };
 
    Node* head;
    Node* tail;
};
 
#endif
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

#include "ListNode.h"
 
int main()
{
    List<int> Lst;
    Lst.push_back(5);
    Lst.push_back(10);
    Lst.push_back(15);
    Lst.push_front(1);
    Lst.push_front(25);
    Lst.push_back(4);
    Lst.insert(9);
    Lst.insert(6);
    Lst.insert(4);
    Lst.insert(5);
    Lst.insert(55);
    Lst.insert(40);
    Lst.insert(0);
    Lst.insert(70);
    Lst.insert(56);
    Lst.erase(5);
    try
    {
        Lst.print();
    }
    catch(const std::string& e)
    {
        std::cout<<e<<'\n';
    }
    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

#ifndef _STACKNODE_H_
#define _STACKNODE_H_
 
#include <string>
 
template<class T>
class Stack
{
public:
    Stack():tail(0), head(0)
    {
    }
    
    ~Stack()
    {
        delete tail;
        delete head;
    }
 
    void push(T val)
    {
        Node* Temp;
        Temp=new Node;
        Temp->elem=val;
        if(tail==0)
        {
            tail=Temp;
        }
        else
        {
            Temp->next=tail;
            tail=Temp;
        }
    }
 
    T top()
    {
        if(tail==0)
        {
            throw std::string("Stack is empty!");
        }
        return tail->elem;
    }
 
    void pop()
    {
        if(tail==0)
        {
            throw std::string("Stack is empty!");
        }
        Node* delptr=tail;
        tail=tail->next;
        delete delptr;
    }
 
    void print()
    {
        if(tail==0)
        {
            throw std::string("Stack is empty!");
        }
        for(Node* ptr=tail; ptr!=0; ptr=ptr->next)
        {
            std::cout<<ptr->elem<<' ';
        }
        std::cout<<'\n';
    }
private:
    struct Node
    {
        Node():elem(0), next(0)
        {
        }
        Node* next;
        T elem;
    };
    Node* head;
    Node* tail;
};
 
#endif
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

#include <iostream>
 
#include "StackNode.h"
 
int main()
{
    Stack<char> St;
    St.push('a');
    St.push('b');
    St.push('d');
    St.push('c');
    try
    {
        St.print();
        std::cout<<St.top()<<'\n';
        St.pop();
        St.print();
        std::cout<<St.top()<<'\n';
        St.pop();
        St.print();
        std::cout<<St.top()<<'\n';
        St.pop();
        St.print();
        std::cout<<St.top()<<'\n';
        St.pop();
        St.print();
    }
    catch(const std::string& e)
    {
        std::cout<<e<<'\n';
    }
    return 0;
}


Добавлено через 48 минут
Очередь
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

#ifndef _QUEUE_H_
#define _QUEUE_H_
 
#include <iostream>
#include <string>
 
template<class T>
class NodeQueue
{
public:
    NodeQueue():head(0), tail(0)
    {
    }
 
    ~NodeQueue()
    {
        delete head;
        delete tail;
    }
 
    void enqueue(T val)
    {
        Node* Temp=new Node;
        Temp->elem=val;
        if(head==0)
        {
            head=Temp;
            tail=Temp;
            return;
        }
        tail->next=Temp;
        tail=Temp;
    }
 
    void dequeue()
    {
        if (empty())
        {
            throw std::string("Queue is empty");
        }
        Node* delPtr=head;
        std::cout<<"Element "<< head->elem <<" is deleted from the queue\n";
        head=head->next;
        delete delPtr;
    }
 
    const T& front() const
    {
        if (empty())
        {
            throw std::string("Queue is empty");
        }
        return head->elem;
    }
 
    void print() const
    {
        if (empty())
        {
            throw std::string("Queue is empty");
        }
        for(Node* ptr=head; ptr!=0; ptr=ptr->next)
            std::cout<<ptr->elem<<' ';
        std::cout<<'\n';
    }
 
    bool empty() const
    {
        return head==0;
    }
private:
    struct Node
    {
                Node():next(0), elem(0)
                {
                }
        Node* next;
        T elem;
    };
    Node* head;
    Node* tail;
};
 
#endif
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
 
#include "Queue.h"
 
int main()
{
        try
        {
    NodeQueue<int> Queue;
    Queue.enqueue(10);
    Queue.enqueue(20);
    Queue.enqueue(30);
    std::cout<<"Top is: "<<Queue.front()<<'\n';
    Queue.dequeue();
    Queue.print();
        }
        catch(const std::string& e)
        {
             std::cout<<e<<'\n';
        }
}
13
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 19.10.2010, 12:11
Ответы с готовыми решениями:

Списки. Стеки. Очереди
Квадрат разбит на {4}^{k} равновеликих квадратных клеток. Квадрат перегибается поочередно...

Задача на тему Стеки, очереди, деки, списки, кольца
Программа на вход получает список школьников следующего вида: 9 Иванов 10 Петров ...

Списки, Стеки,Очереди (На сколько кусков распадется оставшаяся часть листа? )
Доброго всем времени суток!! Помогите написать программу: Из листа клетчатой бумаги размером М*N...

Очереди и стеки
#include &quot;stdafx.h&quot; #include &quot;iostream&quot; using namespace std; struct stack { int x; stack...

53
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
27.05.2011, 12:23  [ТС] 21
Лучший ответ Сообщение было отмечено как решение

Решение

Author24 — интернет-сервис помощи студентам
lemegeton, Поддержки STL нету, а так шикарно.
Для списка исправить легко - ввести typedef-ы iterator_category и difference_type.

Добавлено через 9 часов 38 минут
Чуть более чем полностью нестандартный стек. Слишком уж много заданий с издевательством над стеком стало появляться.

"Стэк"
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

#include <iterator>
#include <numeric>
 
namespace my
{
 
template<class T>
class stack
{
    struct Node
    {
        Node():elem(T()), next(0)
        {
        }
        Node(T el):elem(el), next(0)
        {
        }
        T elem;
        Node* next;
    };
    class Const_Iterator;
    class Iterator;
 
public:
    typedef T value_type;
    typedef size_t size_type;
    typedef T* pointer;
    typedef T& reference;
    typedef const T* const_pointer;
    typedef const T& const_reference;
    typedef Const_Iterator const_iterator;
    typedef Iterator iterator;
 
    stack():data(0), sz(0)
    {
    }
    ~stack()
    {
        while(data)
        {
            pop();
        }
    }
    stack(const stack& other):sz(0), data(0)
    {
        stack temp;
        for(Node* tmp = other.data; tmp; tmp = tmp->next)
        {
            temp.push(tmp->elem);
        }
        while(!temp.empty())
        {
            push(temp.top());
            temp.pop();
        }
    }
    stack& operator =(const stack& other)
    {
        stack tmp(other);
        swap(tmp);
        return *this;
    }
    void push(const_reference el)
    {
        Node* tmp = new Node(el);
        tmp->next = data;
        data = tmp;
        ++sz;
    }
    void pop()
    {
        Node* tmp = data;
        data = data->next;
        --sz;
        delete tmp;
    }
    bool empty() const {return sz == 0;}
    size_type size() const {return sz;}
    reference top() {return data->elem;}
    const_reference top() const {return data->elem;}
    iterator begin() {return iterator(data);}
    iterator end() {return iterator(0);}
    const_iterator begin() const {return const_iterator(data);}
    const_iterator end() const {return const_iterator(0);}
private:
    void swap(stack& other)
    {
        std::swap(data, other.data);
        std::swap(sz, other.sz);
    }
    Node* data;
    size_t sz;
    
    class Const_Iterator
    {
    public:
        typedef std::forward_iterator_tag iterator_category;
        typedef ptrdiff_t difference_type;
        typedef T value_type;
        typedef const T& reference;
        typedef const T* pointer;
 
        Const_Iterator(Node* curr):
            current(curr)
        {
        }
        Const_Iterator& operator ++()
        {
            if(current)
                current = current->next;
            return *this;
        }
        Const_Iterator operator ++(int)
        {
            Const_Iterator temp(current);
            ++(*this);
            return temp;
        }
        reference operator *() const {return current->elem;}
        pointer operator ->() const {return &current->elem;}
        bool operator ==(const Const_Iterator& other) const
        {
            return current == other.current;
        }
        bool operator !=(const Const_Iterator& other) const
        {
            return (!(*this == other));
        }
    private:
        Node* current;
    };
    
    class Iterator
    {
    public:
        typedef std::forward_iterator_tag iterator_category;
        typedef ptrdiff_t difference_type;
        typedef T value_type;
        typedef T& reference;
        typedef T* pointer;
 
        Iterator(Node* curr):
            current(curr)
        {
        }
        Iterator& operator ++()
        {
           if(current)
                current = current->next;
           return *this;
        }
        Iterator& operator ++(int)
        {
            Iterator temp(current);
            ++(*this);
            return temp;
        }
        reference operator *() {return current->elem;}
        pointer operator ->() {return &current->elem;} 
        bool operator !=(const Iterator & other)
        {
            return current != other.current;
        }
        bool operator ==(const Iterator& other)
        {
            return (!(other != *this));
        }
    private:
        Node* current;
    };
};
 
}//namespace my
Пример.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include "stack.hpp"
#include <iostream>
#include <numeric>
 
int main()
{
    my::stack<int> stck;
    stck.push(5);
    stck.push(4);
    stck.push(10);
    stck.push(1);
    stck.push(3);
    std::cout << std::accumulate(stck.begin(), stck.end(), 0) << '\n';
}


Добавлено через 2 часа 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
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

#ifndef QUEUE_HPP
#define QUEUE_HPP
 
#include <iterator>
 
namespace my
{
 
template<class T>
class queue
{
    struct Node
    {
        Node():elem(T()), next(0)
        {
        }
        Node(T el):elem(el), next(0)
        {
        }
        Node* next;
        T elem;
    };
    class Iterator;
    class Const_Iterator;
public:
    typedef T value_type;
    typedef size_t size_type;
    typedef T* pointer;
    typedef T& reference;
    typedef const T* const_pointer;
    typedef const T& const_reference;
    typedef Iterator iterator;
    typedef Const_Iterator const_iterator;
    
    queue():head(0), tail(0), sz(0)
    {
    }
    
    ~queue()
    {
        while(head)
            pop();
    }
    
    queue(const queue& other)
    {
        for(Node* tmp = other.head; tmp; tmp = tmp->next)
            push(tmp->elem);
    }
    
    queue& operator =(const queue& other)
    {
        queue tmp(other);
        swap(tmp);
        return *this;
    }
 
    void push(T el)
    {
        Node* temp = new Node(el);
        if(!head)
        {
            head = temp;
            tail = temp;
        }
        else
        {
            tail->next = temp;
            tail = temp;
        }
        ++sz;
    }
 
    void pop()
    {
        Node* temp = head;
        head = head->next;
        delete temp;
        --sz;
    }
    
    reference back() {return tail->elem;}
    reference front() {return head->elem;}
    const_reference back() const {return tail->elem;}
    const_reference front() const {return head->elem;}
    size_type size() const {return sz;}
    bool empty() const {return sz == 0;}
    iterator begin() {return iterator(head);}
    iterator end() {return iterator(0);}
    const_iterator begin() const {return const_iterator(head);}
    const_iterator end() const {return const_iterator(0);}
 
private:
    void swap(queue& other)
    {
        std::swap(head, other.head);
        std::swap(tail, other.tail);
        std::swap(sz, other.sz);
    }
    
    class Const_Iterator
    {
    public:
        typedef T value_type;
        typedef const T* pointer;
        typedef const T& reference;
        typedef ptrdiff_t difference_type;
        typedef std::forward_iterator_tag iterator_category;
 
        Const_Iterator(Node* curr):current(curr)
        {
        }
        Const_Iterator& operator ++()
        {
            if(current)
                current = current->next;
            return *this;
        }
        Const_Iterator operator ++(int)
        {
            Const_Iterator temp(current);
            ++(*this);
            return temp;
        }
        reference operator *() const {return current->elem;}
        pointer operator ->() const {return &current->elem;}
        bool operator ==(const Const_Iterator& other) const
        {
            return current == other.current;
        }
        bool operator !=(const Const_Iterator& other) const
        {
            return (!(*this == other));
        }
    private:
        Node* current;
    };
    
    class Iterator
    {
    public:
        typedef T value_type;
        typedef T* pointer;
        typedef T& reference;
        typedef ptrdiff_t difference_type;
        typedef std::forward_iterator_tag iterator_category;
 
        Iterator(Node* curr):current(curr)
        {
        }
        Iterator& operator ++()
        {
            if(current)
                current = current->next;
            return *this;
        }
        Iterator operator ++(int)
        {
            Iterator temp(current);
            ++(*this);
            return temp;
        }
        reference operator *() {return current->elem;}
        pointer operator ->() {return &current->elem;}
        bool operator ==(const Iterator& other) const
        {
            return current == other.current;
        }
        bool operator !=(const Iterator& other) const
        {
            return (!(*this == other));
        }
    private:
        Node* current;
    };
 
    Node* head;
    Node* tail;
    size_type sz;
};
 
}
 
#endif
Пример.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <iostream>
#include <algorithm>
 
#include "simple_stl/queue.hpp"
 
int main()
{
    my::queue<int> queue;
    queue.push(10);
    queue.push(15);
    queue.push(6);
    queue.push(3);
    std::cout << *std::max_element(queue.begin(), queue.end()) << '\n';
    return 0;
}
6
4773 / 2582 / 894
Регистрация: 29.11.2010
Сообщений: 5,590
29.05.2011, 22:55 22
Опять-таки сильно упрощенный, (например без конст-итераторов), мало чем отличающийся от связного списка
дек на базе связного списка.
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

#include <cstdlib>
 
struct node_base_ {
  node_base_ *next;
  node_base_ *prev;
  node_base_() : next(this), prev(this) {}
  node_base_(node_base_ *next_, node_base_ *prev_)
    : next(next_), prev(prev_) {
    prev->next = next->prev = this;
  }
  virtual ~node_base_() {
    prev->next = next;
    next->prev = prev;
  }
};
 
template <class Tp_>
struct node_: public node_base_ {
  Tp_ value;
  node_() : node_base_() {}
  node_(node_base_ *next_, node_base_ *prev_, const Tp_ &value_)
    : node_base_(next_, prev_), value(value_) {}
};
 
template <class Tp_>
struct iterator_base_ {
  typedef iterator_base_<Tp_> _self;
  typedef node_<Tp_> _node;
  typedef ptrdiff_t  difference_type;
  typedef Tp_        value_type;
  typedef Tp_*       pointer;
  typedef Tp_&       reference;
  iterator_base_() : node(0) {}
  explicit iterator_base_(node_base_ *node_) : node(node_) {}
  reference operator*() { return static_cast<_node*>(node)->value; }
  pointer operator->() { return &static_cast<_node*>(node)->value; }
  _self &operator++() {
    node = node->next;
    return *this;
  }
  _self &operator--() {
    node = node->prev;
    return *this;
  }
  _self operator++(int) {
    _self result(node);
    operator++();
    return result;
  }
  _self operator--(int) {
    _self result(node);
    operator--();
    return result;
  }
  _self operator-(int value) {
    _self result(node);
    while (value--) --result;
    return result;
  }
  _self operator+(int value) {
    _self result(node);
    while (value--) ++result;
    return result;
  }
  bool operator==(const _self &other) const {
    return node == other.node;
  }
  bool operator!=(const _self &other) const {
    return node != other.node;
  }
  node_base_ *node;
};
 
template <class iterator_begin, class iterator_end>
size_t distance(iterator_begin begin, iterator_end end) {
  size_t result = 0;
  for (; begin != end; ++result, ++begin);
  return result;
}
 
template <class Tp_>
class deque {
 public:
  typedef iterator_base_<Tp_> iterator;
  typedef node_<Tp_> node;
  typedef ptrdiff_t  difference_type;
  typedef Tp_        value_type;
  typedef Tp_*       pointer;
  typedef Tp_&       reference;
  deque() {}
  ~deque() { clear(); }
  deque(const deque &other) {
    insert(begin(), other.begin(), other.end());
  }
  reference at(size_t position) {
    return *(begin() + position);
  }
  bool empty() const {
    return (base_.next == &base_ && base_.prev == &base_);
  }
  iterator erase(iterator position) {
    iterator result = position + 1;
    delete position.node;
    return result;
  }
  iterator erase(iterator begin, iterator end) {
    while (begin != end) erase(begin);
  }
  size_t size() {
    return distance(begin(), end());
  }
  void clear() {
    while (!empty()) delete base_.next;
  }
  iterator insert(iterator before, const value_type &value) {
    return iterator(new node(before.node, before.node->prev, value));
  }
  iterator insert(iterator before, iterator begin, iterator end) {
    while (begin != end) push_back(*(begin++));
  }
  iterator begin() { return iterator(base_.next); }
  iterator end() { return iterator(&base_); }
  reference front() { return *begin(); }
  reference back() { return *(end() - 1); }
  iterator push_back(const value_type &value) {
    return insert(end(), value);
  }
  iterator push_front(const value_type &value) {
    return insert(begin(), value);
  }
  void pop_back() {
    delete base_.prev;
  }
  void pop_front() {
    delete base_.next;
  }
  reference operator[](size_t position) {
    return *(begin() + position);
  }
  deque &operator=(const deque &other) {
    clear();
    insert(begin(), other.begin(), other.end());
  }
 private:
  node_base_ base_;
};
Пример.
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

//#include "ideque.h"
#include <iostream>
 
int main(int argc, char *argv[]) {
  deque<int> a;
  a.push_back(2);
  a.push_front(3);
  a.push_back(1);
  a.push_front(4);
  a.push_front(5);
  for (deque<int>::iterator i = a.begin(); i != a.end(); ++i)
    std::cout << "= " << *i << std::endl;
  std::cout << "Size: " << a.size() << std::endl;
  std::cout << a.front() << std::endl;
  std::cout << a.back() << std::endl;
  a.pop_back();
  a.pop_front();
  a.erase(a.begin());
  a.erase(a.end() - 1);
  for (deque<int>::iterator i = a.begin(); i != a.end(); ++i)
    std::cout << "= " << *i << std::endl;
  std::cout << a.front() << std::endl;
  std::cout << a.back() << std::endl;
  return 0;
}

Главная фишка подхода в том, что в основном классе нет ни одного метода, длиннее 3-х строк.
2
4773 / 2582 / 894
Регистрация: 29.11.2010
Сообщений: 5,590
02.06.2011, 21:16 23
Функции дека на Си
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

#include <stdlib.h>
#include <stdio.h>
 
typedef int ValueType;
 
typedef struct Node {
  ValueType value;
  struct Node *prev;
  struct Node *next;
} Node;
 
typedef struct Deque {
  Node base;
  size_t size;
} Deque;
// создание элемента с добавлением его в список
Node *NodeNew(Node *next, Node *prev, ValueType value) {
  Node *node = (Node*)malloc(sizeof(Node));
  prev->next = next->prev = node;
  node->next = next;
  node->prev = prev;
  node->value = value;
  return node;
}
// удаление ноды с изъятием её из списка
void NodeDelete(Node *node) {
  node->next->prev = node->prev;
  node->prev->next = node->next;
  free(node);
}
// инициализация дека
void DequeNew(Deque *deque) {
  deque->base.next = deque->base.prev = &(deque->base);
  deque->size = 0;
}
// проверка на пустоту дека
int DequeEmpty(Deque *deque) {
  return (deque->base.next == &(deque->base));
}
// удаление дека
void DequeDelete(Deque *deque) {
  while (!DequeEmpty(deque))
    NodeDelete(deque->base.next);
  deque->size = 0;
}
// добавление в конец
void DequePushBack(Deque *deque, ValueType value) {
  NodeNew(&(deque->base), deque->base.prev, value);
  ++deque->size;
}
// удаление с конца
void DequePopBack(Deque *deque) {
  NodeDelete(deque->base.prev);
  --deque->size;
}
// добавление в начало
void DequePushFront(Deque *deque, ValueType value) {
  NodeNew(deque->base.next, &(deque->base), value);
  ++deque->size;
}
// удаление с конца
void DequePopFront(Deque *deque) {
  NodeDelete(deque->base.next);
  --deque->size;
}
// первый элемент дека
ValueType DequeFront(Deque *deque) {
  return deque->base.next->value;
}
// последний элемент дека
ValueType DequeBack(Deque *deque) {
  return deque->base.prev->value;
}
// печать всех элементов дека
void DequePrintf(Deque *deque, const char *format, const char *finish) {
  Node *node = deque->base.next;
  while (node != &(deque->base)) {
    printf(format, node->value);
    node = node->next;
  }
  printf("%s", finish);
}
 
int main(int argc, char *argv[]) {
  int i;
  Deque deque;
  DequeNew(&deque);
  for (i = 0; i < 100; ++i)
    if (i % 2)
      DequePushBack(&deque, i);
    else
      DequePushFront(&deque, i);
  DequePopBack(&deque);
  DequePopFront(&deque);
  DequePrintf(&deque, "%4d", "\n");
  DequeDelete(&deque);
  return 0;
}
2
5231 / 3204 / 362
Регистрация: 12.12.2009
Сообщений: 8,116
Записей в блоге: 2
22.06.2011, 15:15 24
Лучший ответ Сообщение было отмечено как решение

Решение

Для учебы пришлось написать, выкладываю - может кому-нибудь пригодится.
Stack с вложенным классом iterator
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

#ifndef _TSTACK_H_
#define _TSTACK_H_
 
#include <iostream>
 
typedef unsigned int size_type;
 
template<class T>
class Stack{
    struct Node{
        T data;
        Node *next;
        Node(T dat,Node *nxt):
            data(dat),next(nxt){}
    }*head;
    size_type count;
public:
    Stack():head(NULL),count(0){}
    ~Stack(){
        while(head){
            Node *oldHead=head;
            head=head->next;
            delete oldHead;
        }
    }
 
    void push(T &dat){
        head=new Node(dat,head);
        ++count;
    }
 
    void pop(){
        Node *oldHead=head;
        head=head->next;
        delete oldHead;
        --count;
    }
 
    const T& top()const{
        if(head==NULL){
            std::cout<<"Stack is empty!"<<std::endl;
            return 0;
        }
        
        return head->data;
    }
 
    bool empty()const{
        return head==NULL;
    }
 
    size_type size()const{
        return count;
    }
 
 
    class iterator;
    friend class iterator;
    class iterator{
            Node *p;
        public:
            iterator(const Stack<T>& t):p(t.head){}
 
            iterator(const iterator& t):p(t.p){}
 
            iterator():p(NULL){}
 
            bool operator++(){
                if(p->next)
                    p=p->next;
                else p=NULL;
                return static_cast<bool>(p);
            }
 
            bool operator++(int){
                return operator++();
            }
 
            T* current()const{
                if(!p)return NULL;
                return &(p->data);
            }
 
            T* operator->()const{
                if(p==NULL){
                    std::cerr<<"Stack::iterator::operator-> returns 0"<<std::endl;
                    exit(1);
                }
                return current();
            }
 
            T* operator*()const{
                return current();
            }
 
            operator bool()const{
                return static_cast<bool>(p);
            }
 
            bool operator==(const iterator&)const{
                return p==NULL;
            }
 
            bool operator!=(const iterator&)const{
                return p!=NULL;
            }
        };
 
            iterator begin()const{
                return iterator(*this);
            }
 
            iterator end()const{
                return iterator();
            }
};
 
 
#endif  //_TSTACK_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

#include "TStack.h"
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
int main(){
    std::string filename;
    std::cout<<"Enter file name: ";
    getline(std::cin,filename);
    std::ifstream input(filename);
    if(!input){
        perror(filename.c_str());
        exit(1);
    }
    Stack<std::string> textfile;
    std::string line;
    Stack<size_type> count;
    while(getline(input,line)){
        textfile.push(line);
        size_type n=textfile.size();
        count.push(n);
    }
    for(Stack<std::string>::iterator it=textfile.begin();it!=textfile.end();it++){
        std::cout<<std::setw(2)<<count.top()<<" "<<it->c_str()<<std::endl;
        count.pop();
    }
    size_type size=textfile.size();
    for(size_type i=0;i<size;i++)
        textfile.pop();
    std::cout<<"Stack<std::string> is "<<(textfile.empty() ? "empty!" : "not empty!")<<std::endl;
        return 0;
}


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

Не по теме:

не заметил, что похожее уже есть...

5
Заблокирован
26.08.2011, 18:17 25
Kastaneda, а зачем собственно стеку итераторы?
0
Kastaneda
26.08.2011, 18:26
  #26

Не по теме:

Цитата Сообщение от LosAngeles Посмотреть сообщение
Kastaneda, а зачем собственно стеку итераторы?
Ну так, чтобы было) Это я писал для универа, просто показать, что умею:)

0
214 / 116 / 14
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 01:13 27
Прошу протестировать. Вектор.
Свернуть не получилось.

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

#pragma once
#include <memory>
using std::memcpy;
 
template <class Z> class My_Container
{
 
 struct STOR
    {
        
        STOR(){/*val=0;*/}
        Z val;
    };
 
 
    STOR* top;
    size_t capacity;
    size_t size;
    
public:
    STOR* begin (void)
    {
        return top;
    }
 
    STOR* end (void)
    {
        return top+capacity;
    }
 
    My_Container(void)
    {
        capacity = 1;
        size = 0;
    
        top = new STOR [capacity];      
    }
 
    My_Container(size_t siz)
    {
 
        capacity = 1;
        size=0;
    
 
        if(capacity<siz){capacity=siz;size=siz;}
        top = new STOR[capacity];
    }
 
    My_Container(My_Container& m)
    {
        if(this==&m)return;
        //if(top!=0)delete [] top;
        capacity = m.size;
        size=m.size;
        top = new STOR[capacity];
        memcpy(top,m.begin(),size*sizeof(STOR));
    }
 
    My_Container(const My_Container& m)
    {
        if(this==&m)return;
        //if(top!=0)delete [] top;
        capacity = m.size;
        size=m.size;
        top = new STOR[capacity];
        memcpy(top,m.begin(),size*sizeof(STOR));    
 
 
    }
 
    virtual ~My_Container(void)
    {
        if(top!=0)
        delete [] top;
        top =0;
    }
 
 
    void push_back(Z z)
    {
    
        if (size>0&&size==capacity)
        {
        STOR* temp = new STOR[capacity+4];
        memcpy(temp,top,size*sizeof(STOR));
        capacity +=4;
        delete [] top;
        top = temp;
        (top+size++)->val = z;
        }
        else
        {
        (top+size++)->val = z;
        }
        
    }
 
    void pop_back ()
    {
        size--;
    }
 
    void reserve(size_t s)
    {
 
        if(capacity<s)
            {capacity = s;
            top = new STOR[capacity];
            }
    }
 
    Z& operator [](size_t i) throw(...)
    {
 
        if(i>capacity-1)i=capacity-1;
        if(i<0)i=0;
 
        return (top+i)->val;
    }
 
    const Z& operator <<(size_t i)
    {
        return (top+i)->val;
    }
 
    size_t size_of()
    {
        return size;
    }
 
    size_t capacity_of()
    {
 
        return capacity;
    }
 
    void update(size_t cap,size_t s, STOR* tp)
    {
        top =tp;
        size = s;
        capacity =cap;
    }
 
 
    void operator =( My_Container & m)
    {
        if(this==&m)return;
        if(top!=0)delete [] top;
        capacity = m.size;
        size=m.size;
        top = new STOR[capacity];
        memcpy(top,m.begin(),size*sizeof(STOR));        
 
    }
 
    void resize(size_t s)
    {   
        size = s;
    }
 
    void swap (My_Container& m)//нормально реализовать не хватат знаний. стл вектор использует swap из <utility> 
    {
        if(this==&m) return;
 
        
        size_t tmp1 = size;
        size_t tmp2 = capacity;
        STOR* tmp3 = top;
 
        this->top = m.begin();
        this->size = m.size_of();
        this->capacity = m.capacity_of();
 
        m.update(tmp2,tmp1,tmp3);
 
 
    }
 
    void clear()
    {
        if(top!=0)delete [] top;
        capacity =1;
        size=0;
        top = new STOR[capacity];
    }
 
};
0
Эксперт С++
2381 / 1665 / 279
Регистрация: 29.05.2011
Сообщений: 3,399
28.08.2011, 01:28 28
Цитата Сообщение от AzaKendler Посмотреть сообщение
C++
1
2
3
4

        STOR* end (void)
        {
                return top+capacity;
        }
Видимо end() должен ориентироваться всё-таки на size, а не на capacity.
C++
1

                return top+size;
resize() позволяет сделать size > capacity.
Класс не годится для хранения объектов. Только для скалярных встроенных типов.
В общем, ещё много над чем можно поработать
1
Каратель
Эксперт С++
6609 / 4028 / 401
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
28.08.2011, 01:31 29
Цитата Сообщение от AzaKendler Посмотреть сообщение
C++
1

void operator =( My_Container & m)
в операторе присваивания лучше использовать идиому copy-swap

Цитата Сообщение от AzaKendler Посмотреть сообщение
C++
1
2
3
4

void resize(size_t s)
 { 
 size = s;
 }
странный resize, без проверок и перевыделения если потребуется

C++
1

void push_back(Z z)
лучше так
C++
1

void push_back(const Z & z)
1
214 / 116 / 14
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 01:50 30
Цитата Сообщение от grizlik78 Посмотреть сообщение
Класс не годится для хранения объектов
как так. я структурки запихивал.
А вот про end. да - в векторе он показывает на участок сразу за последним валидным элементом и сам является недействительным. а у меня там будут идти валидные элементы(например после ресайз), недодумал как затереть их нормально если честно. есть идеи? и про больше капасити - спасиб)))

Добавлено через 2 минуты
Цитата Сообщение от Jupiter Посмотреть сообщение
странный resize, без проверок и перевыделения если потребуетс
все понял. ресайз по любому на доводку

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

Jupiter,
лучше так
Код C++
1
void push_back(const Z & z)
но я же специально делал закос под вектор. он ведь хранит в себе копии объектов. или мож я опять что то не понял? если ссылку передавать, копия ведь не создается?
0
Каратель
Эксперт С++
6609 / 4028 / 401
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
28.08.2011, 02:40 31
Цитата Сообщение от AzaKendler Посмотреть сообщение
но я же специально делал закос под вектор. он ведь хранит в себе копии объектов. или мож я опять что то не понял? если ссылку передавать, копия ведь не создается?
ссылка на константу передается в std::vector-e
0
Заблокирован
28.08.2011, 07:14 32
Цитата Сообщение от AzaKendler Посмотреть сообщение
как так. я структурки запихивал
структурки с тривиальными КК можно хранить, как они называются plain of data кажись. А чё то сложное нет, ты используешь memcpy везде
0
214 / 116 / 14
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 11:59 33
LosAngeles, ок. а что посоветуешь вместо мема? как скопировать сложные объекты? более сложные это насколько, в двух словах чтобы я понял. Я просто сложного то и не успел увидеть ни одного объекта. Учусь тока
0
Эксперт С++
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
28.08.2011, 12:15 34
AzaKendler, копируйте циклом. Тогда главное, чтобы у класса, объекты которого хранятся в контейнере, был определён оператор присваивания (определён-то он всегда, спасибо компилятору, но в некоторых случаях, как известно, его приходится переопределять).
0
Эксперт С++
5043 / 2622 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 1
28.08.2011, 12:22 35
Цитата Сообщение от silent_1991 Посмотреть сообщение
копируйте циклом
std::copy?
0
214 / 116 / 14
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 12:24 36
silent_1991, да. думал про цикел.

Добавлено через 30 секунд
fasked, для копи там наверно итераторы надо будет заводить.
0
Эксперт С++
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
28.08.2011, 12:43 37
fasked, можно и алгоритмами, без разницы))
AzaKendler, в вашем случае указатели будут являться итераторами.
1
Эксперт С++
5043 / 2622 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 1
28.08.2011, 12:44 38
AzaKendler, никакой разницы:
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

#include <iostream>
#include <algorithm>
 
static int counter;
 
class Object {
public:
   Object() {
      data = new int();
      *data = counter++;
   }
   
   ~Object() {
      delete data;
   }
   
   Object &operator= (const Object &obj) {
      if (this != &obj) {
         *data = obj.get();
      }
      
      return *this;
   }
   
   int get() const {
      return *data;
   }
   
private:
   int *data;
};
 
int main() {
   Object src[5], dst_copy[5], dst_loop[5];
   
   for (int i = 0; i < 5; ++i) {
      std::cout << src[i].get() << ',' << 
              dst_copy[i].get() << ',' <<
              dst_loop[i].get() << ',' << std::endl;
   }
     
   for (int i = 0; i < 5; ++i) {
      dst_loop[i] = src[i];
   }
   
   std::copy(src, src + 5, dst_copy);
 
   std::cout << std::endl;
   for (int i = 0; i < 5; ++i) {
      std::cout << src[i].get() << ',' << 
              dst_copy[i].get() << ',' <<
              dst_loop[i].get() << ',' << std::endl;
   }
   
   return 0;
}
Код
0,5,10,
1,6,11,
2,7,12,
3,8,13,
4,9,14,

0,0,0,
1,1,1,
2,2,2,
3,3,3,
4,4,4,
1
214 / 116 / 14
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 12:55 39
да. копи копирует даже контейнер векторов корректно. спрашивается нафига нужен мемцпай? он очень быстр на простых типах?
0
Эксперт С++
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
28.08.2011, 13:06 40
AzaKendler, ну, скажем так, были времена, когда алгоритмов и вообще STL не существовало в природе...
0
28.08.2011, 13:06
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 28.08.2011, 13:06
Помогаю со студенческими работами здесь

C++ Стеки, Очереди
Дан целочисленный массив размера N. Преобразовать его, прибавив к нечетным числам последний...

Стеки и очереди
Ребят, помогите справится с заданием. Задача 6. Система состоит из процессора P, трёх очередей...

Стеки, очереди, массивы
Помогите реализовать стек с помощью двух очередей, используя массивы (операции удаления,...

Динамические структуры: стеки и очереди
Создать стек из вещественных чисел. Определить максимальный элемент в стеке. Организовать просмотр...


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
2 из 3 « 1 2 3 »
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru