Динамические структуры данных. Алексеев А.Ю - 18 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

элемент списка, называемый текущим. Относительно этого элемента и произ-
водятся некоторые действия. Здесь список s фактически представляется парой
последовательностей Left(s), Right(s), вторая из которых начинается с текуще-
го элемента.
Рассмотрим теперь другой подход к организации и обработке списков, ос-
нованный на систематическом применении рекурсии и не предполагающий ни
явного выделения текущего элемента, ни разделения списков на однонаправ-
ленные и двунаправленные. На рис.1.17 изображен линейный список, разде-
ленный на две неравные части: "голову" (первый элемент списка) и "хвост"
(все остальное).
“Хвост” списка
“Голова” списка
Рис. 1.17. Модельное представление линейного списка
Линейный список, таким образом, или пуст (не содержит ни одного эле-
мента) или представляет собой упорядоченную пару "голова"–"хвост", в кото-
рой "голова" есть элемент базового типа El, а "хвост", в свою очередь, есть
линейный список (возможно пустой). Отметим, что такое определение линей-
ного списка по существу рекурсивно.
Пусть множество T
0
состоит из единственного элемента, которым является
пустой список, и пусть T
n
– множество всех линейных списков, состоящих
ровно из n элементов базового типа El. Тогда множество T
1
одноэлементных
линейных списков есть декартово произведение вида T
1
= El ⊗ T
0
, а множест-
во T
n
может быть определено как T
n
= El ⊗ T
n-1
∀n : n > 0. Такое индуктивное
определение линейного списка отражает существенные характеристики его
структуры и не зависит от конкретной формы наглядного представления или
реализации списка. В дальнейшем будем считать его определением понятия
"линейный список".
Списки, особенно обсуждаемые в 1.7 иерархические списки, часто пред-
ставляют в виде различных, наглядных изображений или специфических
форм записи. Одной из распространенных форм представления списков явля-
ется так называемая скобочная запись, применяемая, например, в языке функ-
ционального программирования Лисп.
Используя форму Бэкуса-Наура (БНФ), дадим рекурсивное определение
скобочной записи линейного списка, соответствующее ранее приведенному
индуктивному определению множества линейных списков:
18
элемент списка, называемый текущим. Относительно этого элемента и произ-
водятся некоторые действия. Здесь список s фактически представляется парой
последовательностей Left(s), Right(s), вторая из которых начинается с текуще-
го элемента.
    Рассмотрим теперь другой подход к организации и обработке списков, ос-
нованный на систематическом применении рекурсии и не предполагающий ни
явного выделения текущего элемента, ни разделения списков на однонаправ-
ленные и двунаправленные. На рис.1.17 изображен линейный список, разде-
ленный на две неравные части: "голову" (первый элемент списка) и "хвост"
(все остальное).




                                        “Хвост” списка
                “Голова” списка



               Рис. 1.17. Модельное представление линейного списка


   Линейный список, таким образом, или пуст (не содержит ни одного эле-
мента) или представляет собой упорядоченную пару "голова"–"хвост", в кото-
рой "голова" есть элемент базового типа El, а "хвост", в свою очередь, есть
линейный список (возможно пустой). Отметим, что такое определение линей-
ного списка по существу рекурсивно.
   Пусть множество T0 состоит из единственного элемента, которым является
пустой список, и пусть Tn – множество всех линейных списков, состоящих
ровно из n элементов базового типа El. Тогда множество T1 одноэлементных
линейных списков есть декартово произведение вида T1 = El ⊗ T0, а множест-
во Tn может быть определено как Tn = El ⊗ Tn-1 ∀n : n > 0. Такое индуктивное
определение линейного списка отражает существенные характеристики его
структуры и не зависит от конкретной формы наглядного представления или
реализации списка. В дальнейшем будем считать его определением понятия
"линейный список".
   Списки, особенно обсуждаемые в 1.7 иерархические списки, часто пред-
ставляют в виде различных, наглядных изображений или специфических
форм записи. Одной из распространенных форм представления списков явля-
ется так называемая скобочная запись, применяемая, например, в языке функ-
ционального программирования Лисп.
   Используя форму Бэкуса-Наура (БНФ), дадим рекурсивное определение
скобочной записи линейного списка, соответствующее ранее приведенному
индуктивному определению множества линейных списков:

                                       18

Страницы