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'; // Печатаме числото на текущия възел, после минаваме на нов ред.
} // Край на програмата.
- На коя стойност спира previous?
- Кои две връзки се задават при вмъкването?
- Какво извежда програмата?
- Ако 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.
В речника Сортиран линеен списък.