Array (datatyp)

En matris  är en datastruktur som lagrar en uppsättning värden (matriselement) identifierade av ett index eller en uppsättning index som tar heltalsvärden (eller konvertibla) värden från ett givet kontinuerligt område. En endimensionell array kan ses som en implementering av en abstrakt datatyp,  en vektor. I vissa programmeringsspråk kan en array också kallas en tabell, en rad, en vektor, en matris.

Dimensionen för en array är antalet index som krävs för att unikt adressera ett element inom arrayen [1] . Med antalet använda index delas arrayer in i endimensionella, tvådimensionella, tredimensionella, etc.

Arrayens form eller struktur - information om antalet dimensioner och storleken (längden) av arrayen för var och en av dimensionerna [2] ; kan representeras av en endimensionell array [3] .

En egenskap hos en array som en datastruktur (till skillnad från till exempel en länkad lista ) är den konstanta beräkningskomplexiteten för att komma åt ett arrayelement genom index [4] . Array hänvisar till datastrukturer med direkt åtkomst .

I det enklaste fallet har en array en konstant längd i alla dimensioner och kan bara lagra data av en typ som anges i beskrivningen. Ett antal språk stöder också dynamiska arrayer , vars längd kan ändras under programkörning, och heterogena arrayer , som kan lagra data av olika typer i olika element. Några specifika arraytyper som används i olika språk och implementeringar är associativ array , segment tree , V-list , parallell array , sparse array .

De främsta fördelarna med att använda arrayer är att det är lätt att beräkna adressen till ett element genom dess index (eftersom elementen i arrayen är placerade efter varandra), samma åtkomsttid till alla element, den lilla storleken på elementen (de endast består av ett informationsfält). Bland nackdelarna är oförmågan att ta bort eller lägga till ett element utan att förskjuta andra när man använder statiska arrayer, och när man använder dynamiska och heterogena arrayer, långsammare prestanda på grund av överkostnaderna för att upprätthålla dynamik och heterogenitet. När du arbetar med arrayer med en C-implementering (med pekare) och inga ytterligare kontroller, är ett typiskt körtidsfel hotet om arrayöverskridande och datakorruption.

Implementeringsalternativ

En array är en ordnad uppsättning element, som vart och ett lagrar ett enda värde, identifierat av ett eller flera index. I det enklaste fallet har en array en konstant längd och lagrar dataenheter av samma typ, och heltal fungerar som index.

Antalet arrayindex som används kan vara olika: arrayer med ett index kallas endimensionella, de med två kallas tvådimensionella och så vidare. Endimensionell array - motsvarar löst en vektor i matematik; tvådimensionell ("rad", "kolumn") - matris . Matriser med ett eller två index används oftast; mindre ofta - med tre; ett ännu större antal index är extremt sällsynt.

Det första elementet i en array, beroende på programmeringsspråket , kan ha ett annat index. Det finns tre huvudtyper av arrayer: nollbaserad ( nollbaserad ), enbaserad ( enbaserad ) och baserad på ett specifikt värde som ges av programmeraren ( n-baserat ). Att räkna från noll är mer typiskt för programmeringsspråk på låg nivå , även om det också finns på högnivåspråk, till exempel används det på nästan alla språk i C-familjen. På ett antal språk ( Pascal , Ada , Modula-2 ) kan ett indexintervall definieras som ett godtyckligt värdeintervall av vilken datatyp som helst som kan gjutas till ett heltal, d.v.s. heltal, symboler, uppräkningar, även booleans (i det senare fallet har en array två element indexerade med värdena "True" och "False").

Ett exempel på en fast array i Pascal {Endimensionell matris av heltal. Numrering av element från 1 till 15} a : array [ 1 .. 15 ] av heltal ; {Tvådimensionell uppsättning tecken. Kolumnnumrering efter bytetyp (från 0 till 255) efter rader från 1 till 5} multiArray : array [ Byte , 1 .. 5 ] of Char ; {Endimensionell array av strängar. Ordnumrering (från 0 till 65536)} rangeArray : array [ Word ] av String ; Fixed Array Exempel i C int Array [ 10 ]; // Endimensionell array: heltal, storlek 10; // Numrering av element — från 0 till 9. dubbel Array [ 12 ][ 15 ]; // Tvådimensionell matris: // reella tal med dubbel precision, // storlek 12 gånger 15; // Numrering: efter rader - från 0 till 11, // efter kolumner - från 0 till 14.

I vissa programmeringsspråk skapas flerdimensionella arrayer på basis av endimensionella arrayer, där elementen är arrayer [5] .

Exempel på JavaScript 2D Array //Skapa en tvådimensionell array av tal: var array = [ [ 11 , 12 , 13 , 14 , 15 , 16 ], // Den första raden är en array [ 21 , 22 , 23 , 24 , 25 , 26 ] , // Den andra [ 31 , 32 , 33 , 34 , 35 , 36 ] // Tredje ]; // Utdatamatris till konsolen: matris . forEach (( subArray ) => { // För varje sub-array, subArray . forEach (( item ) => { // för vart och ett av dess element, console . log ( item ); // skriv ut detta element till konsolen. }); });

Stöd för indexmatriser (dess egen deklarationssyntax, funktioner för att arbeta med element, och så vidare) finns i de flesta högnivåprogrammeringsspråk . Den maximalt tillåtna arraydimensionen, typer och intervall av indexvärden, begränsningar för elementtyper bestäms av programmeringsspråket eller en specifik översättare .

I programmeringsspråk som tillåter programmeraren att deklarera sina egna typer , är det i allmänhet möjligt att skapa en "array" -typ. I definitionen av en sådan typ specificeras typerna och/eller värdeintervallen för vart och ett av indexen och typen av arrayelement. Den deklarerade typen kan senare användas för att definiera variabler, formella parametrar och funktionsreturvärden. Vissa språk stöder tilldelningsoperationer för arrayvariabler (när en operation tilldelar alla element i en array till värdena för motsvarande element i en annan array).

Array-typdeklaration i Pascal typ TArrayType = array [ 0 .. 9 ] av heltal ; (* Matriser som har följande parametrar: 1. Storlek - 10 celler; 2. Typ av element som är lämpliga för lagring - - heltal i intervallet [−32 768; 32 767], - deklareras av en operandtyp som kallas "TArrayType" . *) var arr1 , arr2 , arr3 : TArrayType ; (* Deklaration av tre matrisvariabler av samma typ (ovan "TArrayType"). *)

I APL -programmeringsspråket är en array huvuddatatypen (en nolldimensionell array kallas en skalär, en endimensionell array kallas en vektor och en tvådimensionell array kallas en matris) [3] . Förutom matristilldelning stöder detta språk vektor- och matrisaritmetiska operationer, som var och en utförs av ett kommando, dataskiftningsoperationer i matriser och matrisradsortering.

Dynamiska arrayer

Arrayer kallas dynamiska, vars storlek kan ändras under körningen av programmet. Vanliga (icke-dynamiska) arrayer kallas även fasta eller statiska .

Dynamiska arrayer kan implementeras både på nivån för programmeringsspråket och på nivån för systembibliotek. I det andra fallet är den dynamiska matrisen ett objekt i standardbiblioteket, och alla operationer med den implementeras inom samma bibliotek. På ett eller annat sätt innebär stöd för dynamiska arrayer följande funktioner:

  1. Beskrivning av den dynamiska arrayen. På språknivå kan detta vara en speciell syntaktisk konstruktion, på biblioteksnivå kan det vara en biblioteksdatatyp vars värde deklareras på ett standardsätt. Som regel, när man beskriver (skapar) en dynamisk array, anges dess initiala storlek, även om detta inte är nödvändigt.
  2. Operationen att bestämma den aktuella storleken på en dynamisk array.
  3. Operationen att ändra storleken på en dynamisk array.

Ett exempel på strukturer för att arbeta med dynamiska arrayer i Delphi :

var // Beskrivningar av dynamiska arrayer byteArray : Array of Byte ; // Endimensionell array multiArray : Array av Array av sträng ; // Flerdimensionell array ... SetLength ( byteArray , 1 ) ; // Ställ in arraystorleken till 1 element. byteArray [ 0 ] := 16 ; // Skrivelement. SetLength ( byteArray , Length ( byteArray ) + 1 ) ; // Öka arraystorleken med en byteArray [ Length ( byteArray ) - 1 ] := 10 ; // Skriv värdet till det sista elementet. WriteLn ( byteArray [ Length ( byteArray ) - 1 ] ) ; // Visa det sista elementet i arrayen. ... SetLength ( multiArray , 20 , 30 ) ; // Ställ in storleken på en tvådimensionell array multiArray [ 10 , 15 ] := 12 ; // Skriv värde SetLength ( multiArray , 10 , 15 ) ; // Minska storleken på WriteLn ( Length ( multiArray ) , ' ' , Length ( multiArray [ 0 ])

Heterogena arrayer

En array kallas heterogen , i vars olika element värden relaterade till olika datatyper kan skrivas direkt . En array som lagrar pekare till värden av olika typer är inte heterogen, eftersom data som faktiskt lagras i arrayen tillhör en enda typ - "pekare" -typen. Heterogena arrayer är praktiska som en universell struktur för att lagra datamängder av godtyckliga typer. Implementeringen av heterogenitet kräver komplikationen av arraystödmekanismen i språköversättaren.

Arbeta med minne

Ett typiskt sätt att implementera en statisk homogen (lagring av data av samma typ) array är att allokera ett kontinuerligt minnesblock med volymen , där  är storleken på ett element, och  är storleken på indexområdena (det vill säga antal värden som motsvarande index kan ta). Vid åtkomst till ett arrayelement med ett index beräknas adressen  för  motsvarande element som Ordningen på indexen i adressberäkningsformeln kan vara annorlunda. (Detta sätt motsvarar implementeringen i de flesta C -kompilatorer ; i Fortran är indexordningen omvänd [2] ).

Således beräknas adressen för ett element med en given uppsättning index på ett sådant sätt att åtkomsttiden till alla element i arrayen är teoretiskt densamma; dock kan olika värden på svarsfördröjningar från RAM till celler placerade på olika minneselement påverka, men i praktiken av högnivåprogrammering försummas sådana subtiliteter, med sällsynta undantag.

Det vanliga sättet att implementera heterogena arrayer är att lagra värdena för själva elementen separat och placera pekare till dessa element i arrayens minnesblock (organiserat som en vanlig homogen array, beskriven ovan). Eftersom pekare till värden av vilken typ som helst tenderar att vara av samma storlek, är det möjligt att hålla adressberäkningen enkel, även om det finns ytterligare overhead för att allokera och komma åt elementvärden.

Dynamiska arrayer kan använda samma layoutmekanism som statiska arrayer, men med lite extra minne tilldelat för expansion och tilläggsmekanismer för att ändra storlek och flytta innehållet i arrayen i minnet.

Dynamiska och heterogena arrayer kan också implementeras genom att använda fundamentalt olika metoder för att lagra värden i minnet, till exempel enkel- eller dubbellänkade listor. Sådana implementeringar kan vara mer flexibla, men kräver vanligtvis ytterligare omkostnader. Dessutom misslyckas de vanligtvis med att uppfylla kravet på konstant elementåtkomsttid.

Anteckningar

  1. ↑ Drot V. L., Novikov F. A. "Explanatory Dictionary of Modern Computer Vocabulary", Dimension of an array . Datum för åtkomst: 18 oktober 2012. Arkiverad från originalet den 3 juli 2013.
  2. ↑ 1 2 Barteniev, 2000 .
  3. ↑ 1 2 Magariu, 1983 .
  4. ↑ Wirth, 1989 , 1.6 Array.
  5. ↑ Michael McMillan. Datastrukturer och algoritmer med JavaScript  (engelska) . - O'Reilly Media , 2014. - S. 30-32. — ISBN 978-1-4493-7396-2 .

Litteratur

  • Wirth N. Algoritmer och datastrukturer = Algoritmer och datastruktur. — M .: Mir, 1989. — 360 sid. — ISBN 5-03-001045-9 .
  • Magariu N.A. Programmeringsspråk APL. - M . : "Radio och kommunikation", 1983. - 96 sid.
  • Barteniev O. V. Modern Fortran. - 3:e uppl., tillägg. och reviderade .. - M . : Dialog-MEPhI, 2000. - 449 sid.
 Data struktur
Listor
Träd
Räknar
Övrig
 Datatyper
Otolkbart
Numerisk
Text
Referens
Sammansatt
abstrakt
Övrig
Relaterade ämnen