Спискові структури

Список, що містить всі підсписки, які відходять від нього, називають списковою структурою. Ці структури являють собою узагальнення лінійних списків.

Спискові структури описуються трьома характеристиками.

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

2. Глибина. Це максимальний рівень, який приписується елементам в середині списку, або в середині всякого підсписку в списку. Рівень елемента визначається в залежності від кількості підсписків, що містяться в середині списку, тобто числом пар дужок, якими оточується елемент.

Наприклад, на рис. 11.1 графічно зображений список (а,(b,c,d), e,(f,g)) у якого рівень елементів a i e дорівнює одиниці, а елементів b,c,d,f,g - двом. Глибина цього списку дорівнює двом.

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

Рис.11.1. Спискова структура

Наприклад, максимальний рівень елементів у списку на рис.8.6 дорівнює двом, тому глибина списку також дорівнює двом.

3. Довжина. Це число елементів списку першого рівня.

Наприклад, довжина списку (a,(b,c), d) дорівнює трьом, а списку, зображеного на рис.11.1 - чотирьом, тому що він містить чотири елементи: елемент a, підсписок (b, c, d), елемент e і підсписок (f,g).