- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 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Кафедра Вычислительной Техники и Программирования Московского Государственного Открытого Университета
A
B ptr P
ptr Q
R S T U ptr D
ptr nilV w ptr nil
Рис. 5.10. Представление строки многосимвольными звеньями переменной длины.
Многосимвольные звенья с управляемой длиной. Память выделяется блоками фиксированной длины. В каждом блоке помимо символов строки и указателя на следующий блок содержится номера первого и последнего символов в блоке. При обработке строки в каждом блоке обрабатываются только символы, расположенные между этими номерами. Признак пустого символа не используется: при удалении символа из строки оставшиеся в блоке символы уплотняются и корректируются граничные номера.
Вставка символа может быть выполнена за счет имеющегося в блоке свободного места, а при отсутствии – выделением нового блока. Хотя операции вставки/удаления требуют пересылки символов, диапазон пересылок ограничивается одним блоком. При каждой операции изменения может быть проанализирована степень заполнения соседних блоков, и два полупустых соседних блока могут быть переформированы в один.
Для определения конца строки может использоваться пустой указатель в последнем блоке или указатель на последний блок в дескрипторе строки. Второй способ может быть весьма полезен при выполнении некоторых операций, например, сцепления. В дескрипторе может храниться также и длина строки: считывать ее из дескриптора удобнее, чем подсчитывать перебором всех блоков строки. Пример представления строки в виде звеньев с управляемой длиной 8 показан на рис. 5.11.
Дескриптор
50
1 8 П р е д с т а в
2 7 ? Л е н и е ?
1 8 С т р о к и з
1 8 В е н ь я м и
1 8 С у п р а в л
1 8 Я е м о й д л
1 4 И н о й ? ? ? ? nil
Рис. 5.11. Представление строки звеньями управляемой длины.
Контрольные вопросы
Перечислите свойства полстатических структур данных.
Опишите работу стека. Перечислите области применения.
Опишите работу кольцевой очереди и очереди с приоритетами.
Строки. Способы представления и операции над строками.
6. Динамические структуры данных
6.1. Связное представление данных в памяти
Динамические структурыхарактеризуются отсутствием физической смежности элементов структуры в памяти, непостоянством и непредсказуемостью размера (числа элементов) в процессе ее обработки. Элементы динамической структуры располагаются по непредсказуемым адресам памяти, поэтому адрес элемента структуры не может быть вычислен по адресу начального или предыдущего элемента. Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным.
Элемент динамической структуры состоит из двух полей:
информационного поля или поля данных, в котором содержатся данные; в общем случае поля данных само является интегрированной структурой – вектором, массивом, записью и т.п.;
поля связок, в котором содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры.
Когда связное представление данных используется для решения прикладной задачи, для конечного пользователя «видимым» делается только содержимое информационного поля, а поле связок используется только разработчиком.
Достоинства связного представления данных:
возможность обеспечения значительной изменчивости структур;
размер структуры ограничивается только доступным объемом машинной памяти;
при изменении логической последовательности элементов структуры требуется только коррекция указателей, без фактического перемещения данных в памяти.
Вместе с тем связное представление не лишено и недостатков:
работа с указателями требует, как правило, более высокой квалификации от разработчика;
на поля связок расходуется дополнительная память;
доступ к элементам связной структуры может быть менее эффективным по времени.
Последний недостаток является наиболее серьезным и им ограничивается применимость связного представления данных. Если в смежном представлении для вычисления адреса любого элемента во всех случаях достаточен номер элемента и информации, содержащейся в дескрипторе структуры, то для связного представления адрес элемента не может быть вычислен из исходных данных.
Дескриптор связной структуры содержит один или несколько указателей, позволяющих войти в структуру, далее выполняется поиск требуемого элемента путем следования по цепочке указателей от элемента к элементу. Поэтому связное представление не применяется в задачах, где логическая структура данных имеет вид вектора или массива (с доступом по номеру элемента), но часто применяется в задачах, где логическая структура требует другой исходной информации доступа (таблицы, списки, деревья и т.д.).