Розділ 13. Структури даних, колекції і класи-прототипи
У даному розділі приводиться огляд основних структур даних і їх реалізація в бібліотеці .NET у вигляді колекцій. Крім того, описуються класи-прототипи (generics), часткові типи (partial types) і типи, що обнуляються (nullable types).
13.1. Абстрактні структури даних
Найчастіше в програмах використовуються наступні структури даних: масив, список, стек, черга, бінарне дерево, хеш-таблиця, граф і множина. Далі надані короткі характеристики кожній їз цих структур.
Масив - це кінцева сукупність однотипних величин. масив займає безперервну область пам'яті і надає доступ до своїх елементів по індексу. Пам'ять під масив виділяється до початку роботи з ним і згодом не змінюється.
У списку кожен елемент пов'язаний з наступним і, можливо, з попереднім. У першому випадку список називається однозвязковим, в другому - двозвязковим. Також застосовуються терміни однонапрямковим і двонапрямковим. Якщо останній елемент зв'язати покажчиком з першим, виходить кільцевий список. Кількість елементів в списку може змінюватися в процесі роботи програми.
Кожен елемент списку містить ключ, що ідентифікує цей елемент. Ключ зазвичай буває або цілим числом, або рядком і є частиною даних, що зберігаються в кожному елементі списку. Як ключ в процесі роботи із списком можуть виступати різні частини даних. Наприклад, якщо створюється список із записів, що містять прізвище, рік народження, стаж роботи і стать, будь-яка частина запису може виступати як ключ: при впорядковуванні списку по зростанню ключа буде прізвище, а при пошуку, наприклад, ветеранів праці ключем можна зробити стаж. Ключі різних елементів списку можуть збігатися.
Над списками можна виконувати наступні операції:
додавання елементу в кінець списку;
читання елементу із заданим ключем;
вставка елементу в задане місце списку;
видалення елементу із заданим ключем;
впорядковування списку по ключу.
Список не забезпечує довільний доступ до елементу, тому при виконанні операцій читання, вставки і видалення виконується послідовний перебір елементів, поки не буде знайдений елемент із заданим ключем. Для списків великого об'єму перебір елементів може займати значний час, оскільки середній час пошуку елементу пропорційний кількості елементів в списку.
Стек - це окремий випадок однонапрямкового списку, додавання елементів в який і вибірка з якого виконуються з одного кінця, званого вершиною стека. Інші операції із стеком не визначені. При вибірці елемент виключається із стека. Говорять, що стек реалізує принцип обслуговування LIFO (Last In - First Out, останнім прийшов - першим пішов). Стек найпростіше уявити собі як закриту з одного кінця вузьку трубу, в яку кидають м'ячики. Дістати перший кинутий м'ячик можна тільки після того, як вийняті всі останні. Стеки широко застосовуються в системному програмному забезпеченні, компіляторах, в різних рекурсивних алгоритмах.
Черга - це окремий випадок однонапрямкового списку, додавання елементів в який виконується в один кінець, а вибірка - з іншого кінця. Інші операції з чергою не визначені. При вибірці елемент виключається з черги. Говорять, що чергу реалізує принцип обслуговування FIFO (First In - First Out, першим прийшов - першим пішов). Чергу найпростіше уявити собі, постоявши в ній час-другий. У програмуванні черги застосовуються, наприклад, в моделюванні, диспетчеризації завдань операційною системою.
Бінарне дерево - це динамічна структура даних, що складається з вузлів, кожен з яких містить окрім даних не більше двох посилань на різні бінарні піддерева. На кожен вузол є рівно одне посилання. Початковий вузол називається коренем дерева.
Приклад бінарного дерева приведений на рис. 13.1 (корінь зазвичай зображається зверху). Вузол, що не має піддерев, називається листом. Витікаючи вузли називаються предками, що входять - нащадками. Висота дерева визначається кількістю рівнів, на яких розташовуються його вузли.
Якщо дерево організоване таким чином, що для кожного вузла всі ключі його лівого піддерева менші ключа цього вузла, а всі ключі його правого піддерева - більші, воно називається деревом пошуку. Однакові ключі не допускаються.
У дереві пошуку можна знайти елемент по ключу, рухаючись від кореня і переходячи на ліве або праве піддерево залежно від значення ключа в кожному вузлі. Такий пошук набагато ефективніший пошуку за списком, оскільки час пошуку визначається висотою дерева, а вона пропорційна двійковому логарифму кількості вузлів.
Втім, швидкість пошуку в значній мірі залежить від порядку формування дерева: якщо на вхід подається впорядкована або майже впорядкована послідовність ключів, дерево вироджується в список. Для прискорення пошуку застосовується процедура балансування дерева, що формує дерево, піддерева якого розрізняються не більше ніж на один елемент. Бінарні дерева застосовуються для ефективного пошуку і сортування даних.
Хеш-таблиця, асоціативний масив, або словник - це масив, доступ до елементів якого здійснюється не по номеру, а по деякому ключу. Можна сказати, що це таблиця, що складається з пар “ключ-значення” (таблиця 13.1). Хеш-таблиця ефективно реалізує операцію пошуку значення по ключу. При цьому ключ перетвориться в число (хеш - код), яке використовується для швидкого знаходження потрібного значення в хеш-таблиці.
Рис. 13.1. Приклад бінарного дерева пошуку
Таблиця 13.1
Приклад хеш-таблиці
|
Ключ |
Значення |
|
boy |
хлопчик |
|
girl |
дівчинка |
|
dog |
собачка |
Перетворення виконується за допомогою хеш-функціі, або функції розстановки. Ця функція проводить які-небудь перетворення внутрішнього представлення ключа. Наприклад, обчислює середнє арифметичне кодів символів ключа. Якщо хеш-функція розподіляє сукупність можливих ключів рівномірно по множині індексів масиву, то доступ до елементу по ключу виконується майже так само швидко, як в масиві. Якщо хеш-функція генерує для різних ключів однакові хеш-коди, час пошуку зростає і стає порівнянним з часом пошуку в списку.
Сенс хеш-функціі полягає в тому, щоб відобразити широку множину ключів у вужчу множину індексів. При цьому неминуче виникають так звані колізії, коли хеш-функція формує для двох різних елементів одні і ті ж хеш-коди.
Граф - це сукупність вузлів і ребер, що сполучають різні вузли. Наприклад, можна уявити собі карту автомобільних доріг як граф з містами, як вузли і шосе між містами, як ребра. Множина реальних практичних завдань можна описати в термінах графів, що робить їх структурою даних, часто використовуваною при написанні програм.
Множина - це неврегульована сукупність елементів. Для множин визначені операції перевірки приналежності елементу множині, включення і виключення елементу, а також об'єднання, перетину і віднімання множин.
Описані структури даних називаються абстрактними, оскільки в них не задається реалізація допустимих операцій.
У бібліотеках більшості сучасних об'єктно-орієнтованих мов програмування представлені стандартні класи, що реалізовують основні абстрактні структури даних. Такі класи називаються колекціями, або контейнерами. Для кожного типу колекції визначені методи роботи з її елементами, не залежні від конкретного типу даних, які зберігаються в колекції, тому один і той же вид колекції можна використовувати для зберігання даних різних типів. Використання колекцій дозволяє скоротити терміни розробки програм і підвищити їх надійність.
Кожен вид колекції підтримує свій набір операцій над даними, і швидкодія цих операцій може бути різною. Вибір виду колекції залежить від того, що потрібно робити з даними в програмі і які вимоги пред'являються до її швидкодії. Наприклад, при необхідності частої вставки і видалення елементів з середини послідовності слід використовувати список, а не масив, а якщо включення елементів виконується головним чином в кінець або початок послідовності - чергу. Тому вивчення можливостей стандартних колекцій і їх грамотне застосування є необхідними умовами створення ефективних і професійних програм.
У бібліотеці .NET визначена множина стандартних класів, що реалізовують більшість перерахованих раніше абстрактних структур даних.
Основні простори імен, в яких описані ці класи:
System.Collections;
System.Col1ections.Specialized;
System.Col1ections.Generiс.
У наступних розділах коротко описані основні елементи цих просторів імен.