Tömb (adattípus)

A tömb egy olyan adatstruktúra , amely egy index által azonosított értékkészletet (tömbelemeket) tárol, vagy olyan indexek halmazát, amelyek egész (vagy konvertálható) értékeket vesznek fel egy adott folytonos tartományból. Az egydimenziós tömb egy absztrakt adattípus, egy vektor megvalósításaként fogható fel. Egyes programozási nyelvekben egy tömb táblának, sornak, vektornak, mátrixnak is nevezhető.

Egy tömb dimenziója azoknak az indexeknek a száma, amelyek egy elem egyedi megcímzéséhez szükségesek a tömbön belül [1] . A felhasznált indexek száma szerint a tömböket egydimenziósra, kétdimenziósra, háromdimenziósra stb.

A tömb alakja vagy szerkezete - információ a dimenziók számáról és a tömb méretéről (hosszáról) az egyes dimenziókhoz [2] ; egydimenziós tömbbel ábrázolható [3] .

A tömb, mint adatstruktúra jellemzője (ellentétben például a linkelt listával ) a tömbelemek indexen keresztüli elérésének állandó számítási bonyolultsága [4] . A tömb véletlen hozzáférésű adatstruktúrákra utal .

A legegyszerűbb esetben egy tömb minden dimenziójában állandó hosszúságú, és csak egy, a leírásban megadott típusú adatot tárolhat. Számos nyelv támogatja a dinamikus tömböket is, amelyek hossza változhat a program végrehajtása során, valamint a heterogén tömböket , amelyek különböző típusú adatokat tárolhatnak különböző elemekben. Néhány speciális tömbtípus, amelyet különféle nyelveken és megvalósításokban használnak: asszociatív tömb , szegmensfa , V-lista , párhuzamos tömb , ritka tömb .

A tömbök használatának fő előnye az elem címének egyszerű kiszámítása az index alapján (mivel a tömb elemei egymás után helyezkednek el), az összes elemhez azonos hozzáférési idő, az elemek kis mérete (ezek csak információs mezőből áll). A hátrányok közé tartozik, hogy statikus tömbök használatakor képtelenség eltávolítani vagy hozzáadni egy elemet a többi elem eltolása nélkül, dinamikus és heterogén tömbök használatakor pedig a dinamika és a heterogenitás fenntartása miatti lassabb teljesítmény. Ha C implementációval (mutatókkal) rendelkező tömbökkel dolgozik, további vezérlők nélkül, egy tipikus futási hiba a tömbtúlcsordulás és az adatsérülés veszélye.

Megvalósítási lehetőségek

A tömb elemek rendezett halmaza, amelyek mindegyike egyetlen értéket tárol, amelyet egy vagy több index azonosít. A legegyszerűbb esetben egy tömb állandó hosszúságú és azonos típusú adategységeket tárol, az egész számok pedig indexként működnek.

A felhasznált tömbindexek száma eltérő lehet: az egy indexű tömböket egydimenziósnak, a kettővel rendelkezőket kétdimenziósnak és így tovább. egydimenziós tömb - lazán megfelel egy vektornak a matematikában; kétdimenziós ("sor", "oszlop") - mátrix . Leggyakrabban az egy vagy két indexű tömböket használják; ritkábban - hárommal; még nagyobb számú index rendkívül ritka.

A tömb első elemének a programozási nyelvtől függően eltérő indexe lehet. A tömböknek három fő típusa van: nulla alapú ( nulla alapú ), egy alapú ( egy alapú ) és a programozó által megadott meghatározott érték alapján ( n alapú ). A nullától való számolás jellemzőbb az alacsony szintű programozási nyelvekre , bár magas szintű nyelvekben is megtalálható, például a C család szinte minden nyelvén használják. Számos nyelven ( Pascal , Ada , Modula-2 ) az indexek tartománya bármely adattípus tetszőleges értéktartományaként definiálható, amely egész számra önthető, azaz egész számok, szimbólumok, felsorolások, még logikai értékeket is (az utóbbi esetben egy tömbnek két eleme van, amelyeket "igaz" és "hamis" értékkel indexelnek).

Példa egy rögzített tömbre Pascalban {Egész számok egydimenziós tömbje. Elemek számozása 1-től 15-ig} a : tömb [ 1 .. 15 ] of Integer ; {Karakterek kétdimenziós tömbje. Oszlopszámozás byte típus szerint (0-tól 255-ig) sorok szerint 1-től 5-ig} multiArray : tömb [ Byte , 1 .. 5 ] of Char ; {Karakterláncok egydimenziós tömbje. Szószámozás (0-tól 65536-ig)} rangeArray : tömb [ Word ] of String ; Példa rögzített tömbre C-ben int Array [ 10 ]; // Egydimenziós tömb: egész számok, 10-es méret; // Elemek számozása — 0-tól 9-ig. double Array [ 12 ][ 15 ]; // Kétdimenziós tömb: // dupla pontosságú valós számok, // méret 12 x 15; // Számozás: sorok szerint - 0-tól 11-ig, // oszlopok szerint - 0-tól 14-ig.

Egyes programozási nyelvekben többdimenziós tömbök jönnek létre egydimenziós tömbök alapján, amelyekben az elemek tömbök [5] .

JavaScript 2D tömb példa //Kétdimenziós számtömb létrehozása: var array = [ [ 11 , 12 , 13 , 14 , 15 , 16 ], // Az első sor egy tömb [ 21 , 22 , 23 , 24 , 25 , 26 ] , // A második [ 31 , 32 , 33 , 34 , 35 , 36 ] // Harmadik ]; // Kimeneti tömb a konzolba: array . forEach (( subArray ) => { // Minden egyes altömbhöz subArray . forEach (( item ) => { // minden egyes eleméhez konzol . log ( item ); // kinyomtatja ezt az elemet a konzolra. } ); });

Az indextömbök támogatása (saját deklarációs szintaxisa, az elemekkel végzett munka függvényei stb.) a legtöbb magas szintű programozási nyelvben megtalálható . A maximálisan megengedett tömbdimenziót, az indexértékek típusait és tartományait, az elemtípusokra vonatkozó korlátozásokat a programozási nyelv vagy egy adott fordító határozza meg .

Azokban a programozási nyelvekben, amelyek lehetővé teszik a programozó számára, hogy deklarálja saját típusait , általában lehetséges "tömb" típus létrehozása. Egy ilyen típus definíciójában meg van adva az egyes indexek típusai és/vagy értéktartományai, valamint a tömbelemek típusa. A deklarált típus később változók, formális paraméterek és függvény visszatérési értékek meghatározására használható. Egyes nyelvek támogatják a tömbváltozók hozzárendelési műveleteit (amikor az egyik művelet egy tömb összes elemét egy másik tömb megfelelő elemeinek értékéhez rendeli).

Tömbtípus deklaráció Pascalban típus TArrayType = egész szám [ 0..9 ] tömbje ; _ _ (* A következő paraméterekkel rendelkező tömbök: 1. Méret - 10 cella; 2. A tárolásra alkalmas elemek típusa - - a [−32 768; 32 767] tartományba eső egész számok, - a "TArrayType" nevű operandustípus deklarálja *) var arr1 , arr2 , arr3 : TArrayType ; (* Három azonos típusú tömbváltozó deklarációja (a fenti "TArrayType"). *)

Az APL programozási nyelvben a tömb a fő adattípus (a nulldimenziós tömböt skalárnak, az egydimenziós tömböt vektornak, a kétdimenziós tömböt mátrixnak nevezzük) [3] . A tömb-hozzárendelésen kívül ez a nyelv támogatja a vektor- és mátrix-aritmetikai műveleteket, amelyek mindegyikét egy-egy paranccsal hajtják végre, a tömbök adateltolási műveleteit és a mátrixsorok rendezését.

Dinamikus tömbök

Dinamikusnak nevezzük azokat a tömböket, amelyek mérete a program végrehajtása során változhat. A közönséges (nem dinamikus) tömböket rögzítettnek vagy statikusnak is nevezik .

A dinamikus tömbök mind a programozási nyelv, mind a rendszerkönyvtárak szintjén megvalósíthatók. A második esetben a dinamikus tömb a szabványos könyvtár objektuma, és minden vele végzett művelet ugyanabban a könyvtárban valósul meg. Így vagy úgy, a dinamikus tömbök támogatása a következő funkciókat foglalja magában:

A dinamikus tömb leírása. Nyelvi szinten ez lehet egy speciális szintaktikai konstrukció, könyvtári szinten pedig egy olyan könyvtári adattípus, amelynek értékét szabványos módon deklaráljuk. Általános szabály, hogy egy dinamikus tömb leírásánál (létrehozásakor) a kezdeti mérete megadásra kerül, bár ez nem szükséges.
Egy dinamikus tömb aktuális méretének meghatározására szolgáló művelet.
A dinamikus tömb méretének megváltoztatásának művelete.

Példa struktúrákra a dinamikus tömbökkel való munkavégzéshez Delphiben :

var // Dinamikus tömbök leírása byteArray : Array of Byte ; // Egydimenziós tömb multiArray : Array of Array of string ; // Többdimenziós tömb ... SetLength ( byteArray , 1 ) ; // Állítsa be a tömb méretét 1 elemre. byteArray [ 0 ] := 16 ; // Íróelem. SetLength ( byteArray , Length ( byteArray ) + 1 ) ; // Tömb méretének növelése egy byteArray [ Length ( byteArray ) - 1 ] := 10 ; // Írja be az értéket az utolsó elemre. WriteLn ( byteArray [ Length ( byteArray ) - 1 ]) ; // A tömb utolsó elemének megjelenítése. ... SetLength ( multiArray , 20 , 30 ) ; // Kétdimenziós tömb méretének beállítása multiArray [ 10 , 15 ] := 12 ; // Érték írása SetLength ( multiArray , 10 , 15 ) ; // A WriteLn méretének csökkentése ( Length ( multiArray ) , ' ' , Length ( multiArray [ 0 ] )

Heterogén tömbök

Egy tömböt heterogénnek nevezünk, amelynek különböző elemeibe a különböző adattípusokhoz kapcsolódó értékek közvetlenül írhatók . A különböző típusú értékekre mutatókat tároló tömb nem heterogén, mivel a tömbben ténylegesen tárolt adatok egyetlen típushoz tartoznak - a „mutató” típushoz. A heterogén tömbök kényelmesek univerzális struktúraként tetszőleges típusú adatkészletek tárolására. A heterogenitás megvalósítása megköveteli a nyelvi fordító tömbtámogató mechanizmusának bonyolítását.

Munka a memóriával

A statikus homogén (azonos típusú adatokat tároló) tömb megvalósításának tipikus módja az, hogy egy folytonos memóriablokkot foglalunk le, amelynek térfogata , ahol egy elem mérete, és az indextartományok méretei (vagyis a a megfelelő index által felvehető értékek száma). Ha egy indexszel rendelkező tömbelemhez hozzáférünk, a megfelelő elem címét a rendszer a következőképpen számítja ki Az indexek sorrendje a címszámítási képletben eltérő lehet. (Ez a mód megfelel a legtöbb C fordító implementációjának ; Fortranban az indexek sorrendje fordított [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}}}\jobbra)\cdot m_{n-1}+i_{n{\text{p}}}\jobbra)$ $B$ $i_{k\mathrm {p} }$ $k$

Így egy adott indexkészlettel rendelkező elem címét úgy számítjuk ki, hogy a hozzáférési idő a tömb összes eleméhez elméletileg azonos legyen; azonban a RAM-tól a különböző memóriaelemeken elhelyezkedő cellákig a válaszkésleltetés különböző értékei befolyásolhatják, de a magas szintű programozás gyakorlatában az ilyen finomságokat ritka kivételekkel figyelmen kívül hagyják.

A heterogén tömbök megvalósításának szokásos módja az, hogy maguknak az elemeknek az értékét külön tároljuk, és ezekre az elemekre mutatókat helyezünk el a tömb memóriablokkjában (szabályos homogén tömbként szervezve, fentebb leírtuk). Mivel a bármilyen típusú értékekre mutató mutatók általában azonos méretűek, a címszámítás egyszerű maradhat, bár az elemértékek kiosztása és elérése további többletköltséggel jár.

A dinamikus tömbök ugyanazt az elrendezési mechanizmust használhatják, mint a statikus tömbök, de némi extra memóriával rendelkeznek a bővítéshez és a tömb tartalmának a memóriában lévő tartalmának átméretezéséhez és mozgatásához szükséges mechanizmusok hozzáadásához.

Ezenkívül a dinamikus és heterogén tömbök alapvetően eltérő módszerek segítségével valósíthatók meg az értékek memóriában való tárolására, például egyszeresen vagy kétszeresen összekapcsolt listákkal. Az ilyen megvalósítások rugalmasabbak lehetnek, de általában többletköltséget igényelnek. Ezenkívül általában nem teljesítik az állandó elemelérési idő követelményét.

Jegyzetek

↑ Drot V. L., Novikov F. A. "A modern számítógépes szókincs magyarázó szótára", Egy tömb mérete . Hozzáférés dátuma: 2012. október 18. Az eredetiből archiválva : 2013. július 3. (határozatlan)
↑ 1 2 Bartenyev, 2000 .
↑ 1 2 Magariu, 1983 .
↑ Wirth, 1989 , 1.6 Array.
↑ Michael McMillan. Adatstruktúrák és algoritmusok JavaScripttel (angol) . - O'Reilly Media , 2014. - P. 30-32. — ISBN 978-1-4493-7396-2 .

Irodalom

Wirth N. Algoritmusok és adatstruktúrák = Algoritms and data structure. — M .: Mir, 1989. — 360 p. — ISBN 5-03-001045-9 .
Magariu N.A. Programozási nyelv APL. - M . : "Rádió és kommunikáció", 1983. - 96 p.
Bartenyev O. V. Modern Fortran. - 3. kiadás, add. és átdolgozott .. - M . : Dialog-MEPhI, 2000. - 449 p.

Adatstruktúrák
Listák	sor egyenként linkelt lista duplán linkelt lista Pass list
fák	B-fa Bináris keresőfa AVL fa Vörös-fekete fa halom
Számít	Irányított grafikon Irányított aciklikus gráf Bináris döntési diagram Hipergráf
Egyéb	Hash táblázat Kazal

Adattípusok
Értelmezhetetlen	Bit Rágcsál Byte qubit Csemege Jellemvonás Szó
Numerikus	Egész fix pont lebegőpont Racionális Összetett Hosszú intervallum
Szöveg	Szimbolikus Húr
Referencia	Cím Link Mutató Csomagolás
Összetett	Algebrai adattípus ( általános ) Osztály Típus-termék ( Írj Tuple szerkezet ) Egy tárgy Konszolidáció ( címkézett ) Rendelt pár
absztrakt	sor Lista Fordulat Kazal Asszociatív tömb (megjelenítés, térkép ) Sok multiset típus Grafikon
Egyéb	Logikus Alsó Magasabb Polimorf Funkcionális felsorolható Gyűjtemény Kivétel nemzetség ( metaosztály ) Monád Szemafor Folyam üres
Kapcsolódó témák	Absztrakt adattípus primitív típus Adatstruktúra Generikus típusú változó Felület Konstruktor (OOP) Konstruktor (FP) Konstruktor típusa Típusöntés Prototípus Típusrendszer