Рекурсивний тип даних

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Cтруктури даних регулярного і комбінованого типів (arrayіrecord), називаються фундаментальними. Опис цих даних фіксує кардинальне число і однозначно визначає розмір виділеної для них пам'яті, у зв'язку з чим їх також називають статичними.

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

Для подальшого обговорення механізму формування динамічних структур істотною виявляється аналогія між методами структурування дій і даних.

Так, наприклад, елементарним неструктурованих оператором є присвоювання. Відповідний йому тип даних - простий (скалярний) тип. В обох випадках це елементарні будівельні блоки для ускладнених операторів і типів даних.

Складовою оператор і record- найпростіші структури, одержувані за допомогою перерахування. Обидві ці структури складаються з кінцевого кількості явно перераховуються різних компонент. Якщо все перераховуються компоненти однакові і число їх повторень відомо, зручно використовувати оператор циклу з параметром (for) і структуру даних тіпаarray. Вибір з двох або більше варіантів при розгалуження виражається умовним або вибирають оператором і, відповідно, записом з варіантаміі, нарешті, повторення невідомого (потенційно нескінченного) кількості компонент виражається операторами ціклаwhileіліrepeat. Відповідна ним структура даних - послідовність (файл), тобто найпростіший вид структури, допускає побудову типів з нескінченним кардинальним числом.

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

Прикладом рекурсивно визначається об'єкта може служити синтаксична конструкція арифметичного виразу. Рекурсія в даному випадку відображає вкладеність, тобто використання ув'язнених в дужки подвираженій в якості операндів у виразах. Цей об'єкт описується, наприклад, таким чином:

type Expression = record Op: Operator; Opd1, Opd2: Term end;


Term = record case В: Boolean of true: (Id: string); False: (Subex: Experession) end;

При такому описі кожна змінна типу Term складається з двох компонент: поля ознаки В і, якщо В істинно, то поля Id, інакше - поля Subex.

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

Наведене опис типу нижче ілюструється наступними чотирма виразами: 1. a + b; 2. a- (b * c); 3. (a + b) * (c -d): 4. (a * (b + c)) / d.


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

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

type Ped = record case Known: Boolean of true: (Name: string; Father, Mother: Ped); False: () end;


Як уже зазначалося, істотною відмінністю рекурсивних структур від фундаментальних, є їх здатність змінювати розмір. Тому для рекурсивно певних структур неможливо встановити фіксований розмір пам'яті і транслятор не може зіставити компонентів такої структури певні адреси. Для їх розміщення найчастіше застосовується метод динамічного розподілу, тобто виділення пам'яті для окремих компонент в той момент, коли вони з'являються під час виконання програми, а не під час її трансляції. В цьому випадку транслятор виділяє фіксований обсяг пам'яті тільки для зберігання адреси динамічно розміщується компоненти. Наприклад, генеалогічне дерево, зображене на Pіс.7.2, можна представити у вигляді окремих (не обов'язково поруч розташованих в пам'яті) записів. Ці записи зв'язуються за допомогою адрес, які перебувають у відповідних поляхfat (від father - батько) іmot (від mother-мати "). Графічно це зображено стрілками (Pіс.7.3).

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

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

Тип посилання в мові Паскаль визначається як type t = T. Його значеннями є посилання на дані тіпаТ (стрілка тут читається як "посилання на"). Істотно, що тип даних, на які посилаються значення тіпаt, заданий в його визначенні (тіпtоказиваетсяжестко связаннимсТ). Цей зв'язок відрізняє посилання від адрес в мові асемблера і є дуже важливим засобом підвищення надійності програм за допомогою надмірності позначень. Так, наприклад, можна описати кілька змінних типу посилання:

type Tp = T; Tq = Т1; var P, P1: Tp; Q: Tq;


Ілюстрацією можливостей, що надаються динамічними структурами даних, може служити приклад обробки лінійних списків.

Нехай кожна компонента списку є змінна деякого типу item, що представляє собою запис з полем ідентифікує ключа (key) і, можливо, іншими полями, що характеризують деякий інформаційний об'єкт (істотним для розглянутих прикладів тут є тільки полеkey, а згадка про інших полях просто свідчать про те , що об'єкт може бути досить складним):

typе Item = record Key: Integer; . . . {Інші поля записи} end;

Тоді список можна було б уявити, наприклад, у вигляді масиву, тип якого визначається як:

Vector = array [1 ..SizeArray] of Item.

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

Використання найпростішої динамічної структури даних - зв'язного списку дозволяє доповнювати і вкорочувати список, не піклуючись про те, куди помістити нову компоненту, або про те, що відбувається з вільним простором, що виникають при виключенні компонент, т. Е. Усунути перераховані незручності. При використанні динамічних структур втрачається таке гідність фундаментальних структур, як можливість прямого доступу до окремих компонентів.

Тип Item в цьому випадку повинен бути визначений як: typе Referenc = ^ Item; Item = record Key: Integer; Next: Reference end;


Формування списку. Найпростіше дію, яке можна виконати з уже сформованим списком, це вставити в його початок нову компоненту (в початок тому, що відома посилання тільки на першу компоненту). Для цього необхідно розмістити нову компоненту в пам'яті за допомогою процедуриNew (q), гдеq- посилання на адресу компоненти, а потім виконати оператори прісваіваніяq next: = p; p: = q. Порядок операторів не можна міняти, так як це призведе до "втрати" адреси початку списку, а, отже, і списку в цілому.

Таким чином, сформувати список найпростіше послідовним доповненням елементів в його початок, природно, починаючи з "пустого" списку. Наведена нижче програма ілюструє процес формування списку. При цьому порядок компонент в списку протилежний порядку їх надходження.

program Prim7_1; type Ref = Item; Item = record Key: Integer; Next: Ref end; var N: Integer; P, Q: Ref; begin Write ( 'введіть кількість компонент списку'); Read (N); P: = nil; {Початок порожнього списку} while N> 0 do begin New (Q); Q. Next: = P; P: = Q; Read (Q.Key); {Введення значення чергового поля Key} N: = N-1 end end.


Включення в список. Нехай компоненту, на яку вказує ссилка, необхідно включити в список після компонентів, на яку вказує ссилка. Необхідні для цього дії іллюструются і зводяться до виконання операторів R.Next: = Q.Next; Q.Next: = R.

Включення компоненти перед тою, на яку вказує ссилка пов'язане з певними труднощами, оскільки значення посилання на неї невідомо і може бути визначено тільки за допомогою перегляду списку аж до цієї компоненти. Але бажаний результат можна отримати включенням нової компоненти після тої, на яку вказує і наступного обміну значень KeyіQ.Next.Key.

Включення в список ілюструється фрагментами програм, які оформлені як процедури InsertNextіInsertBefore.

procedure InsertNext (var Q: Ref); begin R.Next: = Q.Next; Q.Next: = R end; {InsertNext} procedure InsertBefore (var Q: Ref); var Buf: Integer; begin R.Next: = Q.Next; Q.Next: = R; Buf: = Q.Key; Q.Key: = R.Key; R.Key: = Buf end; {InsertBefore}

Видалення з списку .Операція видалення зі списку компоненти після Q, відноситься до найпростіших. Для її виконання досить знищити відповідне посилання. Привласнити полюQ.Next значення посилання на компоненту, яка слідує за видаляється, наприклад, за допомогою присвоєння .Next: = Q.Next.Next:

procedure DelitеNext (var Q: Ref); begin Q.Next: = Q.Next.Next end; {DelitеNext}