7. Data Structures: Arrays
Data Structures
• A data structure is a means of organising many data items into an aggregate, so that we can:
– operate on the aggregate as a whole
– gain access to individual data items within the aggregate
– arrays, stacks, lists, trees, graphs, and many more…
• A variable which just holds a single value (a number, or a character) is sometimes called a simple variable or a scalar variable.
• Simplest structure is an array.
– arrays may have one, two or more dimensions
– simplest array is one-dimensional, a vector.
– we will only consider vector arrays in this course.
Systems and Networks 7. Arrays 2
Arrays
• An array is a collection of data where
– Every element has same type (e.g. integer)
– Elements don’t have individual names, but are accessed by indices
– An index is an integer from 0, 1, …, N-1 where N is the size of the array
• Examples: vectors, matrices, character strings, …
• The elements of the array do not have individual names
– There may be too many of them!
– At the time the program is written, may not know how many there will be.
• Instead, we can place the data in a sequence x0, x1, x2, …, xn and refer to an individual element by its index.
• Notation
– Mathematical xi
– Programming x[i]
Systems and Networks 7. Arrays 3
Representation of Arrays
• An array is held as a sequence of words in memory, with consecutive addresses.
• Suppose X is the name of the array. Then X is the label (address) of the location
that contains X[0], next location contains X[1], and so on. X is the base address.
• In the Sigma16 assembly language, arrays are established as follows
Example: suppose we have an integer x with value 2, an array Y = {11,-3,4,28}, and an integer z with unspecified value. These could be defined thus…
x DATA 2
Y DATA 11
DATA -3
DATA 4
DATA 28 z DATA 0
; the integer variable x
; this is y[0]
; here is y[1]
; and y[2]
; and y[3], last element ; the integer variable z
• To create an array in memory, need to allocate space for every element
– If there are 4 elements, you need four DATA statements even if no initial values.
– Only the first element gets a label (the name of the array)
– A real assembly language would allow us to allocate arrays of any size with one statement (assuming elements do not need to be individually initialised).
Systems and Networks 7. Arrays 4
Effective Addresses
• How does the CPU access X[i]?
– Value of label X is the address of X[0]
– Word that contains X[i] has address X+i.
• Recall: LOAD and STORE instructions specify memory address as label[Rn]
• The effective address (EA) is the value of label + Rn
• Lots of flexibility.
– X[R0] the EA is X (R0 contains 0). This mimics absolute addressing.
– 0[R4] the EA is the contents of R4. This mimics register indirect addressing.
– X[R3] the EA is X + R3. This is indexed addressing using its full potential.
• The last form is perfectly suited to access X[i] if R3 contains i
• Addresses are always unsigned numbers ranging from 0 to 65535. What if X+i > 65535?
– As the result has to be a 16-bit address, the overflow carry is discarded, whereupon X+i < X.
– E.g. if X is $000A and R3 contains $FFFE, then X[R3] evaluates to $0008;
– Any value in R3 bigger than 65525 ($FFF5) will produce a result < $000A
– Offsets that generate a result > 65535 behave as if they were negative but only when the sum X+i exceeds 65535.
• This is sometimes called address arithmetic and can support the use of negative values of i.
– Negative offsets are not needed to access arrays however and will not be considered further.
Systems and Networks 7. Arrays 5
• Consider the address X[R1] where X is the base address of the array and R1 contains value 3. Suppose X=$1000. Then X[R1] will access address $1003 which contains element X[3] of the array.
• If R1 contains value 4, X[R1] is $1004 which contains X[4]
X[R1]
X=$1000 X+1=$1001 $1002 $1003 $1004
Example
X[0]
X[1]
X[2]
X[3]
X[4]
X[5]
Systems and Networks
7. Arrays
6
Indexing and Effective Address
a = X[i]; Y[i] = X[i];
; a = X[i]
LOAD R1,i[R0]
LOAD R2,X[R1] STORE R2,a[R0]
; Y[i] = X[i]
LOAD R1,i[R0]
LOAD R2,X[R1] STORE R2,Y[R1]
; R1 = i
; R2 = X[i] ; a = X[i];
; R1 = i
; R2 = X[i] ; Y[i] = X[i]
Systems and Networks 7. Arrays 7
Unassessed Exercise Example 1: Array Sum. Given an array X[0], …, X[n-1], write an
assembly language program to compute the sum of the elements.
Test the program with a 5 element array as follows: {17, 2, 150, -3, 25}
Example 2: Array Max. Suppose an array X, of arbitrary size, contains a sequence of non-negative numbers in memory. The first negative number marks the end of the data (this representation is sometimes used for strings). Write a program to find the largest element and store it in a variable, max.
Test the program with a 5 element array as follows: {2, 42, 224, 19, 4, -1}
Systems and Networks Sigma16 Examples 8