Along with strings, arrays are probably the most commonly used composite data. Yet most beginning programmers don't understand how arrays operate internally and their associated efficiency trade-offs. It's surprising how many novice (and even advanced!) programmers view arrays from a completely different perspective once they learn how to deal with arrays at the machine level.
Abstractly, an array is an aggregate data type whose members (elements) are all the same type. Selection of a member from the array is by an integer index.[62] Different indices select unique elements of the array. This text assumes that the integer indices are contiguous (though this is by no means required). That is, if the number x is a valid index into the array and y is also a valid index, with x < y, then all i such that x < i < y are valid indices.
Whenever you apply the indexing operator to an array, the result is the specific array element chosen by that index. For example, A[i] chooses the ith element from array A. Note that there is no formal requirement that element i be anywhere near element i+1 in memory. As long as A[i] always refers to the same memory location and A[i+1] always refers to its corresponding location (and the two are different), the definition of an array is satisfied.
In this text, we assume that array elements occupy contiguous locations in memory. An array with five elements will appear in memory as Figure 4-4 shows.
The base address of an array is the address of the first element on the array and always appears in the lowest memory location. The second array element directly follows the first in memory, the third element follows the second, and so on. Note that there is no requirement that the indices start at 0. They may start with any number as long as they are contiguous. However, for the purposes of discussion, this book will start all indexes at 0.
To access an element of an array, you need a function that translates an array index to the address of the indexed element. For a single-dimensional array, this function is very simple. It is:
Element_Address=Base_Address+ ((Index-Initial_Index) *Element_Size)
where Initial_Index is the value of the first index in the array (which you can ignore if 0) and the value Element_Size is the size, in bytes, of an individual array element.
[62] Or it could be some value whose underlying representation is integer, such as character, enumerated, and boolean types.