МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
||||||||||||||||||||||||||||
Зв’язним списком називається структура даних, кожний елемент якої зв’язаний з наступним (або попереднім, або з обома сусідніми) елементом за допомогою покажчиків.Кожний елемент списку представлений значенням та покажчиком на наступний елемент, який представлений значенням та покажчиком на наступний для нього елемент і т.д. Тобто, явним чином проглядається рекурсивний опис цієї структури: будь-який наступний елемент є таким, як і той, що на нього посилається. Специфічними є лише початок і кінець списку. Початком списку є покажчик на його перший елемент, а кінцем ― покажчик в «нікуди». Опис структури «список»:
Перш ніж організовувати роботу з елементами списку його необхідно створити. Створення списку ― це запис початкової послідовності елементів. Може існувати декілька способів створення списку. Основна ідея полягає у тому, щоб кожного разу дописувати у кінець поточного списку новий елемент. Розглянемо рекурсивну функцію, яка за відомим значенням n заповнює список, таким чином створюючи його:
Звернення до функції створення списку в основній програмі може бути таким: a:=create_list(n). Ще одним варіантом створення списку може бути використання такої підпрограми:
Послідовність дій виглядає так. 1) Процедура new(x^.next) визначає адресу в динамічній пам’яті, за якою далі записуватиметься значення нового елемента. 2) Переходимо у цей наступний елемент, що розташований на новою адресою: x:=x^.next;. 3) Новий елемент, що знаходитиметься за адресою x^.next, стає останнім, тобто в нього записується значення: read(x^.data); . Використати підпрограму create_list для створення списку можна, організувавши цикл: new(a); {визначення адреси «голови» списку} x:=a; {копіювання адреси «голови» списку у змінну х для подальшої роботи з нею} write(’Input data:’); {введення значення першого елементу списку} readln(x^.data); for i:=1 to n-1 do{введення решти елементів списку за допомогою передавання} create_list(x); {у підпрограму створення поточної адреси останнього елемента списку} x^.next:=nil; {визначення для останнього елемента ознаки кінця списку } Порівняємо два наведених способи створення списку. Перший ― рекурсивна функція ― створює список, використовуючи стекову пам’ять. Другий ― підпрограма-процедура ― дописує у кінець списку новий елемент, що задається користувачем. Позитиви та недоліки кожного з таких підходів такі: § функція вимагає використання додаткової стекової пам’яті, але може створювати порожній список, якщо n=0; § процедура не вимагає додаткової стекової пам’яті, але передбачає на початку введення хоча б одного елемента списку. Кожний з цих варіантів має право на існування. Розглянемо підпрограму перегляду елементів створеного списку:
Цикл while x <>nil do дозволяє «пробігти» всі елементи списку, які вже в ньому є. Цей перебіг елементами списку досягається виконанням у циклі оператора x:=x^.next. Тобто у змінну x, що має містити адресу розміщення у пам’яті наступного елемента списку, пересилається адреса, записана у полі next даного елемента списку, що як раз і вказує на нього. Завершується цикл тоді, коли значенням x стає nil, тобто поточний елемент списку є кінцевим. Для захисту попередньої та всіх наступних підпрограм, які працюють зі списком, варто передбачити перевірку наявності у списку елементів. Для цього можна додати в основну програму оператор if а=nil then writeln(’Список порожній. Дії з ним неможливі’); Розглянемо підпрограму читання або вилучення елемента зі списку. Може бути декілька варіантів читання елемента списку: читаємо вказаний елемент або читаємо елемент, що розміщений після вказаного. Перш за все у будь-якому з цих варіантів спочатку необхідно пробігти списком до заданого елемента. Подібний цикл вже використовувався.
Запишемо підпрограму читання елемента списку, що знаходиться після заданого елемента зі значенням l:
Для читання самого елемента зі значенням l необхідно спочатку переглянути список для його знаходження. В попередній наведеній підпрограмі зупинялись саме на цьому елементі, але вилучали наступний. Як вилучити той елемент, на якому зупинилися? На місце поточного елемента скопіюємо всю інформацію про наступний елемент: його значення і значення покажчика на елемент, що слідує за ним. Розглянемо реалізацію запропонованого алгоритму:
Має право на існування ще одна версія алгоритму читання зі списку заданого елемента. Вона побудована на попередній процедурі читання наступного за заданим елементом delete_after. Її смисл полягає у тому, що при перегляді списку будемо дивитись не на поточний елемент, а на той, що слідує за ним: while x^.next^.data<>l do x:=x^.next; Зрозуміло, що зупинимось в списку на елементі, який передує шуканому. Тепер процедура delete_after вилучить зі списку саме той елемент, що нам потрібен. Розглянемо різноманітні операції запису або вставлення елементів у список. Першою розглянемо операцію запису у список елемента зі значенням l після елемента зі значенням k.
Прокоментуємо послідовність виконання операцій при записові нового елемента l після заданого елемента k. Першим кроком необхідно визначити адресу х елемента k. Другим ― визначення адреси q для розміщення в пам’яті нового елемента l. Третім ― копіювання в поле next нового елемента значення покажчика, що записане в полі next за адресою х. Четвертим ― запис значення l в поле data за адресою q. П’ятим ― запис в поле next за адресою х значення адреси q. Запишемо текст процедури, що виконує ці операції:
Запис нового елемента l перед заданим елементом k виконується такою послідовністю дій. Спочатку знайдемо шуканий елемент k у списку. Потім визначимо у пам’яті адресу q для нового елемента списку. Оскільки «бачимо» лише наступний, а не попередній, елемент списку, то можна вдатися до таких хитрощів. Відомо, що в результаті запису за попереднім елементом повинен іти новий елемент, а потім елемент зі значенням k. Тому на місце нового елемента перепишемо значення елемента k та значення покажчика на наступний за ним елемент, а на звільнене місце ― значення нового елемента l та в його поле next значення адреси q. Наведемо текст підпрограми, що виконує описані операції:
Вище розглянуто односпрямований список, тобто список, кожний елемент якого має покажчик лише на наступний елемент. Існує і двоспрямований список, тобто такий, кожний елемент якого має два покажчики: на наступний і попередній елементи списку. Список може бути і кільцевим. Для односпрямованого кільцевого списку останній елемент має покажчик на перший або перший елемент ― на останній. Для двоспрямованого списку обидві властивості присутні одночасно. Тепер щодо доступу до елементів структури даних «список» можна зробити логічний висновок: це структура послідовного доступу, оскільки дістатися будь-якого елементу списку не можна інакше, ніж переглянувши усі елементи, що йому передують, починаючи із самого першого, тобто з голови списку. Однак ця структура значно відрізняється від попередніх ― масиву, стека, черги, оскільки дає можливість читання та запису елементів у будь-яке місце заданої послідовності.
Читайте також:
|
|||||||||||||||||||||||||||||
|