ВВЕДЕНИЕ. Рассмотрим переходный процесс при включении цепи R, C на постоянное напряжение (рис

СОДЕРЖАНИЕ

ВВЕДЕНИЕ....................................................................................................................................... 4

1. CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ............................................................................ 4

1.1. Понятие структур данных и алгоритмов................................................................... 4

1.2. Информация и ее представление в памяти.............................................................. 7

1.2.1. Природа информации.............................................................................................. 7

1.2.2. Хранение информации............................................................................................. 7

1.3. Системы счисления.......................................................................................................... 9

1.3.1. Непозиционные системы счисления................................................................... 9

1.3.2. Позиционные системы счисления...................................................................... 9

1.3.3. Изображение чисел в позиционной системе счисления............................ 10

1.3.4. Перевод чисел из одной системы счисления в другую............................. 11

1.4. Классификация структур данных................................................................................. 11

1.5. Операции над структурами данных........................................................................... 14

1.6. Структурность данных и технология программирования.................................. 15

2. ПРОСТЫЕ СТРУКТУРЫ ДАННЫХ.................................................................................... 17

2.1. Числовые типы................................................................................................................. 18

2.1.1. Целые типы................................................................................................................ 18

2.1.2. Вещественные типы............................................................................................... 22

2.1.3. Десятичные типы.................................................................................................... 30

2.1.4. Операции над числовыми типами.................................................................... 32

2.2. Битовые типы.................................................................................................................. 33

2.3. Логический тип.............................................................................................................. 34

2.4. Символьный тип............................................................................................................. 35

2.5. Перечислимый тип....................................................................................................... 36

2.6. Интервальный тип.......................................................................................................... 37

2.7. Указатели........................................................................................................................... 38

2.7.1. Физическая структура указателя.......................................................................... 39

2.7.2. Представление указателей в языках программирования......................... 40

2.7.3. Операции над указателями.................................................................................. 41

3. СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ........................................................................... 43

3.1. Векторы.............................................................................................................................. 44

3.2. Массивы............................................................................................................................. 47

3.2.1. Логическая структура............................................................................................. 47

3.2.2. Физическая структура............................................................................................. 47

3.2.3. Операции................................................................................................................... 48

3.2.4. Адресация элементов с помощью векторов Айлиффа............................. 50

3.2.5. Специальные массивы.......................................................................................... 52

3.3. Множества......................................................................................................................... 58

3.3.1. Числовые множества.............................................................................................. 59

3.3.2. Символьные множества........................................................................................ 60

3.3.3. Множество из элементов перечислимого типа........................................... 60

3.3.4. Множество от интервального типа................................................................... 61

3.3.5. Операции над множествами............................................................................... 62

3.4. Записи................................................................................................................................ 62

3.4.1. Логическое и машинное представление записей........................................ 62

3.4.2. Операции над записями....................................................................................... 64

3.5. Записи с вариантами..................................................................................................... 64

3.6. Таблицы............................................................................................................................. 67

3.7. Операции логического уровня над статическими структурами. Поиск..... 68

3.7.1. Последовательный или линейный поиск...................................................... 69

3.7.2. Бинарный поиск...................................................................................................... 69

3.8. Операции логического уровня над статическими структурами. Сортировка 71

3.8.1. Сортировки выборкой............................................................................................ 73

3.8.2. Сортировки включением...................................................................................... 79

3.8.3. Сортировки распределением.............................................................................. 91

3.8.4. Сортировки слиянием........................................................................................... 95

4. Полустатические структуры данных.............................................................................. 98

4.1. Характерные особенности полустатических структур....................................... 98

4.2. Стеки................................................................................................................................... 98

4.2.1. Логическая структура стека.................................................................................. 98

4.2.2. Машинное представление стека и реализация операций......................... 99

4.2.3. Стеки в вычислительных системах................................................................. 101

4.3. Очереди FIFO............................................................................................................... 103

4.3.1. Логическая структура очереди.......................................................................... 103

4.3.2. Машинное представление очереди FIFO и реализация операций..... 103

4.3.3. Очереди с приоритетами................................................................................... 105

4.3.4. Очереди в вычислительных системах.......................................................... 105

4.4. Деки................................................................................................................................... 106

4.4.1. Логическая структура дека................................................................................. 106

4.4.2. Деки в вычислительных системах.................................................................. 108

4.5. Строки............................................................................................................................... 108

4.5.1. Логическая структура строки............................................................................. 108

4.5.2. Операции над строками...................................................................................... 110

4.5.3. Представление строк в памяти......................................................................... 112

5. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ. СВЯЗНЫЕ СПИСКИ............................ 122

5.1. Связное представление данных в памяти............................................................. 122

5.2. Связные линейные списки......................................................................................... 124

5.2.1. Машинное представление связных линейных списков............................ 124

5.2.2. Реализация операций над связными линейными списками................... 126

5.2.3. Применение линейных списков...................................................................... 133

5.3. Мультисписки................................................................................................................ 137

5.4. Нелинейные разветвленные списки...................................................................... 139

5.4.1. Основные понятия................................................................................................. 139

5.4.2. Представление списковых структур в памяти............................................. 141

5.4.3. Операции обработки списков........................................................................... 143

5.5. Язык программирования LISP.................................................................................. 152

5.6. Управление динамически выделяемой памятью.............................................. 153

6. НЕЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ......................................................................... 158

6.1.Графы................................................................................................................................. 158

6.1.1. Логическая структура, определения................................................................ 158

6.1.2. Машинное представление оpгpафов............................................................... 160

6.2. Деревья............................................................................................................................. 164

6.2.1. Основные определения....................................................................................... 164

6.2.2. Логическое представление и изображение деревьев.............................. 166

6.2.3. Бинарные деревья................................................................................................. 167

6.2.4. Представление любого дерева, леса бинарными деревьями............... 168

6.2.5. Машинное представление деревьев в памяти ЭВМ.................................... 171

6.2.6. Основные операции над деревьями............................................................... 174

6.2.7. Приложения деревьев......................................................................................... 188

6.2.8 Деревья Хаффмена (деревья минимального кодирования).................... 188

6.2.9 Деревья при работе с арифметическими выражениями........................... 189

6.2.10 Формирование таблиц символов..................................................................... 192

6.2.11 Сбалансированные деревья................................................................................ 197

Л И Т Е Р А Т У Р А.................................................................................................................. 220

ВВЕДЕНИЕ

Они служат базовыми элементами любой машинной
программы. В организации структур данных и
процедур их обработки заложена возможность
проверки правильности работы программы.
Никлас Вирт

Без понимания структур данных и алгоритмов невозможно создать сколько-нибудь серьезный программный продукт. И слова эпиграфа служат тому подтверждением. Поэтому главная задача данного учебного пособия заключалась в следующем:

· показать все разнообразие имеющихся структур данных, представление их в памяти на физическом уровне, т.е., "как это сделано внутри", и на логическом уровне, т.е., как эти структуры реализованы в языках программирования;

· выполняемые над ними операции физического и логического уровней;

· показать значение структурного подхода к разработке алгоритмов, продемонстрировать порядок разработки алгоритмов наиболее, по мнению авторов, интересных задач.

Нельзя сказать, что такие вопросы не рассматривались в литературе, но с полной уверенностью можно отметить, что так сконцентрировано, так подробно и в доступной для понимания форме, с таким количеством демонстрационных примеров ни в каком из известных нам изданий этого не сделано.

В пособии приводится классификация структур данных, обширная информация о физическом и логическом представлении структур данных всех классов памяти ЭВМ: простых, статических, полустатических, динамических; исчерпывающая информация об операциях над всеми перечисленными структурами. Приведено достаточно большое количество алгоритмов выполнения особенно важных операций, реализованных в виде процедур и функций, написанных на Turbo Pascal, которые могут быть применены как "заготовки" в самостоятельных разработках студентов и программистов.