Strukture podataka i algoritmi: kompletan vodič za programere

Informatec Digital » Resursi » Strukture podataka i algoritmi: kompletan vodič za programere

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

Ako želite da se bavite profesionalnim programiranjem, pripremite se za tehničke intervjue ili jednostavno prestanete da se mučite sa vježbama poput LeetCode-a i Codewars-a, potrebna vam je solidna osnova u strukture podataka i algoritmiU ovom članku ćete vidjeti šta su oni, 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 selekcije.

Šta 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 efikasno raditi. Ova organizacija nije slučajna: ona direktno 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 kao recept za kuhanje: govori vam šta da radite, kojim redoslijedom i pod kojim uvjetima, ali se ne brine o tome kako čuvate 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 ta dva dijela mogu ili poboljšati ili smanjiti performanse.

Sa teorijske perspektive, autori poput Niklausa Wirtha popularizirali su ideju još 70-ih. algoritmi + strukture podataka = programiDecenijama kasnije, ostaje podjednako istinito: nije važno da li programirate u Javi, Pythonu, C++ ili dolazite iz bootcampa, ono što će se od vas tražiti na intervjuima i ozbiljnim projektima jeste da znate kako dobro odabrati i kombinovati oba elementa.

Zašto su toliko važni u programiranju?

U bilo kojoj aplikaciji iz stvarnog svijeta, koliko god jednostavnom izgledala, uvijek radite s podacima: plate, 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 se koriste za pohranjivanje informacija na uredan i koherentan način u skladu s problemom. Nije isto Stalno pristupljanje prvom elementu, pretraživanje po ključu, kretanje po redoslijedu, umetanje u sredinu ili često brisanje; svaki obrazac korištenja bolje odgovara drugačijoj strukturi.

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

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

Nadalje, formalna i profesionalna obuka se često vrti oko ovog područja. Mnogi univerziteti i programi visokog obrazovanja uključuju predmet o... Strukture podataka i algoritmi, sa službenim programom, preduvjetima, teorijskim i praktičnim sesijama, ispitima i zadacima, jer se smatra osnovnim predmetom za svakog softverskog inženjera.

Preduslovi i neophodni temelji

Da 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, uvjetni izrazi, petlje, funkcije i prosljeđivanje parametara.

Takođe mnogo pomaže u razumijevanju ideje o 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ćava vam da uporedite alternative sa zdravim rasuđivanjem i opravdate svoje odluke.

Još jedan važan aspekt je to što sam se malo borio sa rešavanje problemaStrukturirane vježbe programiranja, mali logički izazovi, jednostavne kata, itd. Što više trenirate svoj "nos" da razložite problem na korake, lakše će vam biti vidjeti koja struktura podataka odgovara svakom slučaju.

Neki nastavni planovi i programi eksplicitno navode preduvjeti ili korekviziti Za kurs Strukture podataka i algoritmi, potrebno je da imate položene Osnove programiranja, Programiranje I ili Diskretnu matematiku. Ovo ima smisla: bez solidne osnove u osnovnom programiranju i malo logike, lako se frustrirati ovom temom.

Konačno, imajući neko upoznavanje sa praktična okruženja iz stvarnog svijeta (kao što su mali web projekti, skripte ili konzolne aplikacije) pomaže vam da bolje vizualizirate za šta ćete koristiti svaku strukturu, umjesto da je posmatrate kao nešto čisto akademsko.

Najčešće korištene strukture podataka

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

Sad idemo pregledajte svaki, sa svojom glavnom idejom, tipičnim operacijama i primjerima problema koji se obično pojavljuju na časovima, vježbama i razgovorima za posao za programere.

Nizovi

Niz To je najjednostavnija linearna struktura podataka i jedna od najčešće korištenih. Sastoji se od kontinuiranog 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 direktno pristupiti bilo kojem elementu s njegovim indeksom u konstantnom vremenu O(1). Ovo čini nizove vrlo efikasnim 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:

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

Na intervjuima i ispitima, ovakve vježbe su vrlo česte. 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 ovo oslanja na pristup indeksu i linearne ili dvostruke obilaske.

Hromade

Baterija To je linearna struktura podataka koja slijedi LIFO princip: Posljednji 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 steka.Ne možemo ukloniti srednji element bez prethodnog uklanjanja elemenata iznad njega. Zbog toga je idealna struktura za modeliranje historije akcija (poništavanje), ugniježđenih poziva funkcija, navigacije (nazad/naprijed) itd.

Tipične operacije sa stekom su:

• Guranje: ubacite novu stavku na vrh.
• tata: izdvojiti i vratiti element na vrhu, smanjujući veličinu steka.
• Vrh ili pogled: konsultuje gornji element bez njegovog 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 stekova ili provjera da li je niz zagrada (i drugih simbola) pravilno balansiran korištenjem push i pop funkcija.

U praksi, mnoge interne implementacije jezika (na primjer, stek sistemskih poziva) rade po istim principima, iako ih ne vidimo direktno.

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četkuKo prvi dođe, njemu prvi služi, što ga čini idealnim za upravljanje neriješenim zadacima, procesima operativnog sistema, zahtjevima servera, redovima čekanja za ispis itd.

Osnovne operacije reda čekanja uključuju:

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

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

Pored osnovnog repa, postoje i 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

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

Svaki čvor obično sadrži dva dijela: podataka koji se trebaju pohraniti i pokazivač (ili nekoliko) koji pokazuje na sljedeći čvor u nizu (i, u slučaju dvostruko povezanih lista, i na prethodni). Lista se upravlja putem reference na njen početak, koji pokazuje na prvi čvor, a u složenijim listama 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 ukazuje na sljedeći i prethodni čvor, olakšavajući dvosmjerno kretanje i efikasnije operacije brisanja.

Tipične operacije na povezanim listama uključuju:

• Umetni na početak: umetnite novi čvor na početak liste.
• Umetni na kraju: dodaje čvor na kraj, ažurirajući red ako postoji.
• izbrisati: uklonite određeni čvor, prilagođavajući pokazivače susjednih čvorova.
• Izbriši na početku: izbrišite prvi čvor i pomaknite glavu na sljedeći.
• PRETRAGA: pregledavanje liste u potrazi za određenom vrijednošću.
• prazno jeProvjeri da li je zaglavlje null i da li stoga lista nema elemenata.

Problemi poput ovih obiluju na predavanjima i intervjuima. obrnuto povezanu listu, otkriti da li postoji ciklus (obično koristeći algoritam "kornjača i zec"), dobiti čvor N brojanjem od kraja ili ukloniti duplikate čvorova, uvijek pažljivo rukujući pokazivačima.

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

Árboles

Drvo To je hijerarhijska struktura podataka sastavljena od čvorova povezanih rubovima. Za razliku od općih grafova, stablo nema cikluse: uvijek postoji korijen, djeca, roditelji, braća i sestre, listovi, nivoi i podstabla, s organizacijom tipa "porodica" ili "organizacijska shema".

Drveće je veoma korisno kada želimo predstavljaju hijerarhijske odnose ili podijeliti problem na manje podprobleme: datotečne sisteme, menije, DOM strukture u preglednicima, stabla odlučivanja u vještačkoj inteligenciji itd.

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

• N-arno stablo: svaki čvor može imati varijabilan (i moguće veliki) broj djece.
• Uravnoteženo drvo: 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 varijanteOvo su uravnotežena stabla pretraživanja koja garantuju dobra ograničenja složenosti pri operacijama umetanja, brisanja i pretraživanja.

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

Nadalje, algoritmi prolaska kroz proces (preorder, inorder, postorder, level by level) su fundamentalni za mnoge naredne procese: sortirano štampanje, evaluaciju izraza, serijalizaciju i deserijalizaciju stabla itd.

grafovi

Grafikon Generalizuje koncept stabla dozvoljavajući cikluse i višestruke proizvoljne veze između čvorova. Sastoji se od skupa vrhova (čvorova) i skupa ivica koje povezuju parove vrhova, ponekad sa pridruženom težinom ili cijenom.

Postoji nekoliko vrsta grafova: neusmeren (rubovi nemaju smjer, odnos je dvosmjeran) i usmjeren (Grave imaju početnu i odredišnu tačku). Također se mogu klasificirati kao ponderirane ili neponderirane, povezane ili nepovezane, sa ili bez ciklusa itd.

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

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

Najklasičniji algoritmi za prelazak su Pretraga u širinu (BFS) I to detaljna pretraga (DFS)Oba se koriste kao osnovni gradivni blokovi za mnoštvo problema: provjeru povezanosti grafa, otkrivanje ciklusa, pronalaženje povezanih komponenti itd.

U tehničkim testovima, uobičajeno je da se od vas traži da implementirate BFS i DFS, provjerite da li graf formira stablo, prebrojite broj ivica ili pretražite najkraćim putevima između dva čvora (na primjer, na mapi gradova) korištenjem varijanti kao što su Dijkstra ili BFS 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, sistemima za automatsko dovršavanje ili pretragama prefiksa.

U trie-u, svaki čvor obično predstavlja znak, a putevi od korijena do određenih čvorova označavaju kompletne riječiPosljednji čvorovi riječi obično su označeni na neki način (na primjer, logičkim indikatorom) kako bi se razlikovali od jednostavnih prefiksa.

Ako pohranimo riječi „top“, „thus“ i „their“ u trie, podijelit ćemo dio početne putanje za sve one koje počinju istim slovima, omogućavajući pretrage i prijedloge po prefiksu u vrlo efikasno vrijeme, proporcionalno dužini 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 u leksikografskom redoslijedu, 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 redovno pojavljuje u kompanijama koje rade sa pretrage, obrada teksta ili sistemi za predlaganje.

Hash tabele i hashiranje

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

La hash table Ovo je struktura podataka koja koristi ovaj mehanizam. Svaki element se pohranjuje kao par ključ-vrijednost: ključ se transformira u indeks tabele pomoću hash funkcije, a vrijednost (ili referenca na nju) se tamo pohranjuje. Kasnije, za pretragu, jednostavno ponovo heširajte ključ i pristupite odgovarajućoj poziciji.

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

Tipične vježbe heš programiranja često zahtijevaju, na primjer, pronađite simetrične parove u nizuRekonstrukcija kompletnog itinerera putovanja iz pojedinačnih letova, brza provjera da li je jedan niz podskup drugog ili provjera da li su dva niza disjunktna, sve korištenjem približnog broja pretraga heš tabele od O(1).

U većini modernih jezika, strukture poput mapa, rječnik, hash mapa ili hash skup Oni se interno oslanjaju na heš tabele, iako se programeru nudi interfejs visokog nivoa.

Kako su algoritmi i strukture podataka povezani

Izbor strukture podataka direktno određuje koji algoritmi imaju smisla i kakva će biti njihova složenost. Linearni algoritam pretraživanja na neuređena lista Iterira kroz elemente jedan po jedan; ako promijenimo strukturu u uravnoteženo stablo pretraživanja ili heš tabelu, dobijamo mnogo bolja vremena.

Na primjer, ako želite više puta pretraživati ​​ključeve u velikoj kolekciji, pohranjivanje podataka u hash tabela ili binarno stablo pretraživanja Omogućava vam da dizajnirate algoritme pretraživanja koji su mnogo brži nego ako koristite jednostavan nesortirani niz. Isto važi 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, pretraga prefiksa itd. Ove potrebe vode vaš izbor strukture. nizovi, liste, stabla, grafovi, hash tabele, pokušaji...

Ova odgovarajuća kombinacija algoritma i strukture podataka omogućava izradu složenih aplikacija. efikasno i skalabilnoBez dobre osnove, rješenja imaju tendenciju da postanu spora, teška za razumijevanje i održavanje ili ih je nemoguće prilagoditi kako količina informacija raste.

Stoga, savladavanje algoritama i struktura podataka nije gotovo neophodan uslov za svakoga ko teži da postane kompetentan i konkurentan programer na današnjem tržištu rada.

Kako naučiti strukture podataka i algoritme

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

Praktičan pristup obično kombinuje 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 svijetu španskog govornog područja postoje stručnjaci sa bogatim iskustvom koji su doprinijeli olakšavanju ovog učenja. Jedan primjer je rad Profesori sa iskustvom u poslovanju i obrazovanju koji su objavili knjige i kurseve o osnovama programiranja, Javi, strukturama podataka i programerskim izazovima s igrama, čineći ove koncepte dostupnim na zabavan i primjenjiv način na stvarne projekte.

Također je uobičajeno da akademije i centri za obuku uključuju specifične module o strukturama podataka i algoritmima u svoje programe za web developere ili programere aplikacija. U mnogim slučajevima, naglasak se stavlja na određeni pristup. vrlo praktično i zasnovano 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 stekove i redove čekanja, zatim stabla i osnovne grafove, i na kraju heš tabele i pokušaje, uvijek naizmjenično teorijsko objašnjenje, 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, pretrage, sortiranje, jednostavno vraćanje unatrag, osnovno dinamičko programiranje) i osigurajte da možete naglas objasniti zašto ste odabrali određenu strukturu i šta složenost vašeg rješenja.

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

Dobro razumijevanje algoritama, kako funkcionišu glavne strukture podataka i kako su one međusobno povezane omogućit će vam da pišete programe. brže, jasnije i robusnijeTo će vam otvoriti vrata u zahtjevnim procesima selekcije i osigurati da vaši projekti, i akademski i profesionalni, budu zasnovani na čvrstim temeljima s budućnošću.