Datastrukturer og algoritmer: en komplett guide for programmerere

Informatec Digital » Ressurser » Datastrukturer og algoritmer: en komplett guide for programmerere

Algoritmer og datastrukturer De er to brikker som passer sammen som et puslespill: den ene skisserer prosedyren for å løse problemet, og den andre bestemmer hvor og hvordan vi lagrer informasjonen. Selv om det kan høres akademisk ut, er det å mestre dette paret som skiller en kode som bare fungerer fra en som flyr og skalerer uten å bryte.

Hvis du vil forfølge profesjonell programmering, forberede deg til tekniske intervjuer, eller rett og slett slutte å slite med øvelser som LeetCode og Codewars, trenger du et solid grunnlag i datastrukturer og algoritmerGjennom denne artikkelen vil du se hva de er, hvorfor de er så viktige, hvilke hovedtyper som finnes, hvilke grunnleggende operasjoner de utfører og hvilke spørsmål som vanligvis dukker opp i eksamener og utvalgsprosesser.

Hva er datastrukturer og algoritmer?

en datastruktur Det er i bunn og grunn en spesifikk måte å organisere og lagre informasjon i minnet på for å kunne operere effektivt med den. Denne organiseringen er ikke tilfeldig: den bestemmer direkte hvilke operasjoner som er raske og hvilke som blir kostbare (sett inn, søk, slett, bla gjennom osv.).

Når du velger riktig datastruktur, kan programmet ditt håndtere store datamengder uten å bry deg; når du velger dårlig, kan selv et lite program bli tregt, bruke for mye minne eller bli umulig å vedlikeholde over tid.

En algoritme Det er en endelig og ordnet sekvens av veldefinerte trinn som omdanner input til output for å løse et spesifikt problem. Det er som en matoppskrift: den forteller deg hva du skal gjøre, i hvilken rekkefølge og under hvilke forhold, men den bryr seg ikke om hvordan du oppbevarer ingrediensene i kjøleskapet, som ville være datastrukturdelen.

Innen informatikk er hver algoritme utformet med tanke på den typen data den skal fungere med. Valget av datastruktur er ikke en liten detalj: Struktur og algoritme går hånd i håndOg små endringer i en av de to delene kan enten øke eller senke ytelsen.

Fra et teoretisk perspektiv populariserte forfattere som Niklaus Wirth ideen allerede på 70-tallet om at algoritmer + datastrukturer = programmerFlere tiår senere er det fortsatt like sant: det spiller ingen rolle om du programmerer i Java, Python, C++ eller om du kommer fra en bootcamp, det som kreves av deg i intervjuer og seriøse prosjekter er å vite hvordan du velger og kombinerer begge elementene godt.

Hvorfor er de så viktige i programmering?

I enhver applikasjon i den virkelige verden, uansett hvor enkel den kan virke, jobber du alltid med data: lønninger, produkter, brukere, transaksjoner, ruter, dokumenterLoggoppføringer osv. Spørsmålet er ikke om du skal håndtere data, men hvordan du skal organisere dem slik at koden din er rask, tydelig og enkel å vedlikeholde.

Datastrukturer brukes til å lagre informasjon på en ordnet og sammenhengende måte i henhold til problemet. Det er ikke det samme Å alltid måtte åpne det første elementet, søke etter nøkkel, bla gjennom i rekkefølge, sette inn i midten eller slette ofte; hvert bruksmønster passer bedre med en annen struktur.

Algoritmer på sin side tillater behandle dataene effektivtsorter dem, filtrer dem, søk etter elementer, finn optimale ruter, oppdag mønstre med data mining, optimalisere ressurser, osv. Mange problemer som virker vanskelige blir trivielle når du finner den rette kombinasjonen av algoritme og datastruktur.

I tekniske intervjuer for programvareutvikling er det sjelden man blir stilt et spørsmål som ikke direkte tar for seg disse temaene. Noen ganger nevner spørsmålet eksplisitt strukturen, for eksempel «gitt et binærtre…», og andre ganger er det implisitt: «vi ønsker å telle hvor mange bøker hver forfatter har», noe som tyder på å bruke en hash-tabell eller nøkkel-verdi-kart.

Videre dreier formell og profesjonell opplæring seg ofte om dette området. Mange universiteter og høyere utdanningsprogrammer inkluderer et emne om... Datastrukturer og algoritmer, med et offisielt program, forkunnskaper, teori- og praksisøkter, eksamener og oppgaver, fordi det regnes som et kjernefag for enhver programvareingeniør.

Forutsetninger og nødvendige grunnlag

For å få mest mulig ut av å studere datastrukturer og algoritmer, er det nyttig å ha litt kjennskap til et generelt programmeringsspråk, for eksempel Java, Python eller C++Du trenger ikke å være en guru, men du må være komfortabel med grunnleggende konsepter som variabler, datatyper, betingelser, løkker, funksjoner og parameteroverføring.

Det hjelper også mye å forstå ideen om algoritmisk kompleksitet og Big O-notasjon: hvordan utførelsestid eller minnebruk øker når datastørrelsen (n) øker. Å vite hvordan man skiller mellom O(1), O(log n), O(n), O(n log n) og O(n² lar deg sammenligne alternativer med god dømmekraft og begrunne beslutningene dine.

Et annet viktig aspekt er å ha hatt litt krangel med ProblemløsningStrukturerte programmeringsøvelser, små logiske utfordringer, enkle kata, osv. Jo mer du trener «nesen» din til å dele opp et problem i trinn, desto lettere blir det å se hvilken datastruktur som passer i hvert enkelt tilfelle.

Noen læreplaner sier eksplisitt forkunnskaper eller sameiekrav For kurset Datastrukturer og algoritmer må du ha bestått Programmeringsgrunnleggende, Programmering I eller Diskret matematikk. Dette gir mening: uten et solid grunnlag i grunnleggende programmering og litt logikk er det lett å bli frustrert over dette faget.

Endelig litt kjennskap til praktiske miljøer i den virkelige verden (som små webprosjekter, skript eller konsollapplikasjoner) hjelper deg med å bedre visualisere hva du skal bruke hver struktur til, i stedet for å se det som noe rent akademisk.

De vanligste datastrukturene

Innen informatikk finnes det mange datastrukturerDet finnes imidlertid en gruppe «grunnleggende» funksjoner som gjentas gang på gang: arrayer (vektorer), stabler, køer, lenkede lister, trær, grafer, forsøk og hashtabeller. Å forstå hvordan de fungerer, hvilke operasjoner de tilbyr og deres typiske kostnader er nøkkelen til å bevege seg problemfritt gjennom programmering.

Nå skal vi gjennomgå hver enkelt, med hovedideen, typiske operasjoner og eksempler på problemer som vanligvis dukker opp i klasser, øvelser og jobbintervjuer for utviklere.

Matriser

Matrisen Det er den enkleste lineære datastrukturen og en av de mest brukte. Den består av en sammenhengende minneblokk som lagrer en samling elementer av samme type, tilgjengelig via en heltallsindeks, vanligvis startende fra null.

Tenk deg en matrise av størrelse 4 som inneholder verdiene 1, 2, 3 og 4. Hver posisjon har en indeks (0, 1, 2, 3) og du kan få direkte tilgang til et hvilket som helst element med indeksen i konstant tid O(1). Dette gjør arrayer svært effektive for tilfeldig avlesning.

Det er to hovedkategorier: endimensjonale matriser (en enkelt rad med elementer) og flerdimensjonale arrays (for eksempel matriser, som er matriser av matriser). Mange programmeringsspråk tilbyr begge variantene innebygd eller med små forskjeller i syntaks og ytelse.

De grunnleggende operasjonene på en array er vanligvis:

• Sett inn: plassering av et element i en bestemt posisjon, noe som i statiske arrayer kan innebære å forskyve andre elementer.
• Bli: tilgang til elementet ved en gitt indeks, vanligvis O(1).
• Slett: slett eller merk som tomt elementet på en bestemt posisjon, vanligvis ved å flytte elementer til venstre.
• Størrelse: sjekk hvor mange elementer som er lagret eller den maksimale kapasiteten til arrayet.

I intervjuer og eksamener er slike øvelser svært vanlige. finn det andre minimumet i en matriseÅ finne det første ikke-repeterende heltallet, slå sammen to allerede sorterte matriser, eller endre rekkefølgen på positive og negative tall samtidig som visse egenskaper opprettholdes. Alt dette er avhengig av indekstilgang og lineære eller doble traverseringer.

Stabler

Batteriet Det er en lineær datastruktur som følger LIFO-prinsippet: Sist inn, først ut. Tenk deg en stabel med bøker plassert oppå hverandre: du kan bare ta eller legge bøker ovenfra.

Denne oppførselen betyr at Vi får bare tilgang til elementet som er øverst i stakkenVi kan ikke fjerne det midterste elementet uten først å fjerne elementene over det. Dette gjør det til en ideell struktur for modellering av handlingshistorikk (angre), nestede funksjonskall, navigasjon (frem/tilbake) osv.

Typiske stakkoperasjoner er:

• Skyv: sett inn et nytt element øverst.
• Pop: trekk ut og returner elementet øverst, noe som reduserer størrelsen på stabelen.
• Topp eller titt: se det øverste elementet uten å slette det.
• er tom: sjekk om batteriet er tomt.

I intervjusammenheng ser man problemer som følgende: evaluere uttrykk i postfiksnotasjon (RPN), sortere elementer kun ved hjelp av stabler, eller sjekke om en streng med parenteser (og andre symboler) er riktig balansert ved hjelp av push og pop.

I praksis er mange interne implementeringer av språk (for eksempel systemkallstakk) fungerer etter de samme prinsippene, selv om vi ikke ser dem direkte.

Køer

Halen Det er en annen lineær datastruktur, men i stedet for å følge LIFO-prinsippet, bruker den FIFO-modellen: Først inn, først ut. Den tydeligste analogien er en kø med folk som venter ved en billettluke på kino.

I en standardkø er elementene De legger til på slutten og trekker seg tilbake i begynnelsenFørstemann til mølla, noe som gjør den ideell for å administrere ventende oppgaver, operativsystemprosesser, serverforespørsler, utskriftskøer osv.

Grunnleggende køoperasjoner inkluderer:

• Kø: sett inn et nytt element på slutten av køen.
• Sett av køfjern og returner elementet som ligger i begynnelsen.
• Foran eller øverst: se på det første elementet uten å fjerne det.
• er tom: sjekk om køen er tom.

I programmeringsutfordringer er det vanlig at de spør deg, for eksempel, implementer en stabel ved hjelp av to køer, reversere de første k elementene i en kø uten å endre resten, eller generere binære tall fra 1 til n ved å bruke FIFO-oppførselen til køen.

Foruten den grunnleggende halen, finnes det variasjoner som sirkulær hale, prioritetskøen eller doble køer (deque), som tilbyr tilleggsoperasjoner og forbedrer ytelsen i visse scenarier.

koblede lister

Den lenkede listen En lenket liste er også en lineær struktur, men internt er den svært forskjellig fra arrayer. I stedet for å bruke en sammenhengende minneblokk, består den av sparsomme noder som er koblet til hverandre via referanser eller pekere.

Hver node inneholder vanligvis to deler: dataene som skal lagres og en peker (eller flere) som peker til neste node i sekvensen (og, i tilfelle dobbeltlenkede lister, også til den forrige). Listen administreres gjennom en referanse til hodet, som peker til den første noden, og i mer komplekse lister opprettholdes også en referanse til halen.

Det er to hovedvarianter:

• Rett og slett lenket listehver node peker bare til den neste; banen går vanligvis i én retning.
• dobbeltlenket listeHver node peker til neste og forrige node, noe som muliggjør toveis traversering og mer effektive slettingsoperasjoner.

Typiske operasjoner på lenkede lister inkluderer:

• Sett inn ved hodet: sett inn en ny node i begynnelsen av listen.
• Sett inn ved slutten: legg til en node på slutten, og oppdater køen hvis den finnes.
• Deletefjerner en spesifikk node, justerer pekerne til nabonoder.
• SlettVedHodet: slett den første noden og flytt hodet til den neste.
• Søk: bla gjennom listen på jakt etter en bestemt verdi.
• er tom: sjekk om head-verdien er null og at listen derfor ikke har noen elementer.

Slike problemer florerer i klasser og intervjuer reverser en lenket liste, oppdage om det er en syklus (vanligvis ved å bruke algoritmen "skilpadde og hare"), hente node N ved å telle fra slutten, eller fjerne dupliserte noder, og alltid håndtere pekere forsiktig.

Lenkede lister brukes mye til å implementere hash-tabeller med kjedekoblingtilstøtende lister i grafer og dynamiske datastrukturer der elementer ofte settes inn og slettes.

trær

Et tre Det er en hierarkisk datastruktur som består av noder forbundet med kanter. I motsetning til vanlige grafer har ikke et tre sykluser: det finnes alltid en rot, barn, foreldre, søsken, blader, nivåer og undertrær, med en organisering av typen "familie" eller "organisasjonskart".

Trær er veldig nyttige når vi vil representere hierarkiske forhold eller dele et problem inn i mindre delproblemer: filsystemer, menyer, DOM-strukturer i nettlesere, beslutningstrær i kunstig intelligens, osv.

Det finnes mange typer trær, inkludert:

• N-ary-treethver node kan ha et variabelt (og muligens stort) antall barn.
• Balansert tre: holder grenene på samme dybde for å unngå ytelsesforringelse.
• Binært trehver node har maksimalt to barn (venstre og høyre).
• Binært søketre (BST): binært tre med egenskapen at alt til venstre for en node er mindre og alt til høyre er større (i henhold til et bestemt rekkefølgekriterium).
• AVL-tre, rød-svart, 2-3 og andre varianterDette er balanserte søketrær som garanterer gode kompleksitetsgrenser i innsettings-, slettings- og søkeoperasjoner.

I praksis er de vanligste i øvelsene binært tre og binært søketreTypiske problemer inkluderer å beregne høyden på treet, finne den k-te maksimumsverdien i en BST, liste opp nodene i en viss avstand fra roten, eller bestemme forfedrene til en bestemt node.

Videre er traverseringsalgoritmer (forhåndsbestilling, inorder, postordre, nivå for nivå) grunnleggende for mange påfølgende prosesser: sortert utskrift, uttrykksevaluering, treserialisering og deserialisering, etc.

Grafer

En graf Den generaliserer konseptet med et tre ved å tillate sykluser og flere vilkårlige forbindelser mellom noder. Den består av et sett med noder og et sett med kanter som forbinder par av noder, noen ganger med en tilhørende vekt eller kostnad.

Det finnes flere typer grafer: ustyrt (kantene har ingen retningssans, forholdet er toveis) og regissert (Kanter har et startpunkt og en destinasjon). De kan også klassifiseres som vektede eller uvektede, sammenkoblede eller ikke-sammenkoblede, med eller uten sykluser, osv.

I kode representeres grafer vanligvis på to grunnleggende måter:

• Tilstøtende matriseen matrise der cellen indikerer om det er en kant mellom hjørne i og j (og muligens vekten av forbindelsen).
• NærhetslisteFor hvert hjørne lagres en liste over naboene, noe som sparer minne i sparsomme grafer.

De mest klassiske traverseringsalgoritmene er Bredde-først-søk (BFS) og dybdesøk (DFS)Begge brukes som grunnleggende byggeklosser for en rekke problemer: å sjekke om en graf er sammenhengende, oppdage sykluser, finne tilkoblede komponenter, osv.

I tekniske tester er det vanlig å bli bedt om å implementere BFS og DFS, sjekke om en graf danner et tre, telle antall kanter eller søke korteste veier mellom to noder (for eksempel på et kart over byer) ved hjelp av varianter som Dijkstra eller BFS i uvektede grafer.

Forsøk eller prefikstrær

Prøven (eller prefikstre) er en treformet datastruktur som er optimalisert for håndtering av tegnstrenger, spesielt nyttig når man arbeider med ordbøker, autofullføringssystemer eller prefikssøk.

I et trie representerer hver node vanligvis et tegn, og stiene fra roten til bestemte noder markerer fullstendige ordDe siste ordnodene er vanligvis merket på en eller annen måte (for eksempel med en boolsk indikator) for å skille dem fra enkle prefikser.

Hvis vi lagrer ordene «topp», «således» og «deres» i et trie, vil vi dele en del av den opprinnelige stien for alle de som begynner med de samme bokstavene, noe som gir mulighet for søk og forslag etter prefiks i veldig effektiv tid, proporsjonal med lengden på ordet vi leter etter og ikke med det totale antallet ord som er lagret.

Vanlige operasjoner og problemer med forsøk inkluderer: telle hvor mange ord som er lagret, skrive ut alle ord i leksikografisk rekkefølge, sortere elementer i en matrise ved å sette dem inn i en trie, generere gyldige ord fra et sett med bokstaver eller bygge strukturer som ligner på en T9-ordbok.

I intervjusammenhenger er det ikke den mest grunnleggende strukturen de vil be om, men den dukker opp regelmessig i selskaper som jobber med søk, tekstbehandling eller forslagssystemer.

Hash-tabeller og hashing

Hashing Det er en teknikk for å tilordne en numerisk nøkkel (hash) til hvert dataelement på en deterministisk måte, slik at vi kan lagre og hente elementer i nesten konstant tid, ved å bruke den nøkkelen som en indeks i en intern struktur, vanligvis en matrise.

La hasjtabell Dette er datastrukturen som utnytter denne mekanismen. Hvert element lagres som et nøkkel-verdi-par: nøkkelen transformeres til en tabellindeks ved hjelp av en hash-funksjon, og verdien (eller en referanse til den) lagres der. Senere, for å søke, hasher du ganske enkelt nøkkelen på nytt og får tilgang til den tilsvarende posisjonen.

Ytelsen til en hash-tabell avhenger i stor grad av tre faktorer: hash-funksjon valgt (du må fordele tastene godt for å unngå konsentrasjon), den bordstørrelse (utilstrekkelig størrelse forårsaker mange kollisjoner) og metode for å håndtere kollisjoner (kobling med lenkede lister, åpen adressering osv.). Dette ligner på en indeks i databasender det å velge riktig struktur forbedrer søk og tilgang.

Typiske hashprogrammeringsøvelser krever ofte for eksempel finn symmetriske par i en matriseRekonstruere den komplette reiseruten for en reise fra individuelle flyvninger, raskt sjekke om en matrise er et delsett av en annen, eller verifisere om to matriser er disjunkte, alt ved å dra nytte av de omtrentlige O(1)-søkene i hash-tabellen.

I de fleste moderne språk, strukturer som kart, ordbok, hashkart eller hashsett De er internt avhengige av hash-tabeller, selv om et grensesnitt på høyt nivå tilbys programmereren.

Hvordan algoritmer og datastrukturer er relatert

Valget av datastruktur bestemmer direkte hvilke algoritmer som gir mening og hva kompleksiteten deres vil være. En lineær søkealgoritme på en uordnet liste Den itererer gjennom elementene ett etter ett; hvis vi endrer strukturen til et balansert søketre eller en hashtabell, får vi mye bedre tider.

Hvis du for eksempel vil søke gjentatte ganger etter nøkler i en stor samling, kan du lagre dataene i en hash-tabell eller binært søketre Det lar deg designe søkealgoritmer som er mye raskere enn om du bruker en enkel usortert matrise. Det samme gjelder prioriterte køer og heaps for planlegging eller korteste vei-algoritmer.

Motsatt, når du designer en algoritme, innser du ofte at du trenger visse egenskaper: indekstilgang, raske innsettinger i begynnelsen, hierarkiske traverseringer, prefikssøk osv. Disse behovene styrer valget av struktur. matriser, lister, trær, grafer, hashtabeller, forsøk...

Denne passende kombinasjonen av algoritme og datastruktur er det som gjør det mulig å bruke komplekse applikasjoner effektiv og skalerbarUten et godt grunnlag har løsninger en tendens til å bli trege, vanskelige å forstå og vedlikeholde, eller umulige å tilpasse seg etter hvert som informasjonsmengden vokser.

Derfor er det ikke en fordel å mestre algoritmer og datastrukturer. nesten uunnværlig krav for alle som ønsker å bli en kompetent og konkurransedyktig programmerer i dagens arbeidsmarked.

Hvordan lære datastrukturer og algoritmer

Mange føler seg fastlåst når de prøver å lære på egenhånd med plattformer som LeetCode eller CodewarsDet er vanlig å starte med «enkle» øvelser og fortsatt ikke vite hvor man skal gripe an problemet, ender opp med å se på løsningen og ikke være klar over hvordan man skal gjenskape den etterpå.

En praktisk tilnærming kombinerer vanligvis flere ingredienser: a god teoretisk forklaring Hver struktur og algoritme inkluderer visuelle eksempler, rikelig med veiledet øvelse og, om mulig, støtte fra noen med erfaring for å hjelpe deg med å forbedre problemløsningsferdighetene dine.

I den spansktalende verden finnes det fagfolk med lang erfaring som har bidratt til å legge til rette for denne læringen. Et eksempel er arbeidet til Lærere med erfaring fra næringsliv og utdanning som har publisert bøker og kurs om grunnleggende programmering, Java, datastrukturer og programmeringsutfordringer med spill, og gjort disse konseptene tilgjengelige på en morsom og anvendelig måte i virkelige prosjekter.

Det er også vanlig at akademier og opplæringssentre inkluderer spesifikke moduler om datastrukturer og algoritmer i programmene sine for webutviklere eller applikasjonsprogrammerere. I mange tilfeller vektlegges en bestemt tilnærming. veldig praktisk og prosjektbasert, med øvelser med økende vanskelighetsgrad og simulering av typiske tekniske intervjuproblemer.

Hvis du står fast, kan det hjelpe å følge en strukturert rute: starte med arrayer og lister, går gjennom stabler og køer, deretter trær og grunnleggende grafer, og til slutt hash-tabeller og forsøk, alltid vekslende teoretisk forklaring, små kodeeksempler og mye individuell øvelse.

Når du forbereder deg til intervjuer, er det lurt å se gjennom ikke bare strukturene, men også brute force-algoritmer og de tilhørende klassiske algoritmene (traversering, søk, sortering, enkel tilbakesporing, grunnleggende dynamisk programmering) og sørg for at du kan forklare høyt hvorfor du har valgt en bestemt struktur og hva kompleksiteten i løsningen din.

Over tid og litt konsistensDet som først virker som en vegg, ender opp med å bli et sett med kjente verktøy som du bruker nesten instinktivt når du står overfor nye problemer.

En god forståelse av hva algoritmer er, hvordan de viktigste datastrukturene fungerer og hvordan de forholder seg til hverandre, vil gjøre det mulig for deg å skrive programmer. raskere, tydeligere og mer robustDet vil åpne dører for deg i krevende utvelgelsesprosesser og sikre at prosjektene dine, både akademiske og profesjonelle, er basert på et solid fundament med en fremtid.