Meny

Introduktion till datastrukturer i C ++

introduction data structures c

Prova Vårt Instrument För Att Eliminera Problem

En introduktionshandledning om datastrukturer i C ++.

”Datastruktur kan definieras som en organiserad datainsamling som hjälper ett program att komma åt data effektivt och snabbt så att hela programmet kan fungera på ett effektivt sätt. “

Vi vet att i programmeringsvärlden är data centrum och allt kretsar kring data. Vi måste göra alla datahantering inklusive lagring, sökning, sortering, organisering och åtkomst av data effektivt och först då kan vårt program lyckas.

=> Se här för att utforska listan över C ++ -studier.

Introduktion till datastrukturer i C ++ (1)

Vad du kommer att lära dig:

Översikt

Vi måste hitta det mest effektiva sättet att lagra data som kan hjälpa oss att bygga dynamiska lösningar. Datastrukturen hjälper oss att bygga sådana lösningar.

När vi organiserar eller ordnar data i strukturer måste vi se till att arrangemanget representerar nästan ett verkligt objekt. För det andra bör detta arrangemang vara så enkelt att vem som helst kan komma åt det enkelt och bearbeta det när det behövs.

I denna serie kommer vi att lära oss i detalj om såväl grundläggande som avancerad datastruktur. Vi kommer också att lära oss i detalj om olika sök- och sorteringstekniker som kan utföras på datastrukturer.

Efter att ha lärt sig denna handledningsserie bör läsaren bli väl bekant med varje datastruktur och dess programmering.

Låt oss gå igenom några av de termer som vi använder när vi hanterar datastrukturer:

Till exempel,ta en viss student. En student kan ha följande detaljer som visas i bild.

Exempel - Datastruktur

  • Data: Det är det grundläggande värdet. I figuren ovan kan studentrulle nr vara data.
  • Gruppobjekt: Detta är dataobjektet som har mer än ett underobjekt. I figuren ovan har Studentnamn Förnamn och Efternamn.
  • Spela in: Det är en samling dataobjekt. I exemplet ovan bildar dataobjekt som elevrullnummer, namn, klass, ålder, betyg etc. en post tillsammans.
  • Entitet: Det är en klass av poster. I ovanstående diagram är studenten en enhet.
  • Attribut eller fält: Egenskaper för en enhet kallas attribut och varje fält representerar ett attribut.
  • Fil: En fil är en samling poster. I ovanstående exempel kan en studentenhet ha tusentals poster. Således kommer en fil att innehålla alla dessa poster.

Läsaren bör vara medveten om alla dessa termer när vi använder dem då och då när vi använder olika datastrukturer.

Datastrukturer är programmets huvudbyggsten och som programmerare bör vi vara försiktiga med vilken datastruktur som ska användas. Den exakta datastrukturen som ska användas är det tuffaste beslutet att göra när det gäller programmering.

Låt oss diskutera behovet av datastruktur i programmering.

Behov av datastruktur vid programmering

När mängden data fortsätter att växa blir applikationerna mer och mer komplexa, vilket gör det svårt för programmeraren att hantera dessa data såväl som programvaran.

Normalt kan applikationen när som helst möta följande hinder:

# 1) Söka efter stora mängder data: Med en stor mängd data som bearbetas och lagras kan vårt program när som helst krävas för att söka efter en viss data. Om uppgifterna är för stora och inte ordnas ordentligt tar det mycket tid att få den information som krävs.

När vi använder datastrukturer för att lagra och organisera data blir hämtningen av data snabbare och enklare.

# 2) Bearbetningshastighet: Oorganiserad data kan leda till långsam bearbetningshastighet eftersom mycket tid kommer att slösas bort i att hämta och komma åt data.

Om vi ​​ordnar data ordentligt i en datastruktur när vi lagrar kommer vi inte att slösa tid på aktiviteter som att hämta och organisera den varje gång. Istället kan vi koncentrera oss på bearbetningen av data för att producera önskad utdata.

# 3) Flera samtidiga begäranden: Många applikationer idag behöver göra en samtidig begäran om data. Dessa förfrågningar bör behandlas effektivt för att applikationer ska fungera smidigt.

Om våra data lagras bara slumpmässigt kommer vi inte att kunna behandla alla samtidiga förfrågningar samtidigt. Så det är ett klokt beslut att ordna data i en korrekt datastruktur för att minimera den samtidiga begäranens omloppstid.

Datastrukturklassificering

Datastrukturer som används i C ++ kan klassificeras enligt följande.

Klassificering av datastrukturer

En datastruktur är ett sätt att organisera data. Så vi kan klassificera datastrukturer som visas i primitiva eller standarddatastrukturer och icke-primitiva eller användardefinierade datastrukturer.

Vi har sett alla datatyper som stöds i C ++. Eftersom detta också är ett sätt att organisera data säger vi att det är en standarddatastruktur.

De andra datastrukturerna är icke-primitiva och användaren måste definiera dem innan de används i ett program. Dessa användardefinierade datastrukturer klassificeras vidare i linjära och icke-linjära datastrukturer.

Linjär datastruktur

Linjära datastrukturer har alla sina element ordnade linjärt eller i följd. Varje element i en linjär datastruktur har en föregångare (föregående element) och en efterföljare (nästa element)

Linjära datastrukturer är vidare uppdelade i statiska och dynamiska datastrukturer. Statiska datastrukturer har vanligtvis en fast storlek och när deras storlek deklareras vid tidpunkten för sammanställning kan den inte ändras. Dynamiska datastrukturer kan ändra storlek dynamiskt och anpassa sig själva.

Det mest populära exemplet på linjär statisk datastruktur är en matris.

Array

En array är en sekventiell samling av element av samma typ. Varje element i matrisen kan nås med hjälp av dess position i matrisen som kallas ett index eller en del av matrisen. Arrayens namn pekar på det första elementet i arrayen.

array

Ovan visas är en matris 'a' av n-element. Elementen är numrerade från 0 till n-1. Storleken på matrisen (n i det här fallet) kallas också matrisens dimension. Som visas i figuren ovan pekar namnet på arrayen på det första elementet i arrayen.

Matrisen är den enklaste datastrukturen och är effektiv eftersom element kan nås med hjälp av prenumerationer direkt. Om vi ​​vill komma åt det tredje elementet i matrisen måste vi bara säga a (2).

Men att lägga till eller ta bort arrayelement är svårt. Därför använder vi endast matriser i enkla applikationer eller i applikationer där tillägg / radering av element inte krävs.

Populära linjära dynamiska datastrukturer är länkade lista, stack och kö.

Länkad lista

En länkad lista är en samling noder. Varje nod innehåller dataelementet och en pekare till nästa nod. Noder kan läggas till och raderas dynamiskt. En länkad lista kan vara en enstaka länkad lista där varje nod endast har en pekare till nästa element. För det sista elementet är nästa pekare satt till null.

I den dubbelt länkade listan har varje nod två pekare en till föregående nod och den andra till nästa nod. För den första noden är den föregående pekaren noll och för den sista noden är nästa pekare noll.

Länkad lista

Som visas i figuren ovan kallas början på listan huvudet medan slutet på den länkade listan kallas svansen. Som visas ovan har varje nod en pekare till nästa element. Vi kan enkelt lägga till eller ta bort element genom att ändra pekaren till nästa nod.

Stack

Stack är en linjär datastruktur där elementen endast kan läggas till eller tas bort från ena änden, så kallad ”Top” på stacken. På detta sätt visar stacken LIFO (Last In, First Out) typ av minnesåtkomst.

Stack

Som visas ovan läggs alltid element i stacken till i ena änden och tas bort från samma ände. Detta kallas ”toppen” på stacken. När ett element läggs till skjuts det ner i stacken och toppen av stacken ökas med en position.

På liknande sätt, när ett element tas bort, minskas stapelns topp. När en stack är tom är toppen av stacken inställd på -1. Det finns två huvudåtgärder 'Push' och 'Pop' som utförs på stacken.

Kö

Kön är ännu en linjär datastruktur där elementen läggs till i ena änden som kallas 'bakre' och raderas från en annan ände som kallas 'front'. Kön visar FIFO (First In, First Out) vilken typ av minnesåtkomstmetodik.

Kö

Ovanstående diagram visar en kö med bakre och främre ändar. När kön är tom sammanfaller de bakre och främre pekarna med varandra.

Icke-linjär datastruktur

I icke-linjära datastrukturer ordnas inte data sekventiellt, utan är ordnade på ett icke-linjärt sätt. Element är anslutna till varandra i ett icke-linjärt arrangemang.

Icke-linjära datastrukturer är träd och grafer.

hur man tar bort ett element från en array i java

Träd

Träd är icke-linjära datastrukturer med flera nivåer som har en hierarkisk relation mellan elementen. Element av trädet kallas noder.

Noden längst upp kallas trädets rot. Roten kan ha en eller flera barnnoder. De efterföljande noder kan också ha en eller flera underordnade noder. De noder som inte har barnnoder kallas bladnoder.

Träd

I ovanstående diagram har vi visat ett träd med 6 noder. Av dessa tre noder finns bladnoder, en översta nod är roten och de andra är barnnoder. Beroende på antalet noder, barnnoder etc. eller förhållandet mellan noder har vi olika typer av träd.

Grafer

Grafen är en uppsättning noder som kallas hörn anslutna till varandra med hjälp av de anropade länkarna Kanter . Grafer kan ha en cykel inuti det, dvs. samma toppunkt kan vara både en startpunkt och slutpunkten för en viss väg. Träd kan aldrig ha en cykel.

Grafer

Ovanstående diagram är en oriktad graf. Vi kan också ha riktade grafer där vi representerar kanterna med hjälp av riktade pilar.

Operationer på datastruktur

Alla datastrukturer utför olika operationer på dess element.

Dessa är gemensamma för alla datastrukturer och listas enligt följande:

  • Sökande: Denna operation utförs för att söka efter ett visst element eller en nyckel. De vanligaste sökalgoritmerna är sekventiell / linjär sökning och binär sökning.
  • Sortering: Sorteringsoperationen innebär att elementen ordnas i en datastruktur i en viss ordning antingen stigande eller fallande. Det finns olika sorteringsalgoritmer som är tillgängliga för datastrukturer. Mest populära bland dem är Quicksort, Selection sort, Merge sort, etc.
  • Införande: Införande handlar om att lägga till ett element i datastrukturen. Detta är den viktigaste operationen och som ett resultat av tillägget av ett element ändras arrangemanget och vi måste se till att datastrukturen förblir intakt.
  • Radering: Radering tar bort ett element från datastrukturen. Samma villkor som ska övervägas för infogning ska också vara uppfyllda vid borttagning.
  • Korsning: Vi säger att vi går igenom en datastruktur när vi besöker varje element i strukturen. Korsning krävs för att utföra vissa specifika operationer på datastrukturen.

I våra efterföljande ämnen lär vi oss först de olika sök- och sorteringsteknikerna som ska utföras på datastrukturer.

Fördelar med datastruktur

  • Abstraktion: Datastrukturer implementeras ofta som abstrakta datatyper. Användarna får endast åtkomst till dess yttre gränssnitt utan att oroa sig för den underliggande implementeringen. Således ger datastrukturen ett lager av abstraktion.
  • Effektivitet: Korrekt organisering av data resulterar i effektiv åtkomst av data och därigenom effektiviserar program. För det andra kan vi välja rätt datastruktur beroende på våra krav.
  • Återanvändbarhet: Vi kan återanvända datastrukturerna som vi har designat. De kan också kompileras i ett bibliotek och distribueras till klienten.

Slutsats

Med detta avslutar vi denna handledning om introduktion till datastrukturer. Vi har introducerat var och en av datastrukturerna i korthet i denna handledning.

I våra efterföljande handledning kommer vi att utforska mer om datastrukturer tillsammans med de olika sök- och sorteringsteknikerna.

=> Klicka här för den absoluta C ++ träningsserien.

Rekommenderad läsning

^