- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 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Кафедра Вычислительной Техники и Программирования Московского Государственного Открытого Университета
2.5. Интервальный тип
Другой способ образования новых типов из уже существующих заключается в ограничении допустимого диапазона значений некоторого стандартного типа или границ перечисляемого. Ограничение определяется заданием минимального и максимального значений диапазона. При этом изменяется диапазон допустимых значений по отношению к базовому типу, но представление в памяти полностью соответствует базовому типу.
Таким способом формируется интервальный тип. Значения интервального типа могут принадлежать ограниченному поддиапазону некоторого базового типа. Базовым типом диапазона может быть любой порядковый тип, кроме интервального.
Для введения интервального типа необходимо указать имя типа и границы диапазона:
type
< имя типа > = < мин. значение >..< макс. значение >
Минимальное значение при определении не может быть больше максимального:
type
TTemp = -50..+50; { тип ShortInt }
TIndex = 1..100; { тип Byte }
Все операции, применимые к величинам базового типа, можно применять и к величинам соответствующего интервального типа с учетом его границ. Преимущества использования интервальных типов заключается в наглядности представления, экономном распределении памяти под переменные и дополнительном контроле значений переменных.
2.6. Логический тип
Логический тип является перечисляемым с двумя возможными значениями «ложь» и «истина»:
type
Boolean = (False, True);
Логические типы языка Паскаль приведены в табл. 2.4.
Табл. 2.4. Логические типы данных.
Название типа |
Длина, байт |
Boolean |
1 |
ByteBool |
1 |
WordBool |
2 |
LongBool |
4 |
Основным типом является Boolean, для него справедливы следующие соотношения:
Ord(False) = 0; Ord(True) = 1;
Succ(False) = True; Pred(True) = False; False True
Остальные три типа введены для совместимости с другими языками и операционной системой Windows. Для них справедливы следующие соотношения:
Ord(False) = 0;
Ord(True)0 (любое целое число)
Логический тип имеет большое значение поскольку:
операции отношения являются функциями, возвращающими значение булевого типа;
условный оператор проверяет выражение булевого типа;
операции булевой алгебры определены для булевого типа.
Примеры применения логических функций для сведения нескольких условий в одно логическое выражение приведены на рис. 2.2.
а)
б). в).
Рис. 2.2. Одномерная (а), двухсвязная одномерная (б) и двухмерная (в) области координат.
Сформированные логические выражения по этим условиям выглядят следующим образом:
а). -1 x1(-1x) and (x1)
в). x 0 или x1(x0) or (x1)
б). x0(x0) and (y0)
y0
2.7. Битовый тип
В ряде задач может потребоваться работа с отдельными двоичными разрядами данных. Чаще всего это возникают в системном программировании, когда, например, отдельный разряд связан с состоянием аппаратного переключателя. Данные битового типа представляются в виде набора битов, упакованных в байты или слова, и не связанных друг с другом. Операции над такими данными обеспечивают доступ к выбранному биту. В языке Паскаль роль битовых типов выполняют беззнаковые целые типы Byte и Word. Над этими типами помимо операций, характерных для числовых типов, допускаются побитовые логические операции и операции сдвига.