Н Алгоритмы и структуры данных: учебное пособие / П. А. Назаренко – Самара : ПГУТИ, 2015. <...> Учебное пособие «Алгоритмы и структуры данных» содержит теоретический материал по основным структурам данных и их практической реализации в языках программирования Си/Си++ и Паскаль. <...> Рассмотрены основные алгоритмы обработки структур данных, включая создание и удаление элементов, прохождение, сортировку и поиск, с их реализациями на языках программирования Си/Си++ и Паскаль. <...> С этой целью удобно использовать кольцевую очередь (логический уровень), которая в работающей программе может быть реализована при помощи одномерного массива как непрерывного блока в памяти или при помощи связного списка, допускающего разнесѐнное размещение в памяти своих элементов (физический уровень). <...> По уровню сложности структуры данных разделяются на: 1. простые структуры – обычные переменные или константы стандартных для языков программирования типов, а также динамические переменные этих же типов; 2. наборы однотипных данных – массивы одномерные (или векторы), двумерные (матрицы) и многомерные; 3. составные структуры, отличные от массивов – записи и объекты классов и им подобные структуры; 4. динамические структуры с внутренними связями – связные списки, деревья, графы. <...> С точки зрения архитектуры можно выделить: 1. линейные структуры – одномерные массивы (или векторы), линейные списки, линейные очереди, стеки; 2. прямоугольные структуры – двумерные (матрицы) и многомерные массивы; 3. кольцевые структуры – кольцевые списки, кольцевые очереди, некоторые реализа9 ции графов; 4. ветвящиеся структуры – деревья различных видов, некоторые реализации графов; 5. сетевые структуры – графы. <...> 1.2 – Составные статические структуры данных Неоднородные (агрегативные) Простые записи Вариантные записи Объединения Объекты 13 Данные динамической структуры Файлы Текстовые Типизированные Нетипизированные Линейной структуры Односвязные Очередь <...>
Алгоритмы_и_структуры_данных_Учебное_пособие.pdf
УДК 004.65+ 004.43
ББК 32.973
Н 19
Рекомендовано к изданию методическим советом ПГУТИ,
протокол № от . .2015 г.
Рецензент:
профессор кафедры ИВТ ПГУТИ,
к. т. н., доцент Алексеев А. П.
Назаренко, П. А.
Н Алгоритмы и структуры данных: учебное пособие / П. А. Назаренко – Самара :
ПГУТИ, 2015. – 196 с.
Учебное пособие «Алгоритмы и структуры данных» содержит теоретический материал
по основным структурам данных и их практической реализации в языках программирования
Си/Си++ и Паскаль. Приведена классификация структур данных. Рассмотрены основные
алгоритмы обработки структур данных, включая создание и удаление элементов, прохождение,
сортировку и поиск, с их реализациями на языках программирования Си/Си++ и Паскаль.
Учебное
пособие разработано в соответствии с Федеральным государственным образовательным
стандартом высшего профессионального образования по направлению подготовки
02.03.03 – «Математическое обеспечение и администрирование информационных систем»
и предназначено для студентов третьего курса факультета информационных систем и
технологий, а также для студентов других специальностей, изучающих и использующих
структуры данных и алгоритмы их обработки, преподавателей, магистрантов и аспирантов.
ISBN
Назаренко П. А., 2015
3
Стр.3
Содержание
Введение …………………………………………………....
1. Понятие о структурах данных ………………………….
1.1. Основные определения …………………………….
1.2. Уровни структур данных …………………………..
1.3. Классификация структур данных ………………….
1.4. Информация и ее представление в памяти ЭВМ ....
2. Простые структуры и типы данных …………………...
2.1. Понятие о типах данных …………………………...
2.2. Перечисляемый тип данных ……………………….
2.3. Стандартные типы данных ………………………...
2.4. Указатели …………………………………………....
2.5. Алгоритмы обработки простых структур данных ..
3. Линейные статические структуры данных ……………
3.1. Массивы ……………………………………………..
3.2. Динамические массивы …………………………….
3.3. Многомерные массивы …………………………….
3.4. Связь массивов с указателями ……………………..
3.5. Строки ……………………………………………….
3.6. Массивы указателей ………………………………..
3.7. Интерпретация составных описателей ……………
3.8. Алгоритмы обработки статических линейных
структур ......................................................................
4. Ссылки. Временные структуры данных ……………….
5. Составные типы данных ………………………………..
5.1. Структуры ………………………………………..…
5.2. Битовые поля ………………………………………..
5.3. Объединения ………………………………………..
6. Файлы ……………………………………………………
7. Очереди ………………………………………………….
7.1. Кольцевая очередь ………………………………….
7.2. Приоритетная очередь ……………………………...
7.3. Дек …………………………………………………...
8. Стеки …………………………………………….....….…
9. Связные списки …………………………………………
9.1. Линейный односвязный список …………………...
9.2. Линейный двусвязный список ……………………..
9.3. Операции с двусвязным списком ………………….
9.4. Кольцевые списки ………………………………….
9.5. Процедуры работы с двусвязным кольцевым
списком на языке Си++ …………………………….
9.6. Многосвязные списки ……………………………...
10. Древовидные структуры данных ……………………..
10.1. Классификация ……………………………………
10.2. Двоичные деревья поиска ………………………...
10.3. Операции с деревьями …………………………….
10.4. Сбалансированные деревья ………………………
10.5. Многоключевые деревья ………………………….
11. Элементы теории графов ……………………………...
11.1. Способы представления графов ………………….
11.2. Алгоритмы на графах ……………………………..
5
8
8
9
10
17
20
20
22
22
30
38
41
41
42
43
46
49
50
51
53
56
59
59
62
63
67
72
76
80
81
83
90
92
100
101
103
106
108
111
112
113
117
135
143
145
145
154
4
Стр.4
12. Поиск …………………………………………………...
12.1. Последовательный поиск …………………………
12.2. Двоичный поиск …………………………………..
12.3. Специальные виды поиска ………………………..
13. Сортировка ……………………………………………..
13.1. Классификация алгоритмов сортировки ……...…
13.2. Пузырьковая сортировка …………………………
13.3. Сортировка отбором ………………………………
13.4. Сортировка вставками …………………………….
13.5. Алгоритм Шелла …………………………………..
13.6. Алгоритм быстрой сортировки …………………..
13.7. Параллельная сортировка Бэтчера ……………….
Заключение ………………………………………………...
Библиографический список ………………………………
158
158
160
163
166
166
169
174
177
180
184
188
192
193
5
Стр.5