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

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

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

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

19.10.2010, 12:11. Просмотров 44014. Ответов 53
Метки нет (Все метки)

В процессе разбора этой темы появились программки на список. Сделанные через класс, не идеал конечно, но вроде бы и не самый плохой вариант. Выложу, вдруг кому пригодится. Конструктивная критика приветствуется.
Двунаправленный список и очередь будет чуть позже. С двунаправленным возникли некоторые трудности.

Однонаправленный список
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.10.2010, 12:11
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Списки, стеки, очереди (C++):

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

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

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

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

Стеки и очереди - C++
Ребят, помогите справится с заданием. Задача 6. Система состоит из процессора P, трёх очередей F0, F1, F2 и стека S. В систему...

Очереди и стеки - C++
#include &quot;stdafx.h&quot; #include &quot;iostream&quot; using namespace std; struct stack { int x; stack *Next,*Head; ...

53
Jupiter
Каратель
Эксперт С++
6561 / 3982 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
28.08.2011, 02:40 #31
Цитата Сообщение от AzaKendler Посмотреть сообщение
но я же специально делал закос под вектор. он ведь хранит в себе копии объектов. или мож я опять что то не понял? если ссылку передавать, копия ведь не создается?
ссылка на константу передается в std::vector-e
0
LosAngeles
Заблокирован
28.08.2011, 07:14 #32
Цитата Сообщение от AzaKendler Посмотреть сообщение
как так. я структурки запихивал
структурки с тривиальными КК можно хранить, как они называются plain of data кажись. А чё то сложное нет, ты используешь memcpy везде
0
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 11:59 #33
LosAngeles, ок. а что посоветуешь вместо мема? как скопировать сложные объекты? более сложные это насколько, в двух словах чтобы я понял. Я просто сложного то и не успел увидеть ни одного объекта. Учусь тока
0
silent_1991
Эксперт С++
4989 / 3046 / 149
Регистрация: 11.11.2009
Сообщений: 7,028
Завершенные тесты: 1
28.08.2011, 12:15 #34
AzaKendler, копируйте циклом. Тогда главное, чтобы у класса, объекты которого хранятся в контейнере, был определён оператор присваивания (определён-то он всегда, спасибо компилятору, но в некоторых случаях, как известно, его приходится переопределять).
0
fasked
Эксперт С++
4951 / 2531 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
28.08.2011, 12:22 #35
Цитата Сообщение от silent_1991 Посмотреть сообщение
копируйте циклом
std::copy?
0
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 12:24 #36
silent_1991, да. думал про цикел.

Добавлено через 30 секунд
fasked, для копи там наверно итераторы надо будет заводить.
0
silent_1991
Эксперт С++
4989 / 3046 / 149
Регистрация: 11.11.2009
Сообщений: 7,028
Завершенные тесты: 1
28.08.2011, 12:43 #37
fasked, можно и алгоритмами, без разницы))
AzaKendler, в вашем случае указатели будут являться итераторами.
1
fasked
Эксперт С++
4951 / 2531 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 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
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 12:55 #39
да. копи копирует даже контейнер векторов корректно. спрашивается нафига нужен мемцпай? он очень быстр на простых типах?
0
silent_1991
Эксперт С++
4989 / 3046 / 149
Регистрация: 11.11.2009
Сообщений: 7,028
Завершенные тесты: 1
28.08.2011, 13:06 #40
AzaKendler, ну, скажем так, были времена, когда алгоритмов и вообще STL не существовало в природе...
0
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 13:21 #41
silent_1991, в те времена выходит не было таких объектов? ну а как по скорости? мемцпай на ассемблере написан а алгоритм копи? кто быстрее на простых типах?
0
LosAngeles
Заблокирован
28.08.2011, 13:33 #42
memcpy это наследие от Си, который про классы конструкторы и прочую фигню понятия не имеет, он не вызывает конструкторов так же как и все прочие mem* функции включая маллоки и реалоки. Можно выделять память маллоком а потом с помощью placement new размещать объект в этой памяти. Написан специальный класс аллокатор который собственно и инкапсулирует всё это дело, у всех контейнеров одним из шаблонных параметров идёт этот аллокатор. Там allocate deallocate есть на cplusplus почитаешь

Добавлено через 1 минуту
про memcpy и memmove кстати срач был недавно
1
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 20:07 #43
LosAngeles, дай ссылку на срач. интересно почитать
0
grizlik78
Эксперт С++
1970 / 1463 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
28.08.2011, 20:13 #44
Цитата Сообщение от AzaKendler Посмотреть сообщение
LosAngeles, дай ссылку на срач. интересно почитать
Зачем тебе это?
Там речь о копировании для пересекающихся областей источника и приёмника.
0
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
28.08.2011, 20:25 #45
Цитата Сообщение от grizlik78 Посмотреть сообщение
Зачем тебе это?
пока буду есть бутер почитаю.
а черт. там хэппи инглиш.
и правда ни к чему. так поем бутер. без того срача
0
28.08.2011, 20:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2011, 20:25
Привет! Вот еще темы с ответами:

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

Бинарные деревья, очереди, стеки - C++
#include &lt;iostream&gt; // подключение библиотеки ввода-вывода #include &lt;conio.h&gt; // подключение библиотеки функций работы с консолью ...

4 задания по С++ (Бинарные деревья. Стеки,очереди) - C++
1. В текстовом файле записана без ошибок формула вида: цифра или М(формула, формула), или m(формула, формула), где M обозначает функцию...

Указатели,стеки списки. - C++
Здравствуйте помогите решить две задачи на Си++,заранее спасибо! Указатели, работа с динамическими структурами данных. Динамическое...


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

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

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