Лекція 9. Динамічні структури об’єктів (дсо)

1. Зв’язана організація пам’яті. Асоціативні структури.

Зв’язана організація пам’яті задає множину структур даних, зв’язки між якими організовуються за допомогою вказівників. Кожен елемент такої структури володіє властивістю - „мати зв’язок з іншими елементами” (асоціація). ДСО володіють властивістю мати змінний склад структури, яка дозволяє розглядати ДСО як асоціацію зв’язаних об’єктів. Асоціативність – це групова властивість (приклад - кількість елементів в структурі). Асоціація об’єктів, як правило, впорядкована за певною системою правил – відношенням порядку на множині об’єктів.

Приклади правил впорядкування:

• виділення окремих властивостей об’єкта: „вік”, „пріоритет” і т.п.;

• можуть бути побудовані на основі часу модифікації складу членів об’єктів (LIFO, FIFO - див. далі по тексту стек, черга).

Загальна властивість багатьох асоціацій – це можливість відображення їх членів на деяку підмножину натуральних чисел, тобто їх нумерація, що дозволяє задавати відношення лінійного порядку (між елементами першим і наступним немає інших): „предок - нащадок”, „попередній - наступний”... Ця властивість дає можливість реалізовувати багато асоціацій у вигляді лінійних списків:

Head (голова) - це елемент, від якого можна перейти до будь-якого іншого елемента списку.

Tail (хвіст) – це елемент, зв’язок якого є нульовим.

Порожній список – кількість його елементів дорівнює нулю..

Список, в якого всі елементи мають однаковий тип – однорідний, якщо до складу списку входять різнотипні елементи – неоднорідний.

2. Лінійні списки.

. Лінійний список - це така ДСО (такий спосіб організації даних), яка для кожного елемента дозволяє вказати:

1. Який елемент є наступним для заданого;

2. Який елемент є попереднім для заданого;

3. Який лемент є наступним і який є попереднім.

Кожен елемент такого списку містить корисні дані та вказівник (адресу) на наступний елемент списку (або порожній вказівник null для останнього елемента списку). Оскільки довжина списку наперед невідома, то найкраще його елементи розміщувати у динамічній пам’яті, створюючи та знищуючи їх операторами new та delete.

Для організації лінійних списків використовують структури або класи, поля яких поділяють на дві частини – інформаційна і зв’язкова (як правило, це набір вказівників).

class LIST // список

{

int data; // інформаційна частина

LIST *next; //зв’язкова (набір вказівників)

public:

LIST(int newdata, LIST *oldlist=0) // конструктор у виді in-line функції

{data=newdata; next=oldlist;}

~LIST(); // деструктор

virtual void print(); // віртуальний метод

};

(докладні пояснення див. лаб. роб. 10, пункт 2)

Враховуючи рекурсивну природу списку, операції над ним найзручніше реалізовувати з використанням рекурсивних функцій. Так деструктор ~LIST() знищує об’єкт типу LIST, звільняє зайняту ним пам’ять, а також повинен знищити всі наступні елементи списку, на який вказує вказівник next, якщо він не null (тобто поки не досягнуто “хвоста” списку):

Тут деструктор буде викликатись рекурсивно для кожного елемента списку. Використання умови if (next) є обов’язковим, щоб рекурсія завершилась на останньому елементі списку (“хвості”), а не стала нескінченною.

LIST::~LIST()

{

if (next)

delete next;

}

Аналогічно зреалізований рекурсивний метод virtual void print(), що виводить на екран послідовно всі значення поля списку LIST, розділені символом табуляції.

v

Вивід здійснюється починаючи від “голови” списку до його “хвоста”. Ця функція зроблена віртуальною, щоб можна було створювати породжені класи (списки з іншими типами даних), які б виводили свої дані.

oid LIST::print()

{

cout<<data<<'\t';

if (next)

next->print();

}

Функція main() для робити зі списком LIST може мати такий вигляд:

void main(){

LIST *mylist=new LIST(1); //створити список з елементом “1”

mylist=new LIST(2,mylist); //додати елемент “2”

mylist=new LIST(3,mylist); //додати елемент “3”

mylist->print(); //вивід списку на екран

delete mylist; //знищення списку

}

Тут створюється список mylist, що складається з одного елемента зі значенням поля data=1, потім в його “голову” додається ще два елементи (місять числа 2 та 3), далі весь список виводиться на екран і знищується.

Результати виконання програми (числа виводять від “голови” до “хвоста”):

3 2 1

Списки поділяються на :

-

або

однозв’язні

- двозв’язні (мінімум 2 зв’язки)

Лінійні списки можуть бути кільцевими:

- однозв’язний кільцевий

- двозв’язний кільцевий