Алгоритми та структури даних [Текст] : навч. посіб. / Т. О. Коротєєва ; МОН України

НЧЛ - Навчальний посібник

МД

Бібліогр.: с. 276

1. Структури даних. основні визначення та поняття... 7
1.1. Термінологія... 7
1.2. Класифікація структур даних ... 9
1.3. Документування даних... 12
Контрольні запитання та вправи ... 13
Приклади тестових питань... 13
2. Рівні організації даних... 16
2.1. Логічна організація даних... 17
2.2. Представлення даних... 20
2.3. Фізична організація даних ... 26
Контрольні запитання та вправи ... 32
Приклади тестових питань... 33
3. Лінійні структури даних. Стек, черга, дек... 34
3.1. Стек... 34
3.1.1. Реалізація стека ... 38
3.1.2. Використання функції assert... 42
3.2. Черга ... 44
3.2.1. Реалізація черги на основі масиву ... 47
3.3. Дек... 48
Контрольні запитання ... 49
Приклади тестових питань... 49
4. Масиви, множини, кортежі ... 51
4.1. Масиви... 51
4.2. Множини i кортежі ... 53
4.3. Зберігання множин і масивів ... 56
Контрольні запитання та вправи ... 58
Приклади тестових питань... 59
5. Лінійні списки ... 60
5.1. Основні визначення та поняття ... 60
5.2. Однонапрямлені списки ... 62
5.3. Двонапрямлені списки ... 64
5.4. Циклічні списки ... 65
Контрольні запитання та вправи ... 66
Приклади тестових питань... 67
6. Нелінійні структури даних... 69
6.1. Таблиці... 69
6.2. Дерева...71
6.2.1. Бінарні дерева...73
6.2.2. Алгоритми обходу дерева...74
6.2.3. Зображення в пам’яті комп’ютера графоподібних структур ...75
6.3. Спискові структури...77
6.3.1. Ієрархічні списки ...78
6.3.2. Організація спискових структур...79
6.4. Сіткові структури...81
Контрольні запитання та вправи...84
Приклади тестових питань ...85
7. Алгоритми. Складність алгоритмів ...88
7.1. Визначення та способи зображення алгоритмів...88
7.2. Складність алгоритмів ...90
7.3. Класи алгоритмів ...93
7.4. Способи реалізації алгоритмів ...96
7.4.1. Ітерація й рекурсія...97
7.4.2. Паралельна обробка...99
7.4.3. Співпрограми...99
7.5. Документація алгоритмів ...100
Контрольні запитання...101
Приклади тестових питань ...102
8. Методи сортування...103
8.1. Задача сортування ...103
8.2. Метод простої вибірки...103
8.3. Метод бульбашки...105
8.4. Швидкий метод сортування ...107
8.5. Сортування включенням ...109
8.6. Сортування розподілом ...111
8.7. Сортування злиттям або об’єднанням...112
8.8. Сортування підрахунком...114
Контрольні запитання та вправи...116
Приклади тестових питань ...116
9. Пошук даних ...118
9.1. Послідовний пошук ...118
9.2. Двійковий пошук ...120
9.3. Прямий пошук рядка ...121
9.4. Алгоритм Кнута, Моріса і Прата пошуку в рядку...123
9.5. Алгоритм Бойера – Мура пошуку в рядку...125
9.6. Пошук у таблиці...128
9.6.1. Пошук у таблицях з обчислюваними адресами... 128
Контрольні запитання ... 131
Приклади тестових питань... 131
10. Типи даних у мові C + +... 134
10.1. Класифікація та оголошення типів даних... 134
10.2. Арифметичні типи даних ... 136
10.3. Типи рядків... 137
10.3.1. Масиви символів... 137
10.3.2. Тип рядків AnsiString... 138
10.4. Перелічені типи... 139
10.5. Множини ... 141
10.6. Вказівники... 144
10.7. Посилання... 147
10.8. Масиви в С++... 148
10.8.1. Одновимірні масиви в С++ ... 148
10.8.2. Багатовимірні масиви ... 151
10.8.3. Операції з масивами, використання масивів як параметрів функцій... 151
10.9. Структури ... 154
10.9.1. Структури в мові С... 154
10.9.2. Самоадресовані структури... 155
10.9.3. Структури в мові С++ ... 157
10.10. Класи... 159
10.10.1. Оголошення класу ... 159
10.10.2. Шаблони класів ... 162
Контрольні запитання та вправи ... 164
Приклади тестових питань... 165
11. Послідовні контейнери в складі стандартної бібліотеки шаблонів ... 168
11.1. Клас vector ... 169
11.2. Клас deque ... 174
11.3. Клас list... 180
11.3.1. Відмінності між методами списків і методами векторів та двосторонніх черг... 184
11.4. Клас queue ... 191
11.5. Клас stack... 194
11.6. Клас BinSearchTree ... 197
11.6.1. Алгоритми обходу двійкового дерева... 203
11.6.2. Двійкові дерева пошуку... 207
Контрольні запитання та вправи ... 208
Приклади тестових питань... 211
12. Асоціативні контейнери у складі стандартної бібліотеки шаблонів ...214
12.1. Клас Set ...214
12.2. Клас Multiset...216
12.3. Клас Mар ...216
12.4. Клас Multimap...217
Контрольні запитання та вправи...218
Приклади тестових питань ...219
13. Похідні контейнери бібліотеки шаблонів ...220
13.1. Клас priority_queue ...220
13.2. Кучі...223
13.3. Алгоритм Хаффмана...231
13.4. Збалансовані двійкові дерева пошуку ...233
13.5. AVL-дерева...238
13.5.1 Застосування AVL-дерева: програма перевірки орфографії...239
Контрольні запитання та вправи...242
Приклади тестових питань ...245
14. Червоно-чорні дерева ...247
14.1. Висота червоно-чорного дерева...250
14.2. Клас rb_tree Hewlett-Packard ...253
14.3. Метод insert класу rb_tree ...256
14.4. Метод erase ...262
Контрольні запитання та вправи...273
Приклади тестових питань ...274
Предметний покажчик...277
Список літератури...278

Викладено основи класифікації структур даних. Докладно розглянуто рівні організації структур даних та найпоширеніші моделі даних. Наведено способи зображення моделей структур даних у пам’яті комп’ютера. Розглянуто алгоритми сортування та пошуку даних, приклади їх реалізації та обґрунтовано алгоритмічну складність. Фрагменти програм студенти можуть використати для самостійного розроблення власних програм під час виконання лабораторних та курсових завдань. Розглянуто реалізацію структур даних на прикладі мови програмування С++ та описано основні контейнери бібліотеки STL. Розділи супроводжуються контрольними запитаннями та задачами для індивідуального виконання.

Посібник рекомендовано для студентів ВНЗ та коледжів, які навчаються за напрямами «Програмна інженерія» або «Комп’ютерні науки».