Тема 9. Двонаправлені динамічні списки.

Питання теми та основні терміни.

Інформаційні матеріали теми

Поняття двоспрямованого циклічного списку.

Основні процедури обробки двоспрямованих циклічних списків.

1. Поняття двоспрямованого циклічного списку.

Раніше нами був  розглянута нова структура  даних - динамічний односпрямований  лінійний список. У списку для зручності його обробки був передбачений заголовний елемент, що не містив ніякої інформації (за винятком, може бути, службової). Нами були розглянуті основні операції над списком і його елементами і записані відповідні процедури.

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

Для усунення цього недоліку додамо ще одне поле в ланку списку, що буде вказувати на попередній елемент списку (рис. 9.1). У цьому випадку структура ланки списку буде визначатися таким описом

Type

inf = ...{ тип елементів списку  }

circle_list =^chain;

chain= record

  elem: inf;

  next: circle_list;

  pred: circle_list

end;

Рис 9.1. Динамічний двоспрямований список

Структуру, у якій кожен елемент містить посилання і на наступний, і на попередні елементи,  будемо називати динамічним двоспрямованим списком

Наявність посилань на попередній і наступний елементи дозволяє переміщатися за списком в обох напрямках.

Уведемо за аналогією з односпрямованим списком початковий  елемент. Тоді список буде мати такий вид (рис 9.2.)

Рис 9.2. Динамічний двоспрямований список із початковим  елементом.

Часто двоспрямовані для зручності обробки узагальнюють у такий спосіб: у якості значення поля next останнього елемента приймають посилання на заголовну ланку, а в якості значення поля  pred заголовної ланки - посилання на останню ланку списку  (рис 9.3). Список буде мати циклічний вид.  Можлива також така організація списку, коли початковий елемент не включається в цикл  (рис. 9.4).

Рис 9.3. Динамічний двоспрямований циклічний список із включеним початковим елементом

Рис 9.4. Динамічний двоспрямований циклічний список з виключеним  початковим елементом

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

Далі нами буде розглянутий перший варіант циклічного двоспрямованого списку.

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

2.  Основні процедури обробки двоспрямованих циклічних списків.

При описі процедур приймемо наступні допущення :

1. У програмі діють наступні описи

type

inf = ... { тип елементів списку  }

circle_list =^chain;

chain= record

  elem: inf;

  next: circle_list;

  pred: circle_list

end;

data=file of inf;  { дані для формування списку будуть уводитися з файлу }

var

x:inf;

f:data;

s:circle_list;