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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Разработать класс "Номер телефона" с данными код города, код станции и номер линии. http://www.cyberforum.ru/cpp-beginners/thread436073.html
Задание. 1. Объявить класс в соответствии с вариантом и определить для него 2-3 конструктора. 2. Определить функции-методы класса для ввода и вывода свойств внутри объявления класса. 3. Составить программу, которая определяет четыре объекта класса и выводит их на экран. Первый объект должен инициализироваться по умолчанию, второй использовать 1-й конструктор, третий - преобразование типа...
C++ С использованием очереди за один просмотр файла напечатать элементы Сформировать файл из натуральных чисел и с помощью очереди за один просмотр файла напечатать элементы файла в следующем порядке: сначала все числа, большие b, затем все числа, меньшие a, а затем все числа из отрезка , сохраняя исходный порядок в каждом случае. http://www.cyberforum.ru/cpp-beginners/thread436072.html
C++ Вычислить значение данной формулы, при решении использовать стек.
В текстовом файле записана без ошибок формула вида: цифра или S(формула, формула), или P(формула, формула), где S (a, b) = (a+b) mod 10, P(a, b) = (a*b) mod 10. Вычислить значение данной формулы. Например: P(6, S(8, 4)) = 2.
Получить новую строку, заменив в исходной все заглавные буквы строчными и наоборот C++
Дана строка, содержащая текст, включающий русские и английские слова. Получить новую строку, заменив в исходной все заглавные буквы строчными и наоборот. как будет выглядеть код на visual c++? я пропустил пару не могу сделать уже с утра так как незнаю как работать с string h:(
C++ Наиболее часто встречающееся слово http://www.cyberforum.ru/cpp-beginners/thread436045.html
Как можно это реализовать Исходный текст содержит строку, слова в которой разделены пробелами и знаками препинания. Найти наиболее часто встречающееся слово.
C++ Помогите определиться с версией С++ и учебником Всем привет! Ровно через год я опять собираюсь писать олимпиаду по программированию, самое главное что в этом году я победил самого себя) Но сейчас я хочу подготовиться гораздо лучше, но к сожалению привычный FreeBasic в следующем году будет убран из допустимых на олимпиаде. На вложенном файле указаны все допустимые языки, мне не нужно уметь писать приложения и т.д. там совсем другие задачи...)... подробнее

Показать сообщение отдельно
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
27.01.2012, 11:04     Шаблонные двусвязные списки.
Два велосипеда из закрома ов родина. Не пропадать же добру. А поделюсь -- так может какой студиозус найдет и порадуется.

Полнофункциональный, с итераторами.

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
#include <cstddef>
 
struct ListNodeBase {
  ListNodeBase() : prev(this), next(this) {}
  ListNodeBase(ListNodeBase *prev_, ListNodeBase *next_) : prev(prev_), next(next_) {
    prev->next = next->prev = this;
  }
  virtual ~ListNodeBase() {
    prev->next = next;
    next->prev = prev;
  }
  ListNodeBase *prev, *next;
};
 
template <class T>
struct ListNode : public ListNodeBase {
  ListNode(ListNodeBase *prev_, ListNodeBase *next_, const T &data_)
    : ListNodeBase(prev_, next_), data(data_) {}
  T data;
};
 
class ListIteratorBase {
 public:
  ListIteratorBase() : node_(NULL) {}
  ListIteratorBase(ListNodeBase *node) : node_(node) {}
  void increase() { node_=node_->next; }
  void decrease() { node_=node_->prev; }
  bool operator==(const ListIteratorBase &other) {
    return node_ == other.node_;
  }
  bool operator!=(const ListIteratorBase &other) {
    return !operator==(other);
  }
  ListNodeBase *node_;
};
 
template <class T, class R, class P>
class ListIterator : public ListIteratorBase {
 public:
  typedef ListIterator<T, T&, T*>             Iterator;
  typedef ListIterator<T, const T&, const T*> ConstIterator;
  typedef ListIterator<T, R, P>               Self;
  typedef T                                   ValueType;
  typedef R                                   ReferenceType;
  typedef P                                   PointerType;
  typedef ListNode<ValueType>                 Node;
  
  ListIterator() : ListIteratorBase() {}
  ListIterator(ListNodeBase *node) : ListIteratorBase(node) {}
  ListIterator(const Iterator &other) : ListIteratorBase(other.node_) {}
 
  ReferenceType operator*() const { return static_cast<Node*>(node_)->data; }
  ReferenceType operator->() const { return operator*(); }
  Self &operator++() {
    increase();
    return *this;
  }
  Self &operator--() {
    decrease();
    return *this;
  }
  Self operator++(int) {
    Self result(*this);
    increase();
    return result;
  }
  Self operator--(int) {
    Self result(*this);
    decrease();
    return result;
  }
  Self operator+(size_t n) {
    Self result(*this);
    while (n-- > 0) result.increase();
    return result;
  }
  Self operator-(size_t n) {
    Self result(*this);
    while (n-- > 0) result.decrease();
    return result;
  }
};
 
template <class T>
class List {
 public:
  typedef T             ValueType;
  typedef T&            ReferenceType;
  typedef const T&      ConstReferenceType;
  typedef T*            PointerType;
  typedef const T*      ConstPointerType;
  typedef ListNode<T>   Node;
  typedef ListIterator<T, T&, T*>             Iterator;
  typedef ListIterator<T, const T&, const T*> ConstIterator;
 
  List() : base_() {}
  List(const List &other) : base_() {
    insert(begin(), other.begin(), other.end());
  }
  ~List() { clear(); }
  List &operator=(const List &other) {
    if (this != &other) {
      clear();
      insert(begin(), other.begin(), other.end());
    }
    return *this;
  }
  Iterator begin() { return base_.next; }
  ConstIterator begin() const { return base_.next; }
  Iterator end() { return &base_; }
  ConstIterator end() const { return const_cast<ListNodeBase*>(&base_); }
  bool isEmpty() const { return &base_ == base_.next; }
  void clear() {
    while (!isEmpty()) {
      ListNodeBase *next = base_.next->next;
      delete base_.next;
      base_.next = next;
    }
  }
  size_t size() {
    size_t result = 0;
    for (Iterator i = begin(); i != end(); ++i) ++result;
    return result;
  }
  ReferenceType front() { return *begin(); }
  ConstReferenceType front() const { return *begin(); }
  ReferenceType back() { return *(--end()); }
  ConstReferenceType back() const { return *(--end()); }
 
  void pushBack(ConstReferenceType value) {
    new Node(base_.prev, &base_, value);
  }
  void pushFront(ConstReferenceType value) {
    new Node(&base_, base_.next, value);
  }
  ValueType popFront() {
    ValueType value = *begin();
    erase(begin());
    return value;
  }
  ValueType popBack() {
    ValueType value = *(--end());
    erase(--end());
    return value;
  }
  Iterator insert(Iterator before, ConstReferenceType value) {
    return new Node(before.node_->prev, before.node_, value);
  }
  template <class IteratorType>
  Iterator insert(Iterator before, IteratorType first, IteratorType last) {
    while (first != last)
      before = insert(before, *(first++)) + 1;
    return before;
  }
  Iterator erase(Iterator what) {
    Iterator result = what;
    ++result;
    delete what.node_;
    return result;
  }
  Iterator erase(Iterator begin, Iterator end) {
    while (begin != end)
      erase(begin++);
    return end;
  }
 private:
  ListNodeBase 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
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
#include <iostream>
#include "List.hpp"
 
template <class T, class Container = List<T> >
class Stack {
 public:
  Stack() : container() {}
  void push(const T &value) {
    container.pushBack(value);
  }
  T pop() {
    return container.popBack();
  }
  size_t size() const {
    return container.size();
  }
  void clear() {
    container.clear();
  }
  bool isEmpty() {
    return container.isEmpty();
  }
  const T &top() {
    return container.back();
  }
 private:
  Container container;
};
 
template <class T, class Container = List<T> >
class Queue {
 public:
  Queue() : container() {}
  void enqueue(const T &value) {
    container.pushBack(value);
  }
  T dequeue() {
    return container.popFront();
  }
  size_t size() const {
    return container.size();
  }
  void clear() {
    container.clear();
  }
  bool isEmpty() {
    return container.isEmpty();
  }
  const T &top() {
    return container.front();
  }
 private:
  Container container;
};
 
 
int main(int argc, char *argv[]) {
  List<int> list;
  for (int i = 0; i < 10; ++i)
    if (i % 2)
      list.pushBack(i);
    else
      list.pushFront(i);
  for (List<int>::Iterator i = list.begin(); i != list.end(); ++i)
    std::cout << *i << " ";
  std::cout << std::endl;
  
  Stack<int> stack;
  for (int i = 0; i < 10; ++i)
    stack.push(i);
  while (!stack.isEmpty())
    std::cout << stack.pop() << " ";
  std::cout << std::endl;
 
  Queue<int> queue;
  for (int i = 0; i < 10; ++i)
    queue.enqueue(i);
  while (!queue.isEmpty())
    std::cout << queue.dequeue() << " ";
  std::cout << std::endl;
}


Упрощенный, с комментариями.
Сразу с примером.
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
#include <iostream>
 
// нода связного списка
template <class T>
struct Node {
  // нулевой элемент связного списка указывает на себя
  Node() : prev(this), next(this) {}
  // добавление в связный список конструктором
  Node(Node *next_, const T &data_)
    : prev(next_->prev), next(next_), data(data_) {
    prev->next = next->prev = this;
  }
  // удаление из связного списка деструктором
  virtual ~Node() {
    prev->next = next;
    next->prev = prev;
  }
  Node *prev, *next;
  T data;
};
 
// шаблонный класс связного списка
template <class T>
class List {
 public:
  // конструктор
  List() : base(new Node<T>()) {}
  // конструктор копирования
  List(const List<T> &other) : base(new Node<T>()) {
    copyFrom(other);
  }
  // деструктор
  ~List() { clear(); delete base; }
  // оператор присваивания
  List<T> operator=(const List<T> &other) {
    if (&other != this) {
      clear();
      copyFrom(other);
    }
    return *this;
  }
  // проверка на пустоту связного списка
  bool empty() { return base->next == base; }
  // очистка связного списка
  void clear() {
    while (!empty())  delete base->next;
  }
  // вычисление размера связного списка
  size_t size() const {
    size_t size = 0;
    for (Node<T> *node = base->next; node != base; node = node->next)
      ++size;
    return size;
  }
  // копирование связного списка
  void copyFrom(const List<T> &other) {
    for (size_t i = 0; i < other.size(); ++i)      
      pushBack(other.get(i));
  }
  // добавление в конец списка
  void pushBack(const T &value) {
    new Node<T>(base, value);
  }
  // добавление в начало списка
  void pushFront(const T &value) {
    new Node<T>(base->next, value);
  }
  // первый эелемент списка
  const T &front() const {
    return base->next->data;
  }
  // последний элемент списка
  const T &back() const {
    return base->prev->data;
  }
  // возвращение и удаление первого элемента связного списка
  T popFront() {
    T result = front();
    delete base->next;
    return result;
  }
  // возвращение и удаление последнего элемента связного списка
  T popBack() {
    T result = back();
    delete base->prev;
    return result;
  }
  // вставка данных перед индексом
  void insert(size_t beforeIndex, const T &value) {
    Node<T> *before = base->next;
    while (beforeIndex-- > 0) before = before->next;
    new Node<T>(before, value);
  }
  // получение данных по индексу
  T &get(size_t n) {
    Node<T> *result = base->next;
    while (n-- > 0) result = result->next;
    return result->data;
  }
  // константный вариант
  const T &get(size_t n) const {
    Node<T> *result = base->next;
    while (n-- > 0) result = result->next;
    return result->data;
  }
  // получение элемента оператором
  T &operator[](size_t n) { return get(n); }
  // константный вариант
  const T &operator[](size_t n) const { return get(n); }
 
 private:
  // нулевой элемент связного списка
  Node<T> *base;
};
 
int main(int argc, char *argv[]) {
  List<int> a;
  for (size_t i = 0; i < 10; ++i)
    a.pushBack(i);
  a.insert(5, 0);
  
  List<int> b(a);
  a.insert(0, -1);
  b = a;
 
  for (size_t i = 0; i < b.size(); ++i)
    std::cout << b[i] << std::endl;
 
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 23:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru