Podatkovne strukture in algoritmi: popoln vodnik za programerje

Informatec Digital » Viri » Podatkovne strukture in algoritmi: popoln vodnik za programerje

Algoritmi in podatkovne strukture Gre za dva dela, ki se ujemata kot sestavljanka: eden opisuje postopek reševanja problema, drugi pa določa, kje in kako shranimo informacije. Čeprav se morda sliši akademsko, je obvladovanje tega para tisto, kar loči kodo, ki zgolj deluje, od tiste, ki leti in se skalira brez okvar.

Če se želite profesionalno ukvarjati s programiranjem, se pripraviti na tehnične razgovore ali preprosto nehati mučiti z vajami, kot sta LeetCode in Codewars, potrebujete trdne temelje v podatkovne strukture in algoritmiV tem članku boste videli, kaj so, zakaj so tako pomembni, katere glavne vrste obstajajo, katere osnovne operacije izvajajo in katera vprašanja se običajno pojavljajo na izpitih in izbirnih postopkih.

Kaj so podatkovne strukture in algoritmi?

Podatkovna struktura V bistvu gre za specifičen način organiziranja in shranjevanja informacij v pomnilniku, da se z njimi lahko učinkovito dela. Ta organizacija ni naključna: neposredno določa, katere operacije so hitre in katere postanejo drage (vstavljanje, iskanje, brisanje, premikanje itd.).

Ko izberete pravo podatkovno strukturo, lahko vaš program upravlja velike količine podatkov brez posebnega truda; če se odločite slabo, lahko celo majhna aplikacija postane počasna, porabi preveč pomnilnika ali pa jo sčasoma postane nemogoče vzdrževati.

Algoritem Gre za končno in urejeno zaporedje dobro definiranih korakov, ki pretvori vhodne podatke v izhodne podatke za rešitev določenega problema. Je kot kuharski recept: pove vam, kaj storiti, v kakšnem vrstnem redu in pod kakšnimi pogoji, vendar ga ne skrbi, kako shranite sestavine v hladilniku, kar bi bil del podatkovne strukture.

V računalništvu je vsak algoritem zasnovan z mislijo na vrsto podatkov, s katerimi bo deloval. Izbira podatkovne strukture ni nepomembna podrobnost: Struktura in algoritem gresta z roko v rokiIn majhne spremembe v enem od obeh delov lahko bodisi izboljšajo bodisi zmanjšajo učinkovitost.

S teoretičnega vidika so avtorji, kot je Niklaus Wirth, popularizirali idejo že v sedemdesetih letih prejšnjega stoletja, da algoritmi + podatkovne strukture = programiDesetletja pozneje ostaja enako res: ni pomembno, ali programirate v Javi, Pythonu, C++ ali pa prihajate z bootcampa, na razgovorih in resnih projektih se od vas bo zahtevalo, da znate dobro izbrati in kombinirati oba elementa.

Zakaj so tako pomembni pri programiranju?

V vsaki resnični aplikaciji, pa naj se zdi še tako preprosta, vedno delate s podatki: plače, izdelki, uporabniki, transakcije, poti, dokumentiDnevniški zapisi itd. Vprašanje ni, ali boste obravnavali podatke, temveč kako jih boste organizirali, da bo vaša koda hitra, jasna in enostavna za vzdrževanje.

Podatkovne strukture se uporabljajo za shranjevanje informacij na urejen in koherenten način glede na problem. Ni isto Vedno je treba dostopati do prvega elementa, iskati po ključu, premikati se po vrstnem redu, vstavljati na sredino ali pogosto brisati; vsak vzorec uporabe se bolje ujema z drugačno strukturo.

Algoritmi pa s svoje strani omogočajo učinkovito obdelati te podatke: razvrščanje, filtriranje, iskanje elementov, iskanje optimalnih poti, zaznavanje vzorcev z rudarjenje podatkov, optimizirati vire itd. Številni problemi, ki se zdijo težki, postanejo trivialni, ko najdete pravo kombinacijo algoritma in podatkovne strukture.

Na tehničnih razgovorih za razvoj programske opreme se redko zgodi, da vam zastavijo vprašanje, ki se ne nanaša neposredno na te teme. Včasih vprašanje izrecno omenja strukturo, na primer »glede na binarno drevo ...«, drugič pa je implicitno: »želimo prešteti, koliko knjig ima vsak avtor«, kar nakazuje uporabo zgoščevalna tabela ali zemljevid ključ-vrednost.

Poleg tega se formalno in strokovno usposabljanje pogosto vrti okoli tega področja. Številne univerze in programi visokošolskega izobraževanja vključujejo predmet o ... Podatkovne strukture in algoritmi, z uradnim programom, predpogoji, teoretičnimi in praktičnimi vajami, izpiti in nalogami, ker velja za osrednji predmet vsakega programskega inženirja.

Predpogoji in potrebni temelji

Da bi kar najbolje izkoristili preučevanje podatkovnih struktur in algoritmov, je koristno imeti nekaj znanja o splošnem programskem jeziku, kot je npr. Java, Python ali C++Ni vam treba biti guru, vendar morate biti seznanjeni z osnovnimi koncepti, kot so spremenljivke, podatkovni tipi, pogojni izrazi, zanke, funkcije in posredovanje parametrov.

Prav tako zelo pomaga razumeti idejo algoritmična kompleksnost in notacija Big O: kako se čas izvajanja ali poraba pomnilnika povečuje z naraščanjem velikosti podatkov (n). Poznavanje razlikovanja med O(1), O(log n), O(n), O(n log n) in O(n²) vam omogoča, da primerjate alternative s trezno presojo in utemeljite svoje odločitve.

Drug pomemben vidik je, da sem se nekoliko prepiral z reševanje problemovStrukturirane programerske vaje, majhni logični izzivi, preproste kata itd. Bolj ko boste urili svoj "nos" za razčlenitev problema na korake, lažje boste videli, katera podatkovna struktura ustreza posameznemu primeru.

Nekateri učni načrti izrecno navajajo predpogoji ali sopredpogoji Za tečaj Podatkovne strukture in algoritmi morate imeti opravljene Osnove programiranja, Programiranje I ali Diskretno matematiko. To je smiselno: brez trdnih temeljev osnovnega programiranja in nekaj logike se pri tej temi zlahka znajdete razočarani.

Končno, nekaj poznavanje praktičnih okoljih v resničnem svetu (kot so majhni spletni projekti, skripti ali konzolne aplikacije) vam pomaga bolje vizualizirati, za kaj boste uporabljali posamezno strukturo, namesto da jo vidite zgolj kot nekaj akademskega.

Najpogosteje uporabljene podatkovne strukture

V računalništvu obstaja veliko podatkovnih strukturVendar pa obstaja skupina "osnovnih" funkcij, ki se vedno znova ponavljajo: polja (vektorji), skladi, čakalne vrste, povezani seznami, drevesa, grafi, poskusi in zgoščevalne tabele. Razumevanje njihovega delovanja, operacij, ki jih ponujajo, in njihovih tipičnih stroškov je ključnega pomena za nemoten prehod skozi programiranje.

Zdaj bomo šli pregledajte vsakega posebej, z glavno idejo, tipičnimi operacijami in primeri problemov, ki se običajno pojavljajo pri pouku, vajah in razgovorih za službo razvijalcev.

Polja

Matrika Je najpreprostejša linearna podatkovna struktura in ena najbolj razširjenih. Sestavljena je iz sosednjega bloka pomnilnika, ki shranjuje zbirko elementov istega tipa, dostopnih prek celoštevilskega indeksa, običajno od nič.

Predstavljajte si tabelo velikosti 4, ki vsebuje vrednosti 1, 2, 3 in 4. Vsaka pozicija ima indeks (0, 1, 2, 3) in do katerega koli elementa z njegovim indeksom lahko dostopate neposredno v konstantnem času O(1). Zaradi tega so polja zelo učinkovita za naključno branje.

Obstajata dve glavni kategoriji: enodimenzionalne matrike (ena sama vrsta elementov) in večdimenzionalni nizi (na primer matrike, ki so polja polja). Mnogi programski jeziki ponujajo obe različici izvorno ali z rahlimi razlikami v sintaksi in zmogljivosti.

Osnovne operacije na matriki so običajno:

• Vstavi: postavitev elementa na določen položaj, kar lahko v statičnih nizih vključuje premikanje drugih elementov.
• Pridobi: dostop do elementa pri danem indeksu, običajno O(1).
• Izbriši: izbriše ali označi kot prazen element na določenem položaju, običajno s premikom elementov v levo.
• Velikost: preveri, koliko elementov je shranjenih ali največjo kapaciteto polja.

Na razgovorih in izpitih so takšne vaje zelo pogoste. poiščite drugi minimum v tabeliIskanje prvega neponavljajočega se celega števila, združevanje dveh že razvrščenih polj ali prerazporeditev pozitivnih in negativnih števil ob ohranjanju določenih lastnosti. Vse to je odvisno od dostopa do indeksa in linearnih ali dvojnih prehodov.

Skladi

Baterija Gre za linearno podatkovno strukturo, ki sledi načelu LIFO: zadnji noter, prvi ven. Predstavljajte si kup knjig, postavljenih ena na drugo: knjige lahko jemljete ali odlagate samo od zgoraj.

To vedenje pomeni, da Dostopamo samo do elementa, ki je na vrhu skladaSrednjega elementa ne moremo odstraniti, ne da bi najprej odstranili elemente nad njim. Zaradi tega je idealna struktura za modeliranje zgodovine dejanj (razveljavitev), ugnezdenih klicev funkcij, navigacije (nazaj/naprej) itd.

Tipične operacije skladanja so:

• Push: vstavi nov element na vrh.
• Pop: izvleči in vrniti element na vrhu, s čimer zmanjša velikost sklada.
• Vrh ali pokuka: posvetujte se z zgornjim elementom, ne da bi ga izbrisali.
• je prazno: preverite, ali je baterija prazna.

V kontekstu intervjujev se pojavijo težave, kot so naslednje: ovrednoti izraze v postfiksni notaciji (RPN), razvrščanje elementov samo z uporabo skladov ali preverjanje, ali je niz oklepajev (in drugih simbolov) pravilno uravnotežen z uporabo push in pop.

V praksi veliko notranjih implementacij jezikov (na primer sklad sistemskih klicev) delujejo po istih načelih, čeprav jih ne vidimo neposredno.

Čakalne vrste

Rep Gre za še eno linearno podatkovno strukturo, vendar namesto načela LIFO uporablja model FIFO: prvi noter, prvi ven. Najbolj jasna analogija je vrsta ljudi, ki čakajo na blagajni v kinu.

V standardni čakalni vrsti so elementi Na koncu dodajo, na začetku pa odvzamejo.Kdor prej pride, prej melje, je idealen za upravljanje čakajočih nalog, procesov operacijskega sistema, zahtev strežnika, čakalnih vrst za tiskanje itd.

Osnovne operacije čakalne vrste vključujejo:

• V vrsti: vstavi nov element na konec čakalne vrste.
• Na vrsti: odstrani in vrni element, ki se nahaja na začetku.
• Spredaj ali zgoraj: preverite prvi element, ne da bi ga odstranili.
• je prazno: preveri, ali je čakalna vrsta prazna.

Pri programerskih izzivih je običajno, da vas na primer vprašajo, implementirajte sklad z uporabo dveh čakalnih vrst, obrne prvih k elementov čakalne vrste brez spreminjanja preostalih ali generira binarna števila od 1 do n z uporabo FIFO vedenja čakalne vrste.

Poleg osnovnega repa obstajajo tudi različice, kot so krožni rep, prednostna čakalna vrsta ali dvojne čakalne vrste (deque), ki ponujajo dodatne operacije in izboljšajo zmogljivost v določenih scenarijih.

povezani seznami

Povezani seznam Povezani seznam je prav tako linearna struktura, vendar se notranje zelo razlikuje od polj. Namesto uporabe sosednjega bloka pomnilnika je sestavljen iz redkih vozlišč, ki so med seboj povezana s sklici ali kazalci.

Vsako vozlišče običajno vsebuje dva dela: podatke ki jih je treba shraniti, in kazalec (ali več), ki kaže na naslednje vozlišče v zaporedju (in v primeru dvojno povezanih seznamov tudi na prejšnje). Seznam se upravlja s sklicevanjem na njegovo glavo, ki kaže na prvo vozlišče, v bolj kompleksnih seznamih pa se ohranja tudi sklicevanje na rep.

Obstajata dve glavni različici:

• enojno povezan seznam: vsako vozlišče kaže samo na naslednje; pot je običajno v eno smer.
• dvojno povezan seznamVsako vozlišče kaže na naslednje in prejšnje vozlišče, kar omogoča dvosmerno prehajanje in učinkovitejše operacije brisanja.

Tipične operacije na povezanih seznamih vključujejo:

• Vstavi na glavo: vstavi novo vozlišče na začetek seznama.
• Vstavi na koncu: doda vozlišče na konec in posodobi čakalno vrsto, če ta obstaja.
• Brisanje: odstranitev določenega vozlišča s prilagajanjem kazalcev sosednjih vozlišč.
• Izbriši na vrhu: izbriši prvo vozlišče in premakni glavo na naslednje.
• Iskalnik: prečkanje seznama in iskanje določene vrednosti.
• je prazno: preveri, ali je glava nična in zato seznam nima elementov.

Takšnih težav je v razredih in na razgovorih veliko. obrni povezan seznam, zaznati, ali obstaja cikel (običajno z uporabo algoritma "želva in zajec"), pridobiti vozlišče N s štetjem od konca ali odstraniti podvojena vozlišča, pri čemer vedno previdno ravnati s kazalci.

Povezani seznami se pogosto uporabljajo za implementacijo zgoščevalne tabele z veriženjemseznami sosednosti v grafih in dinamične podatkovne strukture, kjer se elementi pogosto vstavljajo in brišejo.

Arbole

Drevo Gre za hierarhično podatkovno strukturo, sestavljeno iz vozlišč, povezanih z robovi. Za razliko od splošnih grafov drevo nima ciklov: vedno obstajajo koren, otroci, starši, sorojenci, listi, ravni in poddrevesa z organizacijo tipa "družina" ali "organizacijska shema".

Drevesa so zelo koristna, kadar si to želimo predstavljajo hierarhične odnose ali pa problem razdelite na manjše podprobleme: datotečne sisteme, menije, strukture DOM v brskalnikih, odločitvena drevesa v umetni inteligenci itd.

Obstaja veliko vrst dreves, vključno z:

• N-arno drevo: vsako vozlišče ima lahko spremenljivo (in morda veliko) število otrok.
• Uravnoteženo drevo: ohranja svoje veje na podobni globini, da se prepreči poslabšanje delovanja.
• Binarno drevo: vsako vozlišče ima največ dva otroka (levo in desno).
• Binarno iskalno drevo (BST): binarno drevo z lastnostjo, da je vse levo od vozlišča manjše, vse desno pa večje (glede na neki kriterij urejanja).
• AVL drevo, rdeče-črno, 2-3 in druge različiceTo so uravnotežena iskalna drevesa, ki zagotavljajo dobre omejitve kompleksnosti pri operacijah vstavljanja, brisanja in iskanja.

V praksi so najpogostejši pri vajah binarno drevo in binarno iskalno drevoTipične težave vključujejo izračun višine drevesa, iskanje k-te največje vrednosti v BST, seznam vozlišč na določeni razdalji od korena ali določanje prednikov določenega vozlišča.

Poleg tega so algoritmi prečkanja (predorder, inorder, postorder, level by level) temeljni za številne nadaljnje procese: razvrščeno tiskanje, vrednotenje izrazov, serializacijo in deserializacijo dreves itd.

grafov

Graf Posplošuje koncept drevesa tako, da dovoljuje cikle in več poljubnih povezav med vozlišči. Sestavljen je iz množice oglišč (vozlišč) in množice robov, ki povezujejo pare oglišč, včasih s pripadajočo težo ali ceno.

Obstaja več vrst grafov: neusmerjen (robovi nimajo smeri, odnos je dvosmeren) in usmerjen (Rebovi imajo začetno in ciljno točko.) Lahko jih tudi razvrstimo kot utežene ali neutežene, povezane ali nepovezane, s cikli ali brez njih itd.

V kodi so grafi običajno predstavljeni na dva osnovna načina:

• Matrika sosednosti: matrika, kjer celica označuje, ali obstaja rob med vozlišči i in j (in morebiti težo povezave).
• Seznam sosednosti: za vsako vozlišče je shranjen seznam njegovih sosedov, kar prihrani pomnilnik v redkih grafih.

Najbolj klasični algoritmi prečkanja so Iskanje v širino (BFS) in poglobljeno iskanje (DFS)Oba se uporabljata kot osnovna gradnika za številne probleme: preverjanje, ali je graf povezan, odkrivanje ciklov, iskanje povezanih komponent itd.

Pri tehničnih testih se pogosto zgodi, da se od uporabnikov zahteva implementacija BFS in DFS, preverjanje, ali graf tvori drevo, štetje števila robov ali iskanje najkrajše poti med dvema vozliščema (na primer na zemljevidu mest) z uporabo variant, kot sta Dijkstra ali BFS v neuteženih grafih.

Poskusna ali predponska drevesa

Poskus (ali predponsko drevo) je drevesna podatkovna struktura, optimizirana za obdelavo nizov znakov, še posebej uporabna pri delu s slovarji besed, sistemi za samodejno dokončanje ali iskanjem predpon.

V triju vsako vozlišče običajno predstavlja znak, poti od korena do določenih vozlišč pa označujejo popolne besedeKončna besedna vozlišča so običajno na nek način označena (na primer z logičnim indikatorjem), da se ločijo od preprostih predpon.

Če besede »top«, »thus« in »their« shranimo v vzorec, bomo del začetne poti delili za vse tiste, ki se začnejo z istimi črkami, kar bo omogočilo iskanje in predloge po predponi v zelo učinkovit čas, sorazmerno z dolžino besede, ki jo iščemo, in ne s skupnim številom shranjenih besed.

Pogoste operacije in težave s poskusi vključujejo: preštejte, koliko besed je shranjenih, izpiše vse besede v leksikografskem vrstnem redu, razvrsti elemente tabele z vstavljanjem v vzorec, ustvari veljavne besede iz nabora črk ali zgradi strukture, podobne slovarju T9.

V kontekstu razgovorov to ni najosnovnejša struktura, ki jo bodo zahtevali, vendar se redno pojavlja v podjetjih, ki delajo z iskanja, obdelava besedil ali sistemi za predloge.

Zgoščevalne tabele in zgoščevanje

Zgoščevanje Gre za tehniko, s katero se vsakemu podatku na determinističen način dodeli numerični ključ (hash), tako da lahko elemente shranjujemo in pridobivamo v skoraj konstantnem času, pri čemer ta ključ uporabljamo kot indeks v notranji strukturi, običajno v polju.

La zgoščevalna tabela To je podatkovna struktura, ki izkorišča ta mehanizem. Vsak element je shranjen kot par ključ-vrednost: ključ se s pomočjo zgoščevalne funkcije pretvori v indeks tabele in vrednost (ali sklic nanjo) se shrani tam. Kasneje za iskanje preprosto ponovno zgoščite ključ in dostopajte do ustreznega položaja.

Učinkovitost zgoščevalne tabele je ključno odvisna od treh dejavnikov: zgoščevalna funkcija izbrani (ključe morate dobro razporediti, da se izognete koncentraciji), velikost mize (nezadostna velikost povzroča veliko trkov) in metoda za obvladovanje trkov (povezovanje s povezanimi seznami, odprto naslavljanje itd.). To je podobno kot indeks v zbirki podatkovkjer odločitev o ustrezni strukturi izboljša iskanje in dostop.

Tipične vaje programiranja zgoščevalnih funkcij pogosto zahtevajo na primer poiščite simetrične pare v matrikiRekonstrukcija celotnega itinerarja potovanja iz posameznih letov, hitro preverjanje, ali je ena tabela podmnožica druge, ali preverjanje, ali sta dve tabeli disjunktni, vse z izkoriščanjem približnih O(1) iskanj v zgoščevalni tabeli.

V večini sodobnih jezikov so strukture, kot so zemljevid, slovar, zgoščevalni zemljevid ali zgoščevalni nabor Notranje se zanašajo na zgoščevalne tabele, čeprav je programerju na voljo vmesnik na visoki ravni.

Kako so algoritmi in podatkovne strukture povezani

Izbira podatkovne strukture neposredno določa, kateri algoritmi so smiselni in kakšna bo njihova kompleksnost. Linearni iskalni algoritem na neurejen seznam Iterira skozi elemente enega za drugim; če strukturo spremenimo v uravnoteženo iskalno drevo ali zgoščevalno tabelo, dobimo veliko boljše čase.

Na primer, če želite večkrat iskati ključe v veliki zbirki, shranjevanje podatkov v zgoščevalna tabela ali binarno iskalno drevo Omogoča vam oblikovanje iskalnih algoritmov, ki so veliko hitrejši kot če bi uporabili preprosto nesortirano tabelo. Enako velja za čakalne vrste in kopice s prednostjo za razporejanje ali algoritme najkrajše poti.

Nasprotno pa se pri načrtovanju algoritma pogosto zavedate, da potrebujete določene lastnosti: dostop do indeksa, hitro vstavljanje na začetku, hierarhično prečkanje, iskanje predpon itd. Te potrebe vodijo vašo izbiro strukture. polja, seznami, drevesa, grafi, zgoščevalne tabele, poskusi...

Ta ustrezna kombinacija algoritma in podatkovne strukture omogoča izvajanje kompleksnih aplikacij. učinkovito in prilagodljivoBrez dobre podlage rešitve postanejo počasne, težko razumljive in vzdržne ali pa jih je nemogoče prilagoditi, ko količina informacij narašča.

Zato obvladovanje algoritmov in podatkovnih struktur ni skoraj nepogrešljiva zahteva za vse, ki si želijo postati kompetenten in konkurenčen programer na današnjem trgu dela.

Kako se naučiti podatkovnih struktur in algoritmov

Mnogi ljudje se počutijo zataknjene, ko se poskušajo učiti sami s platformami, kot je LeetCode ali CodewarsPogosto se zgodi, da začnemo z "lahkimi" vajami in še vedno ne vemo, kje se lotiti problema, na koncu pa pogledamo rešitev in nam ni jasno, kako jo nato reproducirati.

Praktičen pristop običajno združuje več sestavin: a dobra teoretična razlaga Vsaka struktura in algoritem vključuje vizualne primere, veliko vodenih vaj in, če je mogoče, podporo nekoga z izkušnjami, ki vam bo pomagal izpopolniti vaše sposobnosti reševanja problemov.

V špansko govorečem svetu obstajajo strokovnjaki z bogatimi izkušnjami, ki so prispevali k olajšanju tega učenja. En primer je delo Učitelji z izkušnjami v poslovnem in izobraževalnem sektorju ki so objavili knjige in tečaje o osnovah programiranja, Javi, podatkovnih strukturah in programskih izzivih z igrami, s čimer so te koncepte na zabaven in uporaben način približali resničnim projektom.

Prav tako je običajno, da akademije in centri za usposabljanje v svoje programe za spletne razvijalce ali programerje aplikacij vključijo posebne module o podatkovnih strukturah in algoritmih. V mnogih primerih je poudarek na določenem pristopu. zelo praktično in projektno usmerjeno, z vajami naraščajoče težavnosti in simulacijo tipičnih težav na tehničnih razgovorih.

Če se znajdete v zadregi, vam lahko pomaga sledenje strukturirani poti: začnite s polji in seznami, prehajal je skozi sklade in čakalne vrste, nato drevesa in osnovne grafe ter na koncu zgoščevalne tabele in poskuse, vedno izmenično s teoretičnimi razlagami, majhnimi primeri kode in veliko individualne vaje.

Pri pripravi na razgovore je priporočljivo pregledati ne le strukture, temveč tudi algoritmi surove sile in pripadajoče klasične algoritme (prehodi, iskanja, razvrščanje, preprosto sledenje nazaj, osnovno dinamično programiranje) ter poskrbite, da boste lahko na glas razložili, zakaj ste izbrali določeno strukturo in kaj ... kompleksnost vaše rešitve.

Sčasoma in nekaj doslednostiKar se sprva zdi kot zid, se na koncu spremeni v skupek znanih orodij, ki jih skoraj nagonsko uporabljaš, ko se soočiš z novimi težavami.

Dobro razumevanje algoritmov, delovanja glavnih podatkovnih struktur in njihove medsebojne povezanosti vam bo omogočilo pisanje programov. hitrejši, jasnejši in robustnejšiTo vam bo odprlo vrata v zahtevnih izbirnih postopkih in zagotovilo, da bodo vaši projekti, tako akademski kot profesionalni, temeljili na trdnih temeljih s prihodnostjo.