1.3 СИСТЕМЫ СЧИСЛЕНИЯ
Чтобы обеспечить соответствующую основу для изучения структур
данных следует обсудить существующие типы систем счислений:
позиционные и непозиционные. <...> Непозиционные системы счисления
Числа используются для символического представления количества
объектов. <...> В зависимости от отсутствия или наличия явно заданных связей между
элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы,
массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры (связные списки). <...> В FORTRAN (Integer I), в PASCAL (I:integer), в C (int I) в
результате описания типа будет выделена память для соответствующих
переменных. <...> Таблица 2.1
Тип
shortint
integer
longint byte
word
comp
Диапазон значений
Машинное представление
-128 . <...> Для
представления чисел со знаком определены следующие типы SHORTINT,
INTEGER, LONGINT. <...> Перечислимый тип представляет собой
упорядоченный тип данных, определяемый программистом, т.е. программист
перечисляет все значения, которые может принимать переменная этого типа. <...> А) Интервальный тип от символьного: определение кода символа и,
наоборот, символа по его коду. <...> Б) Интервальный тип от перечислимого: определение порядкового
номера идентификатора по его значению и, наоборот, по номеру
идентификатора - его значение. <...> Выделение памяти на
этапе компиляции является столь удобным свойством статических структур,
что в ряде задач программисты используют их даже для представления
объектов, обладающих изменчивостью. <...> Дескриптор необходим, например, в том
случае, когда граничные значения индексов элементов массива неизвестны
на этапе компиляции, и, следовательно, выделение памяти для массива
может быть выполнено только на этапе выполнения программы (как в языке
PL/1, ALGOL-60). <...> Представление вектора в памяти
Здесь: @ Имя -адрес вектора или, что тоже самое, адрес первого элемента
вектора,
Sizeof(тип)-размер слота (количество байтов памяти для записи
одного элемента вектора),
(k-n)*Sizeof(тип) - относительный адрес элемента с номером k, или, что
тоже самое, смещение <...>
Алгоритмические_языки_и_технологии_программирования_на_языках_высокого_уровня_[Электронный_ресурс]_.pdf
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА»
(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)
В. Д. Еленев, М. Ю. Гоголев.
АЛГОРИТМИЧЕСКИЕ ЯЗЫКИ И ТЕХНОЛОГИИ
ПРОГРАММИРОВАНИЯ НА ЯЗЫКАХ ВЫСОКОГО УРОВНЯ
ЭЛЕКТРОННЫЙ КУРС ЛЕКЦИЙ
Рекомендовано для студентов высших учебных заведений,
обучающихся по направлению 160400.68 «Ракетные комплексы и
космонавтика» магистерская программа «Проектирование и
конструирование космических мониторинговых и транспортных
систем».
С А М А Р А
2010
Стр.1
УДК 629.7.017.1 (075)
Авторы: Еленев Валерий Дмитриевич,
Гоголев Михаил Юрьевич.
Рекомендовано для студентов высших учебных заведений, обучающихся по направлению
160400.68 «Ракетные комплексы и космонавтика» магистерская программа
«Проектирование и конструирование космических мониторинговых и транспортных
систем».
Разработано на кафедре летательных аппаратов СГАУ.
2
Стр.2
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ.................................................................................................................................................................5
1 CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ.....................................................................................................6
1.1 ПОНЯТИЕ СТРУКТУР ДАННЫХ И АЛГОРИТМОВ....................................................................................................6
1.2 ИНФОРМАЦИЯ И ЕЁ ПРЕДСТАВЛЕНИЕ В ПАМЯТИ ................................................................................................8
1.2.1 Природа информации.................................................................................................................................8
1.2.2. Хранение информации...............................................................................................................................8
1.3 СИСТЕМЫ СЧИСЛЕНИЯ ......................................................................................................................................10
1.3.1. Непозиционные системы счисления ......................................................................................................10
1.3.2 Позиционные системы счисления ..........................................................................................................10
1.3.3 Изображение чисел в позиционной системе счисления.......................................................................11
1.3.4 Перевод чисел из одной системы счисления в другую..........................................................................11
1.4 КЛАССИФИКАЦИЯ СТРУКТУР ДАННЫХ..............................................................................................................12
1.5 ОПЕРАЦИИ НАД СТРУКТУРАМИ ДАННЫХ ..........................................................................................................15
1.6 СТРУКТУРНОСТЬ ДАННЫХ И ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ....................................................................16
2. ПРОСТЫЕ СТРУКТУРЫ ДАННЫХ..............................................................................................................19
2.1. ЧИСЛОВЫЕ ТИПЫ..............................................................................................................................................19
2.1.1.Целые типы...............................................................................................................................................19
2.1.2. Вещественные типы...............................................................................................................................23
2.1.3. Десятичные типы...................................................................................................................................29
2.2. БИТОВЫЕ ТИПЫ................................................................................................................................................31
2.3. ЛОГИЧЕСКИЙ ТИП.............................................................................................................................................33
2.4. СИМВОЛЬНЫЙ ТИП ...........................................................................................................................................33
2.5. ПЕРЕЧИСЛИМЫЙ ТИП .......................................................................................................................................34
2.6. ИНТЕРВАЛЬНЫЙ ТИП ........................................................................................................................................35
2.7. УКАЗАТЕЛИ.......................................................................................................................................................36
2.7.1. Физическая структура указателя.........................................................................................................37
2.7.2. Представление указателей в языках программирования ....................................................................38
2.7.3. Операции над указателями.....................................................................................................................38
3. СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ....................................................................................................41
3.1. ВЕКТОРЫ...........................................................................................................................................................42
3.2. МАССИВЫ.........................................................................................................................................................44
3.2.1. Логическая структура............................................................................................................................44
3.2.2. Физическая структура ...........................................................................................................................44
3.2.3. Операции ..................................................................................................................................................46
3.2.4. Адресация массивов с помощью векторов Айлиффа ...........................................................................47
3.2.5. Специальные массивы.............................................................................................................................48
3.3. МНОЖЕСТВА.....................................................................................................................................................54
3.3.1. Числовые множества .............................................................................................................................55
3.3.2. Символьные множества.........................................................................................................................55
3.3.3. Множество из элементов перечислимого типа...................................................................................56
3.3.4. Множество от интервального типа....................................................................................................56
3.3.5. Операции над множествами..................................................................................................................57
3.4. ЗАПИСИ.............................................................................................................................................................57
3.4.1. Логическое и машинное представление записей ..................................................................................57
3.4.2. Операции над записями...........................................................................................................................59
3.5. ЗАПИСИ С ВАРИАНТАМИ...................................................................................................................................59
3.6. ТАБЛИЦЫ..........................................................................................................................................................61
3.7. ОПЕРАЦИИ ЛОГИЧЕСКОГО УРОВНЯ НАД СТАТИЧЕСКИМИ СТРУКТУРАМИ. ПОИСК..........................................63
3.7.1. Последовательный или линейный поиск................................................................................................64
3.7.2. Бинарный поиск .......................................................................................................................................64
3.8 ОПЕРАЦИИ ЛОГИЧЕСКОГО УРОВНЯ НАД СТАТИЧЕСКИМИ СТРУКТУРАМИ. СОРТИРОВКА. ................................66
3.8.1. Сортировки выборкой.............................................................................................................................67
3.8.2. Сортировки включением.........................................................................................................................72
3.8.3. Сортировки распределением..................................................................................................................84
3.9. ПРЯМОЙ ДОСТУП И ХЕШИРОВАНИЕ .................................................................................................................89
3.9.1. Таблицы прямого доступа ......................................................................................................................89
3.9.2. Таблицы со справочниками.....................................................................................................................90
3.9.3. Хешированные таблицы и функции хеширования ................................................................................90
3
Стр.3
3.9.4. Проблема коллизий в хешированных таблицах.....................................................................................92
4 ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ ......................................................................................101
4.1 ХАРАКТЕРНЫЕ ОСОБЕННОСТИ ПОЛУСТАТИЧЕСКИХ СТРУКТУР.......................................................................101
4.2 СТЕКИ..............................................................................................................................................................101
4.2.1 Логическая структура стека................................................................................................................101
4.2.2 Машинное представление стека и реализация операций...................................................................102
4.2.3 Стеки в вычислительных системах .....................................................................................................104
4.3 ОЧЕРЕДИ FIFO.................................................................................................................................................106
4.3.1 Логическая структура очереди ............................................................................................................106
4.3.2 Машинное представление очереди FIFO и реализация операций......................................................106
4.3.3 Очереди с приоритетами......................................................................................................................108
4.3.4 Очереди в вычислительных системах ..................................................................................................108
4.4 ДЕКИ................................................................................................................................................................109
4.4.1 Логическая структура дека ..................................................................................................................109
4.4.2 Деки в вычислительных системах ........................................................................................................110
4.5 СТРОКИ............................................................................................................................................................111
4.5.1 Логическая структура строки .............................................................................................................111
4.5.2 Операции над строками ........................................................................................................................112
4.5.3 Представление строк в памяти ..........................................................................................................114
5 ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ.....................................................126
5.1 СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ ДАННЫХ В ПАМЯТИ..............................................................................................126
5.2.1 Машинное представление связных линейных списков ........................................................................127
5.2.2 Реализация операций над связными линейными списками.................................................................129
5.2.3. Применение линейных списков .............................................................................................................136
5.3 МУЛЬТИСПИСКИ..............................................................................................................................................140
5.4 НЕЛИНЕЙНЫЕ РАЗВЕТВЛЕННЫЕ СПИСКИ ........................................................................................................142
5.4.1 Основные понятия..................................................................................................................................142
5.4.2 Представление списковых структур в памяти. .................................................................................144
5.4.3 Операции обработки списков...............................................................................................................146
5.5 ЯЗЫК ПРОГРАММИРОВАНИЯ LISP...................................................................................................................155
5.6 УПРАВЛЕНИЕ ДИНАМИЧЕСКИ ВЫДЕЛЯЕМОЙ ПАМЯТЬЮ.................................................................................156
6 НЕЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ ...................................................................................................162
6.1 ГРАФЫ .............................................................................................................................................................162
6.1.1 Логическая структура, определения....................................................................................................162
6.1.2 Машинное представление оpгpафов....................................................................................................163
6.2 ДЕРЕВЬЯ...........................................................................................................................................................168
6.2.1 Основные определения ...........................................................................................................................168
6.2.2 Логическое представление и изображение деревьев. ........................................................................169
6.2.3 Бинарные деревья. .................................................................................................................................170
6.2.4 Представление любого дерева, леса бинарными деревьями..............................................................172
6.2.5 Машинное представление деревьев в памяти ЭВМ. ..........................................................................173
6.2.6 Основные операции над деревьями. ......................................................................................................176
6.3 ПРИЛОЖЕНИЯ ДЕРЕВЬЕВ..................................................................................................................................190
6.3.1 Деревья Хаффмена (деревья минимального кодирования) .................................................................190
6.3.2 Деревья при работе с арифметическими выражениями ...................................................................191
6.3.3 Формирование таблиц символов...........................................................................................................193
6.4 СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ.......................................................................................................................199
ЛИТЕРАТУРА.......................................................................................................................................................222
4
Стр.4
ВВЕДЕНИЕ
Они служат базовыми элементами любой
машинной программы. В организации
структур данных и процедур их обработки
заложена возможность проверки
правильности работы программы.
Никлас Вирт.
Без понимания структур данных и алгоритмов невозможно создать
сколько-нибудь серьезный программный продукт. И слова эпиграфа служат
тому подтверждением. Поэтому главная задача данного учебного пособия
заключалась в следующем:
• показать все разнообразие имеющихся структур данных,
представление их в памяти на физическом уровне, т.е. "как это
сделано внутри", и логическом уровне, или как эти структуры
реализованы в языках программирования;
• выполняемые над ними операции физического и логического
уровней;
• показать значение структурного подхода к разработке алгоритмов,
продемонстрировать порядок разработки алгоритмов наиболее, по
мнению авторов, интересных задач.
Нельзя сказать, что такие вопросы не рассматривались в литературе, но
с полной уверенностью можно отметить, что так сконцентрировано, так
подробно и в доступной для понимания форме, с таким количеством
демонстрационных примеров ни в каком из известных изданиях не сделано.
В пособии приводится классификация структур данных, обширная
информация о физическом и логическом представлении структур данных
всех классов памяти ПВМ: простых, статических, полустатических,
динамических; исчерпывающая информация об операциях над всеми
перечисленными структурами. Приведено достаточно большое количество
алгоритмов особенно важных операций, реализованных в виде процедур и
функций, написанных на Turbo Pascal, которые могут быть применены как
"заготовки" в самостоятельных разработках студентов и программистов.
5
Стр.5