Datastrukturer och algoritmer (DSA) hänvisa till studiet av metoder för att organisera och lagra data och utformningen av procedurer (algoritmer) för att lösa problem, som verkar på dessa datastrukturer. DSA är en av de viktigaste färdigheterna som varje datavetenskapsstudent måste ha. Man ser ofta att personer med goda kunskaper om dessa tekniker är bättre programmerare än andra och därmed knäcker intervjuerna av nästan varje teknikjätte. Detta Handledning för DSA syftar till att hjälpa dig lära dig datastrukturer och algoritmer (DSA) snabbt och enkelt.

Innehållsförteckning

• DSA fullständigt formulär
• Vad är DSA?
• Hur lär man sig DSA?
• Sträng
• Länkade listor
• Matris/Grid
• Stack
• Kö
• Högen
• Hash
• Träd
• Graf

• Sökalgoritm
• Sorteringsalgoritm
• Dela och erövra algoritm
• giriga algoritmer
• Rekursion
• Backtracking-algoritm
• Dynamisk programmering
• Grafalgoritmer:
• Mönstersökning
• Matematiska algoritmer
• Geometriska algoritmer
• Bitvisa algoritmer
• Randomiserade algoritmer
• Gren och bunden algoritm

DSA fullständigt formulär

Termen DSA står för Datastrukturer och algoritmer , inom ramen för datavetenskap.

Vad är DSA?

Datastrukturer och algoritmer (DSA) hänvisa till studiet av metoder för att organisera och lagra data och utformningen av procedurer (algoritmer) för att lösa problem, som verkar på dessa datastrukturer.

Hur lär man sig DSA?

Det första och främsta är att dela upp den totala proceduren i små bitar som måste göras sekventiellt. Hela processen för att lära sig DSA från grunden kan delas upp i 5 delar:

1. Lär dig minst ett programmeringsspråk (vi överlåter detta till ditt val.)
2. Lär dig datastrukturer
3. Lär dig algoritmer
4. Lär dig mer om komplexiteten i tid och rum
5. Övningsproblem på DSA

Hur lär man sig DSA?

Hoppas du har lärt dig ett valfritt programmeringsspråk, låt oss gå vidare med nästa steg för att lära oss DSA i denna DSA-handledning.

Här kommer det viktigaste och mest efterlängtade steget i färdplanen för att lära dig datastruktur och algoritm – det stadium där du börjar lära dig om DSA. Ämnet DSA består av två delar:

• Data struktur
• Algoritmer

Även om de är två olika saker, är de mycket relaterade till varandra, och det är mycket viktigt att följa rätt spår för att lära sig dem mest effektivt. Om du är förvirrad över vilken du ska lära dig först rekommenderar vi att du går igenom vår detaljerade analys om ämnet: Här har vi följt flödet av att lära sig en datastruktur och sedan de mest relaterade och viktiga algoritmerna som används av den datastrukturen.

Lär dig datastrukturer

Data struktur är viktiga komponenter som hjälper till att organisera och lagra data effektivt i datorns minne. De tillhandahåller ett sätt att hantera och manipulera data effektivt, vilket möjliggör snabbare åtkomst, infogning och radering. Vanliga datastrukturer inkluderar arrayer, länkade listor, stackar, köer, träd och grafer , var och en tjänar specifika syften baserat på kraven för det aktuella problemet. Att förstå datastrukturer är grundläggande för att designa effektiva algoritmer och optimera mjukvarans prestanda.

Array är en linjär datastruktur som lagrar en samling element av samma datatyp. Element tilldelas sammanhängande minne, vilket möjliggör konstant tidsåtkomst. Varje element har ett unikt indexnummer.

• Operationer på Array:
  • Traversering : Itererar genom elementen i en array.
  • Införande : Lägga till ett element i arrayen vid ett specifikt index.
  • Radering : Ta bort ett element från arrayen vid ett specifikt index.
  • Sökande : Hitta ett element i arrayen genom dess värde eller index.
• Typer av arrayer :
  • Endimensionell array : En enkel array med en enda dimension.
  • Flerdimensionell array : En matris med flera dimensioner, till exempel en matris.
• Tillämpningar av Array :
  • Lagra data på ett sekventiellt sätt
  • Implementering av köer, stackar och andra datastrukturer
  • Representerar matriser och tabeller
• Relaterade ämnen om Array:
  • Handledning för matriser
  • De 50 bästa problemen med arraykodning för intervjuer
  • Öva problem på Arrays

2. Sträng

A sträng är en teckensekvens som vanligtvis används för att representera text. Det anses vara en datatyp som möjliggör manipulering och bearbetning av textdata i datorprogram.

• Operationer på String :
  • Sammankoppling : Sammanfoga två strängar.
  • Jämförelse : Jämför två strängar lexikografiskt.
  • Delsträng extraktion : Extrahera en delsträng från en sträng.
  • Sök : Söker efter en delsträng i en sträng.
  • Modifiering : Ändra eller ersätta tecken i en sträng.
• Tillämpningar av String :
  • Textbehandling
  • Mönstermatchning
  • Datavalidering
  • Databashantering
• Relaterade inlägg:
  • Stränghandledning
  • Topp 50 strängkodningsproblem för intervjuer
  • Öva problem på sträng

3. Länkade listor

A länkad lista är en linjär datastruktur som lagrar data i noder, som är sammankopplade med pekare. Till skillnad från arrayer lagras inte länkade listor i angränsande minnesplatser.

• Egenskaper för länkad lista:
  • Dynamisk : Länkade listor kan enkelt ändras i storlek genom att lägga till eller ta bort noder.
  • Icke sammanhängande : Noder lagras på slumpmässiga minnesplatser och kopplas samman med pekare.
  • Sekventiell åtkomst : Noder kan endast nås sekventiellt, från början av listan.
• Operationer på länkad lista:
  • Skapande : Skapa en ny länkad lista eller lägga till en ny nod till en befintlig lista.
  • Traversering : Itererar genom listan och kommer åt varje nod.
  • Införande : Lägga till en ny nod på en specifik position i listan.
  • Radering : Tar bort en nod från listan.
  • Sök : Hitta en nod med ett specifikt värde i listan.
• Typer av länkad lista :
  • Enkelt länkad lista : Varje nod pekar på nästa nod i listan.
  • Dubbelt länkad lista : Varje nod pekar på både nästa och föregående nod i listan.
  • Cirkulär länkad lista : Den sista noden pekar tillbaka till den första noden och bildar en cirkulär slinga.
• Tillämpningar av länkad lista :
  • Länkade listor används i olika applikationer, inklusive:
  • Implementering av köer och stackar
  • Representerar grafer och träd
  • Upprätthålla beställd data
  • Minneshantering
• Relaterade ämnen:
  • Handledning för länkad lista
  • Topp 50 problem på länkad lista för intervjuer
  • Öva problem på länkade listor

4. Matris/Grid

A matris är en tvådimensionell matris av element, ordnade i rader och kolumner. Det representeras som ett rektangulärt rutnät, med varje element i skärningspunkten mellan en rad och kolumn.

• Nyckelbegrepp:
  • Rader : Horisontella linjer av element i en matris.
  • Kolumner : Vertikala linjer av element i en matris.
  • Mått : Antalet rader och kolumner i en matris (t.ex. en 3×4-matris har 3 rader och 4 kolumner).
  • Element Tillgång : Element kan nås med hjälp av rad- och kolumnindex (t.ex. M[2][3] hänvisar till elementet i rad 2, kolumn 3).
• Tillämpningar av Matrix/Grid :
  • Bildbehandling
  • Dataanalys
  • Optimeringsproblem
• Relaterade inlägg:
  • Matris/Grid handledning
  • Topp 50 problem på Matrix/Grid för intervjuer
  • Öva problem på Matrix/Grid

5. Stack

Stack är en linjär datastruktur som följer en viss ordning i vilken operationerna utförs. Beställningen kan vara LIFO (sist in först ut) eller FILO (först in sist ut) . LIFO innebär att elementet som sätts in sist kommer ut först och RAD innebär att elementet som sätts in först kommer ut sist.

• Operation på stack :
  • Skjuta på : Lägger till ett element till toppen av stacken
  • Pop : Tar bort och returnerar elementet överst i stapeln
  • Titt : Returnerar elementet överst i stapeln utan att ta bort det
  • Storlek : Returnerar antalet element i stacken
  • Är tom : Kontrollerar om stacken är tom
• Tillämpningar av Stack :
  • Funktionsanrop
  • Uttrycksvärdering
  • Backtracking
  • Ångra/gör om åtgärder
• Relaterade ämnen på Stack:
  • Stack handledning
  • Topp 50 problem på Stack för intervjuer
  • Öva problem på Stack

6. Kö

A Kö Datastruktur är ett grundläggande begrepp inom datavetenskap som används för att lagra och hantera data i en specifik ordning. Det följer principen om Först in först ut ( FIFO ), där det första elementet som läggs till i kön är det första som tas bort

• Operation på kö :
  • Kö : Lägger till ett element längst bak i kön
  • Följaktligen : Tar bort ett element från framsidan av kön
  • Titt : Hämtar frontelementet utan att ta bort det
  • Är tom : Kontrollerar om kön är tom
  • Är full : Kontrollerar om kön är full
• Typ av kö :
  • Cirkulär kö : Sista elementet ansluter till det första elementet
  • Dubbelkö (Deque) : Operationer kan utföras från båda ändarna
  • Prioriterad kö : Elementen är ordnade utifrån prioritet
• Tillämpningar av kö :
  • Jobbschemaläggning
  • Meddelandekö
  • Simuleringsmodellering
  • Databuffring
• Relaterade ämnen:
  • Handledning för kö
  • De 50 bästa problemen i kö för intervjuer
  • Öva problem på kö

7. Högen

A Högen är en komplett binär träddatastruktur som uppfyller heap-egenskapen: för varje nod är värdet på dess barn mindre än eller lika med dess eget värde. Högar används vanligtvis för att implementera prioriterade köer , där det minsta (eller största) elementet alltid är vid roten av trädet.

• Operations av Heap :
  • Föra in : Lägger till ett nytt element till högen samtidigt som heapegenskaperna bibehålls.
  • Extrahera-Max/Extrahera-Min : Tar bort rotelementet och strukturerar om högen.
  • Öka/minska-nyckel : Uppdaterar värdet på en nod och omstrukturerar högen.
• Typer av hög :
  • Max-Heap : Rotnoden har det maximala värdet bland sina underordnade.
  • Min-Hög : Rotnoden har det lägsta värdet bland sina underordnade.
• Tillämpningar av Heap :
  • Prioriterade köer
  • Sortering
  • Grafalgoritmer (t.ex. Dijkstras algoritm)
• Relaterade inlägg:
  • Heap Tutorial
  • Topp 50 problem på Heap för intervjuer
  • Öva problem på Heap

8. Hash

Hashing är en teknik som genererar en utdata med fast storlek (hashvärde) från en indata av variabel storlek med hjälp av matematiska formler som kallas hashfunktioner . Hashing används för att bestämma ett index eller en plats för att lagra ett objekt i en datastruktur, vilket möjliggör effektiv hämtning och infogning.

• Nyckelbegrepp:
  • Hash-funktion : En matematisk funktion som mappar en indata till ett hashvärde.
  • Hash tabell : En datastruktur som lagrar nyckel-värdepar, där nyckeln är ett hashvärde och värdet är den faktiska datan.
  • Kollision : När två olika nycklar producerar samma hashvärde.
• Typer av hashfunktioner :
  • Indelningsmetod : Delar inmatningen med en konstant och använder resten som hashvärde.
  • Mid Square Metod: Kvadraterar inmatningen och tar de mellersta siffrorna som hashvärde.
  • Vikningsmetod : Delar in indata i lika stora block och lägger ihop dem för att få hashvärdet.
  • Multiplikationsmetod : Multiplicerar inmatningen med en konstant och tar bråkdelen som hashvärde.

• Tekniker för kollisionsupplösning :
  • Separat kedja (öppen hashing) : Lagrar kolliderande element i en länkad lista med motsvarande hashvärde.
  • Öppna adressering (stängd hashing) : Använder olika strategier för att hitta en alternativ plats för kolliderande element i hashtabellen.
• Tillämpningar av hashing :
  • Effektiv lagring och hämtning av data i databaser och filsystem.
  • Verifiera lösenord och digitala signaturer.
  • Distribuera förfrågningar över flera servrar.
  • Genererar säkra hash för dataintegritet och autentisering.
• Relaterade inlägg:
  • Hash handledning
  • Öva problem på hashing

9. Träd

A träd är en icke-linjär hierarkisk datastruktur som består av noder sammankopplade med kanter, med en toppnod som kallas roten och noder som har barnnoder. Det används inom datavetenskap för att organisera data effektivt.

sträng till int konvertering i java

• Traversering av träd : Trädgenomgångsmetoder används för att besöka och bearbeta noder i en träddatastruktur. De tre vanliga traverseringsmetoderna är:
  • I ordning : Besök vänster underträd, aktuell nod, sedan höger underträd.
  • Förboka : Besök nuvarande nod, vänster underträd och sedan höger underträd.
  • Postorder : Besök vänster underträd, höger underträd och sedan aktuell nod.
• Klassificeringar av träd:
  • Klassificeringar av Träd syftar på att gruppera träd utifrån vissa egenskaper eller kriterier. Detta kan innebära att kategorisera träd baserat på deras balansfaktor, grad av noder, ordningsegenskaper etc. Nedan följer några viktiga klassificeringar av träd.

• Tillämpningar av träd:
  • Filsystem
  • Databaser
  • XML-dokument
  • Artificiell intelligens
• Relaterade inlägg:
  • Handledning för träd
  • Topp 50 trädkodningsproblem
  • Träningsproblem på Tree

10. Graf

A Graf är en icke-linjär datastruktur som består av en ändlig uppsättning av hörn (eller noder) och en uppsättning kanter som förbinder ett par noder.

• Genomgång av graf:
  • Breadth-First Search (BFS) : Besöker noder nivå för nivå.
  • Depth-First Search (DFS) : Besöker noder rekursivt och utforskar en gren i taget.
• Tillämpningar av grafer :
  • Sociala nätverk
  • Kartor och navigering
  • Schemaläggning
  • Data mining
• Relaterade inlägg:
  • Grafrepresentation
  • Typer av grafer
  • Graf handledning
  • Öva problem på Graph

Lär dig algoritmer

När du har rensat begreppen för Data struktur , nu är det dags att börja din resa genom Algoritmer . Baserat på typen av natur och användning, grupperas algoritmerna i flera kategorier, som visas nedan:

1. Sökalgoritm

Sökande algoritmer används för att lokalisera specifik data inom en större uppsättning data. Det hjälper till att hitta förekomsten av ett målvärde i datan. Det finns olika typer av sökalgoritmer, var och en med sitt eget tillvägagångssätt och effektivitet.

• De vanligaste sökalgoritmerna:
  • Linjär sökning : Iterativ sökning från ena änden till den andra.
  • Binär sökning : Dela-och-härska sökning på en sorterad array, halvera sökutrymmet vid varje iteration.
  • Ternär sökning : Dela-och-härska sökning på en sorterad array, dela upp sökutrymmet i tre delar vid varje iteration.
• Andra sökalgoritmer:
  • Hoppa Sök
  • Interpolationssökning
  • Exponentiell sökning
• Relaterade ämnen:
  • Öva problem med sökalgoritm

2. Sorteringsalgoritm

Sorteringsalgoritmer används för att ordna elementen i en lista i en specifik ordning, till exempel numerisk eller alfabetisk. Den organiserar objekten på ett systematiskt sätt, vilket gör det lättare att söka efter och komma åt specifika element.

Det finns många olika sorters algoritmer. Några allmänt använda algoritmer är:

Relaterade ämnen:

• Handledning för sorteringsalgoritm
• Toppsortering av intervjufrågor och -problem
• Öva problem med sorteringsalgoritm

3. Dela och erövra algoritm

Söndra och erövra Algoritmer följer en rekursiv strategi för att lösa problem genom att dela upp dem i mindre delproblem, lösa dessa delproblem och kombinera lösningarna för att erhålla den slutliga lösningen.

Steg:

1. Dela upp : Dela upp problemet i mindre, oberoende delproblem.
2. Erövra : Lös varje delproblem rekursivt.
3. Kombinera : Slå samman lösningarna för delproblemen för att få den slutliga lösningen.

Exempel:

• Slå samman sortering: Delar upp arrayen i två halvor, sorterar varje halva rekursivt och slår samman de sorterade halvorna.
• Snabbsortering: Väljer ett pivotelement, delar upp arrayen i två subarrayer baserat på pivoten och sorterar rekursivt varje subarray.
• Binär sökning: Delar sökutrymmet på mitten upprepade gånger tills målelementet hittas eller sökutrymmet är slut.

Relaterade artiklar:

• Dela och erövra handledning
• Öva problem på Divide And Conquer-algoritmen

4. giriga algoritmer

Som namnet antyder bygger denna algoritm upp lösningen en bit i taget och väljer nästa bit som ger den mest uppenbara och omedelbara fördelen, dvs. vilket är det mest optimala valet i det ögonblicket. Så problemen där att välja lokalt optimalt också leder till att de globala lösningarna passar bäst för Greedy.

Några viktiga problem med giriga algoritmer är:

Relaterade artiklar:

• Handledning för girig algoritm
• Öva problem på girig algoritm

5. Rekursion

Rekursion är en programmeringsteknik där en funktion anropar sig själv inom sin egen definition. Det används vanligtvis för att lösa problem som kan delas upp i mindre instanser av samma problem. Till exempel: Towers of Hanoi (TOH) , Faktoriell beräkning och Fibonacci-sekvens etc.

Steg :

• Basfallet : Definiera ett tillstånd som stoppar de rekursiva anropen och tillhandahåller en lösning.
• Rekursivt fall : Definiera stegen för att dela upp problemet i mindre instanser och göra rekursiva samtal.
• Lämna tillbaka : Returnera lösningen från de rekursiva anropen och kombinera dem för att lösa det ursprungliga problemet.

Poängen som gör rekursion till en av de mest använda algoritmerna är att den utgör basen för många andra algoritmer som t.ex. Trädövergångar , Grafövergångar , Dela och erövra algoritmer och Backtracking-algoritmer .

Relaterade ämnen:

• Rekursionshandledning
• Rekursiva funktioner
• Svansrekursion
• Topp 50 problem med rekursionsalgoritm för intervju
• Öva problem på rekursionsalgoritm

6. Backtracking-algoritm

Som tidigare nämnts Backtracking Algoritmen härleds från Rekursionsalgoritmen, med möjligheten att återgå om en rekursiv lösning misslyckas, d.v.s. om en lösning misslyckas, spårar programmet tillbaka till det ögonblick då det misslyckades och bygger på en annan lösning. Så i princip testar den alla möjliga lösningar och hittar den rätta.

Några viktiga och vanligaste problem med backtracking-algoritmer som du måste lösa innan du går vidare är:

Relaterad artikel:

• Handledning för bakåtspårning
• Öva problem på Backtracking-algoritmen

7. Dynamisk programmering

Dynamisk programmering är en metod som används inom matematik och datavetenskap för att lösa komplexa problem genom att bryta ner dem i enklare delproblem. Genom att lösa varje delproblem endast en gång och lagra resultaten undviker det redundanta beräkningar, vilket leder till effektivare lösningar för en lång rad problem.

Nyckelbegrepp:

• Optimal underbyggnad : Den optimala lösningen på ett problem kan konstrueras från de optimala lösningarna till dess delproblem.
• Överlappande delproblem : Delproblem upprepas ofta i det större problemet, vilket leder till redundanta beräkningar.
• Memoisering / Tabulering : Lagra lösningarna på delproblem för att undvika omräkning.

Några viktiga och vanligaste problem med dynamiska programmeringsalgoritmer, som du måste lösa innan du går vidare, är:

Relaterade artiklar:

• Tabulering vs Memoisering
• Hur löser man ett dynamiskt programmeringsproblem?
• Handledning för dynamisk programmering
• Topp 50 kodningsproblem för dynamisk programmering för intervjuer
• Öva problem på dynamisk programmeringsalgoritm

8. Grafalgoritmer :

Grafalgoritmer i datastrukturer och algoritmer (DSA) är en uppsättning tekniker och metoder som används för att lösa problem relaterade till grafer, som är en samling av noder och kanter. Dessa algoritmer är designade för att utföra olika operationer på grafer, som t.ex leta, korsa, hitta den kortaste vägen och bestämmer anslutning . De är viktiga för att lösa ett brett spektrum av verkliga problem, inklusive nätverksdirigering, sociala nätverksanalyser och resursallokering.

Relaterade ämnen:

• Graf handledning
• Topp 50 grafkodningsproblem för intervjuer
• Öva problem på grafalgoritmer

9 . Mönstersökning

Mönstersökning är en grundläggande teknik i DSA som används för att hitta förekomster av ett specifikt mönster i en given text.

Nedan följer några vanliga mönstersökningsalgoritmer:

Relaterade ämnen:

• Handledning för mönstersökning
• Öva Problem på Mönstersökning

10 . Matematiska algoritmer

Matematiska algoritmer är en klass av algoritmer som löser problem relaterade till matematiska begrepp. De används ofta inom olika områden, inklusive datorgrafik, numerisk analys, optimering och kryptografi.

Relaterade ämnen:

• Öva problem på matematisk algoritm

11. Geometriska algoritmer

Geometriska algoritmer är en klass av algoritmer som löser problem relaterade till geometri. Geometriska algoritmer är avgörande för att lösa ett brett spektrum av problem inom datavetenskap, som:

Relaterade ämnen:

• Öva problem på geometriska algoritmer

12. Bitvisa algoritmer

Bitvisa algoritmer är algoritmer som arbetar på enskilda bitar av siffror. Dessa algoritmer manipulerar den binära representationen av tal för att utföra uppgifter som bitmanipulation, bitvisa logiska operationer (AND, OR, XOR), skiftande bitar , och miljö eller rensa specifika bitar inom ett nummer. Bitvisa algoritmer används ofta i programmerings-, kryptografi- och optimeringsuppgifter på låg nivå där effektiv manipulering av enskilda bitar krävs.

Relaterade ämnen:

• Handledning för bitvisa algoritmer
• Öva problem på bitvisa algoritmer

13. Randomiserade algoritmer

Randomiserade algoritmer är algoritmer som använder slumpmässighet för att lösa problem. De använder sig av slumpmässig input för att uppnå sina mål, vilket ofta leder till enklare eller effektivare lösningar.

Typer av randomiserade algoritmer:

• Las Vegas : Ger alltid ett korrekt resultat, men körtiden är slumpmässig.
• Monte Carlo : Kan ge ett felaktigt resultat med liten sannolikhet, men körtiden är vanligtvis snabbare.

Viktiga algoritmer som använder randomiseringsalgoritmer:

14. Gren och bunden algoritm

De Gren och bunden algoritm är en metod som används i kombinatoriska optimeringsproblem för att systematiskt söka efter den bästa lösningen. Det fungerar genom att dela upp problemet i mindre delproblem, eller grenar, och sedan eliminera vissa grenar baserat på gränser för den optimala lösningen. Denna process fortsätter tills den bästa lösningen har hittats eller alla grenar har utforskats.

Standardproblem på gren- och bunden algoritm:

Relaterade ämnen:

• Handledning för gren och bunden algoritm

Lär dig mer om komplexiteter

Inom Data Structures and Algorithms (DSA) är huvudmålet att lösa problem effektivt och effektivt. För att bestämma effektiviteten hos ett program tittar vi på två typer av komplexitet:

1. Tidskomplexitet : Detta talar om för oss hur lång tid det tar att köra vår kod.
2. Rymdkomplexitet : Detta talar om för oss hur mycket minne vår kod använder.

Asymptotisk notation :

För att jämföra effektiviteten hos algoritmer använder vi asymptotisk notation, ett matematiskt verktyg som uppskattar tid baserat på ingångsstorlek utan att köra koden. Den fokuserar på antalet grundläggande operationer i programmet.

Den vanligaste notationen för kodanalys är Stor O-notation , vilket ger en övre gräns för körtid eller minnesanvändning avseende ingångsstorleken.

Relaterade ämnen:

• Förstå tidskomplexitet med enkla exempel
• Tidskomplexitet för olika datastrukturer
• Hur man analyserar loopar för komplexitetsanalys av algoritmer
• Öva frågor om tidskomplexitetsanalys

Öva problemfuskblad:

Sammanställda listor över problem från nedanstående artiklar:

• DSA Roadmap av Sandeep Jain
• SDE-BLAD – En komplett guide för SDE-förberedelser
• techcodeview.com Master Sheet – Lista över alla fuskblad