112. Сортиран линеен списък

Сортираният списък поддържа ред между съседните стойности. При ненамаляващ ред всеки елемент е по-малък или равен на следващия. При свързано представяне намираме мястото с обхождане, после сменяме връзките.

Раздел в разширената разработка.

Самостоятелна задача

Условие

Три заети книги трябва да бъдат върнати след 4, 7 и 9 дни, броено от днес. Програмата записва тези числа в списък, подреден от най-близкото връщане към най-далечното. Днес е заета още една книга, която трябва да се върне след 6 дни. Добавяме числото 6 на мястото му в списъка. В кода next сочи следващия възел, nullptr отбелязва края, & взема адрес, а -> чете или променя поле през указател. Тук списъкът е непразен и срокът за вмъкване е поне колкото първия срок. Затова търсим място след първия възел. При равни стойности новият възел застава пред първата равна стойност след началото.

#include <iostream>                     // Включваме библиотеката, която ни дава cout за печат на екрана.
using namespace std;                    // Така можем да пишем cout вместо std::cout.

struct Node {                           // Описваме от какво се състои един възел.
    int value;                          // Тук е числото, което възелът пази.
    Node* next;                         // Тук е адресът на следващия възел. Node* означава „указател към възел“.
};                                      // Край на описанието на възела.

int main() {                            // Оттук започва изпълнението на програмата.
    Node last{9, nullptr};              // Създаваме възел с 9. nullptr означава, че след него няма възел.
    Node middle{7, &last};              // Създаваме възел със 7. &last е адресът на възела с 9.
    Node first{4, &middle};             // Създаваме възел с 4 и го свързваме с възела със 7.
    Node added{6, nullptr};             // Създаваме възел с 6, засега без следващ възел.

    Node* previous = &first;            // Започваме търсенето от адреса на първия възел.
    while (previous->next != nullptr   // Проверяваме дали след възела, към който сочи previous, има друг възел.
           && previous->next->value < added.value) // Ако има, проверяваме дали числото му е по-малко от новото.
        previous = previous->next;     // Ако и двете са верни, местим указателя previous един възел напред.

    added.next = previous->next;       // Новият възел взема адреса на досегашния следващ възел.
    previous->next = &added;            // Възелът, при който спряхме, вече сочи към новия възел.

    for (Node* node = &first;           // За печата започваме от първия възел.
         node != nullptr;              // Печатаме само докато указателят сочи към възел.
         node = node->next)            // След всяко отпечатване местим указателя към следващия възел.
        cout << node->value << '\n';   // Печатаме числото на текущия възел, после минаваме на нов ред.
}                                       // Край на програмата.
  1. На коя стойност спира previous?
  2. Кои две връзки се задават при вмъкването?
  3. Какво извежда програмата?
  4. Ако added.value е 10, след коя стойност се вмъква възелът и какво съдържа added.next?

Отговори за самопроверка

Отговор 1

На 4, защото следващата стойност 7 вече е по-голяма от 6.

Отговор 2

added.next сочи възела със 7, а previous->next сочи added.

Отговор 3

4 6 7 9, по едно число на ред.

Отговор 4

След 9. added.next е nullptr.

Изтегли main.cpp.

В речника Сортиран линеен списък.