Rows and tables of storage.
Arrays are a convenient way of grouping a lot of variables under a single variable name. Arrays are like pigeon holes or chessboards, with each compartment or square acting as a storage place; they can be one dimensional, two dimensional or more dimensional! An array is defined using square brackets []. For example: an array of three integers called "triplet" would be declared like this: int triplet[3];
Notice that there is no space between the square bracket [ and the name of the array. This statement would cause space for three integers type variables to be created in memory next to each other as in the diagram below. ------------------------------------int triplet: ------------------------------------
The number in the square brackets of the declaration is referred to as the `index' (plural: indicies) or `subscript' of the array and it must be an integer number between 0 and (in this case) 2. The three integers are called elements of the array and they are referred to in a program by writing: triplet[0]triplet[1]triplet[2]
Note that the indicies start at zero and run up to one less than the number which is placed in the declaration (which is called the dimension of the array.) The reason for this will become clear later. Also notice that every element in an array is of the same type as every other. It is not (at this stage) possible to have arrays which contain many different data types. When arrays are declared inside a function, storage is allocated for them, but that storage space is not initialized: that is, the memory space contains garbage (random values). It is usually necessary, therefore, to initialize the array before the program truly begins, to prepare it for use. This usually means that all the elements in the array will be set to zero.
Why use arrays?:
Limits and The Dimension of an array:
Arrays and for loops:
Example 19:
Arrays Of More Than One Dimension:
Arrays and Nested Loops:
Example 20:
Output of Game of Life:
Initializing Arrays:
Arrays and Pointers:
Arrays as Parameters:
Questions 19:
Node:Why use arrays?, Next:Limits and The Dimension of an array, Previous:Arrays, Up:Arrays
Why use arrays?
Arrays are most useful when they have a large number of elements: that is, in cases where it would be completely impractical to have a different name for every storage space in the memory. It is then highly beneficial to move over to arrays for storing information for two reasons:
The storage spaces in arrays have indicies. These numbers can often be related to variables in a problem and so there is a logical connection to be made between an array an a program.
In C, arrays can be initialized very easily indeed. It is far easier to initialize an array than it is to initialize twenty or so variables.
The first of these reasons is probably the most important one, as far as C is concerned, since information can be stored in other ways with equally simple initialization facilities in C. One example of the use of an array might be in taking a census of the types of car passing on a road. By defining macros for the names of the different cars, they could easily be linked to the elements in an array. Type Array Element car 0auto 1bil 2
The array could then be used to store the number of cars of a given type which had driven past. e.g. /***********************************************//* *//* Census *//* *//***********************************************/ #include
This program, first of all, initializes the elements of the array to be zero. It then enters a loop which repeatedly fetches a number from the user and increases the value stored in the array element, labelled by that number, by 1. The effect is to count the cars as they go past. This program is actually not a very good program for two reasons in particular:
Firstly, it does not check that the number which the user typed is actually one of the elements of the array. (See the section below about this.)
The loop goes on for ever and the program never gives up the information which is stores. In short: it is not very useful.
Another example, which comes readily to mind, would be the use of a two dimensional array for storing the positions of chess pieces in a chess game. Two dimensional arrays have a chessboard-like structure already and they require two numbers (two indicies) to pinpoint a particular storage cell. This is just like the numbers on chess board, so there is an immediate and logical connection between an array and the problem of keeping track of the pieces on a chess board. Arrays play an important role in the handling of string variables. Strings are important enough to have a section of their own, See Strings.
Node:Limits and The Dimension of an array, Next:Arrays and for loops, Previous:Why use arrays?, Up:Arrays
Limits and The Dimension of an array
C does not do much hand holding. It is invariably up to the programmer to make sure that programs are free from errors. This is especially true with arrays. C does not complain if you try to write to elements of an array which do not exist! For example: char array[5];
is an array with 5 elements. If you wrote: array[7] = '*';
C would happily try to write the character * at the location which would have corresponded to the seventh element, had it been declared that way. Unfortunately this would probably be memory taken up by some other variable or perhaps even by the operating system. The result would be either:
The value in the incorrect memory location would be corrupted with unpredictable consequences.
The value would corrupt the memory and crash the program completely! On Unix systems this leads to a memory segmentation fault.
The second of these tends to be the result on operating systems with proper memory protection. Writing over the bounds of an array is a common source of error. Remember that the array limits run from zero to the size of the array minus one.
Node:Arrays and for loops, Next:Example 19, Previous:Limits and The Dimension of an array, Up:Arrays
Arrays and for loops
Arrays have a natural partner in programs: the for loop. The for loop provides a simple way of counting through the numbers of an index in a controlled way. Consider a one dimensional array called array. A for loop can be used to initialize the array, so that all its elements contain zero: #define SIZE 10; main () { int i, array[SIZE]; for (i = 0; i < SIZE; i++) { array[i] = 0; }}
It could equally well be used to fill the array with different values. Consider: #define SIZE 10; main () { int i, array[size]; for (i = 0; i < size; i++) { array[i] = i; }}
This fills each successive space with the number of its index: index 0 1 2 3 4 5 6 7 8 9 ---------------------------------------element 0 1 2 3 4 5 6 7 8 9 contents ---------------------------------------
The for loop can be used to work on an array sequentially at any time during a program, not only when it is being initialized. The example listing below shows an example of how this might work for a one dimensional array, called an Eratosthenes sieve. This sieve is an array which is used for weeding out prime numbers, that is: numbers which cannot be divided by any number except 1 without leaving a remainder or a fraction. It works by filling an array with numbers from 0 to some maximum value in the same way that was shown above and then by going through the numbers in turn and deleting (setting equal to zero) every multiple of every number from the array. This eliminates all the numbers which could be divided by something exactly and leaves only the prime numbers at the end. Try to follow the listing below.
Node:Example 19, Next:Arrays Of More Than One Dimension, Previous:Arrays and for loops, Up:Arrays
Example Listing/******************************************************//* *//* Prime Number Sieve *//* *//******************************************************/ #include
Node:Arrays Of More Than One Dimension, Next:Arrays and Nested Loops, Previous:Example 19, Up:Arrays
Arrays Of More Than One Dimension
There is no limit, in principle, to the number of indicies which an array can have. (Though there is a limit to the amount of memory available for their storage.) An array of two dimensions could be declared as follows: float numbers[SIZE][SIZE];
SIZE is some constant. (The sizes of the two dimensions do not have to be the same.) This is called a two dimensional array because it has two indicies, or two labels in square brackets. It has (SIZE * SIZE) or size-squared elements in it, which form an imaginary grid, like a chess board, in which every square is a variable or storage area. ------------------------------------ 0 1 2 3 4 5 6 7 8 ... (up to SIZE)------------------------------------ 1 ------------------------------------ 2 ------------------------------------ 3 ------------------------------------ 4 ------------------------------------ 5 ------------------------------------ 6 ------------------------------------ 7 ------------------------------------ . .(up to SIZE)
Every element in this grid needs two indicies to pin-point it. The elements are accessed by giving the coordinates of the element in the grid. For instance to set the element 2,3 to the value 12, one would write: array[2][3] = 12;
The usual terminology for the two indicies is that the first gives the row number in the grid and that the second gives the column number in the grid. (Rows go along, columns hold up the ceiling.) An array cannot be stored in the memory as a grid: computer memory is a one dimensional thing. Arrays are therefore stored in rows. The following array: ------------ 1 2 3 ------------ 4 5 6 ------------ 7 8 9 ------------
would be stored: ------------------------------------ 1 2 3 4 5 6 7 8 9 ------------------------------------* ROW # 1 * ROW # 2 * ROW #3 *
Another way of saying that arrays are stored row-wise is to say that the second index varies fastest, because a two-dimensional array is always thought of as... array[row][column]
so for every row stored, there will be lots of columns inside that row. That means the column index goes from 0..SIZE inside every row, so it is changing faster as the line of storage is followed.
A three dimensional array, like a cube or a cuboid, could also be defined in the same kind of way: double cube[SIZE][SIZE][SIZE];
or with different limits on each dimension: short notcubic[2][6][8];
Three dimensional arrays are stored according to the same pattern as two dimensional arrays. They are kept in computer memory as a linear sequence of variable stores and the last index is always the one which varies fastest.
Node:Arrays and Nested Loops, Next:Example 20, Previous:Arrays Of More Than One Dimension, Up:Arrays
Arrays and Nested Loops
Arrays of more than one dimension are usually handled by nested for loops. A two dimensional array might be initialized in the following way: main () { int i,j; float array[SIZE1][SIZE2]; for (i = 0; i < SIZE1; i++) { for (j = 0; j < SIZE2; j++) { array[i][j] = 0; } }}
In three dimensions, three nested loops would be needed: main () { int i,j,k; float array[SIZE1][SIZE2][SIZE3]; for (i = 0; i < SIZE1; i++) { for (j = 0; j < SIZE2; j++) { for (k = 0; k < SIZE3; k++) { array[i][j][k] = 0; } } }}
An example program helps to show how this happens in practice. The example below demonstrates the so-called "Game of Life". The aim is to mimic something like cell reproduction by applying some rigid rules to a pattern of dots . and stars *. A dot is a place where there is no life (as we know it!) and a star is a place in which there is a living thing. The rules will be clear from the listing. Things to notice are the way the program traverses the arrays and the way in which it checks that it is not overstepping the boundaries of the arrays.
Node:Example 20, Next:Output of Game of Life, Previous:Arrays and Nested Loops, Up:Arrays
Example Listing/*********************************************************//* *//* Game of Life *//* *//*********************************************************/ /* Based upon an article from Scientific American */ /* in 1970. Simulates the reproduction of cells */ /* which depend on one another. The rules are */ /* that cells will only survive if they have a */ /* certain number of neighbours to support them */ /* but not too many, or there won't be enough */ /* food! */ #include
Node:Output of Game of Life, Next:Initializing Arrays, Previous:Example 20, Up:Arrays
Output of Game of Life Game of Life Enter starting setup. Type '.' for empty and any other character for occupied. RETURN after each line. Array SIZE guide: ^^^^^^^^^^^^^^^^^^^^ (user types in: (It doesn't matter if the input .................... spills over the SIZE guide, .................... because "skipgarb()" discards it.) ..................... ..................... ..................... ..........***........ ...........*......... ...................... ..................... ..................... ..................... ********************* ..................... ...................... .................... ..................... ...................... ...................... ...................... ...................... ) Input is complete. Press RETURN. Generation 1 .................... .................... .................... .................... ...........*........ ..........***....... ..........***....... .................... .................... .................... .******************. .******************. .******************. .................... .................... .................... .................... .................... .................... .................... Q for quit. RETURN to continue. Generation 2 .................... .................... .................... .................... ..........***....... .................... ..........*.*....... ...........*........ .................... ..****************.. .*................*. *..................* .*................*. ..****************.. .................... .................... .................... .................... .................... .................... Q for quit. RETURN to continue. Generation 3 .................... .................... .................... ...........*........ ...........*........ ..........*.*....... ...........*........ ...........*........ ...*******...****... ..****************.. .******************. **................** .******************. ..****************.. ...**************... .................... .................... .................... .................... .................... Q for quit. RETURN to continue. Generation 4 .................... .................... .................... .................... ..........***....... ..........*.*....... ..........***....... ....*****.*.*.**.... ..*..............*.. .*................*. *..................* *..................* *..................* .*................*. ..*..............*.. ....************.... .................... .................... .................... .................... Q for quit. RETURN to continue.
etc... Try experimenting with different starting patterns.
Node:Initializing Arrays, Next:Arrays and Pointers, Previous:Output of Game of Life, Up:Arrays
Initializing Arrays
Arrays can be initialized in two ways. The first way is by assigning every element to some value with a statement like: array[2] = 42;array[3] = 12;
or perhaps with the aid of one or more for loops. Because it is tedious, to say the least, not to mention uneconomical, to initialize the values of each element to as different value, C provides another method, which employs a single assignment operator = and curly braces { }. This method only works for static variables and external variables.
Recall that arrays are stored row-wise or with the last index varying fastest. A 3 by 3 array could be initialized in the following way: static int array[3][3] = { {10,23,42}, {1,654,0}, {40652,22,0}};
The internal braces are unnecessary, but help to distinguish the rows from the columns. The same thing could be written: int array[3][3] = {10,23,42,1,654,040652,22,0};
Take care to include the semicolon at the end of the curly brace which closes the assignment.
Note that, if there are not enough elements in the curly braces to account for every single element in an array, the remaining elements will be filled out with zeros. Static variables are always guaranteed to be initialized to zero anyway, whereas auto or local variables are guaranteed to be garbage: this is because static storage is created by the compiler in the body of a program, whereas auto or local storage is created at run time.
Node:Arrays and Pointers, Next:Arrays as Parameters, Previous:Initializing Arrays, Up:Arrays
Arrays and Pointers
The information about how arrays are stored was not included just for interest. There is another way of looking at arrays which follows the BCPL idea of an array as simply a block of memory. An array can be accessed with pointers as well as with [] square brackets.
The name of an array variable, standing alone, is actually a pointer to the first element in the array.
For example: if an array is declared float numbers[34];
then numbers is a pointer to the first floating point number in the array; numbers is a pointer in its own right. (In this case it is type `pointer to float'.) So the first element of the array could be accessed by writing: numbers[0] = 22.3;
or by writing *numbers = 22.3;
For character arrays, which are dealt with in some depth in chapter 20, this gives an alternative way of getting at the elements in the array. char arrayname[5];char *ptr; for (ptr = arrayname; ptr <= arrayname+4; ptr++) { *ptr = 0; }
The code above sets the array arrayname to zero. This method of getting at array data is not recommended by this author except in very simple computer environments. If a program is running on a normal microcomputer, then there should be few problems with this alternative method of handling arrays. On the hand, if the microcomputer is multi-tasking, or the program is running on a larger system which has a limited manager, then memory ceases to be something which can be thought of as a sequence of boxes standing next to one another. A multi-tasking system shares memory with other programs and it takes what it can find, where it can find it. The upshot of this is that it is not possible to guarantee that arrays will be stored in one simple string of memory locations: it might be scattered around in different places. So ptr = arrayname + 5;
might not be a pointer to the fifth character in a character array. This could be found instead using the & operator. A pointer to the fifth element can be reliably found with: ptr = &(arrayname[5]);
Be warned!
Node:Arrays as Parameters, Next:Questions 19, Previous:Arrays and Pointers, Up:Arrays
Arrays as Parameters
What happens if we want to pass an array as a parameter? Does the program copy the entire array into local storage? The answer is no because it would be a waste of time and memory. Arrays can be passed as parameters, but only as variable ones. This is a simple matter, because the name of the array is a pointer to the array. The Game of Life program above does this. Notice from that program how the declarations for the parameters are made. main () {char array[23]; function (array); .....} function (arrayformal) char arrayformal[23]; {}
Any function which writes to the array, passed as a parameter, will affect the original copy. Array parameters are always variable parameters
Node:Questions 19, Previous:Arrays as Parameters, Up:Arrays
Questions
Given any array, how would you find a pointer to the start of it?
How do you pass an array as a parameter? When the parameter is received by a function does C allocate space for a local variable and copy the whole array to the new location?
Write a statement which declares an array of type double which measures 4 by 5. What numbers can be written in the indicies of the array?
0 comments: on " "
Post a Comment