• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Зв’язним списком називається структура даних, кожний елемент якої зв’язаний з наступним (або попереднім, або з обома сусідніми) елементом за допомогою покажчиків.

Кожний елемент списку представлений значенням та покажчиком на наступний елемент, який представлений значенням та покажчиком на наступний для нього елемент і т.д. Тобто, явним чином проглядається рекурсивний опис цієї структури: будь-який наступний елемент є таким, як і той, що на нього посилається. Специфічними є лише початок і кінець списку. Початком списку є покажчик на його перший елемент, а кінцем ― покажчик в «нікуди».

Опис структури «список»:

Перш ніж організовувати роботу з елементами списку його необхідно створити.

Створення списку ― це запис початкової послідовності елементів. Може існувати декілька способів створення списку. Основна ідея полягає у тому, щоб кожного разу дописувати у кінець поточного списку новий елемент.

Розглянемо рекурсивну функцію, яка за відомим значенням 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.

Наведемо текст підпрограми, що виконує описані операції:

Вище розглянуто односпрямований список, тобто список, кожний елемент якого має покажчик лише на наступний елемент. Існує і двоспрямований список, тобто такий, кожний елемент якого має два покажчики: на наступний і попередній елементи списку. Список може бути і кільцевим.

Для односпрямованого кільцевого списку останній елемент має покажчик на перший або перший елемент ― на останній. Для двоспрямованого списку обидві властивості присутні одночасно.

Тепер щодо доступу до елементів структури даних «список» можна зробити логічний висновок: це структура послідовного доступу, оскільки дістатися будь-якого елементу списку не можна інакше, ніж переглянувши усі елементи, що йому передують, починаючи із самого першого, тобто з голови списку. Однак ця структура значно відрізняється від попередніх ― масиву, стека, черги, оскільки дає можливість читання та запису елементів у будь-яке місце заданої послідовності.

Читайте також:

1. II. За зміною ступенів окиснення елементів, які входять до складу реагуючих речовин
2. III. Географічна структура світового ринку позичкового капіталу
3. VІ. План та організаційна структура заняття
4. Адвокатура — неодмінний складовий елемент механізму забезпечення прав людини.
5. Адміністративне правопорушення як підстава юридичної відповідальності: ознаки і елементи.
6. Адміністративно – територіальний устрій і соціальна структура Слобожанщини у половині XVII – кінці XVIII століття
7. Азот, фосфор, біогенні елементи та їх сполуки, органічні речовини
8. Акти з охорони праці, що діють в організації, їх склад і структура.
9. Але відмінні від значення функції в точці або значення не існує, то точка називається точкою усувного розриву функції .
10. Аналіз витрат на підприємстві за їх елементами та статтями калькуляції.
11. Аналіз економічноїї політики за допомогою моделі Мандела-Флемінга. Випадки вільного та фіксованого валютного курсів.
12. Аналіз службового призначення деталей та конструктивних елементів обладнання харчових виробництві, визначення технічних вимог і норм точності при їх виготовленні

Переглядів: 1075