Структури даних та алгоритми: повний посібник для програмістів

Інформатек Діджитал » Ресурси » Структури даних та алгоритми: повний посібник для програмістів

Алгоритми та структури даних Це дві частини, які поєднуються, як пазл: одна окреслює процедуру вирішення проблеми, а інша визначає, де і як ми зберігаємо інформацію. Хоча це може здатися академічним, саме опанування цієї пари відрізняє код, який просто працює, від того, який літає та масштабується без збоїв.

Якщо ви хочете займатися професійним програмуванням, готуватися до технічних співбесід або просто перестати мучитися з такими вправами, як LeetCode та Codewars, вам потрібна міцна основа... структури даних та алгоритмиУ цій статті ви дізнаєтесь, що вони собою являють, чому вони такі важливі, які основні типи існують, які основні операції вони виконують та які питання зазвичай з'являються на іспитах та у відбіркових процесах.

Що таке структури даних та алгоритми?

структура даних Це, по суті, специфічний спосіб організації та зберігання інформації в пам'яті для ефективної роботи з нею. Така організація не є випадковою: вона безпосередньо визначає, які операції є швидкими, а які – витратними (вставка, пошук, видалення, переміщення тощо).

Коли ви оберете правильну структуру даних, ваша програма зможе керувати великі обсяги даних без зайвих зусиль; якщо зробити неправильний вибір, навіть невелика програма може стати повільною, споживати забагато пам’яті або з часом стати неможливою для підтримки.

Алгоритм Це скінченна та впорядкована послідовність чітко визначених кроків, яка перетворює вхідні дані на вихідні для вирішення конкретної проблеми. Це як кулінарний рецепт: він підказує, що робити, в якому порядку та за яких умов, але його не хвилює, як ви зберігаєте інгредієнти в холодильнику, що було б частиною структури даних.

В інформатиці кожен алгоритм розробляється з урахуванням типу даних, з якими він працюватиме. Вибір структури даних — це не дрібниця: Структура та алгоритм йдуть рука об рукуА невеликі зміни в одній із двох частин можуть як підвищити, так і знизити продуктивність.

З теоретичної точки зору, такі автори, як Ніклаус Вірт, популяризували цю ідею ще в 70-х роках. алгоритми + структури даних = програмиДесятиліття потому це залишається таким самим вірним: неважливо, чи програмуєте ви на Java, Python, C++, чи прийшли ви з буткемпу, на співбесідах та в серйозних проектах від вас вимагатимуть знання, як правильно вибрати та поєднати обидва елементи.

Чому вони такі важливі в програмуванні?

У будь-якій реальній програмі, яким би простим вона не здавалася, ви завжди працюєте з даними: зарплати, продукти, користувачі, транзакції, маршрути, документиЗаписи журналів тощо. Питання не в тому, чи збираєтеся ви обробляти дані, а в тому, як ви збираєтеся їх організувати, щоб ваш код був швидким, зрозумілим і простим у обслуговуванні.

Структури даних використовуються для зберігання інформації в упорядкованому та зв'язному вигляді відповідно до проблеми. Чи не те саме Необхідність постійного доступу до першого елемента, пошуку за ключем, переміщення по порядку, вставки в середину або частого видалення; кожен шаблон використання краще відповідає різній структурі.

Зі свого боку, алгоритми дозволяють ефективно обробляти ці дані: сортувати їх, фільтрувати, шукати елементи, знаходити оптимальні маршрути, виявляти закономірності за допомогою обробка даних, оптимізувати ресурси тощо. Багато проблем, які здаються складними, стають тривіальними, коли ви знаходите правильне поєднання алгоритму та структури даних.

На технічних співбесідах щодо розробки програмного забезпечення рідко можна поставити запитання, яке безпосередньо не стосується цих тем. Іноді в запитанні прямо згадується структура, наприклад, «дано бінарне дерево…», а іноді це неявно: «ми хочемо підрахувати, скільки книг має кожен автор», що передбачає використання хеш-таблиця або карта ключ-значення.

Крім того, формальна та професійна підготовка часто зосереджена навколо цієї галузі. Багато університетів та програм вищої освіти включають предмет з... Структури даних і алгоритми, з офіційною програмою, попередніми вимогами, теоретичними та практичними заняттями, іспитами та завданнями, оскільки це вважається основним предметом для будь-якого інженера-програміста.

Передумови та необхідні основи

Щоб отримати максимальну користь від вивчення структур даних та алгоритмів, корисно мати певні знання з мовою програмування загального призначення, такою як Java, Python або C++Вам не потрібно бути гуру, але вам потрібно впевнено володіти базовими поняттями, такими як змінні, типи даних, умовні оператори, цикли, функції та передача параметрів.

Це також дуже допомагає зрозуміти ідею алгоритмічна складність і нотація Big O: як зростає час виконання або використання пам'яті зі збільшенням розміру даних (n). Знання того, як розрізняти O(1), O(log n), O(n), O(n log n) та O(n²), дозволяє вам порівнювати альтернативи з розумом та обґрунтовувати свої рішення.

Ще один важливий аспект — це невелика боротьба з Вирішення проблемСтруктуровані вправи з програмування, невеликі логічні задачі, прості ката тощо. Чим більше ви тренуєте свій «нюх» розбивати проблему на кроки, тим легше буде побачити, яка структура даних підходить для кожного випадку.

У деяких навчальних програмах прямо зазначено передумови або супутні вимоги Для курсу «Структури даних та алгоритми» вам потрібно мати успішно склав курс «Основи програмування», «Програмування I» або «Дискретна математика». Це логічно: без міцної основи базового програмування та певної логіки цей предмет легко розчарувати.

Нарешті, маючи певне знайомство з реальні практичні середовища (наприклад, невеликі веб-проекти, скрипти чи консольні додатки) допомагає краще візуалізувати, для чого ви збираєтеся використовувати кожну структуру, замість того, щоб розглядати її як щось суто академічне.

Найбільш часто використовувані структури даних

В інформатиці існує багато структур данихОднак, існує група «базових» функцій, які повторюються знову і знову: масиви (вектори), стеки, черги, зв'язані списки, дерева, графи, спроби та хеш-таблиці. Розуміння того, як вони працюють, які операції вони пропонують та їх типові витрати, є ключем до плавного просування по програмуванню.

Зараз ми збираємось переглянути кожен, з його основною ідеєю, типовими операціями та прикладами проблем, які зазвичай виникають на заняттях, у вправах та на співбесідах для розробників.

Масиви

Масив Це найпростіша лінійна структура даних і одна з найбільш широко використовуваних. Вона складається з безперервного блоку пам'яті, який зберігає колекцію елементів одного типу, доступних за цілочисельним індексом, зазвичай починаючи з нуля.

Уявіть собі масив розміром 4, що містить значення 1, 2, 3 та 4. Кожна позиція має індекс (0, 1, 2, 3), і ви можете безпосередньо отримати доступ до будь-якого елемента з його індексом за постійний час O(1). Це робить масиви дуже ефективними для випадкового зчитування.

Існує дві основні категорії: одновимірні масиви (один ряд елементів) та багатовимірні масиви (наприклад, матриці, які є масивами масивів). Багато мов програмування пропонують обидва варіанти нативно або з незначними відмінностями в синтаксисі та продуктивності.

Основні операції з масивом зазвичай такі:

• Вставка: розміщення елемента в певній позиції, що в статичних масивах може включати зміщення інших елементів.
• Отримати: доступ до елемента за заданим індексом, зазвичай O(1).
• Видалити: видалити або позначити як порожній елемент у певній позиції, зазвичай шляхом зміщення елементів ліворуч.
• Розмір: перевірити, скільки елементів зберігається або максимальну місткість масиву.

На співбесідах та іспитах такі вправи є дуже поширеними. знайти другий мінімум масивуЗнаходження першого неповторюваного цілого числа, об'єднання двох уже відсортованих масивів або переупорядкування додатних і від'ємних чисел зі збереженням певних властивостей. Все це залежить від доступу до індексів та лінійного або подвійного обходу.

Стеки

Акумулятор Це лінійна структура даних, яка дотримується принципу LIFO: останній прийшов, перший вийшов. Уявіть собі стопку книг, розміщених одна на одній: ви можете брати або класти книги лише зверху.

Така поведінка означає, що Ми отримуємо доступ лише до елемента, який знаходиться на вершині стека.Ми не можемо видалити середній елемент, не видаливши спочатку елементи над ним. Це робить його ідеальною структурою для моделювання історії дій (скасування), вкладених викликів функцій, навігації (назад/вперед) тощо.

Типові операції зі стеком:

• Штовхати: вставити новий елемент зверху.
• Pop: витягнути та повернути елемент зверху, зменшуючи розмір стеку.
• Верх або підглядання: звернутися до верхнього елемента без його видалення.
• пусто: перевірте, чи не розряджена батарея.

У контексті співбесід спостерігаються такі проблеми, як: обчислювати вирази в постфіксній нотації (RPN), сортування елементів лише за стеками або перевірка правильності балансування рядка дужок (та інших символів) за допомогою push та pop.

На практиці багато внутрішніх реалізацій мов (наприклад, стек системних викликів) працюють за цими ж принципами, навіть якщо ми не бачимо їх безпосередньо.

Черги

Хвіст Це ще одна лінійна структура даних, але замість принципу LIFO вона використовує модель FIFO: «Перший прийшов, перший вийшов». Найяскравішою аналогією є черга людей, які чекають біля каси кінотеатру.

У стандартній черзі елементи такі Вони додають в кінці та віднімають на початкуУ порядку живої черги його обслужують, що робить його ідеальним для керування незавершеними завданнями, процесами операційної системи, запитами до сервера, чергами друку тощо.

Основні операції з чергою включають:

• У чергу: вставити новий елемент у кінець черги.
• Зняти чергу: видалити та повернути елемент, розташований на початку.
• Спереду або зверху: зверніться до першого елемента, не видаляючи його.
• пусто: перевірити, чи черга порожня.

У завданнях з програмування вони зазвичай запитують вас, наприклад, реалізувати стек, використовуючи дві черги, перевернути перші k елементів черги без зміни решти або згенерувати двійкові числа від 1 до n, використовуючи поведінку FIFO черги.

Окрім основного хвоста, існують такі варіації, як круглий хвіст, черга пріоритетів або подвійні черги (deque), які пропонують додаткові операції та покращують продуктивність у певних сценаріях.

пов'язані списки

Зв'язаний список Зв'язаний список також є лінійною структурою, але внутрішньо він дуже відрізняється від масивів. Замість використання суцільного блоку пам'яті він складається з розріджених вузлів, з'єднаних один з одним посиланнями або вказівниками.

Кожен вузол зазвичай містить дві частини: дані які мають бути збережені, та вказівник (або кілька), що вказує на наступний вузол у послідовності (а у випадку подвійно зв'язаних списків також на попередній). Список керується через посилання на його голову, яка вказує на перший вузол, а у складніших списках також підтримується посилання на хвіст.

Є два основних варіанти:

• однозв'язний список: кожен вузол вказує лише на наступний; шлях зазвичай пролягає в одному напрямку.
• двозв'язаний списокКожен вузол вказує на наступний та попередній вузол, що сприяє двонаправленому обходу та ефективнішим операціям видалення.

Типові операції зі зв'язаними списками включають:

• Вставити в початок: вставити новий вузол на початку списку.
• Вставити в кінці: додати вузол у кінець, оновивши чергу, якщо вона існує.
• видаляти: видалити певний вузол, налаштувавши вказівники сусідніх вузлів.
• Видалити вгорі: видалити перший вузол і перемістити голову до наступного.
• Пошук: переглянути список у пошуках певного значення.
• пусто: перевірити, чи є заголовок null, і тому список не містить елементів.

Такі проблеми рясніють на заняттях та співбесідах зворотний зв'язаний список, виявити наявність циклу (зазвичай використовуючи алгоритм "черепахи та зайця"), отримати вузол N, рахуючи з кінця, або видалити дублікати вузлів, завжди обережно обробляючи вказівники.

Зв'язані списки широко використовуються для реалізації хеш-таблиці з ланцюжкомсписки суміжності в графах та динамічні структури даних, де елементи часто вставляються та видаляються.

Арболи

Дерево Це ієрархічна структура даних, що складається з вузлів, з'єднаних ребрами. На відміну від загальних графів, дерево не має циклів: завжди є корінь, дочірні елементи, батьки, брати і сестри, листя, рівні та піддерева з організацією типу «сім'я» або «організаційна діаграма».

Дерева дуже корисні, коли нам потрібно представляють ієрархічні відносини або розділити проблему на менші підпроблеми: файлові системи, меню, структури DOM у браузерах, дерева рішень у штучному інтелекті тощо.

Існує багато різновидів дерев, зокрема:

• N-арне дерево: кожен вузол може мати змінну (і, можливо, велику) кількість дочірніх вузлів.
• Збалансоване дерево: зберігає свої гілки на однаковій глибині, щоб уникнути погіршення продуктивності.
• Бінарне дерево: кожен вузол має максимум двох дочірніх вузлів (лівого та правого).
• Бінарне дерево пошуку (BST): бінарне дерево з властивістю, що все ліворуч від вузла менше, а все праворуч більше (відповідно до деякого критерію впорядкування).
• Дерево AVL, червоно-чорне, 2-3 та інші варіантиЦе збалансовані дерева пошуку, які гарантують хороші обмеження складності для операцій вставки, видалення та пошуку.

На практиці найчастіше у вправах використовуються бінарне дерево у-ель- бінарне дерево пошукуТипові проблеми включають обчислення висоти дерева, знаходження k-го максимального значення в BST, перерахування вузлів на певній відстані від кореня або визначення предків певного вузла.

Крім того, алгоритми обходу (попередній порядок, внутрішній порядок, попередній порядок, рівень за рівнем) є фундаментальними для багатьох наступних процесів: відсортованого друку, обчислення виразів, серіалізації та десеріалізації дерев тощо.

графіки

Графік Він узагальнює концепцію дерева, дозволяючи цикли та множинні довільні зв'язки між вузлами. Він складається з набору вершин (вузлів) та набору ребер, що з'єднують пари вершин, іноді з пов'язаною вагою або вартістю.

Існує кілька типів графіків: ненаправлений (ребра не мають напрямку, зв'язок двонаправлений) та спрямований (Ребра мають початкову точку та точку призначення). Їх також можна класифікувати як зважені або незважені, зв'язані або нез'єднані, з циклами або без них тощо.

У коді графіки зазвичай представляють двома основними способами:

• Матриця суміжності: матриця, де комірка вказує, чи є ребро між вершинами i та j (і, можливо, вагу з'єднання).
• Список суміжності: для кожної вершини зберігається список її сусідів, що економить пам'ять у розріджених графах.

Найбільш класичними алгоритмами обходу є Пошук у ширину (BFS) і поглиблений пошук (DFS)Обидва використовуються як основні будівельні блоки для безлічі задач: перевірка зв'язності графа, виявлення циклів, пошук зв'язних компонентів тощо.

У технічних тестах часто запитують реалізувати BFS та DFS, перевірити, чи утворює граф дерево, підрахувати кількість ребер або знайти... найкоротші шляхи між двома вузлами (наприклад, на карті міст) з використанням таких варіантів, як Дейкстра або BFS у незважених графах.

Спроби або префіксні дерева

Спроба (або префіксне дерево) — це деревоподібна структура даних, оптимізована для обробки символьних рядків, особливо корисна під час роботи зі словниками слів, системами автозаповнення або префіксним пошуком.

У trie кожен вузол зазвичай представляє символ, а шляхи від кореня до певних вузлів позначають повні словаКінцеві вузли слів зазвичай позначені певним чином (наприклад, логічним індикатором), щоб відрізнити їх від простих префіксів.

Якщо ми збережемо слова «top», «thus» та «their» у вигляді trie, ми розділимо частину початкового шляху для всіх тих, що починаються з однакових літер, що дозволить пошук та пропозиції за префіксом у дуже ефективний час, пропорційна довжині слова, яке ми шукаємо, а не загальній кількості збережених слів.

Звичайні операції та проблеми зі спробами включають: підрахувати, скільки слів зберігається, виводити всі слова в лексикографічному порядку, сортувати елементи масиву шляхом вставки в триєдине скупчення, генерувати коректні слова з набору літер або будувати структури, подібні до словника T9.

У контексті співбесід це не найпростіша структура, яку вони проситимуть, але вона регулярно зустрічається в компаніях, які працюють з пошукові запити, текстові редактори або системи підказок.

Хеш-таблиці та хешування

Хешування Це техніка призначення числового ключа (хешу) кожному фрагменту даних детермінованим способом, щоб ми могли зберігати та отримувати елементи майже за постійний час, використовуючи цей ключ як індекс у внутрішній структурі, зазвичай масиві.

La хеш-таблиця Це структура даних, яка використовує цей механізм. Кожен елемент зберігається як пара ключ-значення: ключ перетворюється на індекс таблиці за допомогою хеш-функції, і значення (або посилання на нього) зберігається там. Пізніше, для пошуку, просто знову хешуйте ключ і отримуйте доступ до відповідної позиції.

Продуктивність хеш-таблиці вирішально залежить від трьох факторів: хеш-функція вибраний (ви повинні добре розподілити ключі, щоб уникнути концентрації), розмір столу (недостатній розмір спричиняє багато зіткнень) та метод управління колізіями (зв'язування зі зв'язаними списками, відкрита адресація тощо). Це схоже на індекс у базі данихде вибір відповідної структури покращує пошук та доступ.

Типові вправи з хеш-програмування часто вимагають, наприклад, знайти симетричні пари в масивіРеконструкція повного маршруту подорожі з окремих рейсів, швидка перевірка того, чи є один масив підмножиною іншого, або перевірка того, чи два масиви не перетинаються, все це шляхом використання приблизного O(1) пошуку в хеш-таблиці.

У більшості сучасних мов такі структури, як карта, словник, хеш-карта або хеш-набір Вони внутрішньо покладаються на хеш-таблиці, хоча програмісту пропонується високорівневий інтерфейс.

Як алгоритми та структури даних пов'язані

Вибір структури даних безпосередньо визначає, які алгоритми мають сенс і якою буде їхня складність. Лінійний алгоритм пошуку на невпорядкований список Він перебирає елементи один за одним; якщо ми змінимо структуру на збалансоване дерево пошуку або хеш-таблицю, ми отримаємо набагато кращі результати.

Наприклад, якщо ви хочете багаторазово шукати ключі у великій колекції, зберігаючи дані у хеш-таблиця або бінарне дерево пошуку Це дозволяє розробляти алгоритми пошуку, які працюють набагато швидше, ніж якби ви використовували простий несортований масив. Те саме стосується черг пріоритетів та куп для планування або алгоритмів найкоротшого шляху.

І навпаки, під час розробки алгоритму ви часто усвідомлюєте, що вам потрібні певні властивості: доступ до індексу, швидка вставка на початку, ієрархічний обхід, пошук префіксів тощо. Ці потреби спрямовують ваш вибір структури. масиви, списки, дерева, графи, хеш-таблиці, спроби...

Саме це відповідне поєднання алгоритму та структури даних робить можливим створення складних програм. ефективний та масштабованийБез гарної основи рішення, як правило, стають повільними, важкими для розуміння та підтримки, або ж неможливими для адаптації зі зростанням обсягу інформації.

Отже, оволодіння алгоритмами та структурами даних не є майже незамінна вимога для всіх, хто прагне стати компетентним та конкурентоспроможним програмістом на сучасному ринку праці.

Як вивчати структури даних та алгоритми

Багато людей відчувають себе в глухому куті, коли намагаються навчатися самостійно за допомогою таких платформ, як LeetCode або CodewarsЧасто починають із «легких» вправ і все одно не знають, з чого підійти до задачі, в результаті чого дивляться на рішення і не розуміють, як його потім відтворити.

Практичний підхід зазвичай поєднує кілька складових: a гарне теоретичне пояснення Кожна структура та алгоритм містять наочні приклади, безліч практичних посібників та, якщо можливо, підтримку від досвідченого спеціаліста, який допоможе вам удосконалити свої навички вирішення проблем.

В іспаномовному світі є фахівці з великим досвідом, які зробили свій внесок у сприяння цьому навчанню. Одним із прикладів є робота Викладачі з досвідом роботи в бізнесі та освіті які опублікували книги та курси з основ програмування, Java, структур даних та завдань програмування з іграми, зробивши ці концепції доступними у цікавий та застосовний спосіб для реальних проектів.

Також академії та навчальні центри часто включають спеціальні модулі зі структур даних та алгоритмів до своїх програм для веб-розробників або програмістів додатків. У багатьох випадках акцент робиться на певному підході. дуже практичний та орієнтований на проекти, із вправами зростаючої складності та моделюванням типових проблем технічного співбесіди.

Якщо ви застрягли, дотримання структурованого маршруту може допомогти: починати з масивів та списків, переглядаючи стеки та черги, потім дерева та прості графи, і, нарешті, хеш-таблиці та спроби, завжди чергуючи теоретичні пояснення, невеликі приклади коду та багато індивідуальної практики.

Під час підготовки до співбесід бажано переглянути не лише структури, а й алгоритми грубої сили та пов'язані з ними класичні алгоритми (обходи, пошуки, сортування, прості зворотні шляхи, базове динамічне програмування) та переконайтеся, що ви можете пояснити вголос, чому ви обрали певну структуру та що складність вашого рішення.

З часом і певна послідовністьТе, що спочатку здається стіною, зрештою перетворюється на набір звичних інструментів, які ви використовуєте майже інстинктивно, стикаючись з новими проблемами.

Добре розуміння того, що таке алгоритми, як працюють основні структури даних та як вони пов'язані одна з одною, дозволить вам писати програми. швидший, чіткіший та надійнішийЦе відкриє вам двері у складних процесах відбору та гарантуватиме, що ваші проекти, як академічні, так і професійні, базуватимуться на міцному фундаменті з майбутнім.