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

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

Войти
Регистрация
Восстановить пароль
 
 
Anna Bridman
0 / 0 / 0
Регистрация: 12.06.2011
Сообщений: 7
#1

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

12.06.2011, 17:12. Просмотров 8726. Ответов 23
Метки нет (Все метки)

Для решения задачи описать и использовать шаблон класса "двусвязный список".
Необходимо составить программу которая содержит динамическую информацию о наличии автобусов в автобусном парке. сведения о каждом автобусе содержат: 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();
    }
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.06.2011, 17:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Шаблон класса двусвязный список (C++):

Шаблон класса двусвязный список - C++
Доброго времени суток! Препод дал задание реализовать шаблон класса двусвязный список. Сам класс написал, но не знаю как сделать из него...

Кольцевой двусвязный список шаблон класса ошибки - C++
Код выдаёт некоторые ошибки (прикрепили, на картинке): Что исправить? #include &quot;StdAfx.h&quot; #ifndef __list #define...

Составить двусвязный список на основе класса, объекты которого будут формировать этот список - C++
Составить двусвязный список на основе класса, объекты которого будут формировать этот список. В описание класса должны входить данные для...

Шаблоны функций, Ошибка: для использования класса шаблон требуется список аргументов шаблон - C++
Есть у меня 3 структуры Трамвай , Троллейбус , Автобус. Для автобуса определены функции (работают) Троллейбус и Трамвай одинаковые поля...

Реализация класса «двусвязный список» - C++
потребовалось выполнить такое задание, вот только не могу сообразить с чего начать и как собственно будет выглядеть код (в связи с тем, что...

Реализация класса множество через двусвязный список. - C++
дали задание реализовать класс множество через двусвязный список. Сам класс список мне реализовать вроде удалось, но стоит загвоздка в...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
12.06.2011, 17:49 #2
всё переделывать. Это же не шаблон
0
Anna Bridman
0 / 0 / 0
Регистрация: 12.06.2011
Сообщений: 7
12.06.2011, 18:17  [ТС] #3
Я знаю, потому и прошу помочь.
Просто плохо знакома с шаблонами, а времени на изучение литературы мало(( Как я поняла нужно мой класс загнать в шаблон типа
template <class Type>
Type spisok(Type ......) или как?
0
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 ...
1
grizlik78
Эксперт С++
1913 / 1445 / 113
Регистрация: 29.05.2011
Сообщений: 3,001
12.06.2011, 18:44 #5
А я вот так и не смог понять чёрной магии с переменными head и tail. Я понимаю, для чего они нужны в списке, но зачем они в элементах списка?
0
Anna Bridman
0 / 0 / 0
Регистрация: 12.06.2011
Сообщений: 7
12.06.2011, 18:49  [ТС] #6
grizlik78, кажется поняла..) и в самом деле бред. Нужны только указатель на следующий и предыдущий. я сама запуталась..((( уже голова болит от всего этого(
0
Dejust
49 / 49 / 1
Регистрация: 31.01.2011
Сообщений: 156
12.06.2011, 18:53 #7
А ну так вынести их в свойства класса надо бы, желательно в private
Магии нет, не предал им значения просто, когда копипастил
1
lemegeton
2924 / 1353 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
12.06.2011, 19:12 #8
Тут посмотрите: Списки, стеки, очереди
1
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();
    }
}
Компилятор выдает кучу ошибок.
0
Dejust
49 / 49 / 1
Регистрация: 31.01.2011
Сообщений: 156
12.06.2011, 19:48 #10
Ясно дело, что выдает кучу ошибок.
Вы опять не то делаете. Список нужен лишь для того, что бы хранить в нем объекты некоторого типа.

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

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

Как реализуете двухсвязный список - решайте задачу, ведь это вам надо?..
1
Anna Bridman
0 / 0 / 0
Регистрация: 12.06.2011
Сообщений: 7
12.06.2011, 20:48  [ТС] #11
Т.е. что-то вроде
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Bus //Класс описывающий один автобус
{
private:
    string number; //номер
    string driver; //водитель
    string route; //маршрут
public:
            Bus(){}
           ~Bus(){}
  
};
template <class Type>
class spisok//В нем как раз и реализуется двусвязный список?
{...}
 
void main()
{}
Добавлено через 2 минуты
Или я что-то не так понимаю
0
grizlik78
Эксперт С++
1913 / 1445 / 113
Регистрация: 29.05.2011
Сообщений: 3,001
12.06.2011, 20:51 #12
Да, так.
1
lemegeton
2924 / 1353 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
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();
}
2
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 не так объявляю?
0
lemegeton
2924 / 1353 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
13.06.2011, 01:39 #15
"Красивый" способ -- это использовать итератор.
Цитата Сообщение от Anna Bridman Посмотреть сообщение
И как мне потом с найденными автобусами совершать действия(например поменять deport на true или false)?
Могу предложить только итератор. Подойдет?
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.06.2011, 01:39
Привет! Вот еще темы с ответами:

Реализовать классы «стек» и «очередь» наследованием от базового класса «двусвязный список» - C++
Всем добрый вечер! Помогите пожалуйста с лабораторной работой, дело в том что скоро сдавать, а я в С++ новичок. и совсем не понимаю как это...

Как переделать эту прогу в шаблон классов "Двусвязный список" произвольных элементов - C++
#include &lt;iostream.h&gt; #include &lt;stdlib.h&gt;2 #include &lt;conio.h&gt; using namespace std; struct Element { public: double...

Написать конструктор для пользовательского класса "Двусвязный список" - C++
Попытался построить двусвязный список. Как написать этот конструктор ? Может быть правильно будет определить функцию push_back и каждый раз...

Реализовать указанные функции-члены для пользовательского класса "Кольцевой двусвязный список" - C++
Сообственно сабж. У списка два закрытых поля: tail-это узел следующий за &quot;последним&quot;(условно,ибо список -кольцо. в tail-е лежит мусор)...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.06.2011, 01:39
Ответ Создать тему
Опции темы

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