Datastrukturer och algoritmer: en komplett guide för programmerare

Informatec Digital » Resurser » Datastrukturer och algoritmer: en komplett guide för programmerare

Algoritmer och datastrukturer De är två bitar som passar ihop som ett pussel: den ena beskriver proceduren för att lösa problemet, och den andra avgör var och hur vi lagrar informationen. Även om det kan låta akademiskt, är det att behärska detta par som skiljer en kod som bara fungerar från en som flyger och skalar utan att gå sönder.

Om du vill fortsätta med professionell programmering, förbereda dig för tekniska intervjuer eller helt enkelt sluta kämpa med övningar som LeetCode och Codewars, behöver du en solid grund i datastrukturer och algoritmerGenom den här artikeln kommer du att se vad de är, varför de är så viktiga, vilka huvudtyper som finns, vilka grundläggande operationer de utför och vilka frågor som vanligtvis dyker upp i prov och urvalsprocesser.

Vad är datastrukturer och algoritmer?

En datastruktur Det är i grunden ett specifikt sätt att organisera och lagra information i minnet för att kunna arbeta effektivt med den. Denna organisation är inte slumpmässig: den avgör direkt vilka operationer som är snabba och vilka som blir kostsamma (infoga, söka, ta bort, bläddra, etc.).

När du väljer rätt datastruktur kan ditt program hantera stora datamängder utan att behöva svettas; när du väljer dåligt kan även en liten applikation bli långsam, förbruka för mycket minne eller bli omöjlig att underhålla över tid.

En algoritm Det är en ändlig och ordnad sekvens av väldefinierade steg som omvandlar indata till utdata för att lösa ett specifikt problem. Det är som ett matlagningsrecept: det talar om vad du ska göra, i vilken ordning och under vilka förhållanden, men det bryr sig inte om hur du förvarar ingredienserna i kylskåpet, vilket skulle vara datastrukturdelen.

Inom datavetenskap utformas varje algoritm med den typ av data den ska arbeta med i åtanke. Valet av datastruktur är inte en liten detalj: Struktur och algoritm går hand i handOch små förändringar i en av de två delarna kan antingen öka eller sänka prestandan.

Ur ett teoretiskt perspektiv populariserade författare som Niklaus Wirth idén redan på 70-talet att algoritmer + datastrukturer = programÅrtionden senare är det lika sant: det spelar ingen roll om du programmerar i Java, Python, C++ eller om du kommer från ett bootcamp, det som kommer att krävas av dig i intervjuer och seriösa projekt är att du vet hur du väljer och kombinerar båda elementen väl.

Varför är de så viktiga inom programmering?

I alla verkliga tillämpningar, hur enkla de än må verka, arbetar du alltid med data: löner, produkter, användare, transaktioner, rutter, dokumentLoggposter etc. Frågan är inte om du ska hantera data, utan hur du ska organisera den så att din kod är snabb, tydlig och enkel att underhålla.

Datastrukturer används för att lagra information på ett ordnat och sammanhängande sätt beroende på problemet. Det är inte detsamma Att alltid behöva komma åt det första elementet, söka efter nyckel, bläddra i ordning, infoga i mitten eller ofta ta bort; varje användningsmönster passar bättre med en annan struktur.

För sin del tillåter algoritmer bearbeta den informationen effektivtsortera dem, filtrera dem, sök efter element, hitta optimala rutter, upptäck mönster med data mining, optimera resurser, etc. Många problem som verkar svåra blir triviala när man hittar rätt kombination av algoritm och datastruktur.

I tekniska intervjuer för mjukvaruutveckling är det sällsynt att man får en fråga som inte direkt tar upp dessa ämnen. Ibland nämner frågan explicit strukturen, till exempel "givet ett binärt träd...", och andra gånger är den implicit: "vi vill räkna hur många böcker varje författare har", vilket föreslår att man använder en hashtabell eller nyckel-värde-mapp.

Dessutom kretsar formell och yrkesmässig utbildning ofta kring detta område. Många universitet och högre utbildningsprogram inkluderar ett ämne om... Datastrukturer och algoritmer, med ett officiellt program, förkunskapskrav, teori- och praktikpass, tentor och uppgifter, eftersom det anses vara ett kärnämne för alla mjukvaruingenjörer.

Förutsättningar och nödvändiga grunder

För att få ut det mesta av att studera datastrukturer och algoritmer är det bra att ha viss förtrogenhet med ett allmänt programmeringsspråk, till exempel Java, Python eller C++Du behöver inte vara någon guru, men du behöver vara bekväm med grundläggande koncept som variabler, datatyper, villkor, loopar, funktioner och parameteröverföring.

Det hjälper också mycket att förstå idén om algoritmisk komplexitet och Big O-notation: hur exekveringstid eller minnesanvändning ökar när datastorleken (n) ökar. Att veta hur man skiljer mellan O(1), O(log n), O(n), O(n log n) och O(n²) låter dig jämföra alternativ med sunt omdöme och motivera dina beslut.

En annan viktig aspekt är att ha haft lite bråk med problemlösningStrukturerade programmeringsövningar, små logikutmaningar, enkla kata, etc. Ju mer du tränar din "näsa" på att bryta ner ett problem i steg, desto lättare blir det att se vilken datastruktur som passar i varje enskilt fall.

Vissa läroplaner anger uttryckligen förkunskapskrav eller samkrav För kursen Datastrukturer och algoritmer behöver du ha godkänt Programmeringsgrunder, Programmering I eller Diskret matematik. Detta är logiskt: utan en solid grund i grundläggande programmering och lite logik är det lätt att bli frustrerad över detta ämne.

Äntligen lite bekantskap med verkliga praktiska miljöer (som små webbprojekt, skript eller konsolapplikationer) hjälper dig att bättre visualisera vad du ska använda varje struktur till, istället för att se det som något rent akademiskt.

De vanligaste datastrukturerna

Inom datavetenskap finns det många datastrukturerDet finns dock en grupp "grundläggande" funktioner som upprepas gång på gång: arrayer (vektorer), stackar, köer, länkade listor, träd, grafer, försök och hashtabeller. Att förstå hur de fungerar, vilka operationer de erbjuder och deras typiska kostnader är nyckeln till att smidigt gå igenom programmeringen.

Nu ska vi granska var och en, med dess huvudidé, typiska operationer och exempel på problem som vanligtvis dyker upp i lektioner, övningar och jobbintervjuer för utvecklare.

Matriser

Matrisen Det är den enklaste linjära datastrukturen och en av de mest använda. Den består av ett sammanhängande minnesblock som lagrar en samling element av samma typ, åtkomliga via ett heltalsindex, vanligtvis med början från noll.

Föreställ dig en array av storlek 4 som innehåller värdena 1, 2, 3 och 4. Varje position har en index (0, 1, 2, 3) och du kan direkt komma åt vilket element som helst med dess index i konstant tid O(1). Detta gör arrayer mycket effektiva för slumpmässig avläsning.

Det finns två huvudkategorier: endimensionella matriser (en enda rad med element) och flerdimensionella arrayer (till exempel matriser, som är arrayer av arrayer). Många programmeringsspråk erbjuder båda varianterna antingen direkt eller med små skillnader i syntax och prestanda.

De grundläggande operationerna på en array är vanligtvis:

• Infoga: att placera ett element i en specifik position, vilket i statiska arrayer kan innebära att andra element flyttas.
• Få: åtkomst till elementet vid ett givet index, vanligtvis O(1).
• Radera: radera eller markera som tomt elementet på en specifik position, vanligtvis genom att flytta element åt vänster.
• Storlek: kontrollera hur många element som lagras eller arrayens maximala kapacitet.

I intervjuer och prov är övningar som dessa mycket vanliga. hitta det andra minimumet i en arrayAtt hitta det första icke-repeterande heltalet, slå samman två redan sorterade matriser eller ändra ordning på positiva och negativa tal samtidigt som vissa egenskaper bibehålls. Allt detta är beroende av indexåtkomst och linjära eller dubbla genomgångar.

Stackar

Batteriet Det är en linjär datastruktur som följer LIFO-principen: Sist in, först ut. Tänk dig en bunt böcker placerade ovanpå varandra: du kan bara ta eller lägga böcker uppifrån.

Detta beteende innebär att Vi kommer bara åt elementet som är högst upp i stacken.Vi kan inte ta bort elementet i mitten utan att först ta bort elementen ovanför det. Detta gör det till en idealisk struktur för modellering av åtgärdshistorik (ångra), kapslade funktionsanrop, navigering (bakåt/framåt) etc.

Typiska stackoperationer är:

• Tryck: infoga ett nytt objekt högst upp.
• Popextrahera och returnera elementet högst upp, vilket minskar stackens storlek.
• Topp eller kika: konsultera det översta elementet utan att ta bort det.
• är tom: kontrollera om batteriet är tomt.

I intervjusammanhang ses problem som följande: utvärdera uttryck i postfixnotation (RPN), sortera element med endast stackar, eller kontrollera om en sträng av parenteser (och andra symboler) är korrekt balanserad med hjälp av push och pop.

I praktiken används många interna implementeringar av språk (till exempel systemanropsstack) fungerar enligt samma principer, även om vi inte ser dem direkt.

Köer

Svansen Det är en annan linjär datastruktur, men istället för att följa LIFO-principen använder den FIFO-modellen: Först in, först ut. Den tydligaste analogin är en kö av människor som väntar vid en biljettkiosk på en biograf.

I en standardkö är elementen De lägger till i slutet och drar tillbaka i börjanFörst till kvarn, vilket gör den idealisk för att hantera pågående uppgifter, operativsystemprocesser, serverförfrågningar, utskriftsköer etc.

Grundläggande köoperationer inkluderar:

• Kö: infoga ett nytt objekt i slutet av kön.
• Avkö: ta bort och returnera elementet som finns i början.
• Fram eller upptill: titta på det första objektet utan att ta bort det.
• är tom: kontrollera om kön är tom.

I programmeringsutmaningar är det vanligt att de frågar dig till exempel, implementera en stack med två köer, reversera de första k elementen i en kö utan att ändra resten, eller generera binära tal från 1 till n med hjälp av FIFO-beteendet för kön.

Förutom den grundläggande svansen finns det variationer som rund svans, prioritetskön eller dubbla köer (deque), som erbjuder ytterligare åtgärder och förbättrar prestandan i vissa scenarier.

Länkade listor

Den länkade listan En länkad lista är också en linjär struktur, men internt skiljer den sig mycket från arrayer. Istället för att använda ett sammanhängande minnesblock består den av glesa noder som är sammankopplade med varandra via referenser eller pekare.

Varje nod innehåller vanligtvis två delar: data som ska lagras och en pekare (eller flera) som pekar på nästa nod i sekvensen (och, i fallet med dubbellänkade listor, även på den föregående). Listan hanteras genom en referens till dess huvud, som pekar på den första noden, och i mer komplexa listor bibehålls även en referens till svansen.

Det finns två huvudvarianter:

• enskilt länkad listavarje nod pekar bara till nästa; vägen går vanligtvis i en enda riktning.
• dubbelt länkad listaVarje nod pekar på nästa och föregående nod, vilket underlättar dubbelriktade genomfarter och effektivare borttagningsoperationer.

Typiska operationer på länkade listor inkluderar:

• InfogaVidHuvudet: infoga en ny nod i början av listan.
• InfogaVidÄnd: lägg till en nod i slutet och uppdatera kön om den finns.
• Raderata bort en specifik nod, justera pekarna för angränsande noder.
• Ta bort vid huvudet: ta bort den första noden och flytta huvudet till nästa.
• Sök: bläddra igenom listan och leta efter ett specifikt värde.
• är tom: kontrollera om head-värdet är null och listan därför inte har några element.

Problem som dessa förekommer i många klasser och intervjuer omvänd en länkad lista, upptäcka om det finns en cykel (vanligtvis med hjälp av algoritmen "sköldpaddan och haren"), erhålla nod N genom att räkna från slutet, eller ta bort dubbla noder, och hantera alltid pekare försiktigt.

Länkade listor används ofta för att implementera hashtabeller med kedjanärliggande listor i grafer och dynamiska datastrukturer där element ofta infogas och tas bort.

Träd

Ett träd Det är en hierarkisk datastruktur som består av noder sammankopplade med kanter. Till skillnad från vanliga grafer har ett träd inga cykler: det finns alltid en rot, barn, föräldrar, syskon, löv, nivåer och underträd, med en organisation av typen "familj" eller "organisationsschema".

Träd är mycket användbara när vi vill representera hierarkiska relationer eller dela upp ett problem i mindre delproblem: filsystem, menyer, DOM-strukturer i webbläsare, beslutsträd inom artificiell intelligens, etc.

Det finns många olika trädslag, inklusive:

• N-ärt trädvarje nod kan ha ett variabelt (och möjligen stort) antal barn.
• Balanserat träd: håller sina grenar på ett liknande djup för att undvika prestandaförsämring.
• Binärt trädvarje nod har maximalt två barn (vänster och höger).
• Binärt sökträd (BST): binärt träd med egenskapen att allt till vänster om en nod är mindre och allt till höger är större (enligt något ordningskriterium).
• AVL-träd, rödsvart, 2-3 och andra varianterDessa är balanserade sökträd som garanterar goda komplexitetsgränser vid infogning, borttagning och sökoperationer.

I praktiken är de vanligaste i övningarna binärt träd och binärt sökträdTypiska problem inkluderar att beräkna trädets höjd, hitta det k-te maximala värdet i en BST, lista noderna på ett visst avstånd från roten eller bestämma förfäderna till en viss nod.

Dessutom är traversalalgoritmer (förbeställning, inordning, postordning, nivå för nivå) grundläggande för många efterföljande processer: sorterad utskrift, uttrycksutvärdering, trädserialisering och avserialisering, etc.

Grafer

En graf Det generaliserar konceptet med ett träd genom att tillåta cykler och flera godtyckliga kopplingar mellan noder. Det består av en uppsättning noder och en uppsättning kanter som förbinder par av noder, ibland med en tillhörande vikt eller kostnad.

Det finns flera typer av grafer: ostyrd (kanterna har ingen riktningskänsla, förhållandet är dubbelriktat) och regisserad (Kanter har en startpunkt och en destination). De kan också klassificeras som viktade eller oviktade, sammanhängande eller osammanhängande, med eller utan cykler, etc.

I kod representeras grafer vanligtvis på två grundläggande sätt:

• Adjacentmatrisen matris där cellen anger om det finns en kant mellan hörn i och j (och eventuellt vikten på förbindelsen).
• Angränsande listaFör varje nodpunkt lagras en lista över dess grannar, vilket sparar minne i glesa grafer.

De mest klassiska traverseringsalgoritmerna är Bredd-först-sökning (BFS) och djupgående sökning (DFS)Båda används som grundläggande byggstenar för en mängd problem: att kontrollera om en graf är sammanhängande, detektera cykler, hitta sammanhängande komponenter, etc.

I tekniska tester är det vanligt att bli ombedd att implementera BFS och DFS, kontrollera om en graf bildar ett träd, räkna antalet kanter eller söka kortaste vägarna mellan två noder (till exempel på en karta över städer) med hjälp av varianter som Dijkstra eller BFS i oviktade grafer.

Försök eller prefixträd

Försöket (eller prefixträd) är en trädformad datastruktur optimerad för att hantera teckensträngar, särskilt användbar när man arbetar med ordböcker, autokompletteringssystem eller prefixsökningar.

I ett trie representerar varje nod vanligtvis ett tecken, och sökvägarna från roten till vissa noder markerar kompletta ordDe sista ordnoderna är vanligtvis markerade på något sätt (till exempel med en boolesk indikator) för att skilja dem från enkla prefix.

Om vi ​​lagrar orden ”top”, ”thus” och ”deras” i ett sökord, kommer vi att dela en del av den initiala sökvägen för alla de som börjar med samma bokstäver, vilket möjliggör sökningar och förslag med prefix i mycket effektiv tid, proportionell mot längden på ordet vi söker efter och inte mot det totala antalet lagrade ord.

Vanliga operationer och problem med försök inkluderar: räkna hur många ord som lagras, skriva ut alla ord i lexikografisk ordning, sortera element i en array genom infogning i en trie, generera giltiga ord från en uppsättning bokstäver eller bygga strukturer som liknar en T9-ordbok.

I intervjusammanhang är det inte den mest grundläggande strukturen de kommer att be om, men den förekommer regelbundet på företag som arbetar med sökningar, ordbehandling eller förslagssystem.

Hashtabeller och hashing

Hashning Det är en teknik för att tilldela en numerisk nyckel (hash) till varje dataenhet på ett deterministiskt sätt, så att vi kan lagra och hämta element i nästan konstant tid, med hjälp av den nyckeln som ett index i en intern struktur, vanligtvis en array.

La hashtabell Det är den datastruktur som utnyttjar denna mekanism. Varje element lagras som ett nyckel-värde-par: nyckeln omvandlas till ett tabellindex med hjälp av en hashfunktion, och värdet (eller en referens till det) lagras där. För att senare söka, hasha helt enkelt nyckeln igen och få åtkomst till motsvarande position.

Prestandan för en hashtabell beror avgörande på tre faktorer: hashfunktion valt (du måste fördela tangenterna väl för att undvika koncentration), den bordstorlek (otillräcklig storlek orsakar många kollisioner) och metod för att hantera kollisioner (länkning med länkade listor, öppen adressering, etc.). Detta liknar en index i databasendär beslut om lämplig struktur förbättrar sökningar och åtkomst.

Typiska hashprogrammeringsövningar kräver ofta till exempel hitta symmetriska par i en arrayRekonstruera den kompletta resplanen för en resa från enskilda flygningar, snabbt kontrollera om en array är en delmängd av en annan, eller verifiera om två arrayer är disjunkta, allt genom att utnyttja de approximativa O(1)-sökningarna i hashtabellen.

I de flesta moderna språk, strukturer som karta, ordbok, hashkarta eller hashuppsättning De förlitar sig internt på hashtabeller, även om ett högnivågränssnitt erbjuds programmeraren.

Hur algoritmer och datastrukturer är relaterade

Valet av datastruktur avgör direkt vilka algoritmer som är meningsfulla och hur komplexa de blir. En linjär sökalgoritm på en oordnad lista Den itererar genom elementen ett efter ett; om vi ändrar strukturen till ett balanserat sökträd eller en hashtabell får vi mycket bättre tider.

Om du till exempel vill söka efter nycklar upprepade gånger i en stor samling, lagrar du data i en hashtabell eller binärt sökträd Det låter dig designa sökalgoritmer som är mycket snabbare än om du använder en enkel osorterad array. Detsamma gäller prioritetsköer och heaps för schemaläggning eller algoritmer för kortaste vägen.

Omvänt, när man utformar en algoritm, inser man ofta att man behöver vissa egenskaper: indexåtkomst, snabba infogningar i början, hierarkiska genomgångar, prefixsökningar etc. Dessa behov styr ditt val av struktur. arrayer, listor, träd, grafer, hashtabeller, försök.

Denna lämpliga kombination av algoritm och datastruktur är det som gör det möjligt för komplexa applikationer att effektiv och skalbarUtan en bra grund tenderar lösningar att bli långsamma, svåra att förstå och underhålla, eller omöjliga att anpassa i takt med att informationsvolymen växer.

Därför är det inte en utmaning att behärska algoritmer och datastrukturer. nästan oumbärligt krav för alla som strävar efter att bli en kompetent och konkurrenskraftig programmerare på dagens arbetsmarknad.

Hur man lär sig datastrukturer och algoritmer

Många känner sig fastlåsta när de försöker lära sig på egen hand med plattformar som LeetCode eller CodewarsDet är vanligt att man börjar med "enkla" övningar och ändå inte vet var man ska ta sig an problemet, för att sluta med att titta på lösningen och inte vara tydlig med hur man ska reproducera den efteråt.

Ett praktiskt tillvägagångssätt kombinerar vanligtvis flera ingredienser: a bra teoretisk förklaring Varje struktur och algoritm innehåller visuella exempel, gott om guidad övning och, om möjligt, stöd från någon med erfarenhet som hjälper dig att förfina dina problemlösningsfärdigheter.

I den spansktalande världen finns det yrkesverksamma med lång erfarenhet som har bidragit till att underlätta detta lärande. Ett exempel är arbetet med Lärare med erfarenhet inom näringsliv och utbildning som har publicerat böcker och kurser om programmeringsgrunder, Java, datastrukturer och programmeringsutmaningar med spel, vilket gör dessa koncept tillgängliga på ett roligt och tillämpligt sätt i verkliga projekt.

Det är också vanligt att akademier och utbildningscenter inkluderar specifika moduler om datastrukturer och algoritmer i sina program för webbutvecklare eller applikationsprogrammerare. I många fall betonas en särskild metod. mycket praktisk och projektbaserad, med övningar med ökande svårighetsgrad och simulering av typiska tekniska intervjuproblem.

Om du har kört fast kan det hjälpa att följa en strukturerad rutt: börja med arrayer och listor, går igenom stackar och köer, sedan träd och grundläggande grafer, och slutligen hashtabeller och försök, alltid alternerande teoretisk förklaring, små kodexempel och massor av individuell övning.

När man förbereder sig för intervjuer är det lämpligt att inte bara granska strukturerna utan även brute force-algoritmer och de tillhörande klassiska algoritmerna (traverseringar, sökningar, sortering, enkel bakåtspårning, grundläggande dynamisk programmering) och se till att du högt kan förklara varför du har valt en viss struktur och vad komplexiteten i din lösning.

Med tiden och viss konsekvensDet som först verkar vara en vägg blir slutligen en uppsättning välbekanta verktyg som man använder nästan instinktivt när man ställs inför nya problem.

En god förståelse för vad algoritmer är, hur de viktigaste datastrukturerna fungerar och hur de relaterar till varandra gör att du kan skriva program snabbare, tydligare och mer robustDet kommer att öppna dörrar för dig i krävande urvalsprocesser och säkerställa att dina projekt, både akademiska och professionella, bygger på en solid grund med en framtid.