Movatterモバイル変換

[0]ホーム
URL:

array

(data structure)

Definition:An assemblage of items that are randomly accessible by integers, the index.

Formal Definition: Ignoring size an array may be seen as anabstract data type with the operations new(), set(i, v, A), and get(i, A), where i is a numeric index, v is a value, and A is an array. The operations may be defined withaxiomatic semantics as follows.

  1. new() returns an array
  2. get(i, set(i, v, A)) = v
  3. get(i, set(j, v, A)) = get(i, A) if i ≠ j
Compare this with adictionary using integers as keys.

If the contents of a new array are set to some implicit initial value vi, we could add the following rule for get.

  1. get(i, new()) = vi

Typically arrays have a fixed size and use either0-based indexing or1-based indexing. Fixed initial size and 0-based indexing may incorporated as follows.

  1. new(s) returns an array, which has a size s
  2. size(new(s)) = s
  3. size(set(i, v, A)) = size(A)
  4. get(i, set(i, v, A)) = v if 0 ≤ i < size(A)
  5. get(i, set(j, v, A)) = get(i, A) if i ≠ j
One-based or other indexing may be defined similarly.

Specialization (... is a kind of me.)
dynamic array,sorted array.

Aggregate child (... is a part of or used in me.)
array index,1-based indexing,0-based indexing.

See alsoassociative array,matrix,huge sparse array.

Note:An unordered array must be searched with alinear search. Average search time may be improved using amove-to-front heuristic in some cases. Anexternal index, such as ahash table orinverted index may help make anarray search quicker and speed overall processing if the array is not changed often. If the array is kept sorted, abinary search orinterpolation search is faster.

Inserting into an array takesO(n) time. If that's too slow, use abalanced tree,skip list, or alinked list. Knuth uses a balanced tree with a RANK field that supportsΘ(log n) access by index andΘ(log n) insert and delete.[Knuth98, 3:471, Sect. 6.2.3]

If it takes too long to initialize a big array of size S, ahuge sparse array takes time proportional to the number of accesses and onlyΘ(S) extra space.

Author:PEB

Implementation

Sedgewick & Wayne'sintroduction and tutorial to arrays (Java). John Morris'Data Structures - Arrays(C). Bro. David Carlson'ssearch, access, complexity, etc. tutorial and code (C++). Hudak, Peterson, and Fasel's section onarrays (Haskell).Read and write different arrays (Fortran, C++).
Go to theDictionary of Algorithms and DataStructures home page.

If you have suggestions, corrections, or comments, please get in touchwithPaul Black.

Entry modified 16 November 2016.
HTML page formatted Wed Oct 30 12:15:30 2024.

Cite this as:
Paul E. Black, "array", inDictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 16 November 2016. (accessed TODAY)Available from:https://www.nist.gov/dads/HTML/array.html

[8]ページ先頭
©2009-2025 Movatter.jp