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

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

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

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

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

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

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

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

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

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

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

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

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

class List

{

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

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

}

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

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

Порожній список – кількість його елементів рівна 0.

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

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

- однозв’язні

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

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

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

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

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