Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник






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

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

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

Мова Pascal Мова С++
type list= ^tlist; tlist= record data: <тип>; next:list; end; struct tlist { public <тип> data; tlist* next; };

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

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

Розглянемо рекурсивну функцію, яка за відомим значенням n заповнює список, таким чином створюючи його:

Мова Pascal
function create_list(n: integer): list; var q: list; x: integer; begin if n=0 then q:=nil else begin writeln(’Input data:’); read(x); new(q); with q^ do begin data:=x; next:=create_list(n-1); end; end; create_list:=q; end;

Звернення до функції створення списку в основній програмі може бути таким: a:=create_list(n).

Ще одним варіантом створення списку може бути використання такої підпрограми:

Мова Pascal
procedure create_list(var x: list); begin new(x^.next); x:=x^.next; write(’Input data:’); readln(x^.data); end;

Послідовність дій виглядає так.

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;

§ процедура не вимагає додаткової стекової пам’яті, але передбачає на початку введення хоча б одного елемента списку.

Кожний з цих варіантів має право на існування.

Розглянемо підпрограму перегляду елементів створеного списку:

Мова Pascal
procedure show(x: list); begin while x<>nil do begin write(x^.data,’ ’); x:=x^.next end end;

Цикл while x <>nil do дозволяє «пробігти» всі елементи списку, які вже в ньому є. Цей перебіг елементами списку досягається виконанням у циклі оператора x:=x^.next. Тобто у змінну x, що має містити адресу розміщення у пам’яті наступного елемента списку, пересилається адреса, записана у полі next даного елемента списку, що як раз і вказує на нього. Завершується цикл тоді, коли значенням x стає nil, тобто поточний елемент списку є кінцевим.

Для захисту попередньої та всіх наступних підпрограм, які працюють зі списком, варто передбачити перевірку наявності у списку елементів. Для цього можна додати в основну програму оператор

if а=nil then writeln(’Список порожній. Дії з ним неможливі’);

Розглянемо підпрограму читання або вилучення елемента зі списку.

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

 

Запишемо підпрограму читання елемента списку, що знаходиться після заданого елемента зі значенням l:

Мова Pascal
procedure delete_after(x: list); var l: integer; begin write(’Delete after what?’); read(l); while x^.data<>l do x:=x^.next; x^.next:=x^.next^.next end;

Для читання самого елемента зі значенням l необхідно спочатку переглянути список для його знаходження. В попередній наведеній підпрограмі зупинялись саме на цьому елементі, але вилучали наступний.

Як вилучити той елемент, на якому зупинилися?

На місце поточного елемента скопіюємо всю інформацію про наступний елемент: його значення і значення покажчика на елемент, що слідує за ним.

Розглянемо реалізацію запропонованого алгоритму:

Мова Pascal
procedure delete(x: list); var l: integer; begin write(’Delete what?’); read(l); while x^.data<>l do x:=x^.next; x^.data:=x^.next^.data; x^.next:=x^.next^.next; end;

 

Має право на існування ще одна версія алгоритму читання зі списку заданого елемента. Вона побудована на попередній процедурі читання наступного за заданим елементом 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. Запишемо текст процедури, що виконує ці операції:

Мова Pascal
procedure insert_after(x: list); var l, k: integer; begin write(’Input what:’); read(l); write(’Input after?’); read(k); while x^.data<>k do x:=x^.next; new(q); q^.next:=x^.next; q^.data:=l; x^.next:=q; end;

Запис нового елемента l перед заданим елементом k виконується такою послідовністю дій. Спочатку знайдемо шуканий елемент k у списку. Потім визначимо у пам’яті адресу q для нового елемента списку. Оскільки «бачимо» лише наступний, а не попередній, елемент списку, то можна вдатися до таких хитрощів. Відомо, що в результаті запису за попереднім елементом повинен іти новий елемент, а потім елемент зі значенням k. Тому на місце нового елемента перепишемо значення елемента k та значення покажчика на наступний за ним елемент, а на звільнене місце ― значення нового елемента l та в його поле next значення адреси q.

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

Мова Pascal
procedure insert_previous(x: list); var l, k: integer; begin write(’Input what:’); read(l); write(’Input previous?’); read(k); while x^.data<>k do x:=x^.next; new(q); q^:=x^; x^.data:=l; x^.next:=q; end;

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

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

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

 


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

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




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

<== попередня сторінка | наступна сторінка ==>
Лекція №3 | Лекція. СУТЬ І ФУНКЦІЇ НЕВЕРБАЛЬНОГО МАНІПУЛЮВАННЯ

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.002 сек.