Array (datatype)

Et array er en datastruktur, der gemmer et sæt værdier (arrayelementer) identificeret af et indeks eller et sæt indekser, der tager heltal (eller konverterbare) værdier fra et givet kontinuerligt område. Et endimensionelt array kan opfattes som en implementering af en abstrakt datatype, en vektor. I nogle programmeringssprog kan et array også kaldes en tabel, en række, en vektor, en matrix.

Dimensionen af et array er antallet af indekser, der kræves for entydigt at adressere et element i arrayet [1] . Efter antallet af anvendte indekser er arrays opdelt i endimensionelle, todimensionelle, tredimensionelle osv.

Arrayets form eller struktur - information om antallet af dimensioner og størrelsen (længden) af arrayet for hver af dimensionerne [2] ; kan repræsenteres af et endimensionelt array [3] .

Et træk ved et array som en datastruktur (i modsætning til f.eks. en sammenkædet liste ) er den konstante beregningsmæssige kompleksitet ved at få adgang til et array-element efter indeks [4] . Array refererer til random access datastrukturer .

I det enkleste tilfælde har et array en konstant længde i alle dimensioner og kan kun lagre data af én type angivet i beskrivelsen. En række sprog understøtter også dynamiske arrays , hvis længde kan ændres under programafviklingen, og heterogene arrays , som kan lagre data af forskellige typer i forskellige elementer. Nogle specifikke array-typer, der bruges i forskellige sprog og implementeringer, er associative array , segment tree , V-list , parallel array , sparse array .

De vigtigste fordele ved at bruge arrays er letheden ved at beregne adressen på et element ved dets indeks (da elementerne i arrayet er placeret efter hinanden), den samme adgangstid til alle elementer, den lille størrelse af elementerne (de kun består af et informationsfelt). Blandt ulemperne er manglende evne til at fjerne eller tilføje et element uden at flytte andre, når du bruger statiske arrays, og når du bruger dynamiske og heterogene arrays, langsommere ydeevne på grund af omkostningerne ved at opretholde dynamik og heterogenitet. Når du arbejder med arrays med en C-implementering (med pointere) og ingen yderligere kontroller, er en typisk runtime-fejl truslen om array-overløb og datakorruption.

Implementeringsmuligheder

Et array er et ordnet sæt af elementer, som hver lagrer en enkelt værdi, identificeret af et eller flere indekser. I det enkleste tilfælde har et array en konstant længde og gemmer dataenheder af samme type, og heltal fungerer som indekser.

Antallet af array-indekser, der bruges, kan være forskelligt: arrays med ét indeks kaldes endimensionelle, dem med to kaldes todimensionelle, og så videre. En-dimensionel array - svarer løst til en vektor i matematik; todimensionel ("række", "søjle") - matrix . Arrays med et eller to indekser er mest almindeligt anvendt; sjældnere - med tre; et endnu større antal indekser er yderst sjældent.

Det første element i et array, afhængigt af programmeringssproget , kan have et andet indeks. Der er tre hovedtyper af arrays: nul-baseret ( nul-baseret ), en-baseret ( en-baseret ) og baseret på en specifik værdi givet af programmøren ( n-baseret ). At tælle fra nul er mere typisk for programmeringssprog på lavt niveau , selvom det også findes på højt niveau sprog, for eksempel bruges det på næsten alle sprog i C-familien. På en række sprog ( Pascal , Ada , Modula-2 ) kan en række indekser defineres som et vilkårligt interval af værdier af enhver datatype, der kan castes til et heltal, dvs. heltal, symboler, opregninger, selv booleans (i sidstnævnte tilfælde har en matrix to elementer indekseret med værdierne "True" og "False").

Et eksempel på et fast array i Pascal {Et-dimensionelt array af heltal. Nummereringselementer fra 1 til 15} a : array [ 1 .. 15 ] af heltal ; {Todimensionel række af tegn. Kolonnenummerering efter bytetype (fra 0 til 255) efter rækker fra 1 til 5} multiArray : array [ Byte , 1 .. 5 ] af Char ; {Endimensional række af strenge. Ordnummerering (fra 0 til 65536)} rangeArray : array [ Word ] af String ; Fixed Array Eksempel i C int Array [ 10 ]; // Endimensional matrix: heltal, størrelse 10; // Nummerering af elementer — fra 0 til 9. dobbelt Array [ 12 ][ 15 ]; // Todimensionelt array: // reelle tal med dobbelt præcision, // størrelse 12 x 15; // Nummerering: efter rækker - fra 0 til 11, // efter kolonner - fra 0 til 14.

I nogle programmeringssprog skabes multidimensionelle arrays på basis af endimensionelle arrays, hvor elementerne er arrays [5] .

JavaScript 2D Array Eksempel //Opret en todimensional matrix af tal: var matrix = [ [ 11 , 12 , 13 , 14 , 15 , 16 ], // Den første række er en matrix [ 21 , 22 , 23 , 24 , 25 , 26 ] , // Den anden [ 31 , 32 , 33 , 34 , 35 , 36 ] // Tredje ]; // Output array til konsol: array . forEach (( subArray ) => { // For hver sub-array, subArray . forEach (( item ) => { // for hvert af dets elementer, console . log ( item ); // udskriv dette element til konsollen. }); });

Understøttelse af indeks-arrays (dets egen erklæringssyntaks, funktioner til at arbejde med elementer og så videre) findes i de fleste programmeringssprog på højt niveau . Den maksimalt tilladte matrixdimension, typer og intervaller af indeksværdier, begrænsninger for elementtyper bestemmes af programmeringssproget eller en specifik oversætter .

I programmeringssprog, der tillader programmøren at erklære deres egne typer , er det generelt muligt at oprette en "array" type. I definitionen af en sådan type er typerne og/eller værdiintervallerne for hvert af indeksene og typen af array-elementerne specificeret. Den erklærede type kan senere bruges til at definere variabler, formelle parametre og funktionsreturværdier. Nogle sprog understøtter tildelingsoperationer for arrayvariabler (når en operation tildeler alle elementer i et array til værdierne af de tilsvarende elementer i et andet array).

Array type erklæring i Pascal type TArrayType = matrix [ 0 .. 9 ] af heltal ; (* Arrays, der har følgende parametre: 1. Størrelse - 10 celler; 2. Type af elementer, der er egnet til lagring - - heltal i området [−32 768; 32 767], - er deklareret af en operandtype kaldet "TArrayType" . *) var arr1 , arr2 , arr3 : TArrayType ; (* Erklæring af tre matrixvariabler af samme type (den ovenstående "TArrayType"). *)

I APL -programmeringssproget er et array hoveddatatypen (et nuldimensionelt array kaldes en skalar, et endimensionelt array kaldes en vektor, og et todimensionelt array kaldes en matrix) [3] . Ud over array-tildeling understøtter dette sprog vektor- og matrix-aritmetiske operationer, som hver udføres af én kommando, dataskift-operationer i arrays og matrixrækkesortering.

Dynamiske arrays

Arrays kaldes dynamiske, hvis størrelse kan ændre sig under afviklingen af programmet. Almindelige (ikke-dynamiske) arrays kaldes også faste eller statiske .

Dynamiske arrays kan implementeres både på niveau med programmeringssproget og på niveau med systembiblioteker. I det andet tilfælde er det dynamiske array et objekt af standardbiblioteket, og alle operationer med det implementeres i det samme bibliotek. På en eller anden måde indebærer understøttelse af dynamiske arrays følgende funktioner:

Beskrivelse af det dynamiske array. På sprogniveau kan dette være en særlig syntaktisk konstruktion; på biblioteksniveau kan det være en biblioteksdatatype, hvis værdi er deklareret på en standard måde. Som regel, når man beskriver (opretter) et dynamisk array, er dets startstørrelse angivet, selvom dette ikke er nødvendigt.
Operationen til at bestemme den aktuelle størrelse af et dynamisk array.
Operationen med at ændre størrelsen af et dynamisk array.

Et eksempel på strukturer til at arbejde med dynamiske arrays i Delphi :

var // Beskrivelser af dynamiske arrays byteArray : Array of Byte ; // One-dimensional array multiArray : Array af Array af streng ; // Multidimensional array ... SetLength ( byteArray , 1 ) ; // Indstil matrixstørrelsen til 1 element. byteArray [ 0 ] := 16 ; // Skriveelement. SetLength ( byteArray , Length ( byteArray ) + 1 ) ; // Forøg matrixstørrelsen med én byteArray [ Længde ( byteArray ) -1 ] : = 10 ; // Skriv værdien til det sidste element. WriteLn ( byteArray [ Længde ( byteArray ) - 1 ]) ; // Vis det sidste element i arrayet. ... SetLength ( multiArray , 20 , 30 ) ; // Indstil størrelsen af et todimensionelt array multiArray [ 10 , 15 ] := 12 ; // Skriv værdi SetLength ( multiArray , 10 , 15 ) ; // Reducer størrelsen af WriteLn ( Length ( multiArray ) , ' ' , Length ( multiArray [ 0 ])

Heterogene arrays

En matrix kaldes heterogen , i de forskellige elementer, hvis værdier relateret til forskellige datatyper kan skrives direkte . Et array, der gemmer pointere til værdier af forskellige typer, er ikke heterogent, da de data, der faktisk er lagret i arrayet, tilhører en enkelt type - "pointer"-typen. Heterogene arrays er praktiske som en universel struktur til lagring af datasæt af vilkårlige typer. Implementeringen af heterogenitet kræver komplikationen af array-støttemekanismen i sprogoversætteren.

Arbejde med hukommelse

En typisk måde at implementere en statisk homogen (lagring af data af samme type) array er at allokere en kontinuerlig blok af hukommelse med et volumen på , hvor er størrelsen af et element, og er størrelserne af indeksområder (det vil sige antal værdier, som det tilsvarende indeks kan tage). Ved adgang til et array-element med et indeks, beregnes adressen på det tilsvarende element som Rækkefølgen af indekser i adresseberegningsformlen kan være forskellig. (Denne måde svarer til implementeringen i de fleste C - compilere ; i Fortran er indeksrækkefølgen omvendt [2] ). ${\displaystyle S\cdot m_{1}\cdot m_{2}\cdot \dots m_{n))$ $S$ $m_{1},\dots m_{n}$ $(i_{1},i_{2},\dots i_{n})$ $B+S\cdot \left(\left(\dots \left(i_{\text{1p}}m_{1}+i_{\text{2p}}\right)\cdot m_{2}+ \dots +i_{(n-1){\text{p}}}\right)\cdot m_{n-1}+i_{n{\text{p}}}\right)$ $B$ $i_{k\mathrm {p} }$ $k$

Således beregnes adressen på et element med et givet sæt af indekser på en sådan måde, at adgangstiden til alle elementer i arrayet teoretisk er den samme; Forskellige værdier af svarforsinkelser fra RAM til celler placeret på forskellige hukommelseselementer kan imidlertid påvirke, men i praksis med programmering på højt niveau bliver sådanne finesser, med sjældne undtagelser, forsømt.

Den sædvanlige måde at implementere heterogene arrays på er at gemme værdierne af selve elementerne separat og placere pointere til disse elementer i arrayets hukommelsesblok (organiseret som et regulært homogent array, beskrevet ovenfor). Da pointere til værdier af enhver type har en tendens til at være af samme størrelse, er det muligt at holde adresseberegningen enkel, selvom der er yderligere overhead til at allokere og få adgang til elementværdier.

Dynamiske arrays kan bruge den samme layoutmekanisme som statiske arrays, men med noget ekstra hukommelse tildelt til udvidelse og tilføjelse af mekanismer til at ændre størrelse og flytte indholdet af arrayet i hukommelsen.

Dynamiske og heterogene arrays kan også implementeres ved at bruge fundamentalt forskellige metoder til lagring af værdier i hukommelsen, for eksempel enkelt- eller dobbeltforbundne lister. Sådanne implementeringer kan være mere fleksible, men kræver typisk yderligere overhead. Derudover opfylder de normalt ikke kravet om konstant elementadgangstid.

Noter

↑ Drot V. L., Novikov F. A. "Explanatory Dictionary of Modern Computer Vocabulary", Dimension of an array . Dato for adgang: 18. oktober 2012. Arkiveret fra originalen den 3. juli 2013. (ubestemt)
↑ 1 2 Barteniev, 2000 .
↑ 1 2 Magariu, 1983 .
↑ Wirth, 1989 , 1.6 Array.
↑ Michael McMillan. Datastrukturer og algoritmer med JavaScript (engelsk) . - O'Reilly Media , 2014. - S. 30-32. — ISBN 978-1-4493-7396-2 .

Litteratur

Wirth N. Algoritmer og datastrukturer = Algoritmer og datastruktur. — M .: Mir, 1989. — 360 s. — ISBN 5-03-001045-9 .
Magariu N.A. Programmeringssprog APL. - M . : "Radio og kommunikation", 1983. - 96 s.
Barteniev O. V. Moderne Fortran. - 3. udg., tilføje. og revideret .. - M . : Dialog-MEPhI, 2000. - 449 s.

Datastrukturer
Lister	array enkelt linket liste dobbelt linket liste Beståelsesliste
Træer	B-træ Binært søgetræ AVL træ Rød-sort træ dynge
Tæller	Instrueret graf rettet acyklisk graf Binært beslutningsdiagram Hypergraf
Andet	Hash bord Stak

Datatyper
Ufortolkelig	Bit Nappe Byte qubit Behandle Egenskab Ord
Numerisk	Hel fast punkt flydende komma Rationel Kompleks Lang interval
Tekst	Symbolsk Snor
Reference	Adresse Link Pointer Indpakning
Sammensatte	Algebraisk datatype ( generisk ) Klasse Type-produkt ( Skriv Tuple struktur ) Et objekt Konsolidering ( tagget ) Bestilt par
abstrakt	array Liste Tur Stak Associativ array (visning, kort ) Masser af multisæt Type Kurve
Andet	Logisk Nederste Højere Polymorf Funktionel talløse Kollektion Undtagelse Slægt ( metaklasse ) Monade Semafor Flyde ugyldig
relaterede emner	Abstrakt datatype primitiv type Datastruktur Generisk type variabel Interface Konstruktør (OOP) Konstruktør (FP) Type konstruktør Type støbning Prototype Type system