Структури от данни и алгоритми: пълно ръководство за програмисти

Информатек Дигитал » Ресурси » Структури от данни и алгоритми: пълно ръководство за програмисти

Алгоритми и структури от данни Те са две части, които се вписват като пъзел: едната очертава процедурата за решаване на проблема, а другата определя къде и как съхраняваме информацията. Макар че може да звучи академично, овладяването на тази двойка е това, което отличава код, който просто работи, от такъв, който лети и се мащабира, без да се повреди.

Ако искате да се занимавате с професионално програмиране, да се подготвите за технически интервюта или просто да спрете да се затруднявате с упражнения като LeetCode и Codewars, имате нужда от солидна основа в структури от данни и алгоритмиВ тази статия ще видите какво представляват те, защо са толкова важни, какви основни видове съществуват, какви основни операции извършват и какви въпроси обикновено се появяват на изпити и в процесите на подбор.

Какво представляват структурите от данни и алгоритмите?

Структура от данни Това е, по същество, специфичен начин за организиране и съхраняване на информация в паметта, за да може тя да се обработва ефективно. Тази организация не е произволна: тя директно определя кои операции са бързи и кои стават скъпи (вмъкване, търсене, изтриване, преминаване и т.н.).

Когато изберете правилната структура от данни, вашата програма може да управлява големи обеми данни без да се потите; когато изберете лошо, дори малко приложение може да стане бавно, да консумира твърде много памет или да стане невъзможно за поддръжка с течение на времето.

Алгоритъм Това е крайна и подредена поредица от добре дефинирани стъпки, която трансформира входните данни в изходни, за да реши конкретен проблем. Прилича на рецепта за готвене: казва ви какво да правите, в какъв ред и при какви условия, но не се интересува как съхранявате съставките в хладилника, което би било частта, свързана със структурата на данните.

В компютърните науки всеки алгоритъм се проектира с оглед на типа данни, с които ще работи. Изборът на структура на данните не е маловажен детайл: Структурата и алгоритъмът вървят ръка за ръкаИ малки промени в едната от двете части могат или да повишат, или да намалят производителността.

От теоретична гледна точка, автори като Никлаус Вирт популяризират идеята още през 70-те години на миналия век, че алгоритми + структури от данни = програмиДесетилетия по-късно, това остава също толкова вярно: няма значение дали програмирате на Java, Python, C++ или сте от bootcamp, това, което ще се изисква от вас на интервюта и сериозни проекти, е да знаете как да избирате и комбинирате добре и двата елемента.

Защо са толкова важни в програмирането?

Във всяко реално приложение, колкото и просто да изглежда, винаги работите с данни: заплати, продукти, потребители, транзакции, маршрути, документиЗаписи в логове и т.н. Въпросът не е дали ще обработвате данни, а как ще ги организирате, така че кодът ви да е бърз, ясен и лесен за поддръжка.

Структурите от данни се използват за съхраняване на информация по подреден и последователен начин в зависимост от проблема. Не е Необходимостта винаги да се осъществява достъп до първия елемент, да се търси по ключ, да се преминава по ред, да се вмъква в средата или често да се изтрива; всеки модел на употреба се вписва по-добре в различна структура.

От своя страна, алгоритмите позволяват обработват тези данни ефективносортирайте ги, филтрирайте ги, търсете елементи, намирайте оптимални маршрути, откривайте модели с извличане на данни, оптимизиране на ресурси и т.н. Много проблеми, които изглеждат трудни, стават тривиални, когато намерите правилната комбинация от алгоритъм и структура на данните.

В технически интервюта за разработка на софтуер рядко се задава въпрос, който не засяга директно тези теми. Понякога въпросът изрично споменава структурата, например „ако е дадено двоично дърво…“, а друг път е имплицитно: „искаме да преброим колко книги има всеки автор“, което предполага използването на хеш таблица или карта ключ-стойност.

Освен това, формалното и професионалното обучение често се върти около тази област. Много университети и програми за висше образование включват предмет по... Структури от данни и алгоритми, с официална програма, предварителни изисквания, теоретични и практически сесии, изпити и задачи, защото се счита за основен предмет за всеки софтуерен инженер.

Предпоставки и необходими основи

За да извлечете максимума от изучаването на структури от данни и алгоритми, е полезно да имате известни познания с език за програмиране с общо предназначение, като например 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: Последен влязъл, първи излязъл. Представете си купчина книги, поставени една върху друга: можете да вземате или поставяте книги само отгоре.

Това поведение означава, че Достъпваме само до елемента, който е на върха на стекаНе можем да премахнем средния елемент, без първо да премахнем елементите над него. Това го прави идеална структура за моделиране на истории на действия (отмяна), вложени извиквания на функции, навигация (назад/напред) и др.

Типичните операции със стека са:

• Тласък: вмъкване на нов елемент отгоре.
• поп: извлича и връща елемента отгоре, намалявайки размера на стека.
• Отгоре или надникване: консултирайте се с най-горния елемент, без да го изтривате.
• празно е: проверете дали батерията е празна.

В контекста на интервютата се наблюдават проблеми като следните: оценяване на изрази в постфиксна нотация (RPN), сортиране на елементи само с помощта на стекове или проверка дали низ от скоби (и други символи) е правилно балансиран, използвайки push и pop.

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

Опашки

Опашката Това е друга линейна структура от данни, но вместо да следва принципа LIFO, тя използва модела FIFO: First In, First Out (Първи влязъл, първи излязъл). Най-ясната аналогия е опашка от хора, чакащи на билетната каса в киносалон.

В стандартна опашка елементите са Те добавят в края и отнемат в началото„Първи дошъл, първи обслужен“, което го прави идеален за управление на чакащи задачи, процеси на операционната система, заявки към сървъра, опашки за печат и др.

Основните операции с опашки включват:

• Нареди се на опашка: вмъкване на нов елемент в края на опашката.
• Отмяна: премахва и връща елемента, разположен в началото.
• Отпред или отгоре: вижте първия елемент, без да го премахвате.
• празно е: проверете дали опашката е празна.

В предизвикателствата по програмиране е обичайно да ви питат например, имплементирайте стек, използвайки две опашки, да обърнат първите k елемента от опашка, без да променят останалите, или да генерират двоични числа от 1 до n, използвайки FIFO поведението на опашката.

Освен основната опашка, има и вариации като например кръгла опашка, приоритетната опашка или двойните опашки (deque), които предлагат допълнителни операции и подобряват производителността в определени сценарии.

свързани списъци

Свързаният списък Свързаният списък също е линейна структура, но вътрешно е много различен от масивите. Вместо да използва непрекъснат блок памет, той е съставен от разредени възли, които са свързани помежду си чрез препратки или указатели.

Всеки възел обикновено съдържа две части: данните които ще се съхраняват, и указател (или няколко), който сочи към следващия възел в последователността (и, в случай на двойно свързани списъци, също и към предишния). Списъкът се управлява чрез препратка към неговата глава, която сочи към първия възел, а в по-сложни списъци се поддържа и препратка към опашката.

Има два основни варианта:

• едносвързан списък: всеки възел сочи само към следващия; пътят обикновено е в една посока.
• двойносвързан списъкВсеки възел сочи към следващия и предишния възел, което улеснява двупосочно преминаване и по-ефективни операции по изтриване.

Типичните операции със свързани списъци включват:

• Вмъкни в началото: вмъкване на нов възел в началото на списъка.
• Вмъкни в края: добавяне на възел в края, актуализиране на опашката, ако съществува.
• Изтрий: премахване на специфичен възел, коригиране на показалците на съседните възли.
• Изтриване от главата: изтриване на първия възел и преместване на главата към следващия.
• Търсене: обходете списъка, търсейки конкретна стойност.
• празно е: проверява дали заглавието е null и следователно списъкът няма елементи.

Подобни проблеми изобилстват в часовете и интервютата. обръщане на свързан списък, откриване на наличието на цикъл (обикновено използвайки алгоритъма „костенурка и заек“), получаване на възел N чрез броене от края или премахване на дублиращи се възли, като винаги се борави внимателно с указателите.

Свързаните списъци се използват широко за имплементиране хеш таблици с верижно свързванесписъци за съседство в графи и динамични структури от данни, където елементите се вмъкват и изтриват често.

Дървета

Дърво Това е йерархична структура от данни, съставена от възли, свързани чрез ребра. За разлика от обикновените графове, дървото няма цикли: винаги има корен, деца, родители, братя и сестри, листа, нива и поддървета, с организация от типа „семейство“ или „организационна схема“.

Дърветата са много полезни, когато искаме представляват йерархични взаимоотношения или разделяне на проблема на по-малки подпроблеми: файлови системи, менюта, DOM структури в браузъри, дървета на решенията в изкуствения интелект и др.

Има много разновидности на дърветата, включително:

• N-арно дърво: всеки възел може да има променлив (и евентуално голям) брой деца.
• Балансирано дърво: поддържа клоните си на подобна дълбочина, за да избегне влошаване на производителността.
• Бинарно дърво: всеки възел има максимум две деца (ляво и дясно).
• Двоично дърво за търсене (BST): двоично дърво със свойството, че всичко вляво от възел е по-малко, а всичко вдясно е по-голямо (според някакъв критерий за подреждане).
• AVL дърво, червено-черно, 2-3 и други вариантиТова са балансирани дървета за търсене, които гарантират добри ограничения на сложността при операциите по вмъкване, изтриване и търсене.

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

Освен това, алгоритмите за преминаване (предварителен ред, входящ ред, постордер, ниво по ниво) са фундаментални за много последващи процеси: сортиран печат, оценка на изрази, сериализация и десериализация на дървета и др.

Графики

Графика То обобщава концепцията за дърво, като позволява цикли и множество произволни връзки между възлите. Състои се от набор от върхове (възли) и набор от ребра, които свързват двойки върхове, понякога със свързано тегло или цена.

Има няколко вида графики: ненасочен (ръбовете нямат посока, връзката е двупосочна) и насочен (Ръбовете имат начална точка и крайна точка). Те могат да бъдат класифицирани като претеглени или непретеглени, свързани или несвързани, със или без цикли и т.н.

В кода графиките обикновено се представят по два основни начина:

• Матрица на съседство: матрица, където клетката показва дали има ръб между върха i и j (и евентуално теглото на връзката).
• Списък на съседни места: за всеки връх се съхранява списък със съседите му, което спестява памет в разредени графове.

Най-класическите алгоритми за преминаване са Търсене в ширина (BFS) и задълбочено търсене (DFS)И двете се използват като основни градивни елементи за множество проблеми: проверка дали даден граф е свързан, откриване на цикли, намиране на свързани компоненти и др.

В техническите тестове е обичайно да се изисква да се имплементират BFS и DFS, да се провери дали даден граф образува дърво, да се преброят ребрата или да се търсят... най-кратките пътища между два възела (например на карта на градове), използвайки варианти като Dijkstra или BFS в непретеглени графи.

Опити или префиксни дървета

Опитът (или префиксно дърво) е дървовидна структура от данни, оптимизирана за обработка на низове от символи, особено полезна при работа с речници на думи, системи за автоматично довършване или префиксно търсене.

В едно трие, всеки възел обикновено представлява символ, а пътищата от корена до определени възли маркират пълни думиКрайните възли на думите обикновено са маркирани по някакъв начин (например с булев индикатор), за да се различат от простите префикси.

Ако съхраним думите „top“, „thus“ и „their“ в трие, ще споделим част от началния път за всички, които започват с едни и същи букви, което ще позволи търсене и предложения по префикс в много ефективно време, пропорционална на дължината на думата, която търсим, а не на общия брой съхранени думи.

Често срещани операции и проблеми с опитите включват: пребройте колко думи са съхранени, отпечатайте всички думи в лексикографски ред, сортирайте елементите на масив чрез вмъкване в трие, генерирайте валидни думи от набор от букви или изграждайте структури, подобни на T9 речник.

В контекста на интервюта това не е най-основната структура, която ще поискат, но се появява редовно в компании, които работят с търсения, текстообработка или системи за предложения.

Хеш таблици и хеширане

Хеширане Това е техника за присвояване на числов ключ (хеш) на всяка част от данните по детерминистичен начин, така че да можем да съхраняваме и извличаме елементи за почти постоянно време, използвайки този ключ като индекс във вътрешна структура, обикновено масив.

La хеш таблица Това е структурата от данни, която използва този механизъм. Всеки елемент се съхранява като двойка ключ-стойност: ключът се трансформира в табличен индекс с помощта на хеш функция и стойността (или препратка към нея) се съхранява там. По-късно, за да търсите, просто хеширайте ключа отново и достъпете съответната позиция.

Производителността на хеш таблицата зависи изключително много от три фактора: хеш функция избрани (трябва да разпределите добре клавишите, за да избегнете концентрация), размер на масата (недостатъчният размер причинява много сблъсъци) и метод за управление на сблъсъци (свързване със свързани списъци, отворено адресиране и др.). Това е подобно на индекс в базата данникъдето изборът на подходяща структура подобрява търсенето и достъпа.

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

В повечето съвременни езици, структури като карта, речник, хеш карта или хеш набор Те разчитат вътрешно на хеш таблици, въпреки че на програмиста се предлага интерфейс от високо ниво.

Как са свързани алгоритмите и структурите от данни

Изборът на структура от данни директно определя кои алгоритми имат смисъл и каква ще бъде тяхната сложност. Линеен алгоритъм за търсене върху неподреден списък Той итерира през елементите един по един; ако променим структурата на балансирано дърво за търсене или хеш таблица, получаваме много по-добри времена.

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

Обратно, когато проектирате алгоритъм, често осъзнавате, че се нуждаете от определени свойства: достъп до индекси, бързо вмъкване в началото, йерархично обхождане, търсене на префикси и др. Тези нужди ръководят избора ви на структура. масиви, списъци, дървета, графики, хеш таблици, опити...

Тази подходяща комбинация от алгоритъм и структура на данните е това, което прави възможно създаването на сложни приложения. ефективни и мащабируемиБез добра основа, решенията са склонни да стават бавни, трудни за разбиране и поддържане или невъзможни за адаптиране с нарастването на обема на информацията.

Следователно, овладяването на алгоритми и структури от данни не е почти задължително изискване за всеки, който се стреми да стане компетентен и конкурентноспособен програмист на днешния пазар на труда.

Как да научим структури от данни и алгоритми

Много хора се чувстват заседнали, когато се опитват да учат сами с платформи като LeetCode или CodewarsЧесто срещано е да се започне с „лесни“ упражнения и все още да не се знае откъде да се подходи към проблема, в крайна сметка се гледа решението, без да е ясно как да се възпроизведе впоследствие.

Практическият подход обикновено съчетава няколко съставки: a добро теоретично обяснение Всяка структура и алгоритъм включват визуални примери, множество насоки за практикуване и, ако е възможно, подкрепа от някой с опит, който да ви помогне да усъвършенствате уменията си за решаване на проблеми.

В испаноезичния свят има професионалисти с богат опит, които са допринесли за улесняване на това обучение. Един пример е работата на Учители с опит в бизнеса и образованието които са публикували книги и курсове по основи на програмирането, Java, структури от данни и програмни предизвикателства с игри, правейки тези концепции достъпни по забавен и приложим начин за реални проекти.

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

Ако сте заседнали, следването на структуриран маршрут може да ви помогне: започнете с масиви и списъци, преминавайки през стекове и опашки, след това дървета и основни графи, и накрая хеш таблици и опити, винаги редувайки теоретично обяснение, малки примери с код и много индивидуална практика.

Когато се подготвяте за интервюта, е препоръчително да прегледате не само структурите, но и алгоритми за груба сила и свързаните с тях класически алгоритми (обхождане, търсене, сортиране, просто връщане назад, основно динамично програмиране) и се уверете, че можете да обясните на глас защо сте избрали определена структура и какво сложността на вашето решение.

С течение на времето и известна последователностТова, което на пръв поглед изглежда като стена, се превръща в набор от познати инструменти, които използвате почти инстинктивно, когато се сблъскате с нови проблеми.

Доброто разбиране на това какво представляват алгоритмите, как работят основните структури от данни и как са свързани помежду си, ще ви позволи да пишете програми. по-бърз, по-ясен и по-стабиленТова ще ви отвори врати в трудните процеси на подбор и ще гарантира, че вашите проекти, както академични, така и професионални, са базирани на солидна основа с бъдеще.