- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 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.8. Вещественный тип
В отличие от рассмотренных порядковых типов, значения которых всегда сопоставляются с рядом целых чисел и, следовательно, представляются в памяти абсолютно точно, значение вещественных типов может быть определено лишь с некоторой конечной точностью, зависящей от внутреннего формата вещественного числа. Суммарное количество байтов, диапазоны допустимых значений чисел вещественных типов и количество значащих цифр после запятой в представлении чисел приведены в табл. 2.5.
Табл. 2.5. Вещественные типы.
Тип |
Диапазон значений |
Значащие цифры |
Размер в байтах |
Real |
2.9·10-39..1.7·1038 |
11-12 |
6 |
Single |
1.4·10-45..3.4·1038 |
7-8 |
4 |
Double |
4.9·10-324..1.8·10308 |
15-16 |
8 |
Extended |
3.1·10-4944..1.2·104932 |
19-20 |
10 |
В языке Паскаль переменные вещественного типа представляются в форме, близкой к научной нотации:
const
pi: Real = 3.1415926;
eq: Real = 1.19e-31;
Для вычислений с плавающей запятой необходимо минимум 32 разряда (одинарная точность, тип Single). Однако часто и одинарной точности оказывается недостаточно, поэтому языки поддерживают объявления переменных и вычисления с двойной точностью 64 разряда (тип Double).
Для переменных вещественного типа базовыми являются арифметические операции и операции отношения. Другие математические операции реализуются в разных языках по-разному. В языке Паскаль к стандартным функциям относятся также арифметические функции, перечисленные в табл. 2.6.
Табл. 2.6. Стандартные арифметические функции.
Функция |
Назначение |
Тип результата |
Abs(x) |
Абсолютное значение аргумента. |
совпадает с x |
Arctan(x) |
Арктангенс аргумента. |
вещественный |
Cos(x) |
Косинус аргумента. |
-//- |
Exp(x) |
Вычисление экспоненты. |
-//- |
Frac(x) |
Дробная часть аргумента. |
-//- |
Int(x) |
Целая часть числа. |
-//- |
Ln(x) |
Натуральный логарифм. |
-//- |
Pi(x) |
Число pi = 3.1415926535897932385. |
-//- |
Round(x) |
Округление до ближайшего целого. |
-//- |
Sin(x) |
Синус аргумента. |
-//- |
Sqr(x) |
Квадрат аргумента. |
совпадает с x |
Sqrt(x) |
Квадратный корень аргумента. |
вещественный |
Trunc(x) |
Целая часть вещественного числа. |
-//- |
При разработке программного обеспечения для численных расчетов не следует допускать следующие основные ошибки: исчезновение операнда, умножение ошибки и потерю значимости.
Ошибка исчезновения операнда может возникнуть в операциях сложения или вычитания, если один операнд относительно мал по сравнению с другим операндом. Например, при десятичной арифметике с пятью цифрами:
0.1234 x 103+ 0.1234 x 10-4= 0.1234 x 103
второй операнд будет игнорирован вследствие своей малой величины.
Умножение ошибки – это большая абсолютная ошибка, которая может появиться при использовании арифметики с плавающей точкой, даже если относительная ошибка мала. Обычно это является результатом операции умножения или деления. Рассмотрим вычисление x*x:
0.1234 x 103* 0.1234 x 103= 0.1522 x 105
и предположим, что при вычислении x произошла ошибка на единицу младшего разряда, что соответствует абсолютной ошибке 0.1:
0.1235 x 103* 0.1235 x 103= 0.1525 x 105
Абсолютная ошибка теперь равна 30, что на порядок превышает исходную ошибку.
Полная потеря значимости – наиболее грубая ошибка, вызванная вычитанием почти равных чисел:
f1 = 0.12342;
f2 = 0.12346;
В математике f2 – f1 = 0.00004, что, конечно, вполне представимо как четырехразрядное число с плавающей точкой: 0.4000x10-4. Однако программа, выполняющая вычисление разности в четырехразрядном представлении с плавающей точкой даст ответ:
0.1235 – 0.1234 = 0.1000 x 10-3
что даже приблизительно не является приемлемым ответом.
Потеря значимости встречается довольно часто, поскольку проверка на равенство реализуется вычитанием и последующим сравнением с нулем. Следующее выражение для вещественных чисел f1 и f2 недопустимо:
если f1 = f2, тогда...
Правильный способ проверки равенства с плавающей точкой состоит в том, чтобы ввести малую величину epsilon:
если |f2 – f1| < epsilon, тогда...
и затем сравнивать с ней абсолютную разницу.
Ошибки в вычислениях с плавающей точкой часто можно уменьшить изменением порядка действий. Поскольку сложение производится слева направо. Например, для четырехразрядного десятичного вычисления:
1234.0 + 0.5678 + 0.5678 = 1234.0
лучше изменить порядок, чтобы не было исчезновения слагаемых:
0.5678 + 0.5678 + 1234.0 = 1235.0
В качестве другого примера рассмотрим арифметическое тождество:
(x + y)*(x – y) = x2– y2
При вычислении выражения небольшая ошибка, являющаяся результатом сложения и вычитания, значительно возрастает при умножении. При вычислении выражения по формуле x2 – y2 ошибка уменьшается от исчезновения слагаемого, и результат получается более точным.