Основні поняття

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

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

ОПИС СПИСКІВ. Якщо списки узяти в круглі дужки, а елементи списків розділити комами, то як списки можна вважати такі послідовності:

(a,(b,c,d),e,(f,g)), ( ), ((a))

Перший список містить чотири елементи: атомa, список (b,c,d), що містить у свою чергу атоми b,c,d, атом e і список (f,g), елементами якого є атоми f та g. Другий список не містить елементів, проте нульовий список, відповідно до визначення є дійсним списком. Третій список складається з одного елемента: списку(a), що у свою чергу містить атом а.

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

Розгалужені списки описуються трьома характеристиками: порядком, глибиною і довжиною.

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

Глибина. Це максимальний рівень, приписуваний елементам усередині списку або усередині будь-якого підсписку в списку. Рівень елемента визначається вкладеністю підсписків усередині списку, тобто числом пар круглих дужок, що облямовують елемент. На рис. 7.2 елементи a та eзнаходяться на рівні 1, у той час як елементи, що залишилися, – b, c, d, fта g мають рівень 2. Глибина вхідного списку дорівнює 2.

Рис. 7.2. Схематичне представлення розгалуженого списку

При представленні списків схемами концепції глибини і рівня списки полегшуються для розуміння, якщо кожному атомарному або списковому вузлу приписати деяке число l. Значення l для елемента x, що позначається якl(x), є числом вертикальних стрілок, яких необхідно пройти для того, щоб досягти даний елемент із першого елемента списку. На рис. 7.2 (a)=0, l(b)=1 і т.д. Глибина списку є максимальним значенням рівня серед рівнів всіх атомів списку.

Довжина– це число елементів рівня 1 у списку. Наприклад, довжина списку на рис. 7.2 дорівнює 3.

Типовим прикладом застосування розгалуженого списку є представлення арифметичного виразу у вигляді списку (див. рис. 7.3). Арифметичний вираз можна представити у вигляді послідовності елементарних двомісних операцій виду:

<операнд 1> <знак операції> <операнд 2>

При представленні виразу у вигляді розгалуженого списку кожна трійка "операнд-знак-операнд" представляється у вигляді списку, причому, у якості операндів можуть виступати як атоми – перемінні чи константи, так і підсписки такого ж виду.

Рис. 7.3. Схема списку арифметичного виразу

Наприклад, вираз (a+b)*(c+(d/e))-f буде обчислюватися в наступному порядку: 1). a+b, 2). d/e, 3). c + (d/e), 4) (a+b)*(c + d/e), 5) (a+b)*(c + d/e)-f

Скобкове представлення виразу буде мати вигляд:

(((a,+,b),*,(c, + ,(d,/,e))),-,f). Схема списку вказаного виразу подана на рис. 7.3.

Глибина цього списку дорівнює 4, довжина – 3.