Data struktur

I informatikk er en datastruktur en enhet som brukes til å organisere et sett med data i datamaskinens minne , og muligens for å lagre det i et masseminne . Valget av datastrukturene som skal brukes er strengt knyttet til algoritmene ; av denne grunn vurderes de ofte sammen. Faktisk påvirker valget av datastrukturen uunngåelig beregningseffektiviteten til algoritmene som manipulerer den.

Datastrukturen er en metode for å organisere data, så den er uavhengig av hva som faktisk finnes. Hvert programmeringsspråk tilbyr verktøy, mer eller mindre sofistikerte, for å definere datastrukturer, eller for å samle data av en homogen eller heterogen type. Disse instrumentene er vanligvis modulære.

Mer formelt gir språk et forhåndsdefinert sett med elementære datatyper , og datastrukturer er verktøy for å bygge mer komplekse aggregerte datatyper.

Konstruksjonsoperasjonen av en variabel av en kompleks datatype kalles "instansiering", og kan skje både under kompileringen av programmet ( kompileringstid ) og under utførelse av det ( runtime ).

Datastrukturer varierer først og fremst på grunnlag av operasjonene som kan utføres på dem og tjenestene som tilbys. Dette gjør det mulig å studere en abstraksjon fra implementeringen.

Abstrakte datastrukturer

Vi snakker om abstrakte datastrukturer når vi ønsker å skille strukturene fra deres implementeringer ; en abstrakt datastruktur kan implementeres på forskjellige måter i forskjellige programmeringsspråk, eller til og med på samme språk.

Datastrukturbyggere

Array eller vektor

En matrise er en homogen datastruktur, som inneholder et begrenset antall elementer alle av samme type, for eksempel en vektor med 10 heltall. Disse elementene identifiseres gjennom en numerisk indeks, som vanligvis varierer fra 0 til maksimalt antall elementer minus én. Størrelsen på vektoren må deklareres på tidspunktet for opprettelsen. Vektorer av forskjellige størrelser utgjør forskjellige datatyper. Å få tilgang til et element i en matrise har en konstant beregningskostnad, mens det å legge til eller fjerne elementer i tilfeldige posisjoner kan være ganske dyrt, vanligvis prerogativet til dynamiske matriser .

Registrer eller struktur

En post er en datastruktur som kan være heterogen eller homogen. I det første tilfellet inneholder den en kombinasjon av elementer som kan være av forskjellige typer, for eksempel et heltall, et flyttall og et teksttegn. Elementene som utgjør den kalles også felt , og identifiseres med et navn.

Klasse

En klasse er en typisk konstruksjon av objektorienterte språk , og består av en post som operasjoner eller metoder også er knyttet til .

Sammensetning av konstruktører

Disse byggene kan fritt kombineres for å gi opphav til mer komplekse strukturer. For eksempel er det mulig å representere en todimensjonal størrelsesmatrise som en dimensjonsvektor med lengdevektorer som elementer . Igjen kan vi definere en matrise med fem hundre elementer, som hver er en post bestående av fire strenger og to vektorer, som hver inneholder fire vektorer med tre tegn. $n \ ganger m$ $n$ $m$

Datastrukturene som oppnås ved å komponere disse konstruktørene kalles også "statiske", ettersom deres minneopptak er definert på tidspunktet for kompilering, eller på det meste i øyeblikket for instansiering. For eksempel: programmet bestemmer at det trenger en rekke med 100 elementer for å behandle dataene sine, og allokerer dem, det vil si at det forplikter det nødvendige minnet. Fra dette øyeblikket vil matrisen ha en fast størrelse, det vil si at den alltid vil være sammensatt av 100 elementer, og vil holde det nødvendige minnet okkupert til programmet avsluttes eller når det ikke blir ødelagt. Å endre lengden på arrayet er mulig, men svært kostbart med tanke på dataressurser og er derfor en operasjon som unngås så mye som mulig (se dynamiske arrays ).

Grensen for statiske datastrukturer er at de ikke tilpasser seg godt til problemer der antall data som skal behandles ikke er kjent på forhånd og/eller varierer betydelig under programkjøring.

Dynamiske datastrukturer

Dynamiske datastrukturer er basert på bruk av pekerdata , og på dynamisk minneallokering . Elementer kan allokeres (og deallokeres) etter behov, kobles sammen på forskjellige måter, og disse koblingene kan i seg selv endres under programkjøring. Minneplassen som kreves for å tildele pekere, og operasjonene som kreves for å vedlikeholde dem, utgjør tilleggskostnaden for dynamiske datastrukturer.

I mangel av pekere er det også mulig å bygge dynamiske datastrukturer ved hjelp av matriser, samtidig som man gir opp fleksibilitet i bruken av minne: en matrise av tilstrekkelig størrelse tildeles til å inneholde alle elementene du tror du trenger å administrere, og i stedet pekerindekser brukes i matrisen.

Dynamiske datastrukturer kan tilpasses for å representere enhver situasjon. De vanligste typene vises her.

Liste

En liste er et sett med lineært koblede "noder". Noder er poster som inneholder en "nyttelast" av data, og en peker til neste element i listen. Rekkefølgen nodene er koblet sammen definerer en rekkefølge mellom dem. En node fungerer som leder av listen, og fra denne er det mulig å få tilgang til alle nodene i listen. Når du kjenner en node i listen, er det mulig å få tilgang til følgende noder, men ikke de forrige.

Kostnaden for å få tilgang til en node i listen øker med størrelsen på listen. Når du kjenner noden foran en node N, er det mulig å fjerne N fra listen, eller sette inn et element foran den, på en konstant tid.

Toveis eller dobbeltlenket liste

I dette tilfellet inneholder nodene en peker til både forrige og neste node. Ved å bruke C- språksyntaks , gitt en node Ndens etterfølger er N->succ, og dens presedens er N->prec. Det må alltid være sant at N->succ->prec == N. Hver node lar deg få tilgang til alle elementene i listen. De "strukturelle" elementene i denne datastrukturen, dvs. de to pekerne i hver node, er overflødige.

Tre

Et tre er en representasjon av treet i grafteori .

Hver node inneholder to (eller flere) pekere til andre noder som kalles dens "barn". Fortsetter i metaforen, gitt en node, er det mulig å få tilgang til alle dens etterkommere. Et tre må være fritt for sykluser, det vil si at en node ikke kan være en etterkommer av seg selv, det vil si at det ikke må være mulig å starte fra en node, følge pekerne til barna og gå tilbake til startnoden. Videre må hver node være barn til bare én far.

I noen implementeringer inneholder hver node også en lenke til sin "far", klart forskjellig fra de til barna.

Det er vanligvis et rekkefølgeforhold mellom barna til en node, definert av rekkefølgen på pekerne i overordnet.

I mange implementeringer har hver node et fast antall barn, for eksempel to eller tre. I dette tilfellet snakker vi om binære eller ternære trær. I andre tilfeller er antallet barn til en node vilkårlig; dette kan administreres ved å lagre barna til en node i en liste over en av typene beskrevet ovenfor.

Hver node, i tillegg til pekerne til barnenodene, har normalt en "nyttelast", det vil si et stykke data knyttet til noden, nyttig for applikasjonsproblemet som skal løses.

Trær egner seg veldig godt til å representere matematiske formler.

Ordnede binære trær

Når dataene har en total ordensrelasjon, kan de i seg selv enkelt representeres i den binære trestrukturen.

Du kan for eksempel bruke konvensjonen om at en node Ner i venstre undertre Mhvis og bare hvis N < M, ellers Ner den i høyre undertre til M. Et tre med denne egenskapen kalles et binært søketre ( BST). På denne måten krever søket etter et element i et balansert ordnet tre en tid proporsjonal med høyden på treet, som i beste fall er proporsjonal med logaritmen til antall elementer, mens innsetting av et element i en ordnet treet krever også at den tidligere beskrevne sorteringsegenskapen respekteres. Avhengig av rekkefølgen på innsettingene, kan treet komme i ubalanse og derfor ha blader i svært forskjellige dybder fra hverandre, noe som forårsaker ineffektivitet i søket. Det er derfor noen ganger nødvendig at datastrukturen er utstyrt med og er gjenstand for en tvungen balanseringsoperasjon som minimerer høyden på skaftet.

Graf

Grafen er en generalisering av treet. Hver node har et vilkårlig antall "nabo" noder, og kan inneholde løkker. Generelt kan en nyttelast knyttes til både nodene og koblingene mellom dem.

Hash-tabell

En hash-tabell er en datastruktur som er nyttig for raskt å søke etter et element i et sett basert på en nøkkel, det vil si en undergruppe av elementets egenskaper. En nøkkelhash beregnes for hvert element som skal lagres. En matrise blir deretter konstruert, indeksert av hash-verdien, som pekerelementer til lister over noder som samsvarer med denne hash-verdien. Hvis hash-funksjonen er godt valgt, vil listene statistisk ha balanserte lengder.

For å søke etter et element, beregnes hash-verdien, det tilsvarende array-elementet velges og rulles gjennom listen til det blir funnet.

Beholdere

Datastrukturene beskrevet ovenfor kan brukes til å lage noen typer containere med hyppig bruk, som kan tvinge frem en bestemt modus for tilgang til dataene.

Stable eller stable

En stack er en LIFO ( Last In First Out ) datastruktur. Det gjøres vanligvis med matriser eller lister.

Kø

En kø er en FIFO ( First In First Out ) datastruktur. Det gjøres vanligvis med matriser eller lister.

Associative Array

Det er en datastruktur som finnes i mange skriptspråk . Den består av en matrise, hvis elementer imidlertid identifiseres med en nøkkel av en vilkårlig type i stedet for med en numerisk indeks. For å få tilgang til et element er nøkkelen vanligvis plassert i hakeparenteser, i stedet for indeksen. Hvis det ikke er noe element med den nøkkelen, får du en feil eller en konvensjonell verdi.

Datastrukturmaler

Manuell implementering av dynamiske datastrukturer er en repeterende, feilutsatt oppgave. Av denne grunn har forskjellige metoder blitt brukt for å skille definisjonen av datastrukturer fra bruken i algoritmer .

Noen språk tilbyr malverktøyet , som lar deg skrive funksjoner eller klasser som er parametriske med hensyn til typen argumenter eller noen medlemmer av klassen som kan brukes normalt.

En mal instansieres ved å spesifisere typen funksjonsargumenter eller klassemedlemmer som ikke er spesifisert i definisjonen, ved å konstruere en funksjon eller klasse.

På denne måten er det mulig å skrive en generisk listeklasse med hensyn til innholdet, med metodene som er nødvendige for å manipulere en liste, og deretter bruke den til å administrere både lister over heltall og lister over komplekse objekter.

STL og Generics

En viktig innsats for å bygge et bibliotek med generiske datastrukturer med hensyn til typen lagrede data er Standard Template Library (se STL på SGI-nettstedet ), basert på konseptet med å tilby et verktøy for ortogonalt å komponere data, containere (datastrukturer). ) og algoritmer . I STL er et viktig verktøy for å koble datastrukturer og algoritmer på en generisk måte iteratorer , en generalisering av pekere.

STL er et C++- klassebibliotek .

Java-språket har på den annen side to måter å administrere de grunnleggende datastrukturene som er tilstede i språket. Frem til versjon 1.4 ble containeradministrasjon gjort med arv i stedet for maler. Containere inneholder derfor objekter av typen "Object", en type som alle klassene som er definert i Java stammer fra; Følgelig er det i Java ikke like lett å forsikre seg om at alle objekter plassert i en container tilhører en gitt type. Siden versjon 1.5 har generikk blitt introdusert , som oppfører seg veldig likt med C++- maler og løser mange av problemene knyttet til den øvre støpingen av "gamle" beholdere.