Лабораторна робота № 13
(модуль 2)
Тема: Списки. Лінійні списки. Стек. Черга. (4 години)
Мета: Ознайомити з поняттям списку. Формувати вміння і навички обробки лінійних списків засобами мови програмування Pascal. Ознайомити з поняттями стеку та черги. Формувати вміння і навички роботи з елементами стеку та черги засобами мови програмування Pascal.
Література:
Архангельский А.Я. Язык Pascal и основы программирования в Delphi
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с.
Культин Н.Б. Turbo Pascal в задачах и примерах
М.С.Львов, О.В. Співаковський. Основи алгоритмізації та програмування.
Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0
Меженный О.А. Turbo Pascal
Н.Вирт. Алгоритмы + структуры данных = программы. Москва, Мир, 1985 г. 406 с.
Н.Вирт. Алгоритмы и структуры данных. Москва, Мир, 1989 г. 420 с.
Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. программирование на языке Object Pascal
Окулов С.М. Основы программирования.– М.: ЮНИМЕДИАСТАЙЛ, 2002.– 424 с.
Павловская Т.А. Паскаль. Программирование на языке высокого уровня
Пильщиков В.Н. Сборник упражнений по языку Паскаль. Москва, Наука, 1989 г., 160 с.
Фаронов В.В. Turbo Pascal 7.0. Начальный курс. – Учебное пособие. – М.: Издательство «ОМД Групп», 2003 г. -616 с.
Фаронов В.В. Turbo Pascal 7.0. Практика программирования
Фаронов В.В. Turbo Pascal 7.0. Учебный курс
Короткі теоретичні відомості.
Список - це такий спосіб представлення послідовності однотипних елементів, при якому вставка і вилучення елемента допускаються в довільному її місці, а доступ до оброблюваного елемента здійснюється послідовним переглядом від початку списку до його кінця.

Розглянемо процедури, що реалізують стандартні засоби роботи зі списками: пошук елемента, вилучення елемента, вставка елемента. Аналогічними засобами користуються і при обробці інших інформаційних структур. Елемент списку описується у такий спосіб:
Type Point = ^ Item;
Item = Record
Data: Integer;
Next: Point
End;
Відзначимо характерну деталь: опис елемента динамічної структури рекурсивний! Таким чином, опис динамічних структур неможливий без явного опису типів елементів цих структур.
місце вставки елемент, що вилучається
First
Nil

Found
Процедура Search здійснює пошук елемента списку з числом x як значенням поля Data і повертає посилання Found на цей елемент. Якщо такий елемент у списку відсутній, Found = Nil.
Procedure Search(var Found, First: Point; x: Integer);
Begin
Found := First;
While (Found <> Nil) and (Found^.Data <> x)
do Found := Found^.Next
End;
Процедура InsList додає елемент у список на місце, що передує Found^ (див. малюнок). Посилання Found установлюється на вставлений елемент.
Procedure InsList(var Found: Point, x:Integer);
Var p: Point;
Begin
New(p);
p^.Data := Found^.data;
Found^.Data := x;
p^.Next := Found^.Next;
Found^.Next := p
End;
Found
First
P
Процедура DelList вилучає зі списку елемент Found^. Посилання Found установлюється на елемент, наступний за вилученим.
Procedure DelList(Found: Point);
Var p: Point;
y: Integer;
Begin
y := Found^.Next^.Data;
p:= Found^.Next;
Found^.Next := Found^.Next^.Next;
Found^.Data := y;
Dispose(p) {звільнення пам’яті}
End;
Found
First
Р
Стек. Черга

Стек - це такий спосіб представлення послідовності однотипних елементів, при якому вставка і вилучення елемента допускаються тільки в її початку - вершині стека. Доступ до інших елементів стека не підтримується методами обробки стека.

Черга - це такий спосіб представлення послідовності однотипних елементів, при якому вставка елемента допускається тільки в її хвості, а вилучення - тільки на початку. Доступ до інших елементів черги не підтримується методами обробки черги.
Черги і стеки - це т.зв. лінійні динамічні структури. Вони являють собою послідовності записів, у кожному з яких, за винятком останнього, покажчик виставлений на наступний. Відрізняються вони один від одного способом обробки. У стеку елементи додають чи вилучають у одному місці – вершині стека. У черзі записи додаються у хвіст, а вилучаються з голови.
Задачі для самостійного розв’язування
Реалізувати процедуру зчеплення (конкатенації) двох списків. Оцінити складність алгоритму за часом у термінах довжин списків.
Реалізувати процедуру сортування списку злиттям. Оцінити складність алгоритму за часом і пам'яттю (у гіршому випадку).
Реалізувати АТД Однозв'язний список, у якому кожен елемент містить поле зв'язку з наступним елементом списку і виконуються операції одержання доступу до k-го вузла списку та додавання нового вузла перед k-м вузлом.
Реалізувати АТД Однозв'язний список, у якому кожен елемент містить поле зв'язку з наступним елементом списку і виконуються операції вилучення k-го вузла та об'єднання 2-х списків в один.
Реалізувати АТД Однозв'язний список, у якому кожен елемент містить поле зв'язку з наступним елементом списку і виконуються операції розбивка списку на 2 списки та створення копії списку.
Реалізувати АТД Двоїв’язний список, у якому кожен елемент містить поле зв'язку з наступним елементом списку і виконуються операції одержання доступу до k-го вузла списку та вилучення k-го вузла.
Реалізувати АТД Двоїв’язний список, у якому кожен елемент містить поле зв'язку з наступним елементом списку і виконуються операції створення копії списку та визначення кількості вузлів у списку.
Реалізувати АТД Двоїв’язний список, у якому кожен елемент містить поле зв'язку з наступним елементом списку і виконуються операції пошук вузла з заданим значенням якогось поля та сортування вузлів списку за значеннями деяких полів.
Реалізувати АТД Однозв'язний список, у якому кожен елемент містить поле зв'язку з наступним елементом списку і виконуються операції пошук вузла з заданим значенням якогось поля та сортування вузлів списку за значеннями деяких полів.
Реалізувати АТД Двоїв’язний список, у якому кожен елемент містить поле зв'язку з наступним елементом списку і виконуються операції створення копії списку та сортування вузлів списку за значеннями деяких полів.
Нехай T - деякий тип. Розглянемо (відсутній у мові Pascal) тип "стек елементів типу T". Його значеннями є послідовності значень типу T. Реалізувати операції:
Зробити_порожнім (var s: стек елементів типу T).
Додати (t: T; var s: стек елементів типу T).
Отримати (var t: T; var s: стек елементів типу T).
Порожній (s: стек елементів типу T): boolean.
Вершина (s: стек елементів типу T): T.
Реалізувати процедури Push і Pop відповідно додавання і вилучення елемента для стека.
Реалізувати процедури Push і Pop відповідно додавання і вилучення елемента для черги.
Будемо розглядати послідовності круглих і квадратних дужок, що відкриваються і і закриваються ( ) [ ]. Серед усіх таких послідовностей виділимо правильні - ті, котрі можуть бути отримані за такими правилами:
порожня послідовність правильна.
якщо А и В правильні, то й АВ правильна.
якщо А правильна, то [A] і (A) правильні.
Приклад. Послідовності (), [[]], [()[]()][] правильні, а послідовності ], )(, (], ([)] - неправильні.
Перевірити правильність послідовності за час, що не перевершує константи, помноженої на її довжину. Передбачається, що члени послідовності закодовані числами:
( 1
[ 2
) -1
] -2
Вказівки до розв’язування. Нехай a[1]..a[n] - послідовність, що перевіряється. Розглянемо стек, елементами якого є круглі і квадратні дужки, що відкриваються (тобто 1 і 2).
Спочатку стек робимо порожнім. Далі переглядаємо члени послідовності зліва праворуч. Зустрівши дужку, що відкривається, (круглу чи квадратну), поміщаємо її в стек. Зустрівши дужку, що закривається, перевіряємо, що вершина в стеці - парна їй дужка; якщо це не так, то можна стверджувати, що послідовність неправильна, якщо дужка парна, то заберемо її (вершину) зі стека. Послідовність правильна, якщо наприкінці стек виявляється порожній.
Реалізувати k стеків з елементами типу T, загальна кількість елементів у яких не перевершує n, з використанням масивів сумарної довжини C*(n+k), витрачаючи на кожну дію зі стеками (крім початкових дій, що роблять всі стеки порожніми) час, обмежений деякою константою.
Указівки до розв’язування. Метод, що застосовується, називається "посилальною реалізацією". Він використовує три масиви:
Зміст: array [1..n] of T;
Наступний: array [1..n] of 0..n;
Вершина: array [1..k] of 0..n.
Масив Зміст будемо зображувати як n комірок з номерами 1..n, кожна з який містить елемент типу T. Масив Наступний зобразимо у виді стрілок, провівши стрілку з і в j, якщо Наступний[і] = j. (Якщо Наступний[і] = 0, стрілку з і не проводимо.) Зміст s-го стека (s з 1..k) зберігається так: вершина дорівнює Зміст[Вершина[s]], інші елементи s-го стека можна знайти, йдучи по стрілках - доти, поки вони не скінчаться. При цьому (s-ий стек порожній) <=><a,p,q,d,s,t,v,w> Вершина[s] = 0.
Стрілочні траєкторії, що виходять з Вершина[1], ..., Вершина[k] (з тих, котрі не рівні 0) не повинні перетинатися. Крім них, нам знадобиться ще одна стрілочна траєкторія, що містить усі комірки, що не використовуються в даний момент . Її початок ми будемо зберігати у змінній Вільна (рівність Вільна = 0 означає, що порожнього місця не залишилося). От приклад:
n=8 | a | p | q | d | s | t | v | w |
k=2 | | | Вільна
Зміст = , Що Випливає = <3,0,6,0,0,2,5,4>
Вершина = <1, 7>, Вільна = 8
Стеки: 1-ий: p t q a (a-вершина); 2-ий: s v (v-вершина).
Значеннями типу "черга елементів типу T" є послідовності значень типу T. Реалізувати операції з чергами:
Зробити_порожньою (var x: черга елементів типу T);
Додати (t: T, var x: черга елементів типу T);
Отримати (var t: T, var x: черга елементів типу T);
Порожня (x: черга елементів типу T): boolean;
Черговий (x: черга елементів типу T): T.
Як спроститься програма, якщо відомо, що в послідовності можуть бути тільки круглі дужки?
Указівки до розв’язування. У цьому випадку від стека залишається лише його довжина, і ми фактично приходимо до такого твердження: послідовність круглих дужок правильна тоді й тільки тоді, коли в будь-якому початковому її відрізку число дужок, що закриваються, не перевершує числа що відкриваються, а для всієї послідовності ці числа рівні.
Реалізувати за допомогою одного масиву два стека, сумарна кількість елементів у яких обмежена довжиною масиву; усі дії зі стеками повинні виконуватися за час, обмежений константою, що не залежить від довжини стеків.
Указівки до розв’язування. Стеки повинні рости з кінців масиву назустріч один одному: перший повинен займати місця
Зміст[1] ... Зміст[Довжина1],
а другий -
Зміст[n] ... Зміст[n - Довжина2 + 1]
(вершини обох стеків записані останніми).
Реалізувати операції з чергою обмеженої довжини так, щоб кількість дій для кожної операції була обмежена константою, що не залежить від довжини черги.
Указівки до розв’язування. Будемо зберігати елементи черги в сусідніх елементах масиву. Тоді черга буде приростати праворуч і убувати ліворуч. Оскільки при цьому вона може дійти до краю, згорнемо масив у коло.
Введемо масив
Зміст: array [0..n-1] of T
і змінні
Перший: 0..n-1,
Довжина : 0..n.
При цьому елементами черги будуть
Зміст [Перший], Зміст [Перший + 1],...,
Зміст [Перший + Довжина - 1],
де додавання виконується по модулю n. (Попередження. Якщо замість цього ввести змінні Перший і Останній, приймаючі значення у відрахуваннях по модулю n, то порожня черга може бути поплутана з чергою з n елементів.)
Придумати спосіб моделювання черги за допомогою двох стеків (фіксованого числа змінних типу T). При цьому відпрацьовування n операцій з чергою (початих, коли черга була порожня) повинно вимагати порядку n дій.
Указівки до розв’язування. Інваріант: стеки, складені кінцями, утворять чергу. (Перелічуючи елементи одного стека всередину і потім елементи другого назовні, ми перелічуємо всі елементи черги від першого до останнього.) Ясно, що додавання зводиться до додавання до одного зі стеків, а перевірка порожнечі - до перевірки порожнечі обох стеків. Якщо ми хочемо отримати елемент, є два випадки. Якщо стек, де знаходиться початок черги, не порожній, то беремо з нього елемент. Якщо він порожній, то попередньо переписуємо в нього всі елементи другого стека, змінюючи порядок (це відбувається саме собою при перекладанні зі стека в стек) і зводимо справу до першого випадку. Хоча число дій на цьому кроці і не обмежено константою, але вимога задачі виконана, тому що кожен елемент черги може брати участь у цьому процесі не більш одного разу.
Надрукувати в порядку зростання перші n натуральних чисел, у розкладання яких на прості множники входять тільки числа 2, 3, 5.
Указівки до розв’язування. Введемо три черги x2, x3, x5, у яких будемо зберігати елементи, що у 2 (3, 5) разів більше надрукованих, але ще не надруковані.
Реалізувати k черг з обмеженою сумарною довжиною n, використовуючи пам'ять порядку n+k, причому кожна операція (крім початкової, що робить усі черги порожніми) повинна вимагати обмеженого константою числа дій.
Указівки до розв’язування. Діємо аналогічно посилальній реалізації стеків: ми пам'ятаємо (для кожної черги) першого, кожен учасник черги пам'ятає наступного за ним (для останнього вважається, що за ним стоїть фіктивний елемент із номером 0). Крім того, ми повинні для кожної черги знати останнього (якщо він є) - інакше не удасться додавати. Як і для стеків, окремо є ланцюг вільних осередків. Помітимо, що для порожньої черги інформація про останній елемент утрачає зміст - але вона і не використовується при додаванні.
Зміст: array [1..n] of T;
Наступний: array [1..n] of 0..n;
Перший: array [1..k] of 0..n;
Останній: array [1..k] of 0..n;
Вільна : 0..n;
Деком називають структуру, що сполучає чергу і стек: класти і забирати елементи можна з обох кінців. Як реалізувати дек обмеженого розміру на базі масиву так, щоб кожна операція вимагала обмеженого числа дій?
(А.Г.Кушниренко.) Маємо дек елементів типу T і кінцеве число змінних типу T і цілого типу. У початковому стані в деку деяке число елементів. Скласти програму, після виконання якої у деку залишилися б ті ж самі елементи, а їх кількість була б в одній з цілих змінних.
Указівки до розв’язування. (1) Елементи дека можна циклічно переставляти, забираючи з одного кінця і поміщаючи в іншій. Після цього, зробивши стільки ж кроків у зворотному напрямку, можна повернути усе на місце. (2) Як зрозуміти, пройшли ми повне коло чи не пройшли? Якби якийсь елемент свідомо був відсутній у деку, то можна було б його вставити і чекати повторної появи. Але таких елементів немає. Замість цього можна для даного n виконати циклічне зрушення на n двічі, вставивши різні елементи, і подивитися, чи з'являться різні елементи через n кроків.
Реалізувати k деків з обмеженою сумарною довжиною n, використовуючи пам'ять порядку n+k, причому кожна операція (крім початкової, що робить усі деки порожніми) повинна вимагати обмеженого константою числа дій.
Указівка до розв’язування. Дек - структура симетрична, тому треба зберігати посилання в обидва боки (уперед та назад). При цьому зручно до кожного дека додати фіктивний елемент, замкнувши його в кільце, і точно таке ж кільце утворити з вільних позицій.
Пріоритетна черга - це черга, у якій важливо не те, хто став останнім (порядок переміщення в ній не грає ролі), а хто головніше. Більш точно, при поміщенні в чергу вказується пріоритет об'єкта, що поміщається, (будемо вважати пріоритети цілими числами), а при отриманні з черги вибирається елемент із найбільшим пріоритетом (чи один з таких елементів). Реалізувати пріоритетну чергу так, щоб поміщення й отримання елемента вимагали логарифмічного числа дій (від розміру черги).
Указівки до розв’язування. Згідно алгоритму сортування деревом (у його остаточному варіанті), будемо розміщати елементи черги в масиві x[1]..x[k], підтримуючи таку властивість: x[і] старше (має більший пріоритет) своїх синів x[2і] і x[2і+1], якщо такі існують - і, отже, всякий елемент старше своїх нащадків. (Відомості про пріоритети також зберігаються в масиві, так що ми маємо справу з масивом пар (елемент, пріоритет).) Вилучення елемента зі збереженням цієї властивості описано в алгоритмі сортування. Треба ще вміти відновлювати властивість після додавання елемента в кінець. Це робиться так:
t:= номер доданого елемента
{інваріант: у дереві будь-який предок пріоритетніше нащадка,
якщо цей нащадок - не t}
while t - не корінь і t старше свого батька do begin
| поміняти t з його батьком
end;
Якщо чергу утворять громадяни, що стоять у вершинах дерева, тобто за кожним стоїть двоє, а перед кожним (крім першого) - один, то зміст цього алгоритму ясний: ставши в кінець, пріоритетний громадянин починає пробиратися до початку, витісняючи тих, хто стоїть перед ним - поки не зустріне більш пріоритетного.
Зауваження. Пріоритетну чергу природно використовувати при моделюванні процесів, що протікають у часі. При цьому елементи черги - це очікувані події, а їхній пріоритет визначається часом, коли вони відбудуться.