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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 313, средняя оценка - 4.62
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
19.10.2010, 12:11     Списки, стеки, очереди #1
В процессе разбора этой темы появились программки на список. Сделанные через класс, не идеал конечно, но вроде бы и не самый плохой вариант. Выложу, вдруг кому пригодится. Конструктивная критика приветствуется.
Двунаправленный список и очередь будет чуть позже. С двунаправленным возникли некоторые трудности.

Однонаправленный список
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';
        }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 13:21     Списки, стеки, очереди #41
silent_1991, в те времена выходит не было таких объектов? ну а как по скорости? мемцпай на ассемблере написан а алгоритм копи? кто быстрее на простых типах?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
LosAngeles
Заблокирован
28.08.2011, 13:33     Списки, стеки, очереди #42
memcpy это наследие от Си, который про классы конструкторы и прочую фигню понятия не имеет, он не вызывает конструкторов так же как и все прочие mem* функции включая маллоки и реалоки. Можно выделять память маллоком а потом с помощью placement new размещать объект в этой памяти. Написан специальный класс аллокатор который собственно и инкапсулирует всё это дело, у всех контейнеров одним из шаблонных параметров идёт этот аллокатор. Там allocate deallocate есть на cplusplus почитаешь

Добавлено через 1 минуту
про memcpy и memmove кстати срач был недавно
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 20:07     Списки, стеки, очереди #43
LosAngeles, дай ссылку на срач. интересно почитать
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
28.08.2011, 20:13     Списки, стеки, очереди #44
Цитата Сообщение от AzaKendler Посмотреть сообщение
LosAngeles, дай ссылку на срач. интересно почитать
Зачем тебе это?
Там речь о копировании для пересекающихся областей источника и приёмника.
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 20:25     Списки, стеки, очереди #45
Цитата Сообщение от grizlik78 Посмотреть сообщение
Зачем тебе это?
пока буду есть бутер почитаю.
а черт. там хэппи инглиш.
и правда ни к чему. так поем бутер. без того срача
LosAngeles
Заблокирован
29.08.2011, 05:33     Списки, стеки, очереди #46
создай в священных войнах на русском, там много трололо стянется
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
29.08.2011, 08:59     Списки, стеки, очереди #47
LosAngeles, попозжа) мож
mezlogo
3 / 3 / 0
Регистрация: 11.04.2011
Сообщений: 121
26.09.2012, 21:36     Списки, стеки, очереди #48
Огромное спасибо за предоставленный однонаправленный список!
Правда есть вопросы:
1)Зачем нужен int tail?
2)head указывает на первый элемент?
3)Почему если A.pushback(любое_число); написать ТОЛЬКО ОДИН раз, то добавит элемент НО! выдаст ошибку??? (Из-за чего и что за ошибка?) а если сделать сразу несколько пушбэков то нормально? На push_front не распространяется данная ошибка.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
14.11.2012, 02:07     Списки, стеки, очереди #49
Цитата Сообщение от easybudda Посмотреть сообщение
Страуструп удалять будет?
очевидно же... STL могуч(а).
Peoples
718 / 378 / 341
Регистрация: 06.02.2016
Сообщений: 1,009
Записей в блоге: 10
Завершенные тесты: 3
08.10.2016, 15:36     Списки, стеки, очереди #50
Линейный список
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
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
// структура элемента (Узла)
template<typename T>
struct Node {              //  узел (собственно это и является элементом списка)
    T x;                 // информационное поле, которое хранит значение определённого узла
    Node *next;          // указатель на структуру Node
};
// класс Однонаправленный список
template<typename T>
class UList {            // класс однонаправленный список
    private:
        Node<T> *head;             // указатель на последний активный элемент списка( голова списка(начало))
    public:
        UList();               // Конструктор инициализирующий пустой список
        ~UList();              // деструктор для удаления элементов и освобождения памяти
        void AddToHead(T y);     // добавление элемента в начало списка
        void ShowL();           // вывод списка
        int  Size();          // количество элементов списка
        void delNum(int n);    // удаление элемента по номеру
        void printNum(int n);  // вывод элемента по номеру
        void findValue(T v); // есть ли элемент со значением v  и его позиция
        void delValue(T v);  // удалить элемент по значению
        bool empty();         // проверка списка на пустоту
        void AddToTail(T x);  // добавление элемента в конец списка
        T minE();   // нахождение минимального элемента
        T maxE();   // нахождение максимального элемента
        void Lsort();  // сортировка списка
};
/////////////////////////////////////////////////////////////////////////////////////////////////
template<typename T>
UList<T>::UList() {
    head=NULL;
}
template<typename T>
UList<T>::~UList() {
    while(head!=NULL) {
        Node<T> *temp=head->next;  // элемент temp равен следующему элементу идущему за head
        delete head;      // освобождаем адрес начального элемента (головы(1 элемента))
        head=temp;     // присваиваем началу предыдущий элемент
    }
}
template<typename T>
void UList<T>::AddToHead(T y) {
    Node<T> *temp=new Node<T>; // создаём новый элемент в списке
    temp->x=y;          // присваиваем ему значение, переданного аргумента
    temp->next=head;   // элемент следующий за temp равен первому элементу списка
    head=temp;        // приравниваем первому элементу списка temp
 
}
template<typename T>
void UList<T>::ShowL() {
    Node<T> *temp=head;     // temp начальный элемент списка
    while(temp!=NULL) {     // пока он есть
        cout<<temp->x<<" "; // выводим значение
        temp=temp->next;  // 1 элементов становится элементу следующий за temp
    }
}
template<typename T>
int UList<T>::Size() {
    int c=0;                 // счётчик элементов
    Node<T> *temp=head;           // temp 1 элемент
    while(temp!=NULL) {      // пока есть элемент
        temp=temp->next;  // двигаем temp (1 становится элемент за ним)
        c++;               // пока элементы есть наращиваем счётчик
    }
    return c;                // возвращаем результат
}
template<typename T>
void UList<T>::delNum(int n) {
    Node<T> *temp=head;
    Node<T> *help;
    if(temp!=NULL && n<=Size()) {          // если в списке есть элементы и искомый номер не превышает размер списка, то продолжаем
        for(int i=0; i!=n; i++) {          /// двигаем значение tepm он начала списка на n элементов
            help=temp;               // предыдущий элемент
            temp=temp->next;         // сдвигаем temp
        }
        if(temp==head) {             // если temp равен 1  элементу , то 1 элемент равен следующему за temp(2 элементу)
            head=temp->next;
        } else {
            help->next=temp->next;   // иначе предыдущий элемент равен следующий за temp элементу
        }
        delete temp;              // наш элемент удаляется
    }
}
template<typename T>
void UList<T>::printNum(int n) {
    Node<T> *temp=head;      // temp начало списка
    if(temp!=NULL && n<=Size()) {   // пока список есть  и искомый элемент не боле размера списка
        for(int i=0; i!=n; i++) {    // передвигаем элемент на n позиций
            temp=temp->next;
        }
        cout<<temp->x<<endl;     // выводим значение элемента
    }
}
template<typename T>
void UList<T>::findValue(T v) {
    int pos=0;           // начальная позиция
    Node<T> *temp=head;
    int f=0;      // индикатор
    while(temp!=NULL) {     // пока список не пуст
        if(temp->x==v) {     // если значение х=v , то f++
            f++;
            break;
        }
 
        temp=temp->next; // если не равно, то передвигаем элемент
        pos++;  // наращиваем позицию
 
    }
    if(f>0) {
        cout<<"Yes"<<" "<<"Position: "<<pos<<endl;
    } else cout<<"No";
}
template<typename T>
void UList<T>::delValue(T v) {
    Node<T> *temp=head,*help;
    while(temp!=NULL && temp->x!=v) {  // пока список не пуст и значение temp неравно v
        help=temp;  // help принимает предыдущее значение temp
        temp=temp->next;    //  temp перемещается
    }
    if(temp==head) {
        head=temp->next;
    } else {
        help->next=temp->next;
    }
    delete temp;  // удаляем в зависимости от результата
}
template<typename T>
bool UList<T>::empty() {
    if(head==NULL) {   // если 1 элемента в списке нет, вернуть 1, иначе 0
        return true;
    } else return false;
}
template<typename T>
void UList<T>::AddToTail(T x) {
    Node<T> *temp=new Node<T>; // создаём новый элемент
    temp=head;   // он указывает на начало
    while(temp->next!=NULL) {  // передвигаем до предпоследнего элемента
        temp=temp->next;
 
    }
    Node<T> *t=new Node<T>;   // ещё новый
    t->x=x;   // присваиваем ему х
    t->next=NULL;  // указываем что за ним нет элементов
    temp->next=t;  // присваиваем предпоследний элемент ему
}
template<typename T>
T UList<T>::minE() {
    Node<T> *temp=head;
    T min=temp->x;     // минимальный элемент равен значению 1 элемента
    while(temp!=NULL) {     // пока список не пуст
        if(temp->x<min) {  // если значение элемента меньше минимального
            min=temp->x;      // этот элемент становится минимальным
        } else {
            temp=temp->next;     // иначе передвигаем элемент дальше
        }
    }
    return min;   // возвращаем минимальный элемент
}
template<typename T>
T UList<T>::maxE() {   // аналогично минимальному
    Node<T> *temp=head;
    T max=temp->x;
    while(temp!=NULL) {
        if(temp->x>max) {
            max=temp->x;
        } else {
            temp=temp->next;
        }
    }
    return max;
}
template<typename T>
void UList<T>::Lsort() {
    for(int i=0; i!=Size(); i++) {  // проводим size()-1 итерации, так как head-элемент из-за перестановок будет меняться
        Node<T> *temp=head;
        while(temp->next!=NULL) {       // до последнего элемента
            if(temp->x>temp->next->x) {   // сравниваем
                int t=temp->x;     // swqp
                temp->x=temp->next->x;
                temp->next->x=t;
            }
            temp=temp->next;  // передвигаем
        }
    }
}
////////////////////////////////////////////////////////////////////////////////////////
int main() {
    UList<int> list;
    for(int i=0; i!=5; i++) {
        list.AddToHead(i);
    }
    cout<<endl;
    list.ShowL();
    list.delNum(2);
    cout<<endl;
    cout<<list.Size();
    cout<<endl;
    list.printNum(3);
    cout<<endl;
    list.findValue(0);
    cout<<endl;
    list.delValue(0);
    list.AddToTail(9);
    list.ShowL();
    cout<<endl;
    cout<<"Min: "<<list.minE()<<endl;
    cout<<"Max: "<<list.maxE()<<endl;
    list.Lsort();
    list.ShowL();
    return 0;
}
Добавлено через 13 минут
C++
1
2
T Head(); // возвращает 1 элемент списка
T Tail(); // возвращает последний элемент списка
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename T>
T UList<T>::Head() {
    if(head==NULL) {     // если список пуст
        cout<<"List is empty"<<endl;  // сообщение
    } else
        return head->x;  // иначе выводит значение 1 элемента
}
 
template <typename T>
T UList<T>::Tail() {
    Node<T> *temp=head;
    while(temp->next!=NULL) {  // пока temp неравен последнему элементу 
        temp=temp->next;       // перемещаем temp
    }
    return temp->x; // возвращаем значение последнего 
}
GbaLog-
Не Эксперт C++
1478 / 623 / 176
Регистрация: 24.08.2014
Сообщений: 2,533
Записей в блоге: 1
Завершенные тесты: 2
08.10.2016, 15:36     Списки, стеки, очереди #51
Цитата Сообщение от Peoples Посмотреть сообщение
C++
1
void ShowL(); * * * * * // вывод списка
Список не должен уметь себя выводить, имхо.
Peoples
718 / 378 / 341
Регистрация: 06.02.2016
Сообщений: 1,009
Записей в блоге: 10
Завершенные тесты: 3
09.10.2016, 13:25     Списки, стеки, очереди #52
Стек
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
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
template <typename T>
struct Node {
    T x;
    Node *next;
};
template <typename T>
class Stack {
    private:
        Node<T> *head;
    public:
        Stack() {
            head=NULL;
        }
        ~Stack();
        void push(T y);  // добавить элемент в вершину стека
        void pop(); // удалить элемент из вершины стека
        T top();  // возвращает вершину стека
        void printS();  // вывод стека
        int peek(int n);  // вывод n-ного элемента от вершины стека
        bool isempty();   // проверяет пусто ли стек
        int size();     // возвращает размер стека
};
template <typename T>
Stack<T>::~Stack() {
    while (head!=NULL) {
        Node<T> *temp=head->next;
        delete head;
        head=temp;
    }
}
template <typename T>
void Stack<T>::push(T y) {
    Node<T> *temp=new Node<T>;
    temp->x=y;
    temp->next=head;
    head=temp;
 
}
template <typename T>
void Stack<T>::pop() {
 
    if(head==NULL) {
        cout<<"Stack is empty";
    } else {
 
        Node<T> *temp=head;
        cout<<temp->x<<" ";
        head=temp->next;
        delete temp;
    }
}
template <typename T>
T Stack<T>::top() {
    if(head!=NULL) {
        return head->x;
    } else  cout<<"Stack is empty";
}
template <typename T>
void Stack<T>::printS() {
    Node<T> *temp=head;
    while(temp!=NULL) {
        cout<<temp->x<<" ";
        temp=temp->next;
    }
}
template <typename T>
int Stack<T>::peek(int n) {
    Node<T> *temp=head;
    for(int i=0; i!=n; i++) {
        temp=temp->next;
    }
    return temp->x;
}
template <typename T>
bool Stack<T>::isempty() {
    if(head==NULL) {
        return true;
    } else return false;
}
template <typename T>
int Stack<T>::size() {
    int c=0;
    Node<T> *temp=head;
    while(temp!=NULL) {
        temp=temp->next;
        c++;
    }
    return c;
}
int main() {
    Stack<int> st;
    for(int i=0; i!=5; i++) {
        st.push(i);
    }
    st.printS();
    cout<<endl;
    st.pop();
    st.pop();
    st.pop();
    cout<<endl;
    st.printS();
    cout<<endl;
    cout<<"Size: "<<st.size();
    cout<<endl;
    cout<<st.top()<<endl;
    cout<<st.peek(1);
    return 0;
}
Добавлено через 20 часов 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
#include <iostream>
using namespace std;
template<typename T>
struct Node {    // структура узел
    T x;        // информационное поле узла
    Node *next,*prev;    // указатели на структуру
};
template<typename T>
class TWList {        // класс двунаправленный список
    public:
        Node<T> *head,*tail;     // указатели на начало и конец списка
    public:
        TWList():head(NULL),tail(NULL) {}    // инициализируем их пустым значением
        ~TWList();     // деструктор
        void Add(T y);     // добавление элемента
        void ShowFromBegin();   // вывод списка с начала
        void ShowFromEnd();   // вывод списка с конца
        void Head();      // вывод головы
        void Tail();    // вывод хвоста
        void AddH(T y); // добавить в начало списка
        void delNum(int n);  // удаление элемента по номеру
        int Size(); // размер списка
        int findNum(int n);  // вернуть элемент расположенный на n месте сверху
};
template<typename T>
TWList<T>::~TWList() {
    while(head!=NULL) {     // пока список не пуст
        tail=head->next;    // последний элемент равен следующему за 1 элементом
        delete head;       // удаляем 1
        head=tail;    // первым становится последний
    }
}
template<typename T>
void TWList<T>::Add(T y) {
    Node<T> *temp=new Node<T>;   // выделяем память для нового элемента
    temp->next=NULL;      // указываем что за этим элементом нет других
    temp->x=y;       // присваиваем ему значение переданное аргументом
    if(head!=NULL) {       // пока список не пуст
        temp->prev=tail;       // следующий за нашим элементом элемент будет хвостом
        tail->next=temp;        // элемент следующий за хвостом наш
        tail=temp;               // наш элемент равен хвосту
    } else {              // если же список пуст
        temp->prev=NULL;   // тогда перед нашим элементом пусто
        head=tail=temp;   // 1 элемент равен последнему и равен нашему элементу
    }
}
template<typename T>
void TWList<T>::ShowFromBegin() {
    Node<T> *temp=head;       // temp равен началу списка
    while(temp!=NULL) {      // пока список не пуст
        cout<<temp->x<<" ";  // выводим знание поля
        temp=temp->next;      // перемешаем на следующий элемент
    }
}
template<typename T>
void TWList<T>::ShowFromEnd() {
    Node<T> *temp=tail;         // temp равен концу  списка
    while(temp!=NULL) {      // пока элементы есть
        cout<<temp->x<<" "; // выводим значение
        temp=temp->prev;   // перемещаем элемент на предыдущий
    }
}
template<typename T>
void TWList<T>::Head() {
    if(head!=NULL) {
        cout<<head->x<<endl;
    }
}
template<typename T>
void TWList<T>::Tail() {
    if(tail!=NULL) {
        cout<<tail->x<<endl;
    }
}
template<typename T>
void TWList<T>::AddH(T y) {
    Node<T> *temp=new Node<T>;
    temp->x=y;
    if(temp!=NULL) {
 
        temp->next=head;
        head=temp;
    } else {
        head=tail=temp;
    }
}
template<typename T>
void TWList<T>::delNum(int n) {
    Node<T> *temp=head;
    if(temp!=NULL && n<=Size()) {
        for(int i=0; i!=n; i++) {
            temp=temp->next;
        }
        if(temp==head) {
            head=temp->next;
        } else {
            temp->prev->next=temp->next;
        }
        delete temp;
    }
}
template<typename T>
int TWList<T>::Size() {
    Node<T> *temp=head;
    int c=0;
    while(temp!=NULL) {
        temp=temp->next;
        c++;
    }
    return c;
}
template<typename T>
int TWList<T>::findNum(int n) {
    Node<T> *temp=head;
    while(temp!=NULL && n<=Size()) {
        for(int i=0; i!=n; i++) {
            temp=temp->next;
        }
        return temp->x;
    }
}
int main() {
    TWList<int> list;
    for(int i=0; i!=5; i++) {
        list.Add(i);
    }
    list.ShowFromBegin();
    cout<<endl;
    list.ShowFromEnd();
    cout<<endl;
    list.Head();
    list.Tail();
    list.Add(10);
    cout<<endl;
    list.ShowFromBegin();
    list.AddH(7);
    cout<<endl;
    list.ShowFromBegin();
    cout<<endl;
    list.delNum(4);
    list.ShowFromBegin();
    return 0;
}
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11837 / 6816 / 771
Регистрация: 27.09.2012
Сообщений: 16,908
Записей в блоге: 2
Завершенные тесты: 1
09.10.2016, 13:33     Списки, стеки, очереди #53
Цитата Сообщение от Peoples Посмотреть сообщение
C++
1
2
3
4
5
6
template <typename T>
T Stack<T>::top() {
    if(head!=NULL) {
        return head->x;
    } else  cout<<"Stack is empty";
}
Имеем UB, т.к. нет возвращения значения при head == nullptr.
Конечно, можно оставить как есть, чтобы вызывающая
сторона за это беспокоилась, а можно кинуть исключение.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.10.2016, 13:35     Списки, стеки, очереди
Еще ссылки по теме:

Очереди и стеки C++
Задача на тему Стеки, очереди, деки, списки, кольца C++

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

Или воспользуйтесь поиском по форуму:
Peoples
718 / 378 / 341
Регистрация: 06.02.2016
Сообщений: 1,009
Записей в блоге: 10
Завершенные тесты: 3
09.10.2016, 13:35     Списки, стеки, очереди #54
Croessmah, Просмотрел такой момент
Yandex
Объявления
09.10.2016, 13:35     Списки, стеки, очереди
Ответ Создать тему
Опции темы

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