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

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



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


УДК 681.31 (031)


Л - 38


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


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

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

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

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

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

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


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

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

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

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


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

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


СОДЕРЖАНИЕ



Введение 9

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


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

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

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

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

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

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

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

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

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

^ 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 Дек 38

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

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

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

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

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

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

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

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

3.3.1 Операция GetNode 48

3.3.2 Операция FreeNode 49

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

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

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

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

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

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

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

4.1 Деревья 61

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

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

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

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

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

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

5. Поиск 73

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

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

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

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

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

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

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

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

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

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

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

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

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

Задания 175

Лабораторная работа № 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




Введение



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

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

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

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

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

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

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

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

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

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






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


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