Типовими представниками лінійних списків є стеки і черги.

Стек – це такий лінійний список, який має одну точку доступу: з однієї сторони дані додаються і з тієї ж сторони дані вилучаються. Стек організований за принципом LIFO (Last In First Out - останній ввійшов – перший вийшов). Черга - це такий лінійний список, який має дві точки доступу: з однієї сторони дані в чергу додаються, а з іншої – вилучаються. Черга організована за принципом FIFO (First In First Out – перший ввійшов – перший вийшов).

Head – точка видалення, Tail – точка додавання.

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

2 Основні операції над списками – це вставка, вилучення, сортування елементів. Незалежно від способу реалізації такі операції повинні виконуватися коректно, а саме:

• зберігати загальну структуру зв’язаної організації списку ;

• не призводити до утворення „сміття” та висячих посилань;

• зберігати відношення порядку у списку.

Сміття – об’єкти, з якими втрачені зв’язки.

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

Вилучити наступний елемент після елементу з вказівником р

p  next = p  next  next - некоректно

b = p  next

p  next = b  next - коректно

delete b;

Операції із стеками (приклад класу, який буде містити вказівник на вершину стеку)

t ypedef struct StackData

{int Data;

StackData *Next; }

TStackData, *PStackData;

typedef class CStack

{ private: PStackData Top;

public: CStack() { Top = 0; };

~CStack();

void Push (int); // ставить

int Pop(); // забирає

int Count(); // рахує, скільки елементів

void Print(); }

TStack, *PStack;

3. Проблеми при роботі з динамічною пам’яттю

A ) Проблема сміття (збір сміття - garbage collection)

v

q

oid main()

{A*p=new A;

A*q=new A;

p=q; delete q;

if (q==0) {……..}

delete p; } //програма зависає

2. Проблема висячих посилань (вказівник р показує на адресу, яка нічого не містить).

2. Проблема фрагметації p=new int[1000]; q=new int[2000];

В такому випадку треба або використовувати програми-дефрагментатори або перевантаження ОС чи самої програми.

4. Двійкові (бінарні) дерева + НАБОРИ (див. лаб роб 10, п.3)

Деревом називається сукупність взаємопов’язаних елементів, один з яких називається коренем (вершиною дерева), інші елементи утворюють піддерева. Кожен елемент дерева містить певні корисні дані та вказівники на корені (вершини) піддерев. Найчастіше використовуються бінарні дерева, де кожен корінь містить два вказівники: на ліве і праве піддерево

Двійковим деревом з базовим типом Т називається або порожній набір елементів (1) або t типу T (2), якому підпорядковується ліве і праве піддерева Root - корінь

1. 

2. t  T

Способи обходу елементів дерева.

1. Прямий – Root, L, R.

2. Обернений – L, R, Root

3. Змішаний – L, Root, R

4. Д одатковий прямий – Root, R, L

5. Додатковий обернений – R, L, Root

6. Додатковий змішаний – R, Root, L.

Приклад. Синтаксичний аналіз виразу

( a + b * c ) / ( d – e / f )

Для 3 способу – отримаємо інфіксну форму. Беремо а, його L = R = 0, тому роздруковуємо a + b * c / d – e / f (infix)

Д ля 2 способу – отримаємо постфіксну форму a b c * + d e f / - /

( дві букви (операнди) – одна дія ).

Д ля способу 1 – отримаємо префіксну форму / + a * b c – d / e f

Більшість дерев є впорядковані. Часто дерева впорядковуються за таким принципом:

T = (L, Root, R) – кожен елемент L має бути менший, ніж корінь, а елемент R – більший, ніж корінь ( t  L, t < Root;  t  R, t > Root )

Приклад.

Р оздрукуємо це дерево за способом 3.

Отримаємо 7 8 10 11 12 15 18 20 30

За способом 6 30 20 18 15 12 11 10 8 7

Дужковий вираз для роздрукування дерева Root (L, R)

15 (10 (7 (null, 8 (null, null)), 12 (11 (null, null), null)),

20 (18 (null, null), 30 (null, null)))

(програмні приклади до лаб. роб. 10, пп.2,3)