<< Пред. стр. 1 (из 19) След. >>
Список литературы по разделу
УДК 681.31 (031)
Л - 38
Лойко В.И. Структуры и алгоритмы обработки данных. Учебное пособие для вузов.- Краснодар: КубГАУ. 2004. - 261 с., ил.
Учебное пособие разработано на основе лекций по курсу "Структуры и алгоритмы обработки данных в ЭВМ", преподаваемых автором студентам различных специальностей. В теоретической части пособия изложены основные положения теории алгоритмов и структур данных для персональных ЭВМ. Главное внимание в пособии уделено оперативным структурам.
Рассмотрены простые типы данных и такие структуры, как статические, полустатические и динамические. В динамических структурах данных выделены линейные и нелинейные связные списки.
Изложены и проанализированы основные алгоритмы сортировки и поиска данных в различных структурах.
В практической части учебного пособия приведены методические указания к лабораторным работам и курсовому проектированию.
Учебное пособие предназначено для студентов специальности 351400 – «Прикладная информатика (по областям)» и других экономических специальностей, изучающих информатику и информационные технологии.
Ил. 64. Библиогр.: 6 назв.
Рецензенты: проф., д-р техн. наук В. И. Ключко
(зав. кафедрой ВТ и АСУ, КубГТУ)
проф., д-р экон. наук М.И. Семенов
(зав. кафедрой АИТ, КубГАУ)
© Кубанский государственный
аграрный университет
СОДЕРЖАНИЕ
ВВЕДЕНИЕ 8
ЧАСТЬ 1. ВВЕДЕНИЕ В ТЕОРИЮ СТРУКТУР ДАННЫХ И АЛГОРИТМОВ ИХ ОБРАБОТКИ 10
1.ТИПЫ ДАННЫХ 11
1.1 ЦЕЛЫЙ ТИП - INTEGER 12
1.2 ВЕЩЕСТВЕННЫЙ ТИП - REAL 13
1.3 ЛОГИЧЕСКИЙ ТИП - BOOLEAN 14
1.4 СИМВОЛЬНЫЙ ТИП - CHAR 14
1.5 УКАЗАТЕЛЬНЫЙ ТИП - POINTER 15
1.6 СТАНДАРТНЫЕ ТИПЫ ПОЛЬЗОВАТЕЛЯ 16
1.6.1 Перечисляемый 16
1.6.2 Диапазонный или интервальный 17
2. СТАТИЧЕСКИЕ И ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ 19
2.1 УРОВНИ ПРЕДСТАВЛЕНИЯ ДАННЫХ 20
2.2 КЛАССИФИКАЦИЯ СТРУКТУР ДАННЫХ 21
2.3 СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ 22
2.3.1 Векторы 22
2.3.2 Массивы 23
2.3.3 Записи 23
2.3.4 Таблицы 26
2.4 ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ 27
2.4.1 Стеки 28
2.4.2 Очередь 30
2.4.3 Дек 39
3. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ 41
3.1 СВЯЗНЫЕ СПИСКИ 42
3.1.1 Односвязные списки 42
3.1.2 Кольцевой односвязный список 43
3.1.3 Двусвязный список 44
3.1.4 Кольцевой двусвязный список 44
3.2 РЕАЛИЗАЦИЯ СТЕКОВ С ПОМОЩЬЮ ОДНОСВЯЗНЫХ СПИСКОВ 45
3.3 ОРГАНИЗАЦИЯ ОПЕРАЦИЙ GETNODE, FREENODE И УТИЛИЗАЦИЯ ОСВОБОДИВШИХСЯ ЭЛЕМЕНТОВ 49
3.3.1 Операция GetNode 50
3.3.2 Операция FreeNode 51
3.3.3 Утилизация освободившихся элементов в многосвязных списках 51
3.4 ОДНОСВЯЗНЫЙ СПИСОК, КАК САМОСТОЯТЕЛЬНАЯ СТРУКТУРА ДАННЫХ 52
3.4.1 Вставка и извлечение элементов из списка 53
3.4.2 Примеры типичных операций над списками 55
3.4.3 Элементы заголовков в списках 58
3.5 НЕЛИНЕЙНЫЕ СВЯЗАННЫЕ СТРУКТУРЫ 59
4. РЕКУРСИВНЫЕ СТРУКТУРЫ ДАННЫХ 63
4.1 ДЕРЕВЬЯ 63
4.1.1 Представление деревьев 65
4.2 БИНАРНЫЕ ДЕРЕВЬЯ 65
4.2.1 Сведение m-арного дерева к бинарному 67
4.2.2 Основные операции с деревьями 69
4.2.3 Алгоритм создания дерева бинарного поиска 70
4.2.4 Прохождение бинарных деревьев 72
5. ПОИСК 75
5.1. ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК 76
5.2. ИНДЕКСНО-ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК 78
5.3. ЭФФЕКТИВНОСТЬ ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА 80
5.4. ЭФФЕКТИВНОСТЬ ИНДЕКСНО-ПОСЛЕДОВАТЕЛЬНОГО ПОИСКА 81
5.5. МЕТОДЫ ОПТИМИЗАЦИИ ПОИСКА 82
5.5.1. Переупорядочивание таблицы поиска путем перестановки найденного элемента в начало списка 83
5.5.2. Метод транспозиции 84
5.5.3. Дерево оптимального поиска 85
5.6 БИНАРНЫЙ ПОИСК (МЕТОД ДЕЛЕНИЯ ПОПОЛАМ) 87
5.7. ПОИСК ПО БИНАРНОМУ ДЕРЕВУ 90
5.8 ПОИСК СО ВСТАВКОЙ (С ВКЛЮЧЕНИЕМ) 91
5.9 ПОИСК С УДАЛЕНИЕМ 92
6. СОРТИРОВКА 97
6.1. СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ 98
6.2 СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВЫБОРА 101
6.3. СОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ОБМЕНА (ПУЗЫРЬКОВАЯ СОРТИРОВКА) 102
1.4. УЛУЧШЕННЫЕ МЕТОДЫ СОРТИРОВКИ 105
6.4.1. Быстрая сортировка (Quick Sort) 105
6.4.2 Сортировка Шелла (сортировка с уменьшающимся шагом) 106
7. ПРЕОБРАЗОВАНИЕ КЛЮЧЕЙ (РАССТАНОВКА) 110
7.1. ВЫБОР ФУНКЦИИ ПРЕОБРАЗОВАНИЯ 110
7.2. АЛГОРИТМ 112
ЧАСТЬ 2. ПРАКТИКУМ ПО СРУКТУРАМ И АЛГОРИТМАМ ОБРАБОТКИ ДАННЫХ В ЭВМ 116
МЕТОДИЧЕСКОЕ РУКОВОДСТВО К ЛАБОРАТОРНЫМ РАБОТАМ 117
ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЕ УКАЗАНИЯ 117
ЛАБОРАТОРНАЯ РАБОТА № 1. "ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ" 119
КРАТКАЯ ТЕОРИЯ 119
АЛГОРИТМ 121
ЗАДАНИЯ 123
ЛАБОРАТОРНАЯ РАБОТА № 2. "СПИСКОВЫЕ СТРУКТУРЫ ДАННЫХ" 124
КРАТКАЯ ТЕОРИЯ 124
Линейные однонаправленные списки 126
АЛГОРИТМ 127
Удаление элемента из начала односвязного списка 128
Вставка элемента в список 129
Удаление элемента из односвязного списка 130
ЗАДАНИЯ 131
ЛАБОРАТОРНАЯ РАБОТА № 3. "СПИСКОВЫЕ СТРУКТУРЫ ДАННЫХ" 132
КРАТКАЯ ТЕОРИЯ 132
АЛГОРИТМ 133
Вставка элемента в кольцевой список 133
Удаление элемента из кольцевого списка 134
ЗАДАНИЯ 135
ЛАБОРАТОРНАЯ РАБОТА № 4. "МОДЕЛЬ МАССОВОГО ОБСЛУЖИВАНИЯ" 137
КРАТКАЯ ТЕОРИЯ 137
АЛГОРИТМ 139
Процедура прибавления элемента в начало списка. 139
Процедура удаления из начала списка. 139
Процедура прибавления элемента в список. 139
Процедура удаления из списка 140
ЗАДАНИЯ 140
ЛАБОРАТОРНАЯ РАБОТА № 5. "БИНАРНЫЕ ДЕРЕВЬЯ(ОСНОВНЫЕ ПРОЦЕДУРЫ)" 142
КРАТКАЯ ТЕОРИЯ 142
АЛГОРИТМ 145
Процедура создания бинарного дерева 145
Процедуры "обхода" дерева 147
Процедура поиска по бинарному дереву 148
Процедура включения элемента в дерево 149
Процедура удаления элемента из бинарного дерева 151
ЗАДАНИЯ 153
ЛАБОРАТОРНАЯ РАБОТА № 6 . "СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ" 156
КРАТКАЯ ТЕОРИЯ 156
АЛГОРИТМ 158
ЗАДАНИЯ 159
ЛАБОРАТОРНАЯ РАБОТА № 7. "СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВЫБОРА" 161
КРАТКАЯ ТЕОРИЯ 161
АЛГОРИТМ 165
ЗАДАНИЯ 167
ЛАБОРАТОРНАЯ РАБОТА № 8."СОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ОБМЕНА" 168
КРАТКАЯ ТЕОРИЯ 168
АЛГОРИТМ 170
Алгоритм пузырькового метода 170
Алгоритм метода Quiksort 170
ЗАДАНИЯ 171
ЛАБОРАТОРНАЯ РАБОТА № 9. "СОРТИРОВКА С ПОМОЩЬЮ ДЕРЕВА" 174
КРАТКАЯ ТЕОРИЯ 174
АЛГОРИТМ 176
Создание дерева бинарного поиска : 177
Обход дерева слева - направо 178
ЗАДАНИЯ 179
ЛАБОРАТОРНАЯ РАБОТА № 10. "ИССЛЕДОВАНИЕ МЕТОДОВ ЛИНЕЙНОГО И БИНАРНОГО ПОИСКА" 182
КРАТКАЯ ТЕОРИЯ 182
АЛГОРИТМ 183
Линейный поиск 183
Поиск делением пополам (двоичный поиск). 185
ЗАДАНИЯ 188
ЛАБОРАТОРНАЯ РАБОТА №11. "ИССЛЕДОВАНИЕ МЕТОДОВ ОПТИМИЗАЦИИ ПОИСКА " 189
КРАТКАЯ ТЕОРИЯ 189
АЛГОРИТМ 191
Переупорядочение путем перестановки в начало списка 191
Метод транспозиции 192
ЗАДАНИЯ 193
ЛАБОРАТОРНАЯ РАБОТА № 12. "ПОИСК ПО ДЕРЕВУ С ВКЛЮЧЕНИЕМ" 196
КРАТКАЯ ТЕОРИЯ 196
АЛГОРИТМ 197
ЗАДАНИЯ 199
ЛАБОРАТОРНАЯ РАБОТА № 13. "ПОИСК ПО ДЕРЕВУ С ИСКЛЮЧЕНИЕМ" 201
КРАТКАЯ ТЕОРИЯ 201
АЛГОРИТМ 202
ЗАДАНИЯ 205
ТЕСТЫ К ЛАБОРАТОРНЫМ РАБОТАМ 207
МЕТОДИЧЕСКОЕ РУКОВОДСТВО К КУРСОВОЙ РАБОТЕ 222
1 ТРЕБОВАНИЯ К КУРСОВОЙ РАБОТЕ 222
2. ПРИМЕРНЫЙ ПЕРЕЧЕНЬ КУРСОВЫХ РАБОТ 223
3. ПРИМЕР ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ 224
3.1 Постановка задачи 224
3.2 Краткая теория 224
3.3 Метод исследования 228
3.4 Результаты исследования 229
3.5 Контрольный пример 231
3.6 Выводы 231
3.7 Описание процедур, используемых в программе 232
ЗАКЛЮЧЕНИЕ 244
ЛИТЕРАТУРА 246
ПРИЛОЖЕНИЕ. ТЕСТЫ С ОТВЕТАМИ 247
ВВЕДЕНИЕ
Компьютер - это машина, которая обрабатывает информацию. Изучение науки об ЭВМ предполагает изучение того, каким образом эта информация организована внутри ЭВМ, как она обрабатывается и как может быть использована. Следовательно, для изучения предмета студенту особенно важно понять концепции организации информации и работы с ней.
Так как вычислительная техника базируется на изучении информации, то первый возникающий вопрос заключается в том, что такое информация. К сожалению, несмотря на то , что концепция информации является краеугольным камнем всей науки о вычислительной технике, на этот вопрос не может быть дано однозначного ответа. В этом контексте понятие "информация" в вычислительной технике сходно с понятием "точка", "прямая" и "плоскость" в геометрии - все это неопределенные термины, о которых могут быть сделаны некоторые утверждения и выводы, но которые не могут быть объяснены в терминах более элементарных понятий.
Базовой единицей информации является бит, который может принимать два взаимоисключающих значения. Если устройство может находиться более чем в двух состояниях, то тот факт, что оно находится в одном из этих состояний, уже требует нескольких битов информации.
Для представления двух возможных состояний некоторого бита используются двоичные цифры - нуль и единица.
Число битов, необходимых для кодирования символа в конкретной вычислительной машине, называется размером байта, а группа битов в этом числе называется байтом. Размер байта в большинстве ЭВМ равен 8.
Память вычислительной машины представляет собой совокупность битов. в любой момент функционирования в ЭВМ каждый из битов памяти имеет значение 0 или 1 (сброшен или установлен). Состояние бита называется его значением или содержимым.
Биты в памяти ЭВМ группируются в элементы большего размера, например в байты. В некоторых ЭВМ несколько байтов объединяются в группы, называемые словами. Каждому такому элементу назначается адрес, который представляет собой имя, идентифицирующее конкретный элемент памяти среди аналогичных элементов. Этот адрес обычно числовой. Он называется ячейкой, а содержимое ячейки есть значение битов, которые ее составляют.
Итак, мы видим, что информация в ЭВМ сама по себе не имеет конкретного смысла. С некоторой конкретной битовой комбинацией может быть связано любое смысловое значение. Именно интерпретация битовой комбинации придает ей заданный смысл.
Метод интерпретации битовой информации часто называется типом данных. Каждая ЭВМ имеет свой набор типов данных.
Важно осознавать роль, выполняемую спецификацией типа в языках высокого уровня. Именно посредством подобных объявлений программист указывает на то, каким образом содержимое памяти ЭВМ интерпретируется программой. Эти объявления детерминируют объем памяти, необходимый для размещения отдельных элементов, способ интерпретации этих элементов и другие важные детали. Объявления также сообщают интерпретатору точное значение используемых символов операций.
ЧАСТЬ 1.
ВВЕДЕНИЕ В ТЕОРИЮ СТРУКТУР ДАННЫХ И АЛГОРИТМОВ ИХ ОБРАБОТКИ
1.ТИПЫ ДАННЫХ
В математике принято классифицировать переменные в соответствие с некоторыми важными характеристиками. Мы различаем вещественные, комплексные и логические переменные ,переменные ,представляющие собой отдельные значения, множества значений или множества множеств. В обработке данных понятие классификации играет такую же, если не большую роль. Мы будем придерживаться того принципа, что любая константа, переменная, выражение или функция относятся к некоторому типу.
Фактически тип характеризует множество значений, которые может принимать некоторая переменная или выражение и которые может формировать функция.
В большинстве языков программирования различают стандартные типы данных и типы, заданные пользователем. К стандартным относят 5 типов:
a) целый (INTEGER);
b) вещественный (REAL) ;
c) логический (BOOLEAN);
d) символьный (CHAR);
e) указательный (POINTER).
К пользовательским относят 2 типа:
a) перечисляемый;
b) диапазонный.
Любой тип данных должен быть охарактеризован областью значений и допустимыми операциями над этим типом данных.
1.1 Целый тип - INTEGER
Этот тип включает некоторое подмножество целых, размер которого варьируется от машины к машине. Если для представления целых чисел в машине используется n разрядов, причем используется дополнительный код, то допустимые числа должны удовлетворять условию -2 n-1<= x< 2 n-1.
Считается, что все операции над данными этого типа выполняются точно и соответствуют обычным правилам арифметики. Если результат выходит за пределы представимого множества, то вычисления будут прерваны. Такое событие называется переполнением.
Числа делятся на знаковые и беззнаковые. Для каждого из них имеется свой диапазон значений:
a)(0..2n-1) для беззнаковых чисел
b) (-2N-1.. 2N-1-1) для знаковых.
При обработке машиной чисел, используется формат со знаком. Если же машинное слово используется для записи и обработки команд и указателей, то в этом случае используется формат без знака.
Операции над целым типом:
a) Сложение.
b) Вычитание.
c) Умножение.
d) Целочисленное деление.
e) Нахождение остатка по модулю.
f) Нахождение экстремума числа (минимума и максимума)
g) Реляционные операции (операции сравнения) (<,>,<=, >=,=,<>)
Примеры:
A div B = C
A mod B = D
C * B + D = A
7 div 3 = 2
7 mod 3 = 1
Во всех операциях, кроме реляционных, в результате получается целое число.
1.2 Вещественный тип - REAL
Вещественные типы образуют ряд подмножеств вещественных чисел, которые представлены в машинных форматах с плавающей точкой. Числа
в формате с плавающей точкой характеризуются целочисленными значениями мантиссы и порядка, которые определяют диапазон изменения
и количество верных знаков в представлении чисел вещественного типа.
X = +/- M * q(+/-P) - полулогарифмическая форма представления числа, показана на рисунке 2.
937,56 = 93756 * 10-2 = 0,93756 * 103
Удвоенная точность необходима для того, чтобы увеличить точность мантиссы.
1.3 Логический тип - BOOLEAN
Стандартный логический тип Boolean (размер-1 байт) представляет собой тип данных, любой элемент которого может принимать лишь 2 значения: True и False.
Над логическими элементами данных выполняются логические операции. Основные из них:
a) Отрицание (NOT)
b) Конъюнкция (AND)
c) Дизъюнкция (OR)
Таблица истинности основных логических функций.
Логические значения получаются также при реляционных операциях с целыми числами.
1.4 Символьный тип - CHAR
Тип CHAR содержит 26 прописных латинских букв и 26 строчных, 10 арабских цифр и некоторое число других графических символов, например, знаки пунктуации.
<< Пред. стр. 1 (из 19) След. >>
Список литературы по разделу