Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» идругих экономических специальностей, изучающих информатику и информационные технологии. Ил. 64. Библиогр.: 6 назв icon

Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» идругих экономических специальностей, изучающих информатику и информационные технологии. Ил. 64. Библиогр.: 6 назв



Смотрите также:
  1   2   3   4   5   6   7   8   9   ...   18


УДК 681.31 (031)


Л - 38


Лойко В.И. Структуры и алгоритмы обработки данных. Учебное пособие для вузов.- Краснодар: КубГАУ. 2000. - 261 с., ил.


Учебное пособие разработано на основе лекций по курсу "Структуры и алгоритмы обработки данных в ЭВМ", преподаваемых автором студентам различных специальностей. В теоретической части пособия изложены основные положения теории алгоритмов и структур данных для персональных ЭВМ. Главное внимание в пособии уделено оперативным структурам.

Рассмотрены простые типы данных и такие структуры, как статические, полустатические и динамические. В динамических структурах данных выделены линейные и нелинейные связные списки.

Изложены и проанализированы основные алгоритмы сортировки и поиска данных в различных структурах.

В практической части учебного пособия приведены методические указания к лабораторным работам и курсовому проектированию.

Учебное пособие предназначено для студентов специальности 351400 – «Прикладная информатика (по областям)» и других экономических специальностей, изучающих информатику и информационные технологии.

Ил. 64. Библиогр.: 6 назв.


Рецензенты: проф., д-р техн. наук В. И. Ключко

(зав. кафедрой ВТ и АСУ, КубГТУ)

проф., д-р экон. наук М.И. Семенов

(зав. кафедрой АИТ, КубГАУ)


© Кубанский государственный

аграрный университет


СОДЕРЖАНИЕ



Введение 9

часть 1.
введение в теорию структур данных и алгоритмов их обработки 10


1.Типы данных 11

1.1 Целый тип - INTEGER 11

1.2 Вещественный тип - REAL 12

1.3 Логический тип - BOOLEAN 13

1.4 Символьный тип - CHAR 13

1.5 Указательный тип - POINTER 13

1.6 Стандартные типы пользователя 14

1.6.1 Перечисляемый 14

1.6.2 Диапазонный или интервальный 14

^ 2. Статические и полустатические структуры данных 16

2.1 Уровни представления данных 17

2.2 Классификация структур данных 18

2.3 Статические структуры данных 18

2.3.1 Векторы 18

2.3.2 Массивы 19

2.3.3 Записи 19

2.3.4 Таблицы 21

2.4 Полустатические структуры данных 22

2.4.1 Стеки 22

2.4.2 Очередь 24

2.4.3 Дек 29

^ 3. Динамические структуры данных 31

3.1 Связные списки 31

3.1.1 Односвязные списки 32

3.1.2 Кольцевой односвязный список 32

3.1.3 Двусвязный список 33

3.1.4 Кольцевой двусвязный список 33

3.2 Реализация стеков с помощью односвязных списков 34

3.3 Организация операций Getnode, Freenode и утилизация освободившихся элементов 36

3.3.1 Операция GetNode 37

3.3.2 Операция FreeNode 37

3.3.3 Утилизация освободившихся элементов в многосвязных списках 37

3.4 Односвязный список, как самостоятельная структура данных 37

3.4.1 Вставка и извлечение элементов из списка 39

3.4.2 Примеры типичных операций над списками 40

3.4.3 Элементы заголовков в списках 41

3.5 Нелинейные связанные структуры 42

^ 4. Рекурсивные структуры данных 46

4.1 Деревья 46

4.1.1 Представление деревьев 47

4.2 Бинарные деревья 48

4.2.1 Сведение m-арного дерева к бинарному 49

4.2.2 Основные операции с деревьями 51

4.2.3 Алгоритм создания дерева бинарного поиска 52

4.2.4 Прохождение бинарных деревьев 53

5. Поиск 56

5.1 Последовательный поиск 56

5.2.Индексно-последовательный поиск 58

5.3. Эффективность последовательного поиска 59

5.4. Эффективность индексно-последовательного поиска 60

5.5 Методы оптимизации поиска 60

5.5.1 Переупорядочивание таблицы поиска путем перестановки найденного элемента в начало списка 61

5.5.2. Метод транспозиции 62

5.5.3. Дерево оптимального поиска 63

5.6 Бинарный поиск (метод деления пополам) 64

5.7. Поиск по бинарному дереву 66

5.8 Поиск со вставкой (с включением) 67

5.9 Поиск с удалением 67

6. Сортировка 71

6.1. Сортировка методом прямого включения 72

6.2 Сортировка методом прямого выбора 73

6.3. Сортировка с помощью прямого обмена (пузырьковая сортировка) 74

6.4. Улучшенные методы сортировки 75

6.4.1. Быстрая сортировка (Quick Sort) 76

6.4.2 Сортировка Шелла (сортировка с уменьшающимся шагом) 77

^ 7. ПРЕОБРАЗОВАНИЕ КЛЮЧЕЙ (РАССТАНОВКА) 80

7.1. Выбор функции преобразования 80

7.2. Алгоритм 81

часть 2.
практикум по сруктурам и алгоритмам обработки данных в эвм 84


методическое руководство к лабораторным работам 85

Организационно-методические указания 85

Лабораторная работа № 1. "ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ" 86

Краткая теория 86

Алгоритм 87

Задания 88

Лабораторная работа № 2. "СПИСКОВЫЕ СТРУКТУРЫ ДАННЫХ" 89

Краткая теория 89

^ Линейные однонаправленные списки 90

Алгоритм 90

Удаление элемента из начала односвязного списка 91

Вставка элемента в список 92

Удаление элемента из односвязного списка 92

Задания 93

Лабораторная работа № 3. "КОЛЬЦЕВЫЕ СПИСКИ" 94

Краткая теория 94

Алгоритм 94

^ Вставка элемента в кольцевой список 94

Удаление элемента из кольцевого списка 95

Задания 96

Лабораторная работа № 4. "МОДЕЛЬ МАССОВОГО ОБСЛУЖИВАНИЯ" 98

Краткая теория 98

Алгоритм 99

^ Процедура прибавления элемента в начало списка. 99

Процедура удаления из начала списка. 99

Процедура прибавления элемента в список. 99

Процедура удаления из списка 99

Задания 99

Лабораторная работа № 5. "БИНАРНЫЕ ДЕРЕВЬЯ(основные процедуры)" 101

Краткая теория 101

Алгоритм 103

^ Процедура создания бинарного дерева 103

Процедуры "обхода" дерева 104

Процедура поиска по бинарному дереву 105

Процедура включения элемента в дерево 106

^ Процедура удаления элемента из бинарного дерева 106

Задания 108

Лабораторная работа № 6 . "СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ" 110

Краткая теория 110

Алгоритм 111

Задания 112

Лабораторная работа № 7. "СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВЫБОРА" 113

Краткая теория 113

Алгоритм 116

Задания 116

Лабораторная работа № 8."СОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ОБМЕНА" 118

Краткая теория 118

Алгоритм 119

^ Алгоритм пузырькового метода 119

Алгоритм метода Quiksort 120

Задания 120

Лабораторная работа № 9. "СОРТИРОВКА С ПОМОЩЬЮ ДЕРЕВА" 122

Краткая теория 122

Алгоритм 123

^ Создание дерева бинарного поиска : 124

Обход дерева слева - направо 125

Задания 125

Лабораторная работа № 10. "ИССЛЕДОВАНИЕ МЕТОДОВ ЛИНЕЙНОГО И БИНАРНОГО ПОИСКА" 127

Краткая теория 127

Алгоритм 127

^ Линейный поиск 127

Поиск делением пополам (двоичный поиск). 128

Задания 130

Лабораторная работа №11. "ИССЛЕДОВАНИЕ МЕТОДОВ ОПТИМИЗАЦИИ ПОИСКА " 131

Краткая теория 131

Алгоритм 132

^ Переупорядочение путем перестановки в начало списка 132

Метод транспозиции 133

Задания 134

Лабораторная работа № 12. "ПОИСК ПО ДЕРЕВУ С ВКЛЮЧЕНИЕМ" 135

Краткая теория 135

Алгоритм 135

Задания 137

Лабораторная работа № 13. "ПОИСК ПО ДЕРЕВУ С ИСКЛЮЧЕНИЕМ" 138

Краткая теория 138

Алгоритм 139

Задания 141

^ ТЕСТЫ К ЛАБОРАТОРНЫМ РАБОТАМ 142

Методическое руководство к курсовой
работе 152


1 Требования к курсовой работе 152

2. Примерный перечень курсовых работ 153

3. Пример выполнения курсовой работы 153

3.1 Постановка задачи 153

3.2 Краткая теория 153

3.3 Метод исследования 156

3.4 Результаты исследования 156

3.5 Контрольный пример 157

3.6 Выводы 158

3.7 Описание процедур, используемых в программе 158

Заключение 168

Литература 169

приложение.
Тесты с ответами 170




Введение



Компьютер - это машина, которая обрабатывает информацию. Изучение науки об ЭВМ предполагает изучение того, каким образом эта информация организована внутри ЭВМ, как она обрабатывается и как может быть использована. Следовательно, для изучения предмета студенту особенно важно понять концепции организации информации и работы с ней.

Так как вычислительная техника базируется на изучении информации, то первый возникающий вопрос заключается в том, что такое информация. К сожалению, несмотря на то , что концепция информации является краеугольным камнем всей науки о вычислительной технике, на этот вопрос не может быть дано однозначного ответа. В этом контексте понятие "информация" в вычислительной технике сходно с понятием "точка", "прямая" и "плоскость" в геометрии - все это неопределенные термины, о которых могут быть сделаны некоторые утверждения и выводы, но которые не могут быть объяснены в терминах более элементарных понятий.

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

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

Число битов, необходимых для кодирования символа в конкретной вычислительной машине, называется размером байта, а группа битов в этом числе называется байтом. Размер байта в большинстве ЭВМ равен 8.

Память вычислительной машины представляет собой совокупность битов. в любой момент функционирования в ЭВМ каждый из битов памяти имеет значение 0 или 1 (сброшен или установлен). Состояние бита называется его значением или содержимым.

Биты в памяти ЭВМ группируются в элементы большего размера, например в байты. В некоторых ЭВМ несколько байтов объединяются в группы, называемые словами. Каждому такому элементу назначается адрес, который представляет собой имя, идентифицирующее конкретный элемент памяти среди аналогичных элементов. Этот адрес обычно числовой. Он называется ячейкой, а содержимое ячейки есть значение битов, которые ее составляют.

Итак, мы видим, что информация в ЭВМ сама по себе не имеет конкретного смысла. С некоторой конкретной битовой комбинацией может быть связано любое смысловое значение. Именно интерпретация битовой комбинации придает ей заданный смысл.

Метод интерпретации битовой информации часто называется типом данных. Каждая ЭВМ имеет свой набор типов данных.

Важно осознавать роль, выполняемую спецификацией типа в языках высокого уровня. Именно посредством подобных объявлений программист указывает на то, каким образом содержимое памяти ЭВМ интерпретируется программой. Эти объявления детерминируют объем памяти, необходимый для размещения отдельных элементов, способ интерпретации этих элементов и другие важные детали. Объявления также сообщают интерпретатору точное значение используемых символов операций.






страница1/18
Дата конвертации24.10.2013
Размер1,64 Mb.
ТипУчебное пособие
  1   2   3   4   5   6   7   8   9   ...   18
Разместите кнопку на своём сайте или блоге:
rud.exdat.com


База данных защищена авторским правом ©exdat 2000-2012
При копировании материала укажите ссылку
обратиться к администрации
Документы