Data Structures Flashcards
What do One-Dimensional Arrays store?
Store consecutive array elements of the same type in a contiguous block of memory
Block size formula
Block Size = Number of elements * Element Size
How do you get the Address of an element i?
The address for element i is:
Base address + (i * element size)
Where is an array allocated?
Like other local variables, an array is allocated in the function’s stack frame
How is memory used?
[Insert Diagram]
How are array elements accessed?
How can it be optimized?
What should be done if the index is a w register?
Using load and store instructions
[Insert Example]
How are individual array elements accessed in Multidimensional Arrays?
Using 2 or more indices
Most languages use row major order when storing arrays in RAM (First elements of row 0 then 1…)
The block size for an n-dimensional array is:
r = 1, n, pi(dim), x element size
where dim is the number of elements in dimension r
E.g. int ia[2][3][3]
Block size = (233)*4 = 72 bytes
The offset for a given element is?
[∑r = 1→ n - 1[index, x∏r+1 → n, dim] + index subscript n} x element size (where index is the index for the element in dimension r)
*NOT SURE
The offset for an element array[index1][index2][index3] is:
[[index1dim2dim3] + [index2*dim3] +index3] * element size
Structs contain _______ which may be of different types
Are deallocated in a ___________ of memory on the stack
Fields are accessed using ______
fields
single block
offsets
If base addresses are in x19, then the fields are accessed with?
[insert diagram]
What is a nested structure?
A structure that contains a field whose type is another structure
How are the field’s subfields accessed in Nested Structures?
Using a 2nd set of offsets
Check Notes for examples
.
