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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 59, средняя оценка - 4.76
Anna Bridman
0 / 0 / 0
Регистрация: 12.06.2011
Сообщений: 7
12.06.2011, 17:12     Шаблон класса двусвязный список #1
Для решения задачи описать и использовать шаблон класса "двусвязный список".
Необходимо составить программу которая содержит динамическую информацию о наличии автобусов в автобусном парке. сведения о каждом автобусе содержат: 1)номер; 2)фамилию водителя; 3)номер маршрута; 4)признак того, где находится автобус - на маршруте или в парке. Программа должна обеспечивать:
1) начальное формирование данных о всех автобусах в виде списка;
2) при выезде каждого автобуса из парка вводится номер автобуса, и программа устанавливает значение признака "автобус на маршруте";
3) при въезде каждого автобуса в парк вводится номер автобуса, и программа устанавливает значение признака "автобус в парке";
4) по запросу выдаются сведения об автобусах, находящихся в парке, или об автобусах, находящихся на маршруте.

Проблема как раз в составлении шаблона. Задание главным образом состоит в написании шаблона класса "двусвязный список" без использования встроенных типа <list> или <vector>. Ниже то, что я успела сделать. Может кто потратит немного времени на набросок или замечпния по коду, хотя бы подсказать в каком направлении мне двигаться. Спасибо


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
#include "stdafx.h"
#include <string>
#include <conio.h>
#include <iostream>
 
using namespace std;
 
class spisok
{
    struct element              
    {
        string number;          //Номер автобуса
        string driver;          //Водитель
        string route;           //Маршрут
        bool deport;            //Признак того, где находится автобус (в автопарке или на маршруте)     
        element *next;          //Указатель на следующий элемент списка
        element *prev;          //Указатель на предыдущий элемент списка
        element *head;          //Указатель на первый элемент списка
        element *tail;          //Указатель на последний элемент списка
 
                                
        element (): number(0), driver(0), route(0), next(0),prev (0), head (NULL), tail (NULL)
        {}
    }
 
    *bus;
 
    public:
        string get_number()         { return bus->number;           }
        string get_route()          { return bus->route;            }
        string get_driver()         { return bus->driver;           }
        bool get_deport()           { return bus->deport;           }
 
        element &operator [] (int index)                        //Перегрузка оператора индексирования
        {
            return bus[index];
        }
 
        element operator = (element *current)                   //Перегрузка оператора присваивания
        {
            return element( bus->number = current->number,
                            bus->driver = current->driver,
                            bus->route  = current->route,
                            bus->deport = current->deport,
                            bus->next   = current->next,
                            bus->prev   = current->prev);
        }
        spisok() : bus(0) {}//конструктор по умолчанию класса spisok
 
        element *new_bus(string num, string dr, string r)
        {
            bus = new element();
            bus->number = num;
            bus->driver = dr;
            bus->route = r;
            bus->prev = bus->tail;
            bus->next = NULL;
            if (bus->tail != NULL)
                bus->tail->next = bus;
            if(bus->head == NULL)
                bus->head = bus;
            bus->tail = bus;
            return bus;
        }
 
        void print()                //ф-ция печати
        {
            element *E = bus;
 
            while(E
            {
                cout<<E->number
                    <<"\t"<<E->driver
                    <<"\t"<<E->route;
                E = E->next;
            }
            cout<<"\n";
        }
 
        void search(string par_search)//ф-ция поиска. содержит par_search, к-ый определяет что искать
        {
            element *E = bus;
            if (bus == 0)//если список пуст, то ничего не ищется, выход из программы
                return;
 
            while(E)//сам цикл поиска
            {
                if (par_search == E->number)//если par_search, к-ый мы ввели, совпадает с номером автобуса в списке
                {
                    cout<<"\n"<<bus->number //то распечатывает
                        <<"\t"<<bus->driver
                        <<"\t"<<bus->route
                        <<"\n";
                    break;
                }
                E = E->next;//проверяет следующий элемент списка
            }
        }
 
        void in_deport() {bus->deport = false;}
        void on_route() {bus->deport = true;}
 
        void delete_spisok()//
        {
            if(bus == 0)//если список пуст, то ничего не удаляется, выход из программы
                return;
            element *E = bus;//в противном случае идет удаление
            bus = bus->next;
            delete E;
        }
 
        ~spisok()//деструктор 
        {
            while(bus)
                delete_spisok();
        }
};
 
 
void main()
{
    spisok bus[100];
    string number;
    string route;
    string driver;
    string number_build;
    string index;
    int i,q = 0;
    int size = 0;
    string par_search;
    int num;
    
    int CV = 0;
    while (CV != 5)
    {
        cout << endl << "Menu: \n"
        << "1. New bus \n"
        << "2. Show spisok \n"
        << "3. Delete bus \n"
        << "4. Search bus\n"
        << "5. Exit \n"
        <<"Input number menu:  ";
 
        cin >> CV;
        switch(CV)
        {
                case 1: 
                    {
                        cout<<" Name number: "; cin>>number;
                        cout<<" driver: ";      cin>>driver;
                        cout<<" route: ";       cin>>route;
 
                        bus[q].new_bus(number, driver, route);
                        q++;                                                        
                        size = q;                                                   
                    }  break;
 
                case 2:
                    { 
                        for (i = 0; i < size; i++)
                        bus[i].print();//вызывается ф-ция печати
                    }  break;
 
                case 3:
                    {
                        cout<<"\nVvedite nomer:";//вводится номер записи которую надо удалить
                        cin>>i;
                            bus[i].delete_spisok();//вызывается ф-ция удаления записи
                    }  break;
 
                case 4: 
                    {
                        cout<<"\nEnter number bus: ";
                        cin>>par_search;//вводится параметр поиска, т.е. номер автобуса
                        for (int i = 0; i < size; i++)
                        bus[i].search(par_search);//вызывается ф-ция поиска
                    }  break;
 
                case 5:  break;
 
            default: cout << endl << "Enter right number!\n"; break;
        }
 
    _getch();
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.06.2011, 17:12     Шаблон класса двусвязный список
Посмотрите здесь:

Реализация класса «двусвязный список» C++
Реализация класса множество через двусвязный список. C++
C++ Реализовать классы «стек» и «очередь» наследованием от базового класса «двусвязный список»
Переделать двусвязный список в двусвязный кольцевой C++
C++ Как переделать эту прогу в шаблон классов "Двусвязный список" произвольных элементов
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
pito211
 Аватар для pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
12.06.2011, 17:49     Шаблон класса двусвязный список #2
всё переделывать. Это же не шаблон
Anna Bridman
0 / 0 / 0
Регистрация: 12.06.2011
Сообщений: 7
12.06.2011, 18:17  [ТС]     Шаблон класса двусвязный список #3
Я знаю, потому и прошу помочь.
Просто плохо знакома с шаблонами, а времени на изучение литературы мало(( Как я поняла нужно мой класс загнать в шаблон типа
template <class Type>
Type spisok(Type ......) или как?
Dejust
 Аватар для Dejust
49 / 49 / 1
Регистрация: 31.01.2011
Сообщений: 156
12.06.2011, 18:36     Шаблон класса двусвязный список #4
Вы создали список который годиться для хранения информации только об автобусах (тип автобус), а надо что бы получился контейнер для хранения данных разного типа (int, char, string, автобус, etc...)

Я рекомендую все-таки почитать литературу, тем более там совсем немного (ройте в сторону шаблонных классов)

ЗЫ
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<Type>
class spisok
{
     struct element                          
    {
                Type* _el;                        // Указатель на объект закрепленным за данным элементом списка
                element *next;                  //Указатель на следующий элемент списка
                element *prev;                  //Указатель на предыдущий элемент списка
                element *head;                  //Указатель на первый элемент списка
                element *tail;     
     }
// Далее объявление и определение методов присущих двухсвязному списку
   void add(Type* _e); // Добавляет элемент типа Type
   Type* front();           // Возвращает первый элемент типа Type
   // etc ...
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
12.06.2011, 18:44     Шаблон класса двусвязный список #5
А я вот так и не смог понять чёрной магии с переменными head и tail. Я понимаю, для чего они нужны в списке, но зачем они в элементах списка?
Anna Bridman
0 / 0 / 0
Регистрация: 12.06.2011
Сообщений: 7
12.06.2011, 18:49  [ТС]     Шаблон класса двусвязный список #6
grizlik78, кажется поняла..) и в самом деле бред. Нужны только указатель на следующий и предыдущий. я сама запуталась..((( уже голова болит от всего этого(
Dejust
 Аватар для Dejust
49 / 49 / 1
Регистрация: 31.01.2011
Сообщений: 156
12.06.2011, 18:53     Шаблон класса двусвязный список #7
А ну так вынести их в свойства класса надо бы, желательно в private
Магии нет, не предал им значения просто, когда копипастил
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
12.06.2011, 19:12     Шаблон класса двусвязный список #8
Тут посмотрите: Списки, стеки, очереди
Anna Bridman
0 / 0 / 0
Регистрация: 12.06.2011
Сообщений: 7
12.06.2011, 19:36  [ТС]     Шаблон класса двусвязный список #9
Вот, что у меня пока получается
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
#include "stdafx.h"
#include <string>
#include <conio.h>
#include <iostream>
 
using namespace std;
 
template <class Type>
class spisok
{
    private:
        struct element
        {
            Type number;        //Номер автобуса
            Type driver;        //Водитель
            Type route;         //Маршрут
            bool deport;        //Признак того, где находится автобус (в автопарке или на маршруте)
            element *next;          //Указатель на следующий элемент списка
            element *prev;          //Указатель на предыдущий элемент списка
            
            element(Type num, Type dr, Type r, bool dep = false, element* nxt = 0, element* prv = 0) :
                number(num), driver(dr), route(r), deport(dep), next(nxt), prev(prv)
            {}
        }
    public:
        element<Type> *bus;
        element<Type> *head;
        element<Type> *tail;
        spisok() : bus(0) {}
        
        Type get_number()           { return bus->number;           }
        Type get_route()            { return bus->route;            }
        Type get_driver()           { return bus->driver;           }
        bool get_deport()           { return bus->deport;           }
 
        element &operator [] (int index)                        
        {
            return bus[index];
        }
 
        element operator = (element *current)                   
        {
            return element(bus->number  = current->number,
                        bus->driver = current->driver,
                        bus->route  = current->route,
                        bus->deport = current->deport,
                        bus->next   = current->next,
                        bus->prev   = current->prev);
        }
        element *new_bus(Type num, Type dr, Type r)
        {
            bus = new element();
            bus->number = num;
            bus->driver = dr;
            bus->route = r;
            bus->prev = bus->tail;
            bus->next = NULL;
            if (bus->tail != NULL)
                bus->tail->next = bus;
            if(bus->head == NULL)
                bus->head = bus;
            bus->tail = bus;
            return bus;
        }
 
        void add_bus(Type num, Type dr, Type r, bool dep)
        {}
        void del_bus()
        {}
        void print()                
        {
            element *E = bus;
 
            while(E)
            {
                cout<<E->number
                    <<"\t"<<E->driver
                    <<"\t"<<E->route;
                E = E->next;
            }
            cout<<"\n";
        }
        void search(const element<Type> *bus1, Type field_key)
        {
            if(bus1 == 0)
                return;
            if(bus1->number == field_key)
            {
                cout<<"\t"
                    << bus1->number<< "\t"
                    << bus1->driver << "\t"
                    << bus1->route << "\t"
                    << bus1->deport << "\t\n" ;
            }
            search(bus1->get_next(), field_key);
        }
};
 
void main()
{
    spisok <string> bus;
    string number;
    string driver;
    string route;
    bool deport;
    int i,q = 0;
    int size = 0;
    string par_search;
    int num;
    
    int CV = 0;
    while (CV != 5)
    {
        cout << endl << "Menu: \n"
        << "1. New bus \n"
        << "2. Show spisok \n"
        << "3. Delete bus \n"
        << "4. Search bus\n"
        << "5. Exit \n"
        <<"Input number menu:  ";
 
        cin >> CV;
        switch(CV)
        {
                case 1: 
                    {
                        cout<<" number: ";  cin>>number;
                        cout<<" driver: ";  cin>>driver;
                        cout<<" route: ";   cin>>route;
 
                        bus[q].new_bus(number, driver, route);
                        q++;                                                        
                        size = q;                                               
                    }  break;
 
                case 2:
                    { 
                        for (i = 0; i < size; i++)
                        bus[i].print();//вызывается ф-ция печати
                    }  break;
 
                case 3:
                    {
                        
                    }  break;
 
                case 4: 
                    {
                        cout<<"\nEnter number bus: ";
                        cin>>par_search;
                        /*for (int i = 0; i < size; i++)
                        bus[i].search(......, par_search);*/
                    }  break;
 
                case 5:  break;
 
            default: cout << endl << "Enter prev number!\n"; break;
        }
 
    _getch();
    }
}
Компилятор выдает кучу ошибок.
Dejust
 Аватар для Dejust
49 / 49 / 1
Регистрация: 31.01.2011
Сообщений: 156
12.06.2011, 19:48     Шаблон класса двусвязный список #10
Ясно дело, что выдает кучу ошибок.
Вы опять не то делаете. Список нужен лишь для того, что бы хранить в нем объекты некоторого типа.

Создайте класс двухсвязного списка - создайте класс автобуса - храните "автобусы" (объекты класса автобус) в списке (объект класса двухсвязного списка).

Юзайте ссылку lemegeton'а (там вам готовые решения на любой вкус) и почитайте уж о шаблонных классах.

Как реализуете двухсвязный список - решайте задачу, ведь это вам надо?..
Anna Bridman
0 / 0 / 0
Регистрация: 12.06.2011
Сообщений: 7
12.06.2011, 20:48  [ТС]     Шаблон класса двусвязный список #11
Т.е. что-то вроде
class Bus //Класс описывающий один автобус
{
private:
string number; //номер
string driver; //водитель
string route; //маршрут
public:
Bus(){}
~Bus(){}

};
template <class Type>
class spisok//В нем как раз и реализуется двусвязный список?
{...}

void main()
{}

Добавлено через 2 минуты
Или я что-то не так понимаю
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
12.06.2011, 20:51     Шаблон класса двусвязный список #12
Да, так.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
12.06.2011, 21:22     Шаблон класса двусвязный список #13
Давайте попробую разжевать маленько.
Все на самом деле очень просто.
Значит так. Давайте сделаем так, что начало и конец списка хранит элемент класса List под названием base. base.next указывает на первый элемент списка, base.prev на последний. При этом количество кода на удаление и добавление элементов сокращается до одной строки.
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
#include <iostream>
 
// базовый класс элемента связного списка
// не содержит данных, содержит часть логики
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>
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;
  }
 private:
  // базовый эелемент.
  // его поле next указывает на первый элемент списка
  // поле prev указываеты на последний элемент списка
  // если список пуст, next == prev == &base
  NodeBase base;
};
 
// класс автобуса
struct Bus {
  int number;
  int route;
  //... тут наверно нужны другие поля
  Bus(int number_, int route_) : number(number_), route(route_) {}
  // переопределенный оператор для вывода на экран
  friend std::ostream& operator<<(std::ostream &stream, const Bus &bus) {
    return stream << "Bus number " << bus.number
                  << ", route: " << bus.route
                  << std::endl;
  }
};
 
int main(int argc, char *argv[]) {
  List<Bus> a; // список автобусов
  // добавим в список сто автобусов
  for (int i = 0; i < 100; ++i)
    a.PushBack(Bus(i + 1, i));
  // вывод его на экран
  a.PrintAll();
}
Anna Bridman
0 / 0 / 0
Регистрация: 12.06.2011
Сообщений: 7
13.06.2011, 01:03  [ТС]     Шаблон класса двусвязный список #14
Спасибо огромное, попробую разобраться)))

Добавлено через 2 часа 41 минуту
А как получить доступ к какому-либо элементу списка? Вот что у меня с вашей помощью получилось:
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
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <string>
using namespace std;
 
// базовый класс элемента связного списка
// не содержит данных, содержит часть логики
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>
class List
{
  private:
  // базовый эелемент.
  // его поле next указывает на первый элемент списка
  // поле prev указываеты на последний элемент списка
  // если список пуст, next == prev == &base
  NodeBase base;
 public:
                                // конструктору по-умолчанию делать в принципе нечего, он должен быть объявлен
  List() : base() {};
 
  ~List()                       // деструктор удаляет список функцией Clear
  {
    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;
  }
  void search(string par_search)//ф-ция поиска
  {
      Bus *E = A;
      if (A == 0)
          return;
      while(E)
      {
          if (par_search ==  E->number)
          {
              cout<<endl<<A->number 
                  <<"\t"<<A->driver
                  <<"\t"<<A->route
                  <<"\t"<<A->deport
                  <<endl;
              break;
          }
                E = E->next;
      }
  }
};
 
// класс автобуса
struct Bus
{
    int number;
    string driver;
    int route;
    bool deport;
    Bus(int number_, string driver_, int route_, bool deport_) : number(number_), driver(driver_), route(route_),deport(deport_) {}
  // переопределенный оператор для вывода на экран
    
    Bus *A;
 
    friend std::ostream& operator<<(std::ostream &stream, const Bus &bus)
    {
        string dep;
        if(bus.deport)
            dep = "on route";
        else dep = "in deport";
        return stream   << "Bus number: "   << bus.number
                        << ", driver: "     << bus.driver
                        << ", route: "      << bus.route                        
                        << ", locate: "     <<dep
                        << std::endl;
    }
};
 
void main()
{
    List<Bus> a; // список автобусов
    int number;
    int route;
    string driver;
    bool locate;
    int menu = 0;
    while (menu != 6)
    {
        cout<<"1 - Formation bus in deport"<<endl   //Формирование автобусов в парке
            <<"2 - Show spisok"<<endl               //Вывод информации обо всех автобусах 
            <<"3 - Exit bus from deport"<<endl      //вывод автобуса на рейс
            <<"3 - Return bus to deport"<<endl      //возврат автобуса в парк
            <<"4 - Bus in deport"<<endl             //выводит тех кто в парке
            <<"5 - Bus on route"<<endl              //выводит тез кто на маршруте
            <<"6 - Exit"<<endl
            <<"Input number menu: ";
        cin >> menu;
        switch(menu)
        {
                case 1: 
                    {
                        cout<<" number: ";  cin>>number;
                        cout<<" driver: ";  cin>>driver;
                        cout<<" route: ";   cin>>route;
                        cout<<" locate(0 - in deport; 1 - on route): "; cin>>locate;
                        a.PushBack(Bus(number, driver, route, locate));                                 
                    }  break;
 
                case 2:
                    { 
                        a.PrintAll();
                    }  break;
 
                case 3:
                    {
                        
                    }  break;
 
                case 4: 
                    {
                        
                    }  break;
 
                case 5: 
                    {
                        
                    }  break;
 
                case 6:  break;//если введена CV=5, то break и switch(CV)обрывается
 
            default: cout << endl << "Enter right number!\n"; break;//если введена не цифра от 1 до 5, то выводится это сообщение
        }
        _getch();
    }
}
Сомнения только с фунуцией поиска. И как мне потом с найденными автобусами совершать действия(например поменять deport на true или false)? Можете проиллюстрировать, пожалуйста

Добавлено через 12 секунд
А как получить доступ к какому-либо элементу списка? Вот что у меня с вашей помощью получилось:
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
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <string>
using namespace std;
 
// базовый класс элемента связного списка
// не содержит данных, содержит часть логики
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>
class List
{
  private:
  // базовый эелемент.
  // его поле next указывает на первый элемент списка
  // поле prev указываеты на последний элемент списка
  // если список пуст, next == prev == &base
  NodeBase base;
 public:
                                // конструктору по-умолчанию делать в принципе нечего, он должен быть объявлен
  List() : base() {};
 
  ~List()                       // деструктор удаляет список функцией Clear
  {
    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;
  }
  void search(string par_search)//ф-ция поиска
  {
      Bus *E = A;
      if (A == 0)
          return;
      while(E)
      {
          if (par_search ==  E->number)
          {
              cout<<endl<<A->number 
                  <<"\t"<<A->driver
                  <<"\t"<<A->route
                  <<"\t"<<A->deport
                  <<endl;
              break;
          }
                E = E->next;
      }
  }
};
 
// класс автобуса
struct Bus
{
    int number;
    string driver;
    int route;
    bool deport;
    Bus(int number_, string driver_, int route_, bool deport_) : number(number_), driver(driver_), route(route_),deport(deport_) {}
  // переопределенный оператор для вывода на экран
    
    Bus *A;
 
    friend std::ostream& operator<<(std::ostream &stream, const Bus &bus)
    {
        string dep;
        if(bus.deport)
            dep = "on route";
        else dep = "in deport";
        return stream   << "Bus number: "   << bus.number
                        << ", driver: "     << bus.driver
                        << ", route: "      << bus.route                        
                        << ", locate: "     <<dep
                        << std::endl;
    }
};
 
void main()
{
    List<Bus> a; // список автобусов
    int number;
    int route;
    string driver;
    bool locate;
    int menu = 0;
    while (menu != 6)
    {
        cout<<"1 - Formation bus in deport"<<endl   //Формирование автобусов в парке
            <<"2 - Show spisok"<<endl               //Вывод информации обо всех автобусах 
            <<"3 - Exit bus from deport"<<endl      //вывод автобуса на рейс
            <<"3 - Return bus to deport"<<endl      //возврат автобуса в парк
            <<"4 - Bus in deport"<<endl             //выводит тех кто в парке
            <<"5 - Bus on route"<<endl              //выводит тез кто на маршруте
            <<"6 - Exit"<<endl
            <<"Input number menu: ";
        cin >> menu;
        switch(menu)
        {
                case 1: 
                    {
                        cout<<" number: ";  cin>>number;
                        cout<<" driver: ";  cin>>driver;
                        cout<<" route: ";   cin>>route;
                        cout<<" locate(0 - in deport; 1 - on route): "; cin>>locate;
                        a.PushBack(Bus(number, driver, route, locate));                                 
                    }  break;
 
                case 2:
                    { 
                        a.PrintAll();
                    }  break;
 
                case 3:
                    {
                        
                    }  break;
 
                case 4: 
                    {
                        
                    }  break;
 
                case 5: 
                    {
                        
                    }  break;
 
                case 6:  break;//если введена CV=5, то break и switch(CV)обрывается
 
            default: cout << endl << "Enter right number!\n"; break;//если введена не цифра от 1 до 5, то выводится это сообщение
        }
        _getch();
    }
}
Сомнения только с фунуцией поиска. И как мне потом с найденными автобусами совершать действия(например поменять deport на true или false)? Можете проиллюстрировать, пожалуйста

Добавлено через 15 секунд
А как получить доступ к какому-либо элементу списка? Вот что у меня с вашей помощью получилось:
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
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <string>
using namespace std;
 
// базовый класс элемента связного списка
// не содержит данных, содержит часть логики
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>
class List
{
  private:
  // базовый эелемент.
  // его поле next указывает на первый элемент списка
  // поле prev указываеты на последний элемент списка
  // если список пуст, next == prev == &base
  NodeBase base;
 public:
                                // конструктору по-умолчанию делать в принципе нечего, он должен быть объявлен
  List() : base() {};
 
  ~List()                       // деструктор удаляет список функцией Clear
  {
    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;
  }
  void search(string par_search)//ф-ция поиска
  {
      Bus *E = A;
      if (A == 0)
          return;
      while(E)
      {
          if (par_search ==  E->number)
          {
              cout<<endl<<A->number 
                  <<"\t"<<A->driver
                  <<"\t"<<A->route
                  <<"\t"<<A->deport
                  <<endl;
              break;
          }
                E = E->next;
      }
  }
};
 
// класс автобуса
struct Bus
{
    int number;
    string driver;
    int route;
    bool deport;
    Bus(int number_, string driver_, int route_, bool deport_) : number(number_), driver(driver_), route(route_),deport(deport_) {}
  // переопределенный оператор для вывода на экран
    
    Bus *A;
 
    friend std::ostream& operator<<(std::ostream &stream, const Bus &bus)
    {
        string dep;
        if(bus.deport)
            dep = "on route";
        else dep = "in deport";
        return stream   << "Bus number: "   << bus.number
                        << ", driver: "     << bus.driver
                        << ", route: "      << bus.route                        
                        << ", locate: "     <<dep
                        << std::endl;
    }
};
 
void main()
{
    List<Bus> a; // список автобусов
    int number;
    int route;
    string driver;
    bool locate;
    int menu = 0;
    while (menu != 6)
    {
        cout<<"1 - Formation bus in deport"<<endl   //Формирование автобусов в парке
            <<"2 - Show spisok"<<endl               //Вывод информации обо всех автобусах 
            <<"3 - Exit bus from deport"<<endl      //вывод автобуса на рейс
            <<"3 - Return bus to deport"<<endl      //возврат автобуса в парк
            <<"4 - Bus in deport"<<endl             //выводит тех кто в парке
            <<"5 - Bus on route"<<endl              //выводит тез кто на маршруте
            <<"6 - Exit"<<endl
            <<"Input number menu: ";
        cin >> menu;
        switch(menu)
        {
                case 1: 
                    {
                        cout<<" number: ";  cin>>number;
                        cout<<" driver: ";  cin>>driver;
                        cout<<" route: ";   cin>>route;
                        cout<<" locate(0 - in deport; 1 - on route): "; cin>>locate;
                        a.PushBack(Bus(number, driver, route, locate));                                 
                    }  break;
 
                case 2:
                    { 
                        a.PrintAll();
                    }  break;
 
                case 3:
                    {
                        
                    }  break;
 
                case 4: 
                    {
                        
                    }  break;
 
                case 5: 
                    {
                        
                    }  break;
 
                case 6:  break;//если введена CV=5, то break и switch(CV)обрывается
 
            default: cout << endl << "Enter right number!\n"; break;//если введена не цифра от 1 до 5, то выводится это сообщение
        }
        _getch();
    }
}
Сомнения только с фунуцией поиска. И как мне потом с найденными автобусами совершать действия(например поменять deport на true или false)? Можете проиллюстрировать, пожалуйста

Добавлено через 51 минуту
Ой.. Инет гребет..

Добавлено через 2 минуты
Поиск тех автобусов, что в парке:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
        void search_in_deport()
        {
            base *E ;
            if (E == 0)
                return;
            while(E)
            {
                if (E->deport ==  false)
                {
                    cout<<endl<<E->number
                    <<"\t"<<E->driver
                    <<"\t"<<E->route
                    <<endl;
                    break;
                }
                E = E->next;
            }
        }
Что не так? Ребят, помогите понять, пожалуйста

Добавлено через 2 минуты
Если подумать, то ошибка должно быть в начале. While по идее правильный. Может я E не так объявляю?
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
13.06.2011, 01:39     Шаблон класса двусвязный список #15
"Красивый" способ -- это использовать итератор.
Цитата Сообщение от Anna Bridman Посмотреть сообщение
И как мне потом с найденными автобусами совершать действия(например поменять deport на true или false)?
Могу предложить только итератор. Подойдет?
Anna Bridman
0 / 0 / 0
Регистрация: 12.06.2011
Сообщений: 7
13.06.2011, 03:17  [ТС]     Шаблон класса двусвязный список #16
lemegeton, эмм.. что подразумевается под итератором?

Добавлено через 1 минуту
А как мой последний код? Неужели там совсем всё плохо?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.06.2011, 12:05     Шаблон класса двусвязный список
Еще ссылки по теме:

Шаблоны функций, Ошибка: для использования класса шаблон требуется список аргументов шаблон C++
C++ - Реализация класса «двусвязный список» C++
C++ Шаблон класса двусвязный список

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

Или воспользуйтесь поиском по форуму:
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
13.06.2011, 12:05     Шаблон класса двусвязный список #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
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));
}
Yandex
Объявления
13.06.2011, 12:05     Шаблон класса двусвязный список
Ответ Создать тему
Опции темы

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