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

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

Алгоритми и структуре података То су два дела која се уклапају попут слагалице: један описује поступак за решавање проблема, а други одређује где и како чувамо информације. Иако може звучати академски, савладавање овог пара је оно што разликује код који само ради од оног који лети и скалира се без кварова.

Ако желите да се бавите професионалним програмирањем, припремите се за техничке интервјуе или једноставно престанете да се мучите са вежбама попут LeetCode-а и Codewars-а, потребна вам је чврста основа у структуре података и алгоритмиУ овом чланку ћете видети шта су они, зашто су толико важни, које главне врсте постоје, које основне операције обављају и која се питања обично појављују на испитима и у процесима селекције.

Шта су структуре података и алгоритми?

структуру података То је, у основи, специфичан начин организовања и складиштења информација у меморији како би се са њима могло ефикасно радити. Ова организација није случајна: она директно одређује које су операције брзе, а које постају скупе (уметање, претрага, брисање, прелазак итд.).

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

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

У рачунарству, сваки алгоритам је дизајниран имајући у виду врсту података са којима ће радити. Избор структуре података није мали детаљ: Структура и алгоритам иду руку под рукуА мале промене у једном од два дела могу или побољшати или смањити перформансе.

Са теоријске перспективе, аутори попут Никлауса Вирта популаризовали су идеју још седамдесетих година прошлог века да алгоритми + структуре података = програмиДеценијама касније, остаје подједнако тачно: није битно да ли програмирате у Јави, Пајтону, C++ или долазите са обуке за новинаре, оно што ће се од вас тражити на интервјуима и озбиљним пројектима јесте да знате како да добро изаберете и комбинујете оба елемента.

Зашто су толико важни у програмирању?

У било којој апликацији из стварног света, колико год једноставно изгледала, увек радите са подацима: плате, производи, корисници, трансакције, руте, документиЗаписи дневника, итд. Питање није да ли ћете обрађивати податке, већ како ћете их организовати тако да ваш код буде брз, јасан и лак за одржавање.

Структуре података се користе за чување информација на уређен и кохерентан начин у складу са проблемом. Није исто Морање да се стално приступа првом елементу, претрага по кључу, претрага по редоследу, уметање у средину или често брисање; сваки образац коришћења боље одговара другачијој структури.

Са своје стране, алгоритми омогућавају ефикасно обрађује те податке: сортирајте их, филтрирајте их, претражите елементе, пронађите оптималне руте, откријте обрасце помоћу рударјење података, оптимизовати ресурсе итд. Многи проблеми који делују тешки постају тривијални када пронађете праву комбинацију алгоритма и структуре података.

У техничким интервјуима за развој софтвера, ретко се поставља питање које се директно не бави овим темама. Понекад питање експлицитно помиње структуру, као што је „дато је бинарно стабло…“, а понекад је имплицитно: „желимо да избројимо колико књига сваки аутор има“, што сугерише употребу хеш табела или мапа кључ-вредност.

Штавише, формална и стручна обука се често врти око ове области. Многи универзитети и програми високог образовања укључују предмет о... Структуре података и алгоритми, са званичним програмом, предусловима, теоријским и практичним часовима, испитима и задацима, јер се сматра основним предметом за сваког софтверског инжењера.

Предуслови и неопходне основе

Да бисте извукли максимум из проучавања структура података и алгоритама, корисно је имати неко познавање програмског језика опште намене, као што је Јава, Пајтон или 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 модел: Први уђе, први изађе. Најјаснија аналогија је ред људи који чекају на благајни у биоскопу.

У стандардном реду, елементи су Додају на крају, а одузимају на почеткуКо први дође, први се служи, што га чини идеалним за управљање задацима који чекају, процесима оперативног система, захтевима сервера, редовима за штампање итд.

Основне операције реда чекања укључују:

• У реду: уметните нову ставку на крај реда.
• Декуеуе: уклонити и вратити елемент који се налази на почетку.
• Предњи или горњи деоконсултујте прву ставку без њеног уклањања.
• Празно: провери да ли је ред празан.

У програмерским изазовима, уобичајено је да вас питају, на пример, имплементирати стек користећи два реда, обрнути првих k елемената реда без мењања остатка или генерисати бинарне бројеве од 1 до n користећи FIFO понашање реда.

Поред основног репа, постоје варијације као што су кружни реп, ред са приоритетом или двоструки редови (deque), који нуде додатне операције и побољшавају перформансе у одређеним сценаријима.

повезане листе

Повезана листа Повезана листа је такође линеарна структура, али се интерно веома разликује од низова. Уместо коришћења континуираног блока меморије, она је састављена од ретких чворова који су међусобно повезани референцама или показивачима.

Сваки чвор обично садржи два дела: податке који треба да се сачувају и показивач (или више њих) који указује на следећи чвор у низу (и, у случају двоструко повезаних листа, и на претходни). Листа се управља преко референце на њен почетак, који указује на први чвор, а у сложенијим листама се одржава и референца на реп.

Постоје две главне варијанте:

• једноструко повезана листа: сваки чвор указује само на следећи; путања је обично у једном смеру.
• двоструко повезана листаСваки чвор указује на следећи и претходни чвор, олакшавајући двосмерне преласке и ефикасније операције брисања.

Типичне операције на повезаним листама укључују:

• Убаци на почетак: уметните нови чвор на почетак листе.
• Убаци на крају: додаје чвор на крај, ажурирајући ред ако постоји.
• Избрисати: уклонити одређени чвор, подешавајући показиваче суседних чворова.
• Обриши на почетку: обришите први чвор и померите главу на следећи.
• Претрага: пређите кроз листу тражећи одређену вредност.
• ПразноПровери да ли је заглавље null и да ли листа нема елементе.

Проблеми попут ових обилују на часовима и интервјуима обрнути повезану листу, детектовати да ли постоји циклус (обично користећи алгоритам „корњача и зец“), добити чвор N бројећи од краја или уклонити дупликате чворова, увек пажљиво рукујући показивачима.

Повезане листе се широко користе за имплементацију Хеш табеле са уланчавањемлисте суседности у графовима и динамичке структуре података где се елементи често убацују и бришу.

Арболес

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

Дрвеће је веома корисно када желимо представљају хијерархијске односе или поделити проблем на мање подпроблеме: системе датотека, меније, DOM структуре у прегледачима, стабла одлучивања у вештачкој интелигенцији итд.

Постоји много врста дрвећа, укључујући:

• N-арно дрво: сваки чвор може имати променљив (и могуће велики) број деце.
• Уравнотежено дрво: одржава своје гране на сличној дубини како би се избегло смањење перформанси.
• Бинарно дрво: сваки чвор има највише два детета (лево и десно).
• Бинарно стабло претраживања (BST)бинарно дрво са својством да је све лево од чвора мање, а све десно веће (према неком критеријуму уређења).
• AVL дрво, црвено-црно, 2-3 и друге варијантеОво су балансирана стабла претраживања која гарантују добра ограничења сложености у операцијама уметања, брисања и претраживања.

У пракси, најчешће у вежбама су бинарно дрво и бинарно стабло претраживањаТипични проблеми укључују израчунавање висине стабла, проналажење k-те максималне вредности у BST-у, навођење чворова на одређеној удаљености од корена или одређивање предака одређеног чвора.

Штавише, алгоритми обиласка (преордер, инордер, постордер, ниво по ниво) су фундаментални за многе наредне процесе: сортирано штампање, процену израза, серијализацију и десеријализацију стабла итд.

графова

График Генерализује концепт стабла дозвољавајући циклусе и вишеструке произвољне везе између чворова. Састоји се од скупа врхова (чворова) и скупа ивица које повезују парове врхова, понекад са придруженом тежином или ценом.

Постоји неколико врста графикона: неусмерен (ивице немају осећај правца, однос је двосмеран) и усмерен (Ивице имају почетну тачку и одредиште). Такође се могу класификовати као пондерисане или непондерисане, повезане или неповезане, са или без циклуса итд.

У коду, графови се обично представљају на два основна начина:

• Матрица суседности: матрица где ћелија означава да ли постоји ивица између чворова i и j (и могуће тежину везе).
• Листа суседности: за сваки чвор се чува листа његових суседа, што штеди меморију у ретким графовима.

Најкласичнији алгоритми за прелазак су Претрага у ширину (BFS) и детаљна претрага (DFS)Оба се користе као основни градивни блокови за мноштво проблема: провера да ли је граф повезан, откривање циклуса, проналажење повезаних компоненти итд.

У техничким тестовима, уобичајено је да се тражи да се имплементира BFS и DFS, провери да ли граф формира дрво, преброји број грана или претражи најкраћим путевима између два чвора (на пример, на мапи градова) користећи варијанте као што су Дајкстра или BFS у непондерисаним графовима.

Покушаји или префиксна стабла

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

У тројцу, сваки чвор обично представља један знак, а путање од корена до одређених чворова означавају потпуне речиЧворови последње речи су обично означени на неки начин (на пример, Буловим индикатором) како би се разликовали од једноставних префикса.

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

Уобичајене операције и проблеми са покушајима укључују: пребројите колико речи је сачувано, исписати све речи у лексикографском редоследу, сортирати елементе низа уметањем у трие, генерисати валидне речи из скупа слова или изградити структуре сличне Т9 речнику.

У контексту интервјуа, то није најосновнија структура коју ће тражити, али се редовно појављује у компанијама које раде са претраге, обрада текста или системи за предлоге.

Хеш табеле и хеширање

Хеширање То је техника за додељивање нумеричког кључа (хеша) сваком податку на детерминистички начин, тако да можемо да чувамо и преузимамо елементе у готово константном времену, користећи тај кључ као индекс у интерној структури, обично низу.

La хеш табела Ово је структура података која користи овај механизам. Сваки елемент се чува као пар кључ-вредност: кључ се трансформише у индекс табеле помоћу хеш функције, а вредност (или референца на њу) се тамо чува. Касније, да бисте претражили, једноставно поново хеширајте кључ и приступите одговарајућој позицији.

Перформансе хеш табеле кључно зависе од три фактора: хеш функција изабрано (морате добро распоредити тастере да бисте избегли концентрацију), величина стола (недовољна величина узрокује много судара) и метод за управљање колизијама (повезивање са повезаним листама, отворено адресирање итд.). Ово је слично индекс у бази податакагде одабир одговарајуће структуре побољшава претраге и приступ.

Типичне вежбе хеш програмирања често захтевају, на пример, пронађите симетричне парове у низуРеконструкција комплетног итинерера путовања из појединачних летова, брза провера да ли је један низ подскуп другог или провера да ли су два низа дисјунктна, све коришћењем приближних O(1) претрага хеш табеле.

У већини модерних језика, структуре попут мапа, речник, хеш мапа или хеш скуп Они се интерно ослањају на хеш табеле, иако се програмеру нуди интерфејс високог нивоа.

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

Избор структуре података директно одређује који алгоритми имају смисла и каква ће бити њихова сложеност. Линеарни алгоритам претраживања на неуређена листа Понавља се кроз елементе један по један; ако променимо структуру у уравнотежено стабло претраживања или хеш таблицу, добијамо много боља времена.

На пример, ако желите да више пута тражите кључеве у великој колекцији, чување података у хеш табела или бинарно стабло претраживања Омогућава вам да дизајнирате алгоритме претраживања који су много бржи него ако користите једноставан несортирани низ. Исто важи и за редове приоритета и хипове за заказивање или алгоритме за најкраћи пут.

Насупрот томе, приликом дизајнирања алгоритма, често схватате да су вам потребна одређена својства: приступ индексу, брзо уметање на почетку, хијерархијски обиласци, претрага префикса итд. Ове потребе воде ваш избор структуре. низови, листе, стабла, графови, хеш табеле, покушаји...

Ова одговарајућа комбинација алгоритма и структуре података је оно што омогућава сложене апликације ефикасан и скалабиланБез добре основе, решења имају тенденцију да постану спора, тешка за разумевање и одржавање или немогућа за прилагођавање како количина информација расте.

Стога, савладавање алгоритама и структура података није готово неопходан захтев за свакога ко тежи да постане компетентан и конкурентан програмер на данашњем тржишту рада.

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

Многи људи се осећају заглављено када покушају да сами уче помоћу платформи попут LeetCode или CodewarsУобичајено је да се почне са „лаким“ вежбама и даље не зна где да се приступи проблему, на крају се гледа решење и није јасно како да се оно касније репродукује.

Практичан приступ обично комбинује неколико састојака: а добро теоријско објашњење Свака структура и алгоритам укључују визуелне примере, мноштво вођене праксе и, ако је могуће, подршку од некога са искуством како би вам помогли да усавршите своје вештине решавања проблема.

У шпанско-говорном подручју постоје стручњаци са богатим искуством који су допринели олакшавању овог учења. Један пример је рад Наставници са искуством у пословању и образовању који су објавили књиге и курсеве о основама програмирања, Јави, структурама података и програмским изазовима са играма, чинећи ове концепте приступачним на забаван и применљив начин на стварним пројектима.

Такође је уобичајено да академије и центри за обуку укључе посебне модуле о структурама података и алгоритмима у своје програме за веб програмере или програмере апликација. У многим случајевима, наглашава се одређени приступ. веома практично и засновано на пројектима, са вежбама све веће тежине и симулацијом типичних проблема техничког интервјуа.

Ако сте заглављени, праћење структуриране руте може помоћи: почните са низовима и листама, пролазећи кроз стекове и редове, затим стабла и основне графове, и коначно хеш табеле и покушаје, увек наизменично теоријска објашњења, мале примере кода и пуно индивидуалне праксе.

Приликом припреме за интервјуе, препоручљиво је прегледати не само структуре већ и алгоритми грубе силе и повезане класичне алгоритме (обилазак, претрага, сортирање, једноставно враћање уназад, основно динамичко програмирање) и осигурајте да можете наглас објаснити зашто сте изабрали одређену структуру и шта сложеност вашег решења.

Временом и извесна доследностОно што на први поглед делује као зид, на крају постаје скуп познатих алата које користите готово инстинктивно када се суочите са новим проблемима.

Добро разумевање шта су алгоритми, како функционишу главне структуре података и како су међусобно повезане омогућиће вам да пишете програме бржи, јаснији и робуснијиТо ће вам отворити врата у захтевним процесима селекције и осигурати да ваши пројекти, како академски тако и професионални, буду засновани на чврстим темељима са будућношћу.