- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 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Кафедра Вычислительной Техники и Программирования Московского Государственного Открытого Университета
1.5. Структурность данных и технологии программирования
Знание структуры данных позволяет организовать их хранение и обработку максимально эффективным образом с точки зрения минимизации затрат памяти и процессорного времени. Другим важным преимуществом, которое обеспечивается структурным подходом к данным, является возможность структурирования сложного программного изделия.
Современные промышленно выпускаемые программные пакеты – изделия чрезвычайно сложные, объем которых исчисляется тысячами и миллионами строк кода, а трудоемкость разработки – сотнями человеко-лет. Разработать такое программное изделие сразу невозможно, оно должно быть представлено в виде определенной структуры – составных частей и связей между ними. Правильное структурирование дает возможность на каждом этапе разработки сосредоточить внимание на одной обозримой части изделия или поручить реализацию разных его частей разным исполнителям.
При структурировании больших программных изделий возможно применение подхода, основанного на структуризации алгоритмов и известного, как «нисходящее проектирование» или «программирование сверху вниз», или подхода, основанного на структуризации данных и известного, как «восходящее проектирование» или «программирование снизу вверх».
В первом случае структурируют действия, которые должна выполнять программа. Большую и сложную задачу представляют в виде нескольких подзадач меньшего объема. Таким образом, модуль самого верхнего уровня, отвечающий за решение всей задачи в целом, получается достаточно простым и обеспечивает только последовательность обращений к модулям, реализующим подзадачи.
На первом этапе проектирования модули подзадач выполняются в виде «заглушек». Затем каждая подзадача в свою очередь подвергается декомпозиции по тем же правилам. Процесс дробления на подзадачи продолжается до тех пор, пока на очередном уровне декомпозиции не получат подзадачу, реализация которой будет вполне обозримой.
В предельном случае декомпозиция может быть доведена до того, что подзадачи самого нижнего уровня могут быть решены элементарным действием, например, с помощью одного оператора языка программирования.
Другой подход к структуризации основывается на данных. У реального программного изделия всегда есть Заказчик. Заказчик имеет входные данные, и хочет, чтобы по ним были получены выходные данные, а какими средствами это обеспечивается – его не интересует. Таким образом, задачей любого программного изделия является преобразование входных данных в выходные.
Инструментальные средства программирования предоставляют набор базовых типов данных и операции над ними. Интегрируя базовые типы, создают более сложные структуры, и определяет новые операции над ними. Полученные на первом шаге композиции «строительные блоки» используются в качестве базового набора для следующего шага, результатом которого будут еще более сложные конструкции данных с соответствующими операциями над ними. В идеале последний шаг композиции дает структуры, соответствующие выходным данным задачи, а операции над этими типами реализуют в полном объеме задачу проекта.
Нередко противопоставляют нисходящее проектирование восходящему, придерживаясь одного выбранного подхода, что в корне не верно. Реализация проекта всегда ведется встречными путями с постоянной коррекцией алгоритмов по результатам разработки структур данных и наоборот.
Еще одним технологическим приемом, связанным со структуризацией данных является инкапсуляция, которая заключается в том, что сконструированный новый тип данных оформляется таким образом, что его внутренняя структура недоступна извне, т.е. пользователям данного типа. Оперировать с данными этого типа возможно только через вызовы процедур, определенных в нем. Новый тип данных представляется в виде «черного ящика», для которого известны входы и выходы, но содержимое – неизвестно и недоступно.
Инкапсуляция полезна как средство преодоления сложности, и как средство защиты от ошибок. Первая цель достигается за счет того, что сложность внутренней структуры нового типа и алгоритмов выполнения операций над ним исключается из поля зрения разработчика-пользователя. Вторая цель достигается тем, что возможности доступа пользователя ограничиваются лишь заведомо корректными входными точками, следовательно, снижается и вероятность ошибок.
Современные языки программирования блочного типа (PASCAL, C) обладают развитыми возможностями построения программ модульной структуры и управления доступом модулей к данным и процедурам. Сконструированные и полностью закрытые типы данных представляют объекты, а процедуры, работающие с их внутренней структурой – методами. Развитие данного подхода связано с объектно-ориентированной методологией, реализованной в виде объектных моделей в различных языках программирования.