- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 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Кафедра Вычислительной Техники и Программирования Московского Государственного Открытого Университета
Контрольные вопросы
Перечислите свойства статических структур данных.
Приведите примеры объявления и применения вектор и массивов.
В чем состоит преимущество их использования открытых массивов?
Что такое множества? Описание и применение множеств.
Записи упакованные, неупакованные, с вариантами.
Опишите алгоритмы линейного и бинарного поиска.
Перечислите стратегии сортировки, приведите классификацию алгоритмов сортировки.
Опишите алгоритмы сортировки выборкой, пузырьковой, вставками.
Опишите разновидности алгоритмов сортировки методом Шелла.
Опишите алгоритмы поразрядной цифровой сортировки, методом Хоара и слиянием.
5. Полустатические структуры данных
Полустатические структуры данныххарактеризуются следующими признаками:
переменная длина и простые процедуры ее изменения;
изменение длины структуры происходит в определенных пределах, не превышая максимального (предельного) значения.
На логическом уровне полустатическая структура представляет последовательность данных, связанная отношениями линейного списка. Доступ к элементу может осуществляться по его порядковому номеру. На физическом уровне полустатическая структура данных представляет последовательность слотов, где каждый следующий элемент расположен в памяти в следующем слоте. Физическое представление также может иметь вид однонаправленного связного списка (цепочки), где каждый следующий элемент адресуется указателем, находящимся в текущем элементе. В последнем случае ограничения на длину структуры гораздо менее строги.
5.1. Стеки
Стек– последовательный список с переменной длиной, включение и исключение элементов из которого выполняются с одной стороны списка, называемого вершиной. Другие названия стека – магазин или очередь, функционирующая по принципу LIFO (Last-In-First-Out – «последним пришел - первым исключается»). Основные операции над стеком – включение нового элемента (англ. push заталкивать) и исключение элемента из стека (англ. pop – выскакивать). Полезными могут быть также такие как определение текущего числа элементов в стеке и очистка стека.
Рассмотрим пример, демонстрирующий принцип включения элементов в стек и исключения элементов из стека. На рис. 5.1 изображены состояния стека: пустого (а), после последовательного включения в него элементов с именами 'A', 'B', 'C' (б-г), после последовательного удаления из стека элементов 'C' и 'B' (д, е), после включения в стек элемента 'D' (ж).
Вершина
стека 4
3
2
1
A
B
A
C
B
A
B
A
A
D
A
а
б в г д е ж
Рис 5.1. Включение и исключение элементов из стека.
При представлении стека в статической памяти для него выделяется память, как для вектора. В дескрипторе вектора кроме обычных параметров должен находиться указатель стека – адрес вершины стека. Указатель стека может указывать либо на первый свободный элемент стека, либо на последний записанный в стек элемент. Все равно, какой из этих двух вариантов выбрать, важно впоследствии строго придерживаться его при работе со стеком.
При занесении элемента в стек элемент записывается на место, определяемое указателем стека, затем указатель модифицируется таким образом, чтобы он указывал на следующий свободный элемент (если указатель указывает на последний записанный элемент, то сначала модифицируется указатель, а затем производится запись элемента). Модификация указателя состоит в прибавлении или вычитании из него значения, равного размеру элемента.
Операция исключения элемента состоит в модификации указателя стека (в направлении, обратном модификации при включении) и выборке значения, на которое указывает указатель стека. После выборки слот, в котором размещался выбранный элемент, считается свободным.
Операция очистки стека сводится к записи в указатель стека начального значения – адреса начала выделенной области памяти, а операция определения размера стека – к вычислению разности указателя стека и адреса начала области, отведенной под стек.