asyan.org
добавить свой файл
1
Лабораторна робота №4

Тема: «Зв’язний список»

Мета: Ознайомитися з основами роботи зв’язного списку.
Теоретичні відомості

Інколи виникає потреба у доступі до елементів структури, які не є останніми, як це було у стеці та черзі. Така структура існує, і називається вона зв’язним списком.

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

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

Зв’язний список (linked list) — це структура даних, у якій об’єкти розташовані у лінійному порядку. Однак, на відміну від масиву, у якому цей порядок визначається індексами, порядок у зв’язному списку визначається вказівниками на кожен об’єкт.

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

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

Кожний елемент зв’язного списку є окремим об’єктом (або структурою), що містить поля для зберігання інформації та вказівник на наступний елемент списку. (Якщо список є двозв’язним, то в такому об’єкті зберігається також вказівник на попередній елемент.)

Схематично одно- та двозв’язний список можна представити наступним чином.

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

Види зв’язних списків


Існує декілька можливих типів зв’язних списків. Найбільш поширені з них розглядаються у цьому розділі.

Однозв’язний список

http://upload.wikimedia.org/wikipedia/commons/thumb/9/9c/single_linked_list.png/400px-single_linked_list.png

В однозв’язному списку можна пересуватися лише у напрямку від першого до останнього вузла. При цьому довідатися адресу попереднього елемента неможливо.

Двозв’язний список

http://upload.wikimedia.org/wikipedia/commons/thumb/c/ca/doubly_linked_list.png/400px-doubly_linked_list.png

По двозв’язному списку можна пересуватися в будь-якому напрямку — як від першого елементу у напрямку останнього, так і у зворотному напрямку. У цьому списку простіше робити видалення та перестановку елементів, оскільки завжди відомі адреси попереднього та наступного елементів списку.

Кільцевий зв’язний список


Різновидом зв’язних списків є кільцевий (або циклічний, замкнутий) список. Він теж може бути одно- або двозв’язним. Останній елемент кільцевого списку містить покажчик на перший елемент, а перший (для двозв’язного списку) — на останній.

односвязный кольцевой список

Розглянуті у попередніх двох розділах стек і черга є лінійними списками, множина допустимих операцій над якими обмежена операціями над першим або останнім елементом. У даному розділі обговорюватимуться списки, над якими припустимі довільні дії. Найбільш ефективно у списковых структурах реалізуються операції вставки та видалення елементів, оскільки вони, на відміну від операцій видалення та вставки елементів масиву, не потребують зсуву групи елементів. Наведемо всі можливі варіанти застосування цих двох операцій:

  • створення списку, тобто внесення першого елемента до списку;

  • додавання елемента в кінець списку;

  • додавання елемента на початої: списку;

  • вставка елемента в середину списку;

  • видалення елемента з початку списку;

  • видалення елемента з кінця списку;

  • видалення елемента з середини списку.

У загальному випадку для роботи з однозв'язним лінійним списком потрібні такі покажчики: покажчик head на початок списку; покажчик current на поточний елемент списку; покажчик previous на елемент, розташований перед поточним; покажчик newptr на елемент, що додається до списку, та покажчик last на кінець списку. Зауважимо, що у розв'язаннях конкретних задач можуть використовуватися не всі такі покажчики.

Отже, розглянемо алгоритми основних операцій над однозв'язним лінійним списком. Додавання елемента в кінець списку виконується за алгоритмом додавання елемента до черги, а додавання елемента на початок списку - за алгоритмом додавання елемента до стеку. Ці операції вже розглядалися в двох попередніх розділах.

Так само вже розглядалася і операція видалення елемента з початку списку, що здійснюється за алгоритмом видалення елемента зі стеку або з черги. Запишемо алгоритми решти операцій, припускаючи, що при додаванні елемента для нього вже була створена динамічна змінна newptr^ та було введене значення у його поле data.

Алгоритм створення одноелементного списку

  1. Ініціалізувати початок списку: head:=newptr.

  2. Ініціалізувати кінець списку: last:=newptr.

  3. Записати ознаку того, що перший елемент є останнім: head^.next:=nil.

Алгоритм вставки елемента всередину списку

Вважаємо, що новий елемент має бути вставлений між елементами previous^ і current^ (рис.).




  1. Новий елемент вважати наступним для previous^: previous^.next:= newptr.

  2. Елемент current^ вважати наступним для нового елемента: newptr^. next: = current.


Рис. 1 Вставка елемента зсередини списку.

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

Вважаємо, що видаляється елемент current^ , розташований безпосередньо за елементом previous^ (рис. 2).

  1. Вважати, що за елементом previous^ буде розташований той елемент, що раніше знаходився за елементом current^: previous^.next:=current^.next;


previous.next :-current.next
Звільнити пам'ять із-під елемента current^: Dispose (current);
Рис. 2. Видалення елемента з середини списку

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

Вважаємо, що на передостанній елемент посилається покажчик previous.

  1. Записати до передостаннього елемента ознаку кінця списку: previ ous^. next := nil.

  2. Звільнити пам'ять із-під колишнього останнього елемента: Dispose (last).

  3. Вважати останнім колишній передостанній елемент: last:=previous.


Хід роботи

  1. Завантажити середовище програмування. Створити новий файл та зберегти його з назвою spisok_буква вашого классу.pas.

  2. Виконати завдання. Словесний алгоритм та программу записати до зошита. За допомогою коментарів проаналізувати програму. Вивчити призначення процедур, що реалізовують розв’язування задач.

  3. У зошиті окремо оформіть :

Процедуру створення списку;

Процедуру вставки елементу на початок списку;

Процедуру вставки в середину списку;

Процедура виведення списку;

Процедура видалення елемента з середини списку;

Процедуру видалення першого елементу з списку.

4*.Наберіть програму та зафіксуйте у зошиті результати роботи програми.

  1. Дати відповіді на контрольні запитання.


Завдання:

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

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

  1. Вважати список порожнім.

  2. Вивести меню для роботи зі списком.

  3. Якщо натиснута клавіша І, додати елемент до списку.

  1. Виділити пам'ять для нового елемента.

  2. Ввести нове слово та ініціалізувати ним поле даних нового елемента.

  3. Якщо список порожній, вважати щойно утворений елемент списком.

  4. Якщо список непорожній, визначити місце розташування нового елемента та вставити його до списку.

4. Якщо натиснута клавіша й, видалити елемент зі списку.

  1. Ввести слово, що видаляється.

  2. Якщо список порожній, вивести відповідне повідомлення.

  1. Якщо список непорожній, проглядати значення елементів списку доти, доки введене слово не буде знайдено або доки список не буде вичерпано.

  2. Якщо елемент із введеним значенням поля даних було знайдено, то його слід видалити.

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

5. Якщо натиснута клавіша 2, вийти з програми.

Програма ех_4 реалізує розглянутий алгоритм. Крім процедур вставки та видалення елементів, на увагу в цій програмі заслуговують функція SearchPlaseDelete, що виконує пошук введеного слова у списку, та процедура SearchPlaseInsert, яка відшукує позицію для вставки нового елемента. В обох цих підпрограмах здійснюється послідовний перебір елементів списку, під час якого шляхом циклічного виконання присвоєння сuггеnt:= сuггеnt^.next змінюється значення покажчика сuггеnt. Оскільки елемент, на який посилається покажчик ргеvіоus, має бути попереднім для елемента, що на нього посилається сuггеnt, то перш ніж змінна сuггеnt ; набуде нового значення, її старе значення має бути збережене у змінній ргеvіоus.

Program ex_4;

Uses CRT;

tуре

ptr=^Item; {тип покажчика на елемент}

Item=гесогd {тип елемента списку }

Data: string; {інформаційне поле }

Next:ptr;{покажчик на наступний елемент }

End;

var

head: ptr; {покажчик на початок списку }

newptr. {покажчик на елемент, що вводиться}

current, {покажчик на поточний елемент}

previous: ptr; {покажчик на попередній елемент}

ch: char; {код дії над елементом списку}

str: string; {значення елемента, що вводиться}

flag: Boolean;{ознака успішності пошуку}











Контрольні запитання

  1. Дайте означення поняттю зв’язний список.

  2. Які види зв’язних списків ви знаєте.

  3. Чим відрізняється принцип дії зв’язного списку від принципу роботи з елементами черги та стеку.

  4. Поясніть, що таке покажчик.

  5. Запишіть, яким чином описується список.

  6. Запишіть процедуру створення списку.

  7. Запишіть процедури вставки елементів у список (першим та всередину). В чому їх різниця?

  8. Запишіть процедури видалення елементів з списку (першим та всередину). В чому їх різниця?

  9. Поясніть потребу у процедурах пошуку в програмі, розглянутої у лабораторній роботі