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, и го печатаме.
}                                                         // Край на програмата.
  1. Към кой възел сочи first.next преди вмъкването?
  2. Кой ред свързва новия възел със стария наследник на first? Кой ред свързва first с новия възел?
  3. В какъв ред се извеждат номерата и кога спира цикълът?
  4. Кой един ред ще прескочи зала №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.

Изтегли main.cpp.