УДК 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 Считается, что все операции над данными этого типа выполняются точно и соответствуют обычным правилам арифметики. Если результат выходит за пределы представимого множества, то вычисления будут прерваны. Такое событие называется переполнением. Числа делятся на знаковые и беззнаковые. Для каждого из них имеется свой диапазон значений: 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 арабских цифр и некоторое число других графических символов, например, знаки пунктуации.