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




НазваниеУчебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)»
страница1/40
Дата21.12.2012
Размер1.69 Mb.
ТипУчебное пособие
  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 «Прикладная информатика ( в сфере сервиса )»
Учебное пособие предназначено для студентов очной и заочной форм обучения специальности 351400 «Прикладная информатика ( в сфере...
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconУчебное пособие предназначено для студентов очной и заочной форм обучения специальности 351400 «Прикладная информатика ( в сфере сервиса )»
Учебное пособие предназначено для студентов очной и заочной форм обучения специальности 351400 «Прикладная информатика ( в сфере...
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconРабочая программа по дисциплине «логика» для специальности 351400 Прикладная информатика (по областям) Форма обучения: очная
Рабочая программа составлена на основании гос впо специальности 351400 «Прикладная информатика (по областям)» (квалификация – информатик...
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconРабочая программа по дисциплине «логика» для специальности 351400 Прикладная информатика (по областям) Форма обучения: очная
Рабочая программа составлена на основании гос впо специальности 351400 «Прикладная информатика (по областям)» (квалификация – информатик...
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconПрограмма итоговых квалификационных экзаменов для студентов очной формы обучения специальности 351400 "Прикладная информатика (по областям)"
Прикладная информатика (в экономике) и в соответствии с требованиями Государственного образовательного стандарта высшего профессионального...
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconУчебное пособие для студентов специальности 351400 Прикладная информатика (в менеджменте)
Организация дипломного проектировния
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconМетодические указания по дипломному проектированию
Содержание отчета о преддипломной практике для специальности 351400 «Прикладная информатика (по областям)» 15
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconУчебное пособие адресовано студентам, обучающимся по специальности 080801 (351400) «Прикладная информатика в экономике»
Список сокращений
Учебное пособие предназначено для студентов специальности 351400 «Прикладная информатика (по областям)» iconИнформатика по специальности 351400 «прикладная информатика (по областям)» Индекс
Специфика артикуляции звуков, интонации, акцентуации и ритма нейтральной речи в изучаемом языке; основные особенности полного стиля...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница