Лабораторна робота №4 Робота з лінійним однозв’язковим списком, Контент-платформа
Лабораторна робота №4
Як зазначалося, черга і стек є окремими випадками загального поняття " лінійний список " .
Лінійний однозв'язковий список може бути двох різновидів:
1) прямий лінійний однозв'язковий список;
2) зворотний лінійний список.
Чергає окремим випадком прямого лінійного однозв'язкового списку. У зворотному списку зв'язок встановлюється від i-го до (i-l)-мy елементу.
Стекє окремим випадком зворотного лінійного однозв'язкового списку. Неважко помітити, що поділ на прямий та зворотний список є умовним і залежить від того, яку сторону списку вважати початком, а яку – кінцем.
Для роботи з лінійним однозв'язковим списком потрібні такі покажчики:
1) покажчик на початок списку (візьмемо ідентифікатор BegL);
2) покажчик на кінець списку (візьмемо ідентифікатор EndL);
3) покажчик на k-й елемент списку, де будуть проводитися дії: після якого (або перед яким) буде вставлений елемент або який слід видалити (візьмемо ідентифікатор Рk);
4) тимчасовий покажчик для виділення пам'яті під елементи, що додаються, і для звільнення пам'яті елементів, що видаляються (візьмемо ідентифікатор Р).
Розглянемо основні операції над лінійними списками.
1. Створеннялінійниходнозв'язковихсписків
Створення (тобто внесення першого елемента) лінійного однозв'язкового списку виконується так само, як і створення черги. Причому це стосується як прямого, і зворотного лінійного однозв'язкового списку, незважаючи на те, що зворотний лінійний однозв'язковий список є узагальненим випадком стека, ане черги. Так виходить саме через те, що зворотний лінійний однозв'язний список - це узагальнений вид стека, у якого є початок і кінець, як у черги, а не тільки вершина, як у стека.
Додавання елемента до кінця прямого списку виконується аналогічно додавання елемента до кінця черги, а додавання елемента до кінця зворотного списку виконується аналогічно додавання елемента до вершини стека.
Схема додавання для прямого лінійного списку буде наступною:
Додавання елемента до початку прямого списку виконується аналогічно додавання елемента до вершини стека, а додавання елемента до початку зворотного списку виконується аналогічно додавання елемента до кінця черги.
Схема додавання елемента для прямого лінійного списку буде наступною:
4. Обмін місцями значень інформаційних полів k-го та нового елементів та перестановка покажчика Pk на новий елемент.
Змінна Tmp повинна мати такий самий тип,як і інформаційне поле елемента списку Inf.
Видалення елемента з початку прямого списку виконується аналогічно видалення елемента з черги та стека (звернемо увагу, що видалення елемента з черги і стека виконується, по суті, однаково).
Видалення елемента з початку зворотного списку (або кінця прямого списку) немає аналога серед дій з чергою і стеком (це буде розглянуто в наступному підзаголовку).
Схема видалення елемента з початку прямого списку буде наступною:
3. Перестановка покажчика початку списку BegL на наступний елемент, використовуючизначення поля Link, яке зберігається у першому елементі. Після цього звільняється пам'ять початкового елемента списку, використовуючи додатковий покажчик Р:
Видалення елемента з кінця прямого списку не має аналогів серед дій з чергою та стеком, а видалення елемента з кінця зворотного списку виконується аналогічно видаленню з черги або стека, як показано вище.
Схема видалення елемента з кінця прямого списку буде такою:
Відповідна схема має такий вигляд:
Тому, щоб виконати необхідну дію, необхідно відрахувати елементи k від голови списку, послідовно пересуваючи допоміжний покажчик від елемента до елемента.
В результаті отримуємо:
Отже, у найпростішому випадку цикл установки покажчика на заданий k-й елемент матиме такий вигляд:
Однак, цей цикл не враховує випадку, якщо в списку знаходиться менше елементів, ніж задане k. Тобто використовувати його можна тоді й тільки тоді, коли гарантовано відомо, що у списку є не менше елементів. Якщо ж брати загальний випадок, то необхідно в рамках циклу додатково перевіряти, чи ми не досягли кінця списку.
11. Установкавказівниканапередостаннійелементпрямого однозв'язногосписку
Нагадаємо, що виконання такої дії необхідне видалення останнього елемента прямого однозв'язкового списку.
Хоча передостанній елемент прямого однозв'язкового списку знаходиться поруч із хвостом списку, проте щоб встановити на нього покажчик доводиться йти не від кінця, а від початку списку, оскількизв'язки між елементами спрямовані в один бік.
Пересування по списку виконується так, як було розглянуто вище. Відмінність полягає лише в умови закінчення пошуку. Варіантів такої умови може бути два.
Можна порівняти або з вказівником EndL, або зі значенням nil, яке також фіксує кінець списку.
Хоча використання покажчика P^.Link^.Link трохи складніше для розуміння, проте й більш універсально, оскільки працює навіть у разі, якби ми не мали покажчика кінця списку EndL.
12. Друкелементіводнозв'язногоспискувідпочаткудокінцю
Такий варіант виведення на друк елементів списку виконується аналогічно до описаної вище установки покажчика на передостанній елемент з двома відмінностями:
1) пересування робочого покажчика провадиться до останнього елемента;
13. Друкелементіводнозв'язногоспискувідкінцядопочатку
Очевидно, що виведення на друк елементів списку від кінця до початку не можна виконати так само просто, як у попередньому випадку, оскільки зв'язки спрямовані тільки в один бік і неможливо просуватися ними протилежну. У цьому випадку потрібно використовувати ще один додатковий список (але зі зворотними зв'язками!) для тимчасового зберігання елементів вихідного списку, або використовувати рекурсію.
Розглянемо рішення за допомогою рекурсії. Оскільки ми використовуємо рекурсію, дії повинні бути оформлені у вигляді процедури.
1. З якого тексту читаються по черзі всі слова та підраховується частота їх появи, тобто складається частотний словник. Для цього потрібно скласти список слів,знайдених у тексті. Кожне чергове слово шукається у списку. Якщо слово знайдено, лічильник його частоти збільшується, інакше слово додається до списку. Для простоти вважатимемо, що слова виділені з тексту, закодовані цілими позитивними числами та знаходяться у вхідному файлі.
3. Дано лінійний односпрямований список, в інформаційних полях якого розташовані цілі числа. Видалити з цього списку всі елементи, що мають парні значення таких полів, зібравши їх в окремому лінійному списку.