- •Лекція 1. Структури даних. Основні визначення та поняття
- •1.1. Термінологія
- •1.2. Типи даних
- •1.3. Рівні організації даних
- •1.4. Представлення даних
- •1.5. Класифікація структур даних
- •1.6. Основні операції над структурами даних
- •1.7. Документування даних
- •Лекція 2. Алгоритми. Складність алгоритмів.
- •2.1. Зображення алгоритмів
- •2.2. Складність алгоритмів
- •2.3. Класи алгоритмів
- •2.4. Документація алгоритмів
- •Лекція 3. Методи сортування .
- •3.1. Задача сортування
- •3.2.Метод простої вибірки.
- •3.3. Метод бульбашки.
- •3.4.Швидкий метод сортування
- •Лекція 4 методи сортування (продовження)
- •4.5. Сортування включенням
- •4.6. Сортування розподілом
- •4.7. Сортування злиттям або об’єднанням
- •4.8. Сортування підрахунком
- •Лекція 5 нелінійні структури даних
- •5.1. Дерева
- •5.1.1. Бінарні дерева
- •5.1.2. Алгоритм обходу дерева
- •5.1.3. Зображення в пам‘яті комп‘ютера графоподібних структур
- •Лекція 6 методи сортування на деревах
- •6.1. Сортування на деревах
- •6.1.2. Пірамідальне сортування.
- •Питання до першого модуля
- •Тема 1. Основні визначення та поняття. Термінологія. Класифікація структур даних. Основні операції над структурами даних.
- •Тема 2. Поняття алоритму. Зображення алгоритмів. Алгоритмічна складність. Поліноміальна та неполіноміальна складність алгоритмів..
- •Тема 3-4. Алгоритми сортування
- •Тема 5-6. Дерева. Основні визначення та поняття. Бінарні дерева. Зображення в пам‘яті еом графоподібних структур. Алгоритми обходу дерев.Висхідні, нисхідні, змішані алгоритми обходу дерев.
- •Лекція 7. Лінійні структури даних. Стеки, черги і деки.
- •7.1. Стеки
- •7.1.1. Реалізація стеку на базі масиву
- •7.2. Черги
- •7.2.1. Використання черги в програмуванні
- •7.2.2. Реалізація черги на базі масиву
- •7.3. Деки
- •Лекція 8. Лінійні структури даних.
- •8.1. Лінійні списки . Основні визначення та поняття
- •8.2. Однонаправлені списки
- •8.3. Двонаправлені списки
- •8.4. Циклічні списки
- •Лекція 9. Масиви, множини, кортежі
- •9.1. Масиви
- •9.2. Множини I кортежі
- •9.2.1. Реалізація множини
- •9.3. Зберігання множин і масивів
- •9.4. Зберігання розріджених матриць
- •Лекція 10. Нелінійні структури даних
- •10.1. Таблиці
- •10.1.1. Зображення таблиць
- •Лекція 11. Нелінійні структури даних
- •11.1. Спискові структури
- •11.1.1. Ієрархічні списки
- •11.1.2. Організація спискових структур
- •11.2. Сіткові структури
- •Лекція 12 пошук даних.
- •12.1. Послідовний пошук
- •12.2. Двійковий пошук
- •12.2.1. Дерева порівнянь на векторній пам‘яті.
- •12.3. Прямий пошук стрічки
- •12.4. Алгоритм Кнута, Моріса і Прата пошуку в стрічці.
- •12.5. Алгоритм Бойера - Мура пошуку в стрічці
- •12.6. Алгоритми з поверненням
- •Лекція 13 пошук у таблицях
- •13.1. Пошук у таблицях з обчислюваними адресами
- •13.2. Пошук у таблицях з прямим доступом
- •13.3. Пошук у Хеш-таблицях
- •Питання до другого модуля
- •Тема 9 Лінійні списки. Основні визначення та поняття. Однонаправлені списки. Двонаправлені списки. Циклічні списки. Організація списків.
- •Тема 10 Масиви. Множини I кортежі. Зберігання множин і масивів. Зберігання розріджених матриць. Операції з масивами, множинами та кортежами
Лекція 1. Структури даних. Основні визначення та поняття
1.1. Термінологія
Під терміном "дані" розуміється інформація - сукупність фактів, явищ і подій, що представляють інтерес і підлягають реєстрації та обробці - подана у вигляді, який дозволяє автоматизувати процес збору, зберігання і обробки її на комп‘ютері.
Отже, дані відображають і представляють реальний світ. Але при розв'язуванні конкретних проблем маємо справу не з усім реальним світом, а тільки з деякими його об'єктами. Тобто об'єктаминазиваємо елементи реального світу, інформацію про які ми запам'ятовуємо; сукупність таких об'єктів утворює предметну область. Прикладами об‘єктів можуть бути люди, що перелічені в будь-якій платіжній відомості; деталі, які виготовляє завод; банківські рахунки та інше.
Очевидно, що об’єкти відрізняються один від одного. Їх необхідно описати характеристиками, які є найважливішими для даної задачі. Такі характеристики називають атрибутами. Атрибути має кожний об’єкт. Об’єкти відрізняються один від одного значеннями атрибутів. Значення елемента даних повинно бути пов'язане з конкретним атрибутом конкретного об’єкта.
При зображенні даних у пам'яті комп‘ютера одному елементу даних виділяється певна одиниця пам'яті, яку переважно називають полем. Сукупність полів, в яких записана послідовність елементів даних, що розглядаються як одне ціле (наприклад, один рядок накладної), називають записом. Сукупність записів утворює файл. Під файлом здебільшого розуміють сукупність записів, організованих на зовнішній пам'яті комп‘ютера.
Сама сукупність даних, що систематизована певним чином, має ім'я, запам'ятовується в пам'яті комп‘ютера більш-менш постійно, використовується багатьма користувачами і не залежить від програм користувачів, називається базою даних (БД).
Для модифікації та використання цих даних багатьма користувачами необхідне програмне забезпечення - система управління базами даних (СУБД). Головна її роль полягає у можливості оперувати даними незалежно від способу їх зберігання.
Банком даних називають систему програмних, мовних, організаційних і технічних засобів, призначених для нагромадження і колективного використання даних.
Отже, між інформаційною моделлю реального світу і даними в комп‘ютері існує взаємно однозначна відповідність: одній предметній області відповідає один файл; число об’єктів у предметній області дорівнює кількості записів у файлі; число атрибутів, що описує об’єкт, дорівнює кількості полів у кожному записі. БД відображає стан об’єктів і їх відношень в даний момент часу у предметній області, що розглядається.
1.2. Типи даних
Елементи даних звичайно розділяють на дві основні групи: скаляри й структури. До скалярів відносяться прапори, коди, числа й слова; до структур - масиви, таблиці, списки, стеки, множини й записи. Структури формуються зі скалярних даних, згрупованих відповідно до певних правил. Зовнішні до програмної системи дані також формуються зі структурованих елементів.
У той час як деякі мови програмування забезпечені засобами для формування різних даних, інші дозволяють тільки явно задати певну структуру. Способи опису або зображення складних структур даних, прийняті в людській практиці, часто відрізняються від способів їх опису для використання в комп‘ютері. Програмісти настільки звикли до роботи з масивами, що іноді забувають, що структура масиву звичайно не відображає структуру даних, що зберігаються в ньому. При використанні масиву мається на увазі, що, по-перше, відоме число його елементів, по-друге, усі елементи належать тому самому типу й мають той самий розмір і, нарешті, по-третє, доступ до елементів масиву організує відповідно до їхніх положень у масиві. Реальні множини даних рідко бувають однотипними. Порядок використання даних може виявитися несуттєвим або може визначатися значеннями даних. Таким чином, можна зробити висновок про те, що мови програмування накладають штучні обмеження на дані.