- The student problem.
- Let's write a program to deal with students.
- There's about 3,000 students at dear old MU.
- Even with 1,000 bytes per student record, I can load them all into my
program.
- But, how do I store them in my program?
- Using variables.
- There's a problem with variables - you have to name them.
- Give me three variables.
i, j, and k.
- Give me 10,000 variables.
- They take up a lot of space in your program.
- Declarations and use.
- Program text is static; manipulations are cumbersome.
- How can we deal with this?
- We want easy and compact names with simple and efficient access.
- Numbers As Names
- What about
student0000, student0001, student0002, ...
- That solves the name generating problem, but nothing else.
- If we could use numbers as names, we'd be done.
- Numbers are simple.
- There are lots of them.
- They have useful relations between them.
- First, last, next previous, ...
- Assign a number to each datum.
- The first is 0, the last is n - 1.
- The next one is i + 1, the previous one is i - 1.
- Implementing number names.
- How should we store data named by numbers?
- Now do we translate the names?
- Suppose I want students and cars?
-
0 maps to a student or a car, not both.
- Identify the data with its first address.
- Arrays
- An array maps numbers to data.
- Numbers are easy and fun to manipulate.
- And then map the number to a datum.
- Arbitrary array access is optimal (constant time).
- Terms.
- An array: elements, the array type, the element type.
- An index: the upper and lower bounds, the range.
- Array Problems
- Once fixed, the array size can't change.
- This depends on the language.
- Without care, size-changable arrays can be expensive to use.
- Static space and dynamic data is almost always a bad match.
- There are usually more numbers than data.
- An invalid index maps to no data.
- Invalid indices may lead to runtime errors (java, C#) or no errors at
all (C++, C).
- Multidimensional arrays.
- What was the type of
Di?
- We only assumed that
sizeof(Di) > 0.
- What happens when
Di is an array?
-
M[i] is an array, and M[i][j] is an element.
- This is known as a
matrix.
- The nesting degree is the
array dimension.
- An array has one dimension, a matrix has two dimensions.
- The terminology is confusing though; arrays, vectors, matrices.
- Following standard matrix notation, a matrix is stored row-by-row.
- They can also be stored column-by-column, however, as FORTRAN does.
- And so on and so forth to higher dimensions.
- As a practical matter, dimensions higher than two are either
non-existent or small overall.
- Alternative matrix implementations.
- Storing matrices row-by-row (or column-by-column) works well, but
- It can waste a lot of space.
- Every row (or column) has to be the same size.
- Can we do better?
- An array of pointers to arrays is a good alternative.
- Hence the difference between
T * a[] and T a[][] in C++.
- Specialty arrays.
- Some languages (or language implementations) provide special versions
of arrays for particular data types.
- These special versions may be optimized for space and speed, or
provide literals.
- Character arrays and bit vectors.
This page last modified on 11 September 2003.