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

Існують аналогії проміж методами структурування алгоритмів та методами структурування даних.

Елементарним неструктурованим оператором являється оператор присвоювання. Відповідний йому тип даних – простий, скалярний, неструктурований (тип вважається скалярним, якщо всі його значення впорядковані – це всі стандартні, а також перелічимий).

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

Аналог складеного (Begin... End) – запис, обидві структури складаються з кінцевої кількості компонент.

Щоб описати повторення, число яких відоме і кінцеве, використовують цикл з параметром For; аналог – структура масив.

Вибір з двох або більше варіантів виконується умовним оператором вибору; аналог структури даних – запис з варіантами.

Циклам While i Repeat, які допускають потенціально нескінченне число повторень, відповідає структура даних – файл.

Аналогом рекурсивної процедури являються рекурсивні типи даних. По аналогії з рекурсивною процедурою, яка містить у собі виклики самої себе, значення рекурсивного типу даних повинні мати одну або більше компонент того ж типу, що і все значення.

Приклад – генеалогічне дерево. Iм’я людини – імена двох батьків, кожен з яких – людина, що має двох батьків і т. д.

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

Приклад динамічної структури – черга на прийом до лікаря. Кожний пацієнт запам’ятовує людину, за якою зайняв чергу. Всі пацієнти зв’язані у ланцюжок відповідно з чергою, але у просторі вони разміщені довільним чином, хто прийшов - сідає на будь-яке вільне місце. Якщо хтось із пацієнтів покидає чергу, немає необхідності іншим пацієнтам переміщатись, просто той, хто за ним стояв, запам’ятовує тепер другу людину, за якою він зостався в черзі.

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

Дата добавления: 2013-12-12