SME
Data Structures & Algorithms · Problem type
Address of an array element
Use this for “A two-dimensional array of 8-byte numbers starts at address 2000 and has 10 columns. Where is element (3, 4)?”
This is an example. Type your own values to start a new problem.
A
=
B
+
(
r
×
C
+
j
)
×
s
k
Elements before it
worked out (not typed)
Formulas
k
=
r
×
C
+
j
34 = 3 × 10 + 4
A
=
B
+
k
×
s
2,272 = 2,000 + 34 × 8
Assumptions
•
Row-major order: row 0 is stored first, then row 1, and so on, each row’s elements side by side.
•
Rows and columns are numbered from 0, so row r has r whole rows before it.
•
Addresses count bytes, and every element takes the same number of bytes.
Step-by-step
WE KNOW
B = 2,000, C = 10, r = 3, j = 4, s = 8
FIND
elements before it (k), element address (A)
Step 1 · Find elements before it (k)
Use k = r × C + j
The
r
full
rows
before
it
hold
r
×
C
elements,
and
j
more
come
before
it
in
its
own
row.
k
=
3
×
10
+
4
k
=
30
+
4
k
=
34
Step 2 · Find element address (A)
Use A = B + k × s
Each
element
before
it
takes
s
bytes,
so
it
starts
k
×
s
bytes
past
the
base.
A
=
2,000
+
34
×
8
A
=
2,000
+
272
A
=
2,272
Check
Put the numbers back in. Both sides should match.
34 = 3 × 10 + 4 ✓
2,272 = 2,000 + 34 × 8 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Lists, stacks and queues
Main lesson
Circular queue indices
Use this for “A circular queue has 8 slots, its front at slot 6 and 4 items. Where is the last item, and where does the next one go?”
Cost of a growing array
Use this for “An array starts with 1 slot and doubles when full. How many items are copied while 1000 are pushed?”
Evaluate a postfix expression
Use this for “Evaluate the postfix expression 3 4 + 2 × 7 − with a stack.”