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

Шаблон класса двусвязный список - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перевести с DELPHI в С++ http://www.cyberforum.ru/cpp-beginners/thread318359.html
Кто-нибудь сможет помочь переписать код с delphi на с++? И вообще возможно ли это?
C++ Нормальное Распределение чисел есть программа. вычисляет нормально распределенные два числа методом Бокса — Мюллера, не могу сделать что выводила случайную последовательность а не два числа. помогите плиз! #include <math.h> typedef unsigned long long u64; typedef long long s64; typedef double d64; typedef struct { u64 rec_count; u64 start; http://www.cyberforum.ru/cpp-beginners/thread318357.html
C++ Как изучать С++ ?
Уважаемые участники форума, я тут на досуге - невзначай решил научиться азам С++. Нашел кучу учебников сижу типа читаю. Столкнулся с проблемой - масса ненужной информации и нет систематизации материала. Обычно начинают вешать всякую лапшу на уши о том как вначале ничего не было. потом создали компьютер, юзера, админа, Windows итд итп, а потом бац и сложный материал. Может ли мне кто...
C++ Нахождение кратчайшего пути в неорентированном графе от заданой вершины к заданной
Добрый день. Вот решаю задачку о кратчайщем расстояние между двумя верщинами в неорентированном связном графе без циклов. Заданны такие параметры. (Помещаю их в файл text2.txt) 6 -- количество вершин N 1 2 7 -- Начало, конец, длина 2 3 3 2 4 6 4 5 3 5 6 1 4 -- количество пар вершин M для которых нужно узнать короткое растояние
C++ Массив http://www.cyberforum.ru/cpp-beginners/thread318283.html
Помогите разобраться. Только начал читать про указатели и решил написать простенькую программку :) Она считает кол-во прописных букв и записывает эти буквы в массив. Насчет счетчика всё ясно, но вот как записывать буквы в массив не разобрался. GNU nano 2.2.6 Файл: p209E12.cpp #include <cctype> #include <iostream> using namespace std; main() {
C++ исправить код программы #include<iostream.h> #include<conio.h> #include<stdlib.h> #include<string.h> #include<iomanip.h> float f( float, float, float, float); float pr_chet( float *mas, int k); float sum_f( float *mas,int k); void Vivod_mas(float a,int k); подробнее

Показать сообщение отдельно
lemegeton
2918 / 1347 / 134
Регистрация: 29.11.2010
Сообщений: 2,721
13.06.2011, 12:05     Шаблон класса двусвязный список
Итератор это такая штука, которая позволит перебирать элементы списка (или вообще любого контейнера), не нарушая принцип сокрытия данных (известный под хитрым словом "инкапсуляция"). Итератор можно увеличивать (переходить к следующему элементу), уменьшать (переходить к предыдущему элементу), получать значение элемента и другие операции.

Введем еще одно понятие -- функтор. Это такая штука, которую можно вызвать. С параметрами или без, вернув результат или нет. Функтором может быть просто функция или класс с перегруженным оператором "()" -- оператор "скобочки", потому что объект такого класса можно вызвать как функцию. Этот "функтор" поможет искать элемент по какому-либо условию (параметру).

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
#include <iostream>
#include <string>
#include <ctime>
#include <cstdlib>
 
// базовый класс элемента связного списка
// не содержит данных, содержит часть логики
struct NodeBase {
  NodeBase *prev; // указатель на предыдущий элемент связного списка
  NodeBase *next; // указатель на следующий элемент связного списка
  // при создании объекта класса конструктор по-умолчанию
  // назначает следующий и предыдущий элемент указывать на себя 
  NodeBase() : prev(this), next(this) {}
  // при создании с таким констуктором, элемент добавляет сам себя
  // в связный список, представляя себя предыдущему и следующему элементу
  NodeBase(NodeBase *prev_, NodeBase *next_)
    : prev(prev_), next(next_) { // назначаются предыдущий и следующий элементы
    // у предыдущего элемента следующим элементом назначается данный элемент
    // и у следующего элемента предыдущим элементом назначается данный элемент
    prev->next = next->prev = this;
  }
  // деструктор. при удалении элемента связного списка, 
  // элемент убирает сам себя из списка
  virtual ~NodeBase() {
    prev->next = next;
    next->prev = prev;
  }
};
 
// элемент связного списка, уже содержащий данные.
template <typename ValueType>
struct Node: public NodeBase{
  ValueType value; // то значение, которое хранит класс
  // конструктор подставляет значения и вызывает конструтор предка
  Node(NodeBase *prev_, NodeBase *next_, ValueType value)
    : NodeBase(prev_, next_), value(value) {}
};
 
// итератор. класс, который позволит получать доступ к данным,
// сохранив инкапсуляцию
template <typename ValueType>
struct Iterator {
 public:
  // создание итератора при помощи элемента связного списка
  explicit Iterator(NodeBase *node_) : node(node_) {}
  // создание копированием с другого итератора
  Iterator(const Iterator &other) : node(other.node) {}
  // получение значения элемента связного списка
  ValueType &operator*() {
    return static_cast<Node<ValueType>*>(node)->value;
  }
  // присваивание итератору другого итератора
  Iterator &operator=(const Iterator &other) {
    if (&other != this)
      node = other.node;
    return *this;
  }
  // переход к следующему элементу (постфиксный)
  Iterator &operator++() {
    node = node->next;
    return *this;
  }
  // переход к предыдущему элементу (постфиксный)
  Iterator &operator--() {
    node = node->prev;
    return *this;
  }
  // проверка итераторов на равенство
  bool operator==(const Iterator &other) {
    return node == other.node;
  }
  // ... на неравенство
  bool operator!=(const Iterator &other) {
    return node != other.node;
  }
 private:
  // собственно, элемент связного списка, который хранит итератор
  NodeBase *node;
};
 
// собственно, шаблон двусвязного списка
// смотрите, как мало собственно кода, если убрать комментарии
template <typename ValueType>
class List {
 public:
  // конструктору по-умолчанию делать в принципе нечего, он должен быть объявлен
  List() : base() {};
  // деструктор удаляет список функцией Clear
  ~List() {
    Clear();
  }
  // функция проверяет, пустой ли список
  bool Empty() {
    // список пустой, если базовый элемент указывает сам на себя
    return ((base.next == &base) && (base.prev == &base));
  }
  void Clear() {
    // пока список не пуст
    while (!Empty())
      // удаляется первый элемент
      // работу по удалению из списка сделает деструктор класса элемента
      delete base.next;
  }
  // добавление элемента в конец списка
  void PushBack(const ValueType &value) {
    // просто создается новый элемент списка,
    // всё остальное сделает конструктор класса NodeBase
    new Node<ValueType>(base.prev, &base, value);
  }
  // удаление последнего элемента
  void PopBack() {
    // удаляется элемент связного списка 
    // (в данном случае последний, но в принципе, сработает с любым)
    // работу по фактическому удалению элемента из списка выполнит деструктор
    // класса NodeBase
    delete base.prev;
  }
  // плохой стиль, лучше делать через итераторы, но эта концепция, наверно,
  // слишком сложна
  void PrintAll() {
    // перебор всех элементов в одном цикле
    for (NodeBase *node = base.next; node != &base; node = node->next)
      // для получения значения элемент списка приводится к типу Node*
      std::cout << static_cast< Node<ValueType>* >(node)->value;
  }
  // печать данных по условию
  template <class Predicate> // класс или функция, принимающие параметром
                             // ValueType и возвращающая true или false.
  void PrintIf(Predicate condition) {
    // цикл по всем элементам массива
    for (NodeBase *node = base.next; node != &base; node = node->next)
      // если условие выполняется
      if (condition(static_cast<Node<ValueType>*>(node)->value))
        // вывести значение
        std::cout << static_cast<Node<ValueType>*>(node)->value;
  }
  // итератор на начало связного списка
  Iterator<ValueType> Begin() {
    // началом связного списка является элемент, на который указывает
    // поле next переменной base
    return Iterator<ValueType>(base.next);
  }
  // итератор на элемент связного списка _после_ последнего
  Iterator<ValueType> End() {
    // элементом за связным списком является само поле base
    return Iterator<ValueType>(&base);    
  }
  // поиск элемента в списке
  // принимает параметрами первый элемент и последний элемент, в
  // которых надо искать список
  // и функтор, принимающий значение элемента и возвращающая true или
  // false
  // возвращает итератор найденного элемента или последний параметр
  // если элемента не найдено
  template <class Predicate>
  Iterator<ValueType> Search(Iterator<ValueType> begin,
                             Iterator<ValueType> end,
                             Predicate condition) {
    for (; begin != end; ++begin)
      if (condition(*begin)) break;
    return begin;
  }
 private:
  // базовый эелемент.
  // его поле next указывает на первый элемент списка
  // поле prev указываеты на последний элемент списка
  // если список пуст, next == prev == &base
  NodeBase base;
};
 
// класс автобуса
struct Bus {
  int number;
  std::string driver;
  int route;
  bool deport;
  //... тут наверно нужны другие поля
  Bus(int number_, std::string driver_, int route_, bool deport_)
    : number(number_), driver(driver_), route(route_),deport(deport_) {}  // переопределенный оператор для вывода на экран
  friend std::ostream& operator<<(std::ostream &stream, const Bus &bus) {
    return stream  << "Bus number: " << bus.number
                   << ", driver: " << bus.driver
                   << ", route: "  << bus.route                                            
                   << ", locate: " << (bus.deport ? "on route" : "in deport")
                   << std::endl;
  }
  // класс-функтор для поиска по номеру
  struct IsNumber {
    // запоминаем параметр в классе
    IsNumber(int parameter_) : parameter(parameter_) {}
    // оператор-функтор для сравнения параметра
    bool operator()(const Bus &bus) {
      return bus.number == parameter;
    }
    int parameter; // параметр
  };
  // класс-функтор для поиска по депо
  struct IsDeport {
    // запоминаем параметр в классе
    IsDeport(bool parameter_) : parameter(parameter_) {}
    // оператор-функтор для сравнения параметра
    bool operator()(const Bus &bus) {
      return bus.deport == parameter;
    }
    bool parameter; // параметр
  };
  // класс-функтор для поиска по номеру маршрута
  struct IsRoute {
    // запоминаем параметр в классе
    IsRoute(int parameter_) : parameter(parameter_) {}
    // оператор-функтор для сравнения параметра
    bool operator()(const Bus &bus) {
      return bus.route == parameter;
    }
    int parameter; // параметр
  };
  // класс-функтор для поиска по водителю
  struct IsDriver {
    // запоминаем параметр в классе
    IsDriver(const std::string &parameter_) : parameter(parameter_) {}
    // оператор-функтор для сравнения параметра
    bool operator()(const Bus &bus) {
      return bus.driver == parameter;
    }
    std::string parameter; // параметр
  };
};
 
int main(int argc, char *argv[]) {
  srand(time(NULL));
  List<Bus> a; // список автобусов
  // добавим в список сто автобусов
  for (int i = 0; i < 100; ++i)
    a.PushBack(Bus(i + 1, "Ivan", i, rand() % 2));
  // вывод его на экран
  a.PrintAll();
  // поиск автобуса номер десять
  Iterator<Bus> b = a.Search(a.Begin(), a.End(), Bus::IsNumber(10));
  // если автобус найден
  if (b != a.End())
    // вывод на экран. Соответственно, *b возвращает ссылку на объект
    // Bus, так что ей доступны все поля и методы класса Bus.
    // например, *b.deport = false;
    std::cout << *b;
  // печать автобусов, с полем Deport == true,
  // не используя итератор
  a.PrintIf(Bus::IsDeport(true));
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru