Data struktur

Innen datavitenskap er en datastruktur [ 1 ] en spesiell måte å organisere informasjon i en datamaskin på slik at den kan brukes effektivt. [ 2 ] [ 3 ] [ 4 ] Ulike typer datastrukturer er egnet for ulike typer applikasjoner , og noen er svært spesialiserte for spesifikke oppgaver.

Datastrukturer er et middel for å håndtere store mengder informasjon effektivt for slike bruksområder som store databaser og Internett - indekseringstjenester . Generelt er effektive datastrukturer nøkkelen til å designe effektive algoritmer . Noen formelle designmetoder for programmeringsspråk legger vekt på datastrukturer, snarere enn algoritmer, som den viktigste organiserende faktoren i programvaredesign . Mer presist er en datastruktur en samling av verdier, relasjonene mellom dem, og funksjonene og operasjonene som kan brukes på dataene. [ 5 ] det vil si at det er enalgebraisk struktur på data .

Beskrivelse

Datastrukturer er vanligvis basert på en datamaskins evne til å hente og lagre data hvor som helst i minnet .

Datastrukturtyper

Datastrukturer kan være av forskjellige typer, avhengig av teknikken som brukes for lagring og gjenfinning, disse typene er som følger:

Statisk datastruktur.
Dynamisk datastruktur [ 6 ] .

I henhold til sekvensen som oppstår mellom hvert element på tidspunktet for å krysse mellom elementene i datastrukturen, kan det klassifiseres i følgende typer:

Lineær datastruktur.
Ikke-lineær datastruktur.

Eksempler

Det finnes mange typer datastrukturer, vanligvis bygget på toppen av enklere:

En vektor er en rekke elementer i en bestemt rekkefølge, vanligvis alle av samme type (selv om elementene kan være av nesten hvilken som helst type). Elementer åpnes ved å bruke et heltall som en indeks for å spesifisere elementet som kreves. Typiske implementeringer allokerer sammenhengende minneord til array-elementer (selv om dette ikke alltid er tilfelle). Matriser kan endres størrelse eller ha en fast lengde.
En assosiativ matrise (også kalt en ordbok eller kart ) er en mer fleksibel variant av en matrise, ved at du fritt kan legge til og fjerne navn-verdi-par. En hash-tabell er en vanlig implementering av en assosiativ matrise.
En post (også kalt en tuppel eller struct ) er en samlet datastruktur. En post er en verdi som inneholder andre verdier, vanligvis i et fast antall og rekkefølge, og vanligvis indeksert med navn. Postelementer kalles ofte felt eller celler .
En union er en datastruktur som spesifiserer hvilken av en rekke tillatte datatyper som kan lagres i dens instanser, for eksempel float eller longint . I motsetning til et register, som kan defineres til å inneholde en float og et langt heltall , er det i en union bare én verdi om gangen. Det er tildelt nok plass til å holde datatypen til noen av medlemmene.
En varianttype (også kalt en variantpost eller diskriminert forening ) inneholder et tilleggsfelt som indikerer dens gjeldende type.
Et sett er en abstrakt datatype som kan lagre spesifikke verdier, uten spesiell rekkefølge, og uten dupliserte verdier.
Et multisett er en abstrakt datatype som kan lagre spesifikke verdier, uten spesiell rekkefølge. I motsetning til sett, støtter multisett repetisjoner.
En graf er en tilkoblet datastruktur som består av noder. Hver node inneholder en verdi og en eller flere referanser til andre noder. Grafer kan brukes til å representere nettverk, siden noder kan referere til hverandre. Forbindelsene mellom noder kan ha en retning, det vil si en startnode og en ankomstnode.
Et tre er et spesielt tilfelle av en rettet graf der sykluser ikke er tillatt og det er en vei fra en node kalt roten til hver av de andre nodene. En samling av trær kalles en skog.
En klasse er en mal for å lage dataobjekter i henhold til et forhåndsdefinert mønster. Klasser brukes som en abstrakt representasjon av konsepter, de inkluderer felt som poster og operasjoner som kan spørre om verdien av felt eller endre verdiene deres.

Språkstøtte

De fleste monteringsspråk og noen lavnivåspråk , for eksempel BCPL , mangler datastrukturstøtte. I stedet har mange høynivå- språk og noen høynivå-assembly-språk, som MASM , en slags innebygd støtte for visse datastrukturer, for eksempel poster og arrays. For eksempel støtter C- og Pascal -språkene henholdsvis strukturer og poster, samt flerdimensjonale arrays og arrays. [ 7 ] [ 8 ]

De fleste programmeringsspråk har en slags bibliotek eller mekanisme som tillater bruk av datastrukturer i programmer. Moderne språk kommer vanligvis med standardbiblioteker som implementerer de vanligste datastrukturene. Eksempler er C++ Standard Template Library , Java - samlingene [ 9 ] og Microsoft .NET - bibliotekene .

Datastrukturer i programmering

I programmering kan en datastruktur først deklareres ved å skrive et reservert ord , deretter en identifikator for strukturen og et navn for hvert av medlemmene, ikke å glemme datatypene de representerer. Vanligvis er hvert medlem atskilt med en slags operator, tegn eller reservert ord.

I programmeringsspråket Pascal er det mulig å lage en datastruktur på den nevnte måten. Den grunnleggende syntaksen er:

Strukturidentifikator , _ Member1:DataType, _ Member2:DataType, _ ... Member9:DataType

For å få tilgang til medlemmene av en struktur, må du først opprette en referanse til den, vanligvis med en variabel av typen; da kan du redigere og få medlemsdataene fritt.

Strukturstruktur,Medlem1:Heltall,Medlem2:Streng,Medlem3:Byte Var - variabel :Struktur Variabel.Medlem1 = 40000 Variable.Member2 = "Hei verden" Variabel.Medlem3 = 255 Message(Variable.Member2) ' Viser "Hello World"

Referanser

↑ Peláez, Canek (2018). Det naturvitenskapelige fakultet, red. Datastrukturer med moderne Java. Atferd + objekter = programmer . Mexico by: National Autonomous University of Mexico. ISBN 978-607-30-0966-9 .
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduksjon til algoritmer, tredje utgave (3. utgave). MIT Press. ISBN 978-0262033848 .
↑ Black, Paul E. (15. desember 2004). «datastruktur» . I Pieterse, Vreda; Black, Paul E., red. Ordbok for algoritmer og datastrukturer [online] . Nasjonalt institutt for standarder og teknologi . Hentet 6. november 2018 .
↑ «Datastruktur» . Encyclopaedia Britannica . 17. april 2017 . Hentet 6. november 2018 .
↑ Wegner, Peter; Reilly, Edwin D. (29. august 2003). Encyclopedia of Computer Science . Chichester, Storbritannia: John Wiley and Sons. s. 507-512. ISBN 978-0470864128 .
^ "Dynamiske datastrukturer/fulltekst" .
^ "GNU C-manualen" . Free Software Foundation . Hentet 23. mars 2016 .
^ "Gratis Pascal: Referanseguide" . FreePascal . Hentet 23. mars 2016 .
↑ "Java-gjennomgang. Sti: Samlinger» . Oracle . Hentet 23. mars 2016 .