Strukture podataka i algoritmi: cjeloviti vodič za programere

Informatec Digital » Sredstva » Strukture podataka i algoritmi: cjeloviti vodič za programere

Algoritmi i strukture podataka To su dva dijela koja se uklapaju poput slagalice: jedan opisuje postupak rješavanja problema, a drugi određuje gdje i kako pohranjujemo informacije. Iako možda zvuči akademski, savladavanje ovog para ono je što razlikuje kod koji samo radi od onog koji leti i skalira se bez lomljenja.

Ako se želite profesionalno baviti programiranjem, pripremiti se za tehničke razgovore ili jednostavno prestati mučiti se s vježbama poput LeetCodea i Codewarsa, potrebna vam je čvrsta osnova u strukture podataka i algoritmiU ovom članku vidjet ćete što su, zašto su toliko važni, koje glavne vrste postoje, koje osnovne operacije obavljaju i koja se pitanja obično pojavljuju na ispitima i u procesima odabira.

Što su strukture podataka i algoritmi?

strukturu podataka To je, u osnovi, specifičan način organiziranja i pohranjivanja informacija u memoriji kako bi se s njima moglo učinkovito raditi. Ova organizacija nije slučajna: ona izravno određuje koje su operacije brze, a koje postaju skupe (umetanje, pretraživanje, brisanje, kretanje itd.).

Kada odaberete pravu strukturu podataka, vaš program može upravljati velike količine podataka bez puno truda; kada loše odaberete, čak i mala aplikacija može postati spora, trošiti previše memorije ili je s vremenom postati nemoguće održavati.

Algoritam To je konačan i uređen niz dobro definiranih koraka koji transformira ulaze u izlaze kako bi riješio određeni problem. To je poput recepta za kuhanje: govori vam što učiniti, kojim redoslijedom i pod kojim uvjetima, ali ga ne brine kako pohranjujete sastojke u hladnjaku, što bi bio dio strukture podataka.

U informatici, svaki algoritam je dizajniran imajući na umu vrstu podataka s kojima će raditi. Izbor strukture podataka nije mali detalj: Struktura i algoritam idu ruku pod rukuA male promjene u jednom od dva dijela mogu ili poboljšati ili smanjiti performanse.

S teorijskog gledišta, autori poput Niklausa Wirtha popularizirali su ideju još 70-ih algoritmi + strukture podataka = programiDesetljećima kasnije, ostaje jednako istinito: nije važno programirate li u Javi, Pythonu, C++-u ili dolazite li s bootcampa, ono što će se od vas tražiti na razgovorima za posao i ozbiljnim projektima jest znati kako dobro odabrati i kombinirati oba elementa.

Zašto su toliko važni u programiranju?

U bilo kojoj stvarnoj primjeni, koliko god jednostavnom izgledala, uvijek radite s podacima: plaće, proizvodi, korisnici, transakcije, rute, dokumentiZapisi dnevnika itd. Pitanje nije hoćete li rukovati podacima, već kako ćete ih organizirati tako da vaš kod bude brz, jasan i jednostavan za održavanje.

Strukture podataka koriste se za pohranjivanje informacija na uredan i koherentan način prema problemu. No es lo mismo Uvijek je potrebno pristupiti prvom elementu, pretraživati ​​po ključu, kretati se po redoslijedu, umetati u sredinu ili često brisati; svaki obrazac korištenja bolje odgovara drugačijoj strukturi.

Sa svoje strane, algoritmi omogućuju učinkovito obrađivati ​​te podatke: sortirati ih, filtrirati ih, tražiti elemente, pronaći optimalne rute, otkriti uzorke pomoću rudarjenje podataka, optimizirati resurse itd. Mnogi problemi koji se čine teškima postaju trivijalni kada pronađete pravu kombinaciju algoritma i strukture podataka.

U tehničkim intervjuima za razvoj softvera rijetko se postavlja pitanje koje se izravno ne odnosi na ove teme. Ponekad pitanje eksplicitno spominje strukturu, poput "uz dano binarno stablo...", a ponekad je implicitno: "želimo prebrojati koliko knjiga ima svaki autor", što sugerira korištenje hash tablica ili mapa ključ-vrijednost.

Nadalje, formalno i profesionalno osposobljavanje često se vrti oko ovog područja. Mnoga sveučilišta i programi visokog obrazovanja uključuju predmet o... Strukture podataka i algoritmi, sa službenim programom, preduvjetima, teorijskim i praktičnim vježbama, ispitima i zadacima, jer se smatra ključnim predmetom za svakog softverskog inženjera.

Preduvjeti i potrebni temelji

Kako biste izvukli maksimum iz proučavanja struktura podataka i algoritama, korisno je imati neko poznavanje programskog jezika opće namjene, kao što je Java, Python ili C++Ne morate biti guru, ali morate biti upoznati s osnovnim konceptima kao što su varijable, tipovi podataka, uvjeti, petlje, funkcije i prosljeđivanje parametara.

Također puno pomaže u razumijevanju ideje algoritamska složenost i notacija Big O: kako vrijeme izvršavanja ili korištenje memorije raste s povećanjem veličine podataka (n). Poznavanje razlikovanja između O(1), O(log n), O(n), O(n log n) i O(n²) omogućuje vam da usporedite alternative sa zdravim rasuđivanjem i opravdate svoje odluke.

Drugi važan aspekt je mala borba s Rješavanje problemaStrukturirane programske vježbe, mali logički izazovi, jednostavne kata itd. Što više trenirate svoj "nos" da razbije problem na korake, lakše će biti vidjeti koja struktura podataka odgovara svakom slučaju.

Neki nastavni planovi i programi izričito navode preduvjeti ili korekviziti Za tečaj Strukture podataka i algoritmi morate imati položene Osnove programiranja, Programiranje I ili Diskretnu matematiku. To je logično: bez čvrstih temelja u osnovnom programiranju i malo logike, lako se frustrirati s ovim predmetom.

Konačno, imajući neko poznavanje s praktična okruženja u stvarnom svijetu (kao što su mali web projekti, skripte ili konzolne aplikacije) pomaže vam da bolje vizualizirate za što ćete koristiti svaku strukturu, umjesto da je doživljavate kao nešto isključivo akademsko.

Najčešće korištene strukture podataka

U informatici postoji mnogo struktura podatakaMeđutim, postoji skupina "osnovnih" funkcija koje se ponavljaju iznova i iznova: nizovi (vektori), stogovi, redovi čekanja, povezane liste, stabla, grafovi, pokušaji i hash tablice. Razumijevanje kako rade, koje operacije nude i njihovih tipičnih troškova ključno je za nesmetano kretanje kroz programiranje.

Sad idemo pregledajte svaki od njih, s glavnom idejom, tipičnim operacijama i primjerima problema koji se obično pojavljuju na nastavi, vježbama i razgovorima za posao za razvojne programere.

Nizovi

Niz To je najjednostavnija linearna struktura podataka i jedna od najčešće korištenih. Sastoji se od susjednog bloka memorije koji pohranjuje kolekciju elemenata istog tipa, dostupnih putem cjelobrojnog indeksa, obično počevši od nule.

Zamislite niz veličine 4 koji sadrži vrijednosti 1, 2, 3 i 4. Svaka pozicija ima indeks (0, 1, 2, 3) i možete izravno pristupiti bilo kojem elementu s njegovim indeksom u konstantnom vremenu O(1). Zbog toga su nizovi vrlo učinkoviti za nasumično čitanje.

Postoje dvije glavne kategorije: jednodimenzionalni nizovi (jedan red elemenata) i višedimenzionalni nizovi (na primjer, matrice, koje su nizovi nizova). Mnogi programski jezici nude obje varijante izvorno ili s malim razlikama u sintaksi i performansama.

Osnovne operacije na nizu su obično:

• Umetnuti: postavljanje elementa na određenu poziciju, što u statičkim nizovima može uključivati ​​pomicanje drugih elemenata.
• Dobiti: pristup elementu na zadanom indeksu, obično O(1).
• Izbrisati: izbrisati ili označiti kao prazan element na određenoj poziciji, obično pomicanjem elemenata ulijevo.
• Veličina: provjerava koliko je elemenata pohranjeno ili maksimalni kapacitet niza.

Vježbe poput ovih vrlo su česte na razgovorima za posao i ispitima. pronaći drugi minimum nizaPronalaženje prvog neponavljajućeg cijelog broja, spajanje dva već sortirana niza ili promjena redoslijeda pozitivnih i negativnih brojeva uz zadržavanje određenih svojstava. Sve se to oslanja na pristup indeksu i linearne ili dvostruke obilaske.

Slojevi

Baterija To je linearna struktura podataka koja slijedi LIFO princip: Zadnji unutra, prvi van. Zamislite hrpu knjiga postavljenih jedna na drugu: knjige možete uzimati ili stavljati samo s vrha.

Ovo ponašanje znači da Pristupamo samo elementu koji se nalazi na vrhu stekaNe možemo ukloniti srednji element bez prethodnog uklanjanja elemenata iznad njega. Zbog toga je idealna struktura za modeliranje povijesti akcija (poništavanje), ugniježđenih poziva funkcija, navigacije (natrag/naprijed) itd.

Tipične operacije sa stogom su:

• Gurati: umetnite novu stavku na vrh.
• Pop: izdvojiti i vratiti element na vrhu, smanjujući veličinu stoga.
• Vrh ili pogled: konzultirati gornji element bez brisanja.
• prazno je: provjerite je li baterija prazna.

U kontekstu intervjua uočavaju se problemi poput sljedećih: evaluiraj izraze u postfiksnoj notaciji (RPN), sortiranje elemenata korištenjem samo stogova ili provjera je li niz zagrada (i drugih simbola) ispravno uravnotežen korištenjem push i pop.

U praksi, mnoge interne implementacije jezika (na primjer, stog sistemskih poziva) rade prema istim načelima, iako ih ne vidimo izravno.

Redovi čekanja

Rep To je još jedna linearna struktura podataka, ali umjesto LIFO principa, koristi FIFO model: Prvi unutra, Prvi van. Najjasnija analogija je red ljudi koji čekaju na blagajni u kinu.

U standardnom redu čekanja, elementi su Dodaju na kraju, a oduzimaju na početkuTko prvi dođe, njemu prvi služi, što ga čini idealnim za upravljanje zadacima na čekanju, procesima operacijskog sustava, zahtjevima poslužitelja, redovima ispisa itd.

Osnovne operacije reda čekanja uključuju:

• U redu: umetnite novu stavku na kraj reda čekanja.
• U redu čekanja: ukloni i vrati element koji se nalazi na početku.
• Prednji ili gornji dio: pogledajte prvu stavku bez njenog uklanjanja.
• prazno je: provjeri je li red prazan.

U programerskim izazovima uobičajeno je da vas pitaju, na primjer, implementirati stog koristeći dva reda čekanja, obrnuti prvih k elemenata reda bez promjene ostatka ili generirati binarne brojeve od 1 do n koristeći FIFO ponašanje reda.

Osim osnovnog repa, postoje varijacije kao što su kružni rep, red prioriteta ili dvostruki redovi (deque), koji nude dodatne operacije i poboljšavaju performanse u određenim scenarijima.

povezane liste

Povezani popis Povezana lista je također linearna struktura, ali se interno jako razlikuje od nizova. Umjesto korištenja susjednog bloka memorije, sastoji se od rijetkih čvorova koji su međusobno povezani referencama ili pokazivačima.

Svaki čvor obično sadrži dva dijela: podatke koji se pohranjuju i pokazivač (ili nekoliko) koji pokazuje na sljedeći čvor u nizu (i, u slučaju dvostruko povezanih popisa, i na prethodni). Popisom se upravlja putem reference na njegov početak, koji pokazuje na prvi čvor, a u složenijim popisima održava se i referenca na rep.

Postoje dvije glavne varijante:

• jednostruko povezana lista: svaki čvor pokazuje samo na sljedeći; put je obično u jednom smjeru.
• dvostruko povezana listaSvaki čvor pokazuje na sljedeći i prethodni čvor, što olakšava dvosmjerno kretanje i učinkovitije operacije brisanja.

Tipične operacije na povezanim listama uključuju:

• Umetni na početak: umetnite novi čvor na početak popisa.
• Umetni na kraju: dodavanje čvora na kraj, ažuriranje reda ako postoji.
• Izbrisati: ukloniti određeni čvor, prilagođavajući pokazivače susjednih čvorova.
• Izbriši na početku: izbrišite prvi čvor i premjestite glavu na sljedeći.
• Traži: pregledavanje popisa u potrazi za određenom vrijednošću.
• prazno jeprovjeri je li zaglavlje null i stoga lista nema elemenata.

Problemi poput ovih obiluju u nastavi i na razgovorima za posao. obrnuti povezani popis, otkriti postoji li ciklus (obično korištenjem algoritma "kornjača i zec"), dobiti čvor N brojeći od kraja ili ukloniti duplicirane čvorove, uvijek pažljivo rukujući pokazivačima.

Povezane liste se široko koriste za implementaciju hash tablice s ulančavanjemliste susjednosti u grafovima i dinamičke strukture podataka gdje se elementi često ubacuju i brišu.

drveće

Stablo To je hijerarhijska struktura podataka sastavljena od čvorova povezanih bridovima. Za razliku od općih grafova, stablo nema cikluse: uvijek postoji korijen, djeca, roditelji, braća i sestre, listovi, razine i podstabla, s organizacijom tipa "obitelj" ili "organizacijski dijagram".

Drveće je vrlo korisno kada želimo predstavljaju hijerarhijske odnose ili podijeliti problem na manje podprobleme: datotečne sustave, izbornike, DOM strukture u preglednicima, stabla odlučivanja u umjetnoj inteligenciji itd.

Postoji mnogo vrsta drveća, uključujući:

• N-arno stablo: svaki čvor može imati varijabilan (i moguće velik) broj djece.
• Uravnoteženo stablo: održava svoje grane na sličnoj dubini kako bi se izbjeglo smanjenje performansi.
• Binarno stablo: svaki čvor ima maksimalno dva potomka (lijevo i desno).
• Binarno stablo pretraživanja (BST): binarno stablo sa svojstvom da je sve lijevo od čvora manje, a sve desno veće (prema nekom kriteriju uređenja).
• AVL stablo, crveno-crno, 2-3 i druge varijanteTo su uravnotežena stabla pretraživanja koja jamče dobra ograničenja složenosti pri operacijama umetanja, brisanja i pretraživanja.

U praksi, najčešći u vježbama su binarno stablo i binarno stablo pretraživanjaTipični problemi uključuju izračunavanje visine stabla, pronalaženje k-te maksimalne vrijednosti u BST-u, popisivanje čvorova na određenoj udaljenosti od korijena ili određivanje predaka određenog čvora.

Nadalje, algoritmi prolaska (preorder, inorder, postorder, level by level) temeljni su za mnoge sljedeće procese: sortirani ispis, procjenu izraza, serijalizaciju i deserijalizaciju stabla itd.

grafovima

Grafikon Generalizira koncept stabla dopuštajući cikluse i višestruke proizvoljne veze između čvorova. Sastoji se od skupa vrhova (čvorova) i skupa bridova koji povezuju parove vrhova, ponekad s pridruženom težinom ili cijenom.

Postoji nekoliko vrsta grafova: neusmjeren (rubovi nemaju osjećaj smjera, odnos je dvosmjeran) i usmjerena (Rubovi imaju početnu i odredišnu točku). Također se mogu klasificirati kao ponderirani ili neponderirani, povezani ili nepovezani, s ciklusima ili bez njih itd.

U kodu se grafovi obično predstavljaju na dva osnovna načina:

• Matrica susjednosti: matrica gdje ćelija označava postoji li rub između vrha i i j (i moguće težinu veze).
• Popis susjedstva: za svaki vrh pohranjuje se popis njegovih susjeda, što štedi memoriju u rijetkim grafovima.

Najklasičniji algoritmi za prolazak su Pretraživanje u širinu (BFS) i dubinsko pretraživanje (DFS)Oba se koriste kao osnovni građevni blokovi za mnoštvo problema: provjeru je li graf povezan, otkrivanje ciklusa, pronalaženje povezanih komponenti itd.

U tehničkim testovima uobičajeno je da se od vas traži implementacija BFS-a i DFS-a, provjera formira li graf stablo, brojanje bridova ili pretraživanje najkraći putevi između dva čvora (na primjer, na karti gradova) korištenjem varijanti poput Dijkstre ili BFS-a u neponderiranim grafovima.

Pokušaji ili prefiksna stabla

Pokušaj (ili prefiksno stablo) je struktura podataka u obliku stabla optimizirana za rukovanje nizovima znakova, posebno korisna pri radu s rječnicima riječi, sustavima za automatsko dovršavanje ili pretraživanjima prefiksa.

U trie-u, svaki čvor obično predstavlja znak, a putovi od korijena do određenih čvorova označavaju potpune riječiZavršni čvorovi riječi obično su označeni na neki način (na primjer, Booleovim indikatorom) kako bi se razlikovali od jednostavnih prefiksa.

Ako riječi „top“, „thus“ i „their“ pohranimo u trie, podijelit ćemo dio početnog puta za sve one koji počinju istim slovima, omogućujući pretraživanja i prijedloge po prefiksu u vrlo učinkovito vrijeme, proporcionalno duljini riječi koju tražimo, a ne ukupnom broju pohranjenih riječi.

Uobičajene operacije i problemi s pokušajima uključuju: prebrojati koliko je riječi pohranjeno, ispisati sve riječi leksikografskim redoslijedom, sortirati elemente niza umetanjem u trie, generirati valjane riječi iz skupa slova ili izgraditi strukture slične T9 rječniku.

U kontekstu intervjua, to nije najosnovnija struktura koju će tražiti, ali se redovito pojavljuje u tvrtkama koje rade s pretraživanja, obrada teksta ili sustavi za prijedloge.

Hash tablice i hashiranje

Hashiranje To je tehnika dodjeljivanja numeričkog ključa (hash-a) svakom dijelu podataka na deterministički način, tako da možemo pohranjivati ​​i dohvaćati elemente u gotovo konstantnom vremenu, koristeći taj ključ kao indeks u unutarnjoj strukturi, obično nizu.

La hash tablica Ovo je struktura podataka koja koristi ovaj mehanizam. Svaki element pohranjuje se kao par ključ-vrijednost: ključ se pretvara u indeks tablice pomoću hash funkcije, a vrijednost (ili referenca na nju) pohranjuje se tamo. Kasnije, za pretraživanje, jednostavno ponovno hashirajte ključ i pristupite odgovarajućoj poziciji.

Performanse hash tablice ključno ovise o tri faktora: hash funkcija odabrano (morate dobro rasporediti tipke kako biste izbjegli koncentraciju), veličina stola (nedovoljna veličina uzrokuje mnogo sudara) i metoda za upravljanje sudarima (povezivanje s povezanim listama, otvoreno adresiranje itd.). To je slično indeks u bazi podatakagdje odabir odgovarajuće strukture poboljšava pretrage i pristup.

Tipične vježbe hash programiranja često zahtijevaju, na primjer, pronaći simetrične parove u nizuRekonstrukcija kompletnog itinerera putovanja iz pojedinačnih letova, brza provjera je li jedan niz podskup drugog ili provjera jesu li dva niza disjunktna, sve korištenjem približnog broja O(1) pretraživanja hash tablice.

U većini modernih jezika, strukture poput karta, rječnik, hash mapa ili hash skup Interno se oslanjaju na hash tablice, iako se programeru nudi sučelje visoke razine.

Kako su algoritmi i strukture podataka povezani

Izbor strukture podataka izravno određuje koji algoritmi imaju smisla i kakva će biti njihova složenost. Linearni algoritam pretraživanja na neuređeni popis Iterira kroz elemente jedan po jedan; ako promijenimo strukturu u uravnoteženo stablo pretraživanja ili hash tablicu, dobivamo puno bolja vremena.

Na primjer, ako želite više puta pretraživati ​​ključeve u velikoj kolekciji, pohranjivanje podataka u hash tablica ili binarno stablo pretraživanja Omogućuje vam dizajniranje algoritama pretraživanja koji su puno brži nego ako koristite jednostavan nesortirani niz. Isto vrijedi i za redove prioriteta i hrpe za raspoređivanje ili algoritme najkraćeg puta.

Suprotno tome, prilikom dizajniranja algoritma često shvatite da su vam potrebna određena svojstva: pristup indeksu, brzo umetanje na početku, hijerarhijski obilazak, pretraživanje prefiksa itd. Te potrebe vode vaš izbor strukture. nizovi, liste, stabla, grafovi, hash tablice, pokušaji...

Ova odgovarajuća kombinacija algoritma i strukture podataka omogućuje izradu složenih aplikacija. učinkovito i skalabilnoBez dobre osnove, rješenja postaju spora, teška za razumjeti i održavati ili ih je nemoguće prilagoditi kako količina informacija raste.

Stoga, savladavanje algoritama i struktura podataka nije gotovo neizostavan uvjet za sve koji žele postati kompetentan i konkurentan programer na današnjem tržištu rada.

Kako naučiti strukture podataka i algoritme

Mnogi se ljudi osjećaju zaglavljeno kada pokušavaju sami učiti s platformama poput LeetCode ili CodewarsUobičajeno je započeti s "jednostavnim" vježbama i dalje ne znati odakle pristupiti problemu, te na kraju gledati u rješenje i nije jasno kako ga kasnije reproducirati.

Praktičan pristup obično kombinira nekoliko sastojaka: a dobro teorijsko objašnjenje Svaka struktura i algoritam uključuju vizualne primjere, obilje vođene vježbe i, ako je moguće, podršku nekoga s iskustvom kako bi vam pomogli usavršiti vještine rješavanja problema.

U španjolskom govornom području postoje stručnjaci s bogatim iskustvom koji su doprinijeli olakšavanju ovog učenja. Jedan primjer je rad Nastavnici s iskustvom u poslovanju i obrazovanju koji su objavili knjige i tečajeve o osnovama programiranja, Javi, strukturama podataka i programskim izazovima s igrama, čineći te koncepte dostupnima na zabavan i primjenjiv način u stvarnim projektima.

Također je uobičajeno da akademije i centri za obuku uključuju specifične module o strukturama podataka i algoritmima unutar svojih programa za web developere ili programere aplikacija. U mnogim slučajevima naglašava se određeni pristup. vrlo praktično i temeljeno na projektima, s vježbama sve veće težine i simulacijom tipičnih problema tehničkih intervjua.

Ako ste zaglavljeni, praćenje strukturirane rute može pomoći: počnite s nizovima i listama, prolazeći kroz stogove i redove, zatim stabla i osnovne grafove, te na kraju hash tablice i pokušaje, uvijek izmjenjujući teorijska objašnjenja, male primjere koda i puno individualne vježbe.

Prilikom pripreme za intervjue, preporučljivo je pregledati ne samo strukture već i algoritmi grube sile i pridružene klasične algoritme (obilaske, pretraživanja, sortiranje, jednostavno vraćanje unatrag, osnovno dinamičko programiranje) te se pobrinite da možete naglas objasniti zašto ste odabrali određenu strukturu i što složenost vašeg rješenja.

Tijekom vremena i određena dosljednostOno što se na prvi pogled čini kao zid, na kraju postane skup poznatih alata koje gotovo instinktivno koristite kada se suočite s novim problemima.

Dobro razumijevanje algoritama, kako funkcioniraju glavne strukture podataka i kako su međusobno povezane omogućit će vam pisanje programa. brže, jasnije i robusnijeOtvorit će vam vrata u zahtjevnim procesima selekcije i osigurati da vaši projekti, i akademski i profesionalni, budu utemeljeni na čvrstim temeljima s budućnošću.