Організація спискових структур

Розглянемо зображення в пам‘яті спискових структур. Очевидно, що для них найзручнішим є зчеплене зображення, яке при необхідності забезпечує динамічне розміщення вершин, легкість обробки і здатність розділяти підсписки. Список в загальному випадку задається деякою варіацією бінарного зображення натуральних дерев, шляхом використання двох полів зв‘язку: одного - для вказівки членства в середині списку і другого - для вказівки адреси.

Типова структура елемента списку в машинному зображенні буде такою:

Тут поле ПС вказує на перший елемент у підсписку; поле НС - на наступний елемент у даному списку, а поле ІЕ містить інформацію безпосередньо про елемент даних.

Але такий формат елемента зручний тільки тоді, коли інформація про нього займає невеликий обсяг пам‘яті, тоді поле ІЕ буде невеликим.

У більш загальному випадку для елементів даних потрібен відносно великий обсяг пам‘яті, тому частіше використовуються формати, що складаються тільки з двох полів:

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

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

а) (a, (b,c, d),e, (f,g)) - довжина чотири (два ізольованих елементи списку - a, e і два підсписки - (b,c,d), (f,g)).

б) () - нуль-список, довжина нуль;

в) ((а)) - довжина одиниця (ізольований елемент списку утворює підсписок).

Рис.11.3. Зображення спискових структур у пам‘яті

Між списковими структурами і орієнтованими графами існує прямий зв‘язок. Зокрема, список являє собою орієнтований граф з однією початковою вершиною, що відповідає входу в список. Кожна вершина безпосередньо пов‘язана з початковою вершиною, що відповідає елементу списку: або з вершиною з півступінню виходу нуль (для ізольованих), або з вершиною, що має вихідні гілки (для елементів, які самі є списками). Ребра, що виходять із вершин, можна розглядати як впорядковані списки. Це означає, що розпізнається перше ребро, друге і т.д., які відповідають впорядкованим списковим елементам для першого, другого і т.д. елементів.

Тоді списки, зображені на рис.11.3, можна змалювати також у вигляді графів (рис.11.4).

Рис.11.4. Зображення спискових структур у вигляді графа

Існують списки, які не можуть бути зображені як дерева, але кожне дерево може бути зображене у вигляді якогось списку. Списки можуть мати внутрішню рекурсивну структуру, чого не мають дерева. Такі списки відповідають безкінечним графам.

Отже, для зображення в пам‘яті самих спискових структур існує багато способів, але всі вони мають спільні риси, які опираються на використання бінарних дерев для зображення лісів. При цьому одне з полів у записі вузла використовується для вказівника на наступний елемент списку, а друге поле можна використати для вказівника на перший елемент підсписку.