Реферат Курсовая Конспект
Основні поняття - раздел Образование, Графи P Нелінійним Розгалуженим Списком Є Список, Елементами Якого Можуть Бути Теж...
|
Нелінійним розгалуженим списком є список, елементами якого можуть бути теж списки. Якщо один з покажчиків кожного елемента списку задає порядок зворотний до порядку, встановлюваному іншим покажчиком, то такий двозв’язний список буде лінійним.
Якщо ж один з покажчиків задає порядок довільного виду, що не є зворотним стосовно порядку, встановлюваному іншим покажчиком, то такий список буде нелінійним. В обробці нелінійний список визначається як будь-яка послідовність атомів і списків (підсписків), де як атом береться будь-який об'єкт, що при обробці відрізняється від списку тим, що він структурно неподільний.
ОПИС СПИСКІВ. Якщо списки узяти в круглі дужки, а елементи списків розділити комами, то як списки можна вважати такі послідовності:
(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.
– Конец работы –
Эта тема принадлежит разделу:
ДИНАМІЧНІ СТРУКТУРИ ДАНИХ R... Особливості динамічних структурP Лінійні зв язні списки P...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Основні поняття
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов