introduction data structures c
En introduktionsvejledning om datastrukturer i C ++.
”Datastruktur kan defineres som en organiseret dataindsamling, der hjælper et program med at få adgang til data effektivt og hurtigt, så hele programmet kan fungere på en effektiv måde. “
Vi ved, at data i programmeringsverdenen er centrum, og alt drejer sig om data. Vi er nødt til at udføre alle datahandlinger, herunder lagring, søgning, sortering, organisering og adgang til data effektivt, og først derefter kan vores program lykkes.
=> Se her for at udforske den komplette C ++ tutorials-liste.
Hvad du lærer:
- Oversigt
- Behov for datastruktur i programmering
- Datastrukturklassificering
- Operationer på datastruktur
- Fordele ved datastruktur
- Konklusion
- Anbefalet læsning
Oversigt
Vi er nødt til at finde den mest effektive måde at lagre data på, som kan hjælpe os med at opbygge dynamiske løsninger. Datastruktur hjælper os med at opbygge sådanne løsninger.
Mens vi organiserer eller arrangerer data i strukturer, er vi nødt til at sikre, at arrangementet repræsenterer næsten et objekt fra den virkelige verden. For det andet skal dette arrangement være enkelt nok, så enhver let kan få adgang til det og behandle det, når det er nødvendigt.
I denne serie lærer vi detaljeret om såvel grundlæggende som en avanceret datastruktur. Vi lærer også detaljeret om forskellige søge- og sorteringsteknikker, der kan udføres på datastrukturer.
Efter at have lært denne tutorial-serie, skal læseren blive fortrolig med hver datastruktur og dens programmering.
Lad os gennemgå nogle af de termer, som vi bruger, når vi beskæftiger os med datastrukturer:
For eksempel,tage en bestemt studerende. En studerende kan have følgende detaljer som vist i billedet.
- Data: Det er den grundlæggende værdi. I ovenstående figur kan elevrulle nr. Være data.
- Gruppepost: Dette er det dataelement, der har mere end en underemne. I ovenstående figur har Student_name Fornavn og Efternavn.
- Optage: Det er en samling af dataelementer. I ovenstående eksempel danner dataelementer som elevrulle nr., Navn, klasse, alder, lønklasse osv. En post sammen.
- Enhed: Det er en klasse af poster. I ovenstående diagram er den studerende en enhed.
- Attribut eller felt: Egenskaber for en enhed kaldes attributter, og hvert felt repræsenterer en attribut.
- Fil: En fil er en samling poster. I ovenstående eksempel kan en studerende enhed have tusindvis af poster. En fil vil således indeholde alle disse poster.
Læseren skal være opmærksom på alle disse termer, da vi bruger dem nu og da, når vi bruger forskellige datastrukturer.
Datastrukturer er programmets vigtigste byggesten, og som programmører skal vi være forsigtige med, hvilken datastruktur der skal bruges. Den nøjagtige datastruktur, der skal bruges, er den sværeste beslutning at træffe for så vidt angår programmering.
Lad os diskutere behovet for datastruktur i programmering.
Behov for datastruktur i programmering
Efterhånden som datamængden fortsætter med at vokse, bliver applikationerne mere og mere komplekse, hvorfor det bliver svært for programmøren at administrere disse data såvel som softwaren.
Typisk kan applikationen til enhver tid stå over for følgende forhindringer:
# 1) Søgning efter store mængder data: Med en stor mængde data, der behandles og lagres, kan vores program til enhver tid kræves for at søge i bestemte data. Hvis dataene er for store og ikke er organiseret korrekt, tager det meget tid at få de nødvendige data.
Når vi bruger datastrukturer til at gemme og organisere data, bliver hentning af data hurtigere og lettere.
# 2) Behandlingshastighed: Uorganiserede data kan resultere i langsom behandlingshastighed, da der spildes meget tid på at hente og få adgang til data.
Hvis vi organiserer dataene korrekt i en datastruktur under lagring, spilder vi ikke tid på aktiviteter som at hente og organisere dem hver gang. I stedet kan vi koncentrere os om behandling af data for at producere det ønskede output.
# 3) Flere samtidige anmodninger: Mange applikationer i disse dage har brug for at stille en samtidig anmodning om data. Disse anmodninger skal behandles effektivt, så applikationer kører problemfrit.
Hvis vores data kun gemmes tilfældigt, kan vi ikke behandle alle samtidige anmodninger samtidigt. Så det er en klog beslutning at arrangere data i en korrekt datastruktur for at minimere de samtidige anmodningers leveringstid.
Datastrukturklassificering
Datastrukturer anvendt i C ++ kan klassificeres som følger.
En datastruktur er en måde at organisere dataene på. Så vi kan klassificere datastrukturer som vist i primitive eller standard datastrukturer og ikke-primitive eller brugerdefinerede datastrukturer.
Vi har set alle datatyper, der understøttes i C ++. Da dette også er en måde at organisere data på, siger vi, at det er en standard datastruktur.
De andre datastrukturer er ikke-primitive, og brugeren skal definere dem, før de bruges i et program. Disse brugerdefinerede datastrukturer klassificeres yderligere i lineære og ikke-lineære datastrukturer.
Lineær datastruktur
Lineære datastrukturer har alle deres elementer arrangeret på en lineær eller sekventiel måde. Hvert element i en lineær datastruktur har en forgænger (forrige element) og en efterfølger (næste element)
Lineære datastrukturer er yderligere opdelt i statiske og dynamiske datastrukturer. Statiske datastrukturer har normalt en fast størrelse, og når deres størrelse er erklæret på kompileringstidspunktet, kan den ikke ændres. Dynamiske datastrukturer kan ændre deres størrelse dynamisk og imødekomme sig selv.
Det mest populære eksempel på lineær statisk datastruktur er en matrix.
Array
En matrix er en sekventiel samling af elementer af samme type. Hvert element i arrayet kan tilgås ved hjælp af dets position i arrayet kaldet et indeks eller abonnement på arrayet. Navnet på arrayet peger på det første element i arrayet.
Ovenstående er vist et array 'a' af n-elementer. Elementerne er nummereret fra 0 til n-1. Matrixens størrelse (i dette tilfælde) kaldes også arrayets dimension. Som vist i ovenstående figur peger navnet på arrayet på det første element i arrayet.
Arrayet er den enkleste datastruktur og er effektiv, da elementer kan tilgås ved hjælp af abonnementer direkte. Hvis vi ønsker at få adgang til det tredje element i arrayet, er vi bare nødt til at sige a [2].
Men at tilføje eller slette matrixelementerne er svært. Derfor bruger vi kun arrays i enkle applikationer eller i applikationer, hvor tilføjelse / sletning af elementer ikke er påkrævet.
Populære lineære dynamiske datastrukturer er linket liste, stak og kø.
Tilknyttet liste
En linket liste er en samling af noder. Hver node indeholder dataelementet og en markør til den næste node. Noder kan tilføjes og slettes dynamisk. En linket liste kan være en enkelt linket liste, hvor hver node kun har en markør til det næste element. For det sidste element er den næste markør indstillet til null.
På den dobbeltkoblede liste har hver node to markører, en til den forrige node og den anden til den næste node. For den første node er den foregående markør nul, og for den sidste node er den næste markør nul.
Som vist i figuren ovenfor kaldes begyndelsen på listen hovedet, mens slutningen på den sammenkædede liste kaldes halen. Som vist ovenfor har hver node en markør til det næste element. Vi kan nemt tilføje eller slette elementer ved at ændre markøren til den næste node.
Stak
Stak er en lineær datastruktur, hvor elementerne kun kan tilføjes eller fjernes fra den ene ende kendt som 'Top' af stakken. På denne måde udviser stack LIFO (Last In, First Out) type hukommelsesadgang.
Som vist ovenfor tilføjes elementer i stakken altid i den ene ende og fjernes også fra den samme ende. Dette kaldes 'Top' af stakken. Når et element tilføjes, skubbes det ned ad stakken, og toppen af stakken forøges med en position.
Tilsvarende, når et element fjernes, reduceres toppen af stakken. Når en stak er tom, er toppen af stakken indstillet til -1. Der er to hovedoperationer 'Push' og 'Pop', der udføres på stakken.
Kø
Køen er endnu en lineær datastruktur, hvor elementerne tilføjes i den ene ende kaldet 'bag' og slettes fra en anden ende kaldet 'front'. Kø demonstrerer FIFO (First In, First Out) typen af hukommelsesadgangsmetode.
Ovenstående diagram viser en kø med bag- og frontender. Når køen er tom, falder de bageste og forreste markører sammen.
Ikke-lineær datastruktur
I ikke-lineære datastrukturer er data ikke arrangeret sekventielt, men i stedet er de arrangeret på en ikke-lineær måde. Elementer er forbundet med hinanden i et ikke-lineært arrangement.
Ikke-lineære datastrukturer er træer og grafer.
hvordan man bruger en jar-fil
Træer
Træer er ikke-lineære datastrukturer på flere niveauer med et hierarkisk forhold mellem elementerne. Elementer af træet kaldes knudepunkter.
Noden øverst kaldes træets rod. Roden kan have en eller flere underordnede noder. De efterfølgende noder kan også have en eller flere underordnede noder. De noder, der ikke har underknudepunkter, kaldes bladnoder.
I ovenstående diagram har vi vist et træ med 6 noder. Ud af disse tre knudepunkter er bladknudepunkterne, en øverste knude er roden, og de andre er underknudepunkter. Afhængigt af antallet af knudepunkter, underknudepunkter osv. Eller forholdet mellem knudepunkterne har vi forskellige typer træer.
Grafer
Grafen er et sæt noder kaldet hjørner forbundet til hinanden ved hjælp af de kaldte links Kanter . Grafer kan have en cyklus inde i den, dvs. det samme toppunkt kan være et udgangspunkt såvel som slutpunktet for en bestemt sti. Træer kan aldrig have en cyklus.
Ovenstående diagram er en ikke-rettet graf. Vi kan også have rettet grafer, hvor vi repræsenterer kanterne ved hjælp af rettet pile.
Operationer på datastruktur
Alle datastrukturer udfører forskellige operationer på dets elementer.
Disse er fælles for alle datastrukturer og er angivet som følger:
- Søger: Denne handling udføres for at søge efter et bestemt element eller en nøgle. De mest almindelige søgealgoritmer er sekventiel / lineær søgning og binær søgning.
- Sortering: Sorteringsoperation indebærer at arrangere elementerne i en datastruktur i en bestemt rækkefølge enten stigende eller faldende. Der er forskellige sorteringsalgoritmer, der er tilgængelige for datastrukturer. Mest populære blandt dem er Quicksort, Selection sort, Merge sort osv.
- Indskud: Indsættelseshandling handler om at tilføje et element til datastrukturen. Dette er den vigtigste operation, og som et resultat af tilføjelsen af et element ændres arrangementet, og vi er nødt til at passe på, at datastrukturen forbliver intakt.
- Sletning: Sletning fjerner et element fra datastrukturen. De samme betingelser, der skal overvejes for indsættelse, skal også være opfyldt i tilfælde af sletning.
- Traversering: Vi siger, at vi krydser en datastruktur, når vi besøger hvert eneste element i strukturen. Traversering kræves for at udføre bestemte specifikke operationer på datastrukturen.
I vores efterfølgende emner lærer vi først de forskellige søge- og sorteringsteknikker, der skal udføres på datastrukturer.
Fordele ved datastruktur
- Abstraktion: Datastrukturer implementeres ofte som abstrakte datatyper. Brugerne får kun adgang til dets ydre grænseflade uden at bekymre sig om den underliggende implementering. Datastrukturen giver således et lag af abstraktion.
- Effektivitet: Korrekt organisering af data resulterer i effektiv adgang til data og derved gør programmer mere effektive. For det andet kan vi vælge den rigtige datastruktur afhængigt af vores krav.
- Genanvendelighed: Vi kan genbruge de datastrukturer, som vi har designet. De kan også samles i et bibliotek og distribueres til klienten.
Konklusion
Med dette afslutter vi denne vejledning om introduktion til datastrukturer. Vi har introduceret hver af datastrukturer i korte træk i denne vejledning.
I vores efterfølgende tutorials vil vi udforske mere om datastrukturer sammen med de forskellige søge- og sorteringsteknikker.
=> Klik her for den absolutte C ++ træningsserie.
Anbefalet læsning
- C ++ datatyper
- Kø Datastruktur i C ++ med illustration
- Top 10 datavidenskabsværktøjer i 2021 til at fjerne programmering
- JMeter-dataparameterisering ved hjælp af brugerdefinerede variabler
- 10+ bedste dataindsamlingsværktøjer med strategier til dataindsamling
- 10+ bedste datastyringsværktøjer til at opfylde dine databehov i 2021
- Data Pool-funktion i IBM Rational Quality Manager til testdatastyring
- Stak datastruktur i C ++ med illustration