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

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

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

Основні процедури опрацювання списку.

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

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

Розглянемо такий приклад: Нехай при розв'язанні деякої задачі необхідно сформувати список певних елементів (наприклад, студентів групи з заданими оцінками), причому кількість елементів списку заздалегідь невідомо. Як уже відзначалося, використання статичних структур (наприклад масивів) неефективно, тому що це веде до неефективної витрати пам'яті (рис 8.1 а).  Набагато краще виділяти елементу пам'ять у міру його появи. Таку можливість надають посилальні типи. Проте ми, очевидно, повинні якимось чином вказувати на розташування елементів у пам'яті. Це можна зробити, якщо разом з елементом ми будемо записувати посилання на інший елемент. При цьому вирішується відразу дві проблеми:

· немає необхідності резервувати пам'ять під дані;

· немає необхідності  того, щоб дані займали суміжні комірки пам'яті, тому що кожний елемент містить посилання на інший такий елемент.

Рис 8.1 . Схема використання пам'яті  масивом а)  і динамічним списком б).

Структуру,  кожний елемент якої містить посилання на такий же елемент, будемо називати динамічним списком (надалі, просто списком). Подібний підхід реалізований при створенні FAT операційної системи MSDOS.

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

Type

spisok =^chain;

chain= record

  elem: string;

  next: spisok

  end;

Зауважимо, що отут ми маємо справу з рекурсивним визначенням типу даних. Таке можливо тільки при використанні посилального типу даних. Порядок проходження визначення типів даних змінювати не можна!!!

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

var s: spisok;

  x: string;

Помітимо, що змінна s призначена для вказівки як на перший елемент списку , так і одночасно на весь список (рис 8.2).

Рис 8.2. Динамічний список

Список можна сформувати в такий спосіб:

{перший елемент }

read(x);

new(s);

s^.elem:=x;

s^.next:=nil;

{другий елемент}

read(x);

new(s^.next);

s^.next^.elem:=x;

s^.next^.next:=nil;

{третій елемент}

read(x);

new(s^.next^.next);

s^.next^.next^.elem:=x;

s^.next^.next^.next:=nil;

  . .  .

Очевидно, що такий підхід має недоліки:

· запис занадто громіздкий;

· процес створення елементів має явно циклічний характер, але цикл записати неможливо.

Тому ми будемо використовувати інший підхід, Для цього введемо ще одну змінну  p: spisok , що буде вказувати на поточну ланку списку. Тоді процес створення списку буде мати вигляд

{перший елемент}

read(x);

new(s);

p:=s;

p^.elem:=x;

p^.next:=nil;

{другий елемент}

read(x);

new(p^. next);

p:=p^next;

p^.elem:=x;

p^.next:=nil;

{третій елемент}

read(x);

new(p^. next);

p:=p^next;

p^.elem:=x;

p^.next:=nil;

. .  .

або у вигляді циклу (закінченням введення будемо вважати введення порожнього рядка)

{перший елемент}

read(x);

new(s);

p:=s;

p^.elem:=x;

p^.next:=nil;  

{інші елементи}

read(x);

while x<>’' do

begin

new(p^.next);

p:=p^.next;

p^.elem:=x;

p^.next:=nil;

read(x)

end;

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

Рис 8.3. Динамічний список із початковим елементом

  заголовний елемент

{створення початкового елементу}

new(s);

p:=s;

p^.next:=nil;

{інші елементи}

read(x);

while x<>’' do

begin

new(p^. next);

p:=p^.next;

p^.elem:=x;

p^.next:=nil;

read(x)

end;

Саме такі списки будуть розглянуті надалі.