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

Informatec Digital » Ресурси » Структури от данни и алгоритми: Пълно ръководство за програмисти

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

Ако искате да се занимавате с професионално програмиране, да се подготвите за технически интервюта или просто да спрете да се затруднявате с упражнения като 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-тата максимална стойност в двоично дърво за търсене, изброяване на възлите на определено разстояние от корена или определяне на предците на конкретен възел.

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

Графики

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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