Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

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

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

Мова 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;

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

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

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

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

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

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

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