Лойко в и структуры и алгоритмы обработки данных краснодар 2004 261 с

УДК 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 арабских цифр и некоторое число других графических символов, например, знаки пунктуации.

Прокрутить вверх