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

Стек – це такий лінійний список, який має одну точку доступу: з однієї сторони дані додаються і з тієї ж сторони дані вилучаються. Стек організований за принципом LIFO (L ast I n F irst O ut - останній ввійшов – перший вийшов). Черга - це такий лінійний список, який має дві точки доступу: з однієї сторони дані в чергу додаються, а з іншої – вилучаються. Черга організована за принципом FIFO (F irst I n F irst O ut – перший ввійшов – перший вийшов).

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

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

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

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

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

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

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

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

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

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

b = p ® next

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

delete b;

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

typedef struct Stack Data {

int Data;

Stack Data *Next; }

TStack Data, *TStack Data;

typedef class CStack {

PStackData Top;

public: CStack () { Top = 0 };

~CStack ();

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

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

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

void Print (); }

TStack *PStack;

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

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

void main()

{A*p=newA;

A*q=newA;

p=q;

delete q;

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

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

}

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

1. Проблема фрагметації

p=new int[1000]

q=new int[2000]

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

4. Двійкові дерева

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

Двійковим деревом з базовим типом Т називається або порожній набір елементів (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)))

Поиск по сайту: