Структури даних - stack overflow російською
Які види структур даних бувають? (Можете вказати назву структури в певній мові програмування) Хочеться дізнатися їх призначення, сильні і слабкі сторони. Так само цікавить класифікація, чи правильно в вікі написано? Список структур даних Розгорнута відповідь поки кожній структурі не потрібен, просто коротко, для прикладу розповісти в чому перевага цієї структури перед іншими (наприклад найшвидший час доступу до елементу, здатність динамічно змінювати обсяг пам'яті і т.д.) Може на все відразу не варто відповідати, раптом обсяг відповіді буде значним, хоча б по одній з структур яку добре знаєте виходить відмовитись, а я буду додавати в основний пост інформацію. Дуже зручно буде мати перед очима такий список, відразу за ним звірився і вибрав потрібне.
1. Лінійні структури даних - це структури даних, в яких перехід від одного елемента даних до іншого не залежить від будь-яких логічних умов, тобто в лінійних структурах використовуються лише безумовні зв'язку елементів.
1.1 Список Може все те ж саме, що і масив, але дозволяє додавати елементи в будь-яке місце, видаляти елементи з будь-якого місця і отримувати поточну кількість елементів.
1.2 Асоціативний масив
- Важлива властивість хеш-таблиць полягає в тому, що, при деяких розумних припущеннях, все три операції (пошук, вставка, видалення елементів) в середньому виконуються за час O (1), час для найгіршого випадку - O (n).
- Ітерація не в порядку зростання ключів
- Необхідність «перехешірованія» при збільшенні числа збережених об'єктів (?)
- не можна реалізувати швидко працюють додаткові операції MIN, MAX і алгоритм обходу всіх збережених пар в порядку зростання або зменшення ключів (?)
- не підтримує впорядкованості, і не зберігає порядок проходження елементів (?)
- можливість колізій
1.4 Стек Набір елементів одного типу, упорядкованих таким чином, щоб додавати і діставати елементи можна було тільки з одного кінця. Операції: додати елемент в стек, дістати з стека останній доданий елемент, перевірити, чи є стек порожнім.
1.5 Черга Набір елементів одного типу, упорядкованих таким чином, щоб додавати їх можна було тільки в один кінець, а отримувати - з іншого кінця. Операції: додати елемент в кінець черги, дістати перший елемент з черги, отримання розміру черги.
1.5.1 Черга з пріоритетом
1.6 дек - особливий вид черги. Дек (від англ. Deq - double ended queue, тобто чергу з двома кінцями) - це такий послідовний список, в якому як включення, так і виключення елементів може здійснюватися з будь-якого з двох кінців списку. Окремий випадок дека - дек з обмеженим входом і дек з обмеженим виходом.
- включення елемента праворуч;
- включення елемента зліва;
- виключення елемента праворуч;
- виключення елемента зліва;
- визначення розміру;
- очистка.
2.2.3 Червоно-чорне дерево
Основне призначення: B-дерево призначене для зберігання інформації на жорсткому диску. Час довільного доступу до жорсткого диска дуже велике (мілісекунди), оскільки воно визначається швидкістю обертання диска і переміщення головок. Тому важливо зменшити кількість вузлів, що переглядаються при кожній операції, тобто висоту дерева, що досягається шляхом високої гіллястості.
- У всіх випадках корисне використання простору вторинної пам'яті займає понад 50%. З ростом ступеня корисного використання пам'яті не відбувається зниження якості обслуговування.
- Довільний доступ до запису реалізується за допомогою малої кількості підоперацій (звернення до фізичних блокам).
- В середньому досить ефективно реалізуються операції включення та видалення записів; при цьому зберігається природний порядок ключів з метою послідовної обробки, а також відповідний баланс дерева для забезпечення швидкої довільної вибірки.
- Незмінна впорядкованість по ключу забезпечує можливість пакетної обробки
- Основний недолік В-дерев полягає у відсутності для них засобів вибірки даних по вторинному ключу.
2.2.6 Двійкове дерево пошуку
2.2.6.1 самобалансірующіхся дерево пошуку
2.2.6.1.1.1 Дерево Фібоначчі
2.2.6.1.2 Червоно-чорне дерево
2.2.6.1.3 Расширяющееся дерево
2.2.7.2 Біноміальна купа
2.2.7.3 Фібоначчієва купа
2.2.8 Суффіксное дерево
2.2.8 префіксних дерево
Існує ще таке розділення структур:
Статичні структури даних
Полустатіческіе структури даних
Динамічні структури даних
Нелінійні структури даних
загальний вигляд опису структур:
-основне призначення, опис
-готова реалізація в мові програмування (назва функції або класу)
(?) - під сумнівом, поправте будь ласка якщо раптом неправильно написано або навпаки затвердите щоб виключити неоднозначність.
- Масив. Набір фіксованої кількості елементів одного типу, який має можливість прочитати або записати елемент за індексом.
- Перелік. Може все те ж саме, що і масив, але дозволяє додавати елементи в будь-яке місце, видаляти елементи з будь-якого місця і отримувати поточну кількість елементів.
- Безліч. Невпорядкований набір елементів одного типу, кожен з яких може зустрічатися в безлічі не більше одного разу. Основні операції над безліччю: додавання елемента в безліч, видалення елемента з безлічі, перевірка наявності елемента в множині, отримання розміру безлічі.
- Словник. Невпорядкований набір елементів двох типів, в якому кожен елемент першого типу пов'язаний з одним елементом другого типу, і кожен елемент першого типу (ключ) може зустрічатися в словнику не більше одного разу. Основні операції над словником: додавання пари "ключ-значення", видалення пари по ключу, перевірка наявності ключа в словнику, отримання значення по ключу, отримання кількості пар "ключ-значення".
- Черга. Набір елементів одного типу, упорядкованих таким чином, щоб додавати їх можна було тільки в один кінець, а отримувати - з іншого кінця. Операції: додати елемент в кінець черги, дістати перший елемент з черги, отримання розміру черги.
- Стек. Набір елементів одного типу, упорядкованих таким чином, щоб додавати і діставати елементи можна було тільки з одного кінця. Операції: додати елемент в стек, дістати з стека останній доданий елемент, перевірити, чи є стек порожнім.