Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)»


НазваниеУчебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)»
страница1/40
Дата публикации05.05.2013
Размер1.69 Mb.
ТипУчебное пособие
userdocs.ru > Информатика > Учебное пособие
  1   2   3   4   5   6   7   8   9   ...   40


УДК 681.31 (031)
Л - 38

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

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

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

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

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

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

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


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

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

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

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


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

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

СОДЕРЖАНИЕ



Введение 10

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


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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.1 Векторы 23

2.3.2 Массивы 24

2.3.3 Записи 24

2.3.4 Таблицы 27

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

2.4.1 Стеки 29

2.4.2 Очередь 31

2.4.3 Дек 39

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

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

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

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

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

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

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

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

3.3.1 Операция GetNode 49

3.3.2 Операция FreeNode 50

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

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

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

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

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

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

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

4.1 Деревья 62

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

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

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

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

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

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

5. Поиск 74

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7.2. Алгоритм 110

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


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

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

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

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

Алгоритм 119

Задания 121

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

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

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

Алгоритм 125

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

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

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

Задания 128

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

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

Алгоритм 131

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

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

Задания 133

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

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

Алгоритм 137

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

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

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

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

Задания 138

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

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

Алгоритм 143

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

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

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

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

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

Задания 150

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

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

Алгоритм 155

Задания 156

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

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

Алгоритм 162

Задания 163

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

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

Алгоритм 167

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

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

Задания 168

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

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

Алгоритм 172

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

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

Задания 174

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

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

Алгоритм 178

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

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

Задания 182

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

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

Алгоритм 186

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

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

Задания 188

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

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

Алгоритм 192

Задания 194

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

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

Алгоритм 197

Задания 200

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

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


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

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

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

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

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

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

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

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

3.6 Выводы 226

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

Заключение 238

Литература 240

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



  1   2   3   4   5   6   7   8   9   ...   40

Похожие:

Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconМетодическое пособие по выполнению студенческих научных работ, подготовке...
Методическое пособие предназначено для студентов Кубанского государственного аграрного университета, обучающихся по специальностям:...
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconКомпьютерное моделирование в экономике
Учебное пособие предназначено для студентов специальности "Прикладная информатика в экономике". Однако оно может быть полезным для...
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconВопросы к зачету по дисциплине «Предпринимательское право» для студентов...
Коммерческие организации: понятие, организационно-правовые формы, правоспособность
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconУчебное пособие для студентов специальности 010503 и направления 010500 Москва 2007
«Математическое обеспечение и администрирование информационных систем») и к выпускной квалификационной работе бакалавра по направлению...
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconУчебное пособие подготовлено в соответствии с типовой программой...
Учебное пособие предназначено для студентов обучающихся по специальности 060101 лечебное дело
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconУчебное пособие Специальности 100300 «Эксплуатация судовых энергетических установок»
Учебное пособие предназначено для студентов, изучающих двигатели внутреннего сгорания, выполняющих курсовые проекты по современным...
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconУчебное пособие Курс лекций Для студентов высших учебных заведений...
Учебное пособие предназначено для студентов вузов, но может быть полезно и тем, кто самостоятельно изучает экономическую теорию
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconУчебное пособие для студентов лечебного факультета
Учебное пособие предназначено для студентов и преподавателей медицинских вузов
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconН. И. Бухтояров, к э. н., доцент кафедры педагогики и социально-политических наук
Учебное пособие Предназначено для студентов, обучающихся по специальности
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconТомский государственный университет кафедра новой, новейшей истории...
...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница