109. Линеен списък от общ вид — вмъкване в средата
Линейният списък е крайна, възможно празна редица от елементи. Редът има значение и стойностите могат да се повтарят. При списък от общ вид можем да вмъкваме и премахваме елементи и във вътрешността на редицата.
Списъкът може да се представи последователно в масив или чрез свързани възли. В едносвързания списък всеки възел пази стойност и връзка към следващия. head сочи първия възел и е nullptr при празен списък. Последният възел има next == nullptr. За вмъкване след вече намерен възел пренасочваме две връзки. Останалите възли запазват местата си.
Линейни списъци в разширената разработка · М. Тодорова, §2.3.1, печатни с. 77–79 (PDF с. 73–74)
Самостоятелна задача
Условие
За изложба първоначалният маршрут минава през зали №4 и №7 в този ред. Добавяме зала №9 непосредствено след зала №4 и искаме обхождането да покаже новия маршрут. Всяка зала е възел с номер value и указател next към следващата зала. head сочи началото.
В C++ Node* означава указател към възел, &last е адресът на last, а nullptr означава, че указателят не сочи възел. С current->value четем стойността на посочения възел, а с current->next намираме указателя към следващия.
#include <iostream> // Включваме библиотеката, която ни дава cout за печат на екрана.
using namespace std; // Така можем да пишем cout вместо std::cout.
struct Node { // Описваме от какво се състои един възел.
int value; // Тук пазим цяло число за този обект.
Node* next; // Пазим адреса на следващия възел. Node* е указател към възел.
}; // Край на описанието на типа.
int main() { // Оттук започва изпълнението на програмата.
Node last{7, nullptr}; // Създаваме последния възел с число 7. След него няма възел.
Node first{4, &last}; // Създаваме първия възел с число 4 и му даваме адреса на last.
Node* head = &first; // В head пазим адреса, от който започва списъкът.
Node added{9, first.next}; // Създаваме възел с число 9 и му копираме адреса от first.next.
first.next = &added; // Записваме адреса на новия възел в полето next на първия.
for (Node* current = head; current != nullptr; current = current->next) // Тръгваме от head. Минаваме по next и спираме, когато няма текущ възел.
cout << current->value << '\n'; // С -> вземаме числото на възела, към който сочи current, и го печатаме.
} // Край на програмата.
- Към кой възел сочи
first.nextпреди вмъкването? - Кой ред свързва новия възел със стария наследник на
first? Кой ред свързваfirstс новия възел? - В какъв ред се извеждат номерата и кога спира цикълът?
- Кой един ред ще прескочи зала №9, ако го добавим точно преди цикъла?
Отговори за самопроверка
1. Първоначална връзка
first.next сочи last, възела за зала №7.
2. Вмъкване
Node added{9, first.next}; запазва връзката към зала №7 в added.next. first.next = &added; насочва връзката от зала №4 към новата зала.
3. Обхождане
Извеждат се 4, 9 и 7 на отделни редове. След №7 current получава nullptr и цикълът спира.
4. Прескачане на възел
first.next = added.next; насочва връзката от №4 към №7. Възелът за №9 остава локална променлива, а обхождането от head вече минава през №4 и №7.