Операції включення й виключення елементів списку

Лекція 9-10. Статичні й динамічні типи даних

План

1. Структура даних типу «Вказівник».

2. Статичні та динамічні змінні.

3. Створення та знищення динамічних змінних.

4. Структура даних типу «Лінійний однозв’язний список».

5. Структура даних «Двозв’язний лінійний список».

6. Багатозв’язний список.

1. Вказівний тип займає проміжне положення між скалярними й структурними типами: з одного боку значення вказівного типу є атомарним (неподільним), а з іншого, ці типи визначаються через інші (у тому числі й структурні) типи.

Туре <тип вказівника> = ^ <тип об'єкту, що вказується>

(цей тип дозволяє використати базовий тип перед описом)

Type PtrТуре = ^BaseТуре;

BaseТуре = record

х, у: rеаl;

end;

Var А: PtrТуре; {А-змінна статичного типу, значенням якої є адреси розташування в пам’яті конкретних значень заданого типу}

В: BaseТуре;

С:^PtrТуре;

Змінній А можна присвоїти адресу якоїсь змінної, для чого використаємо унарну операцію взяття вказівника: А = @ В.

На фізичному рівні вказівник займає два слоти: у першому слоті перебуває адреса сегмента, у другому – адреса зсуву.

Операції над вказівним типом:

1) операція порівняння на рівність: = (рівність, якщо співпадають адреси сегмента й зсуву);

2) операція порівняння на нерівність: < >;

3) операція доступу: В.Х = В.Х + С.

Серед всіх можливих вказівників виділяється один спеціальний вказівник, що не вказує. Тобто у пам'яті виділяється одна адреса, у яку не записується жодна змінна. На це місце в пам'яті й посилається такий порожній або "нульовий" вказівник, що позначається nil на мові Паскаль або NULL на мові С. Вказівник nil вважається константою, сумісною з будь-яким вказівним типом, тобто це значення можна присвоювати будь-якому вказівному типу.

2. Дотепер ми розглядали змінні, які розміщаються в пам'яті відповідно до цілком певних правил, а саме, для локальних змінних, описаних у підпрограмах, пам'ять виділяється при виклику підпрограми; при виході з неї ця пам'ять звільняється, а самі змінні припиняють існування. Глобальним змінним програми пам'ять виділяється на початку її виконання; ці змінні існують протягом усього періоду роботи програми. Іншими словами, розподіл пам'яті у всіх цих випадках відбувається повністю автоматично. Змінні, пам'ять під які розподіляється подібним чином, називаються статичними.

Змінні, створенням і знищенням яких може управляти програміст, називаються динамічними змінними. Вони можуть перебувати в будь-якій частині динамічної пам'яті, і звертання до них може здійснюватися тільки через вказівник. Засобами доступу до статичних змінних є ідентифікатори цих змінних. Динамічні змінні, кількість яких і місце розташування в пам'яті заздалегідь не відомо, неможливо позначити ідентифікаторами. Тому єдиним засобом доступу до динамічних змінних є вказівник на місце їхнього поточного розташування в пам'яті.

Розглянемо розподіл пам'яті (рис. 5.1).

Під локальні змінні виділяється спеціальний сегмент оперативної пам'яті (сегмент стека). Утворення динамічних змінних реалізується в іншій області пам'яті, що існує окремо від стекового сегмента й називається купою (heap) або динамічною областю пам'яті.

Рис. 5.1. Розподіл памяті для динамічних змінних

3. Основні дії над динамічними змінними – створення та знищення – реалізуються стандартними процедурами New і Dispose (в мові програмування Паскаль).

New (<ім'я посилання>): point; – процедура призначена для створення динамічних змінних певного типу (інакше кажучи, для відведення пам'яті в купі для зберігання значень динамічної змінної).

Dispose (<ім'я посилання>): point; – процедура використовується для звільнення пам'яті, відведеної за допомогою процедури New.

МахAvail: longint; – функція повертає максимальний розмір (у байтах) безперервної вільної ділянки купи. Застосування цієї процедури необхідне для контролю динамічної пам'яті при реалізації операції включення.

Наприклад: if MaxAvail > SizeOf(BaseType) then {генеруємо об'єкт}

Створимо три об'єкти, які розташуються в пам'яті послідовно (без фрагментарності), а потім знищимо другий об'єкт. У результаті виникне фрагментарність, якої треба уникати.

MemAvail: longint; — функція повертає загальну кількість вільної пам'яті. Щоб перевірити, є чи фрагментарність, треба порівняти результати застосування функцій MemAvail та MaxAvail – вони повинні збігатися.

4. Усі вищерозглянуті структури, що реалізувалися як відображення на масив, мають певні недоліки, тобто вони малоефективні при розв'язуванні деяких задач. До таких недоліків можна віднести наступне.

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

2. Якщо ми розглядаємо якусь послідовність елементів у послідовній пам'яті x₁, x₂, …, x_n і необхідно включити який-небудь новий елемент x у цю послідовність, то ми повинні здійснити масову операцію зсуву всіх елементів, що перебувають за тим елементом послідовності, після якого ми хочемо включити новий елемент. Після цього вставимо цей новий елемент х на місце, що звільнилося. Отже, тут проявляється властивість фізичної суміжності (рис. 5.2).

Рис 5.2. – Додавання нового елемента в список

Позбутися фізичної суміжності можна, якщо елементи будуть мати не тільки дані, але й вказівники. У цьому випадку елементи можуть бути хаотично розкидані по оперативній пам'яті, а логічна послідовність буде забезпечуватися одним або декількома вказівниками.

Розглянемо кожен із класів зв'язних списків детальніше

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

Найпростішим зв'язним списком є лінійний однозв'язний список. Кожний елемент у цьому списку складається з різних за призначенням полів: змістовного й поля-вказівника. У типі-вказівнику перебуває адреса наступного елемента. Поле останнього вказівника має вказівку на кінець списку – ознака nil (NULL).

Операції, що визначають структуру типу «лінійний однозв'язннй список»:

- ініціалізація;

- включити елемент як робочий вказівник списку;

- виключити елемент, що перебуває за робочим вказівником списку;

- пересунути робочий вказівник на один крок;

- перевірка: список порожній / список не порожній;

- помістити робочий вказівник у початок списку (похідна операція);

- помістити робочий вказівник у кінець списку (похідна операція);

- зробити список порожнім.

При ініціалізації списку ефективно використати реалізацію такої структури:

Реалізацію списку можна здійснити за допомогою відображення на масив.

Операції включення й виключення елементів списку

Розглянемо операції включення й виключення елементів у загальному випадку. Введемо наступні позначення полів:

Data – поле, куди записуються дані;

Link – поле, де перебуває вказівник на наступний елемент списку;

Start – вказівник на початок списку;

Free – вказівник, який вказує на перший елемент вільного (робочого) списку.

Для реалізації необхідно мати функціональний список, у якому перебуває поле даних, а також вільний список, що є джерелом даних для функціонального. Поле Data у вільному списку не має змістовної інформації. Data (Ptr) вказує на поле Data того елемента, на який указує Prt. Link(Prt) – вказівник того елемента, на який указує Prt.

Операції включення й виключення від розмірності списку не залежать.

Включення елемента в список:

Pntr = Free;

Free – Link(Pntr);

Data(Pntr) = { };

Link(Pntr) - Link(Ptr) {формуємо вказівник у новому елементі};

Link(Pntr) = Pntr {модифікація вказівника}.