Вступ
Ми працюємо над проєктом з розробки системи розкладу потягів для завантаженої залізничної мережі.
Нас попросили розробити прототип маршрутів потягів для цієї системи розкладу. Кожен маршрут складається з послідовності станцій, на яких зупиняється відповідний потяг.
Вказівки
Наша команда вирішила використовувати двонаправлений звʼязаний список, щоб представити кожен маршрут потяга в розкладі.
Кожну станцію на маршруті потяга представлятиме вузол у звʼязаному списку.
Нам не потрібно перейматися часом прибуття та відправлення на станціях.
Кожну станцію просто представлятиме число.
Маршрути можна подовжувати, додаючи станції на початок або в кінець маршруту.
Їх також можна скорочувати, прибираючи станції з початку або з кінця маршруту.
Іноді станцію закривають, і тоді її потрібно прибрати з маршруту, навіть якщо вона не на початку і не в кінці маршруту.
Розмір маршруту вимірюють не тим, яку відстань долає потяг, а тим, на скількох станціях він зупиняється.
Звʼязаний список - фундаментальна структура даних у компʼютерних науках, яку часто використовують для реалізації інших структур даних.
Як випливає з назви, це список вузлів, зʼєднаних між собою.
Це список «вузлів», де кожен вузол посилається на свого сусіда або сусідів.
У однонаправленому звʼязаному списку кожен вузол посилається лише на вузол, що йде за ним.
У двонаправленому звʼязаному списку кожен вузол посилається і на вузол, що йде перед ним, і на вузол, що йде після нього.
Якщо хочеться глибше зануритися у звʼязані списки, погляньте на цю статтю, де все пояснено за допомогою гарних малюнків.
Як цю вправу побудовано в треку C++
Хоча звʼязані списки можна реалізувати в різний спосіб і на основі різних структур даних, тут ми просимо реалізувати звʼязаний список в обʼєктно-орієнтованому стилі.
У файлі linked_list_test.cpp викликається шаблонний клас List.
Цей клас потрібно написати з такими функціями-членами:
-
push додає елемент у кінець списку,
-
pop видаляє та повертає останній елемент списку,
-
shift видаляє та повертає перший елемент списку,
-
unshift додає елемент на початок списку, а
-
count повертає загальну кількість елементів у поточному списку.
Насамкінець, крім перелічених вище методів, реалізуйте ще erase.
erase прийматиме один аргумент: значення, яке потрібно видалити зі звʼязаного списку.
Якщо значення трапляється більше ніж один раз, видалити потрібно лише перше його входження.
Функція має повертати, чи було видалено елемент.
Хоча це й не тестується, можна згенерувати виняток, якщо pop і shift викликати на порожньому List.
Джерело
Класична тема з інформатики
