- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 2007
- •1. Структуры данных и алгоритмы 6
- •1.2. Информация и ее представление
- •1.2.1. Природа информации
- •1.2.2. Хранение информации
- •1.2.3. Классификация структур данных
- •1.3. Операции над структурами данных
- •1.4. Порядок алгоритма
- •1.5. Структурность данных и технологии программирования
- •Контрольные вопросы
- •2. Простые структуры данных
- •2.1. Порядковые типы
- •2.2. Целочисленный тип
- •2.3. Символьный тип
- •2.4. Перечисляемый тип
- •2.5. Интервальный тип
- •2.6. Логический тип
- •2.7. Битовый тип
- •2.8. Вещественный тип
- •2.9. Указательный тип
- •Контрольные вопросы
- •3. Объектные типы данных
- •3.1. Объявление и реализация классов
- •Interface
- •Implementation
- •3.2. Директивы видимости
- •3.3. Свойства классов
- •3.4. Структурированная обработка ошибок
- •3.5. Применение объектов
- •Контрольные вопросы
- •4. Статические структуры данных
- •4.1. Векторы
- •4.2. Массивы
- •4.3. Множества
- •4.4. Записи
- •4.5. Таблицы
- •4.6. Операции над статическими структурами
- •4.6.1. Алгоритмы поиска
- •4.6.2. Алгоритмы сортировки
- •Самые медленные алгоритмы сортировки
- •Быстрые алгоритмы сортировки
- •Самые быстрые алгоритмы сортировки
- •Сортировка слиянием
- •Контрольные вопросы
- •5. Полустатические структуры данных
- •5.1. Стеки
- •5.1.1. Стеки в вычислительных системах
- •5.2. Очереди fifo
- •5.2.1. Очереди с приоритетами
- •5.2.2. Очереди в вычислительных системах
- •5.3. Деки
- •5.3.1. Деки в вычислительных системах
- •5.4. Строки
- •5.4.1. Операции над строками
- •5.4.2. Представление строк в памяти
- •3 A b d 8 p q r s t u V w
- •V w ptr nil
- •1 8 П р е д с т а в
- •2 7 ? Л е н и е ?
- •1 8 С т р о к и з
- •1 8 В е н ь я м и
- •1 8 С у п р а в л
- •1 8 Я е м о й д л
- •1 4 И н о й ? ? ? ? nil
- •6.2. Связные линейные списки
- •6.2.1. Машинное представление связных линейных списков
- •Inf next
- •Inf next
- •Inf nil
- •6.2.2. Реализация операций над связными линейными списками
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •6.2.3. Применение линейных списков
- •6.3. Нелинейные разветвленные списки
- •6.3.1. Основные понятия
- •6.3.2. Представление списковых структур в памяти
- •6.3.3. Операции обработки списков
- •6.4. Язык программирования lisp
- •6.5. Управление динамически выделяемой памятью
- •Контрольные вопросы
- •7. Нелинейные структуры данных
- •7.1. Графы и деревья
- •(B) (a) (b) (a)
- •V0 v1 v2 v5 v6 v3 v4 v7 v8 v9 v10 (v0) (v1) (v7) (v8) (v9) (v10) (v3) (v2) (v4) (v5) (v6)
- •7.3. Бинарные деревья
- •7.3.1. Представление бинарных деревьев
- •7.3.2. Прохождение бинарных деревьев
- •7.4. Алгоритмы на деревьях
- •7.4.1. Сортировка с прохождением бинарного дерева
- •7.4.2. Сортировка методом турнира с выбыванием
- •7.4.3. Применение бинарных деревьев для сжатия информации
- •7.4.4. Представление выражений с помощью деревьев
- •7.5. Представление сильноветвящихся деревьев
- •Контрольные вопросы
- •8. Методы ускорения доступа к данным
- •8.1. Хеширование данных
- •8.1.1. Функции хеширования
- •8.1.2. Оценка качества хеш-функции
- •8.1.3. Методы разрешения коллизий
- •8.1.4. Переполнение таблицы и рехеширование
- •8.2. Организация данных для поиска по вторичным ключам
- •8.2.1. Инвертированные индексы
- •8.2.2. Битовые карты
- •Контрольные вопросы
- •Листинги рабочих примеров
- •1. Создание и управление списковыми объектами
- •Interface
- •Implementation
- •Interface
- •Implementation
- •3. Моделирование работы стека
- •Interface
- •Implementation
- •Interface
- •Implementation
- •4. Создание и редактирование бинарных деревьев
- •5. Создание и редактирование сильноветвящихся деревьев
- •Задания для самостоятельной работы
- •Литература
- •144Кафедра Вычислительной Техники и Программирования Московского Государственного Открытого Университета
6.3. Нелинейные разветвленные списки
6.3.1. Основные понятия
Нелинейным разветвленным спискомявляется список, элементами которого могут быть также списки. В разделе 6.2 были рассмотрены двухсвязные линейные списки. Если один из указателей каждого элемента задает порядок, обратный к порядку, устанавливаемому другим указателем, то такой двусвязный список будет линейным. Однако если один из указателей задает порядок произвольного вида, не являющийся обратным по отношению к порядку, устанавливаемому другим указателем, то такой список будет нелинейным.
В обработке нелинейный список определяется как любая последовательность атомовиподсписков, где в качестве атома берется любой объект, который при обработке отличается от списка тем, что он структурно неделим. Если заключим списки в круглые скобки, а элементы списков разделим запятыми, то в качестве списков можно рассматривать такие последовательности:
(a,(b,c,d),e,(f,g))
( )
((a))
Первый список содержит четыре элемента: атом a, список (b,c,d), содержащий в свою очередь атомы b,c,d, атом e и список (f,g), элементами которого являются атомы f и g. Второй список не содержит элементов, тем не менее, нулевой список, в соответствии с определением является действительным списком. Третий список состоит из одного элемента: списка (a), который в свою очередь содержит атом а.
Другой способ представления, часто используемый для иллюстрации списков, – графические схемы, аналогичен способу представления, применяемому при изображении линейных списков. Каждый элемент списка обозначается прямоугольником; стрелки или указатели показывают, являются ли прямоугольники элементами одного и того же списка или элементами подсписка. Пример такого представления показан на рис. 6.11.
a
nil
e b g
nil c d
nil f
Рис. 6.11. Схематическое представление разветвленного списка.
Разветвленные списки описываются тремя характеристиками: порядком, глубиной и длиной.
Порядок. Над элементами списка задается транзитивное отношение, определяемое последовательностью, в которой элементы появляются внутри списка. В списке (x,y,z) атом x предшествует y, а y предшествует z. При этом подразумевается, что x предшествует z. Данный список не эквивалентен списку (y,z,x). При представлении списков графическими схемами порядок определяется горизонтальными стрелками. Горизонтальные стрелки истолковываются следующим образом: элемент, из которого исходит стрелка, предшествует элементу, на который она указывает.
Глубина. Максимальный уровень, приписываемый элементам внутри списка или внутри любого подсписка в списке. Уровень элемента описывается вложенностью подсписков внутри списка, т.е. числом пар круглых скобок, окаймляющих элемент.
В списке, изображенном на рис. 6.11, элементы a и e находятся на уровне 1, в то время как оставшиеся элементы – b, c, d, f и g имеют уровень 2. Глубина входного списка равна 2. При представлении списков схемами концепции глубины и уровня облегчаются для понимания, если каждому атомарному или списковому узлу приписать некоторое число l. Значение l для элемента x, обозначаемое как l(x), является числом вертикальных стрелок, которое необходимо пройти для того, чтобы достичь данный элемент из первого элемента списка. Для нашего примера l(a)=0, l(b)=1 и т.д. Глубина списка является максимальным значением уровня среди уровней всех атомов списка.
Длина – число элементов уровня 1 в списке. Например, длина списка нашего примера равна 3.
Типичный пример применения разветвленного списка – представление алгебраического выражения в виде списка. Алгебраическое выражение можно представить в виде последовательности элементарных двухместных операций вида:
< операнд 1 > < знак операции > < операнд 2 >
Выражение (a+b)*(c-(d/e))+f
будет вычисляться в следующем порядке:
a+b
d/e
c-(d/e)
(a+b)*(c-d/e)
(a+b)*(c-d/e)+f
При представлении выражения в виде разветвленного списка каждая тройка «операнд-знак-операнд» представляется в виде списка, причем, в качестве операндов могут выступать как атомы – переменные или константы, так и подсписки такого же вида (рис. 6.12). Скобочное представление выражения будет иметь вид:
(((a,+,b),*,(c,-,(d,/,e)),+,f)
Глубина списка равна 4, длина - 3.
Рис. 6.12. Схема списка, представляющего алгебраическое выражение.