You can define a variable called grades, which represents not a single value of a grade, but an entire set of grades. Each element of the set can then be referenced by means of a number called an index number or subscript. Whereas in mathematics a subscripted vari- able, xi, refers to the ith element x in a set, in C the equivalent notation is as follows:
x[i]
So the expression
grades[5]
(read as “grades sub 5”) refers to element number 5 in the array called grades. Array elements begin with the number zero, so
grades[0]
actually refers to the first element of the array. (For this reason, it is easier to think of it as referring to element number zero, rather than as referring to the first element.)
An individual array element can be used anywhere that a normal variable can be used. For example, you can assign an array value to another variable with a statement such as the following:
g = grades[50];
This statement takes the value contained in grades[50] and assigns it to g. More gener- ally, if i is declared to be an integer variable, the statement
g = grades[i];
takes the value contained in element number i of the grades array and assigns it to g.
So if i is equal to 7 when the preceding statement is executed, the value of grades[7] is assigned to g.
A value can be stored in an element of an array simply by specifying the array ele- ment on the left side of an equal sign. In the statement
grades[100] = 95;
the value 95 is stored in element number 100 of the grades array. The statement
grades[i] = g;
has the effect of storing the value of g in grades[i].
The capability to represent a collection of related data items by a single array enables you to develop concise and efficient programs. For example, you can easily sequence through the elements in the array by varying the value of a variable that is used as a sub- script in the array. So the for loop
for ( i = 0; i < 100; ++i )
sum += grades[i];
sequences through the first 100 elements of the array grades (elements 0 through 99) and adds the value of each grade into sum.When the for loop is finished, the variable sum then contains the total of the first 100 values of the grades array (assuming sum was set to zero before the loop was entered).
When working with arrays, remember that the first element of an array is indexed by zero, and the last element is indexed by the number of elements in the array minus one.
In addition to integer constants, integer-valued expressions can also be used inside the brackets to reference a particular element of an array. So if low and high are defined as integer variables, the statement
next_value = sorted_data[(low + high) / 2];
assigns the value indexed to the variable next_value by evaluating the expression (low+ high) / 2. If low is equal to 1 and high is equal to 9, the value of sorted_data[5] is assigned to next_value. In addition, if low is equal to 1 and high is equal to 10, the value of sorted_data[5] is also referenced because you know that an integer division of 11 by 2 gives the result of 5.
Just as with variables, arrays must also be declared before they are used. The declara- tion of an array involves declaring the type of element that will be contained in the array—such as int, float, or char—as well as the maximum number of elements that will be stored inside the array. (The C compiler needs this latter information to deter- mine how much of its memory space to reserve for the particular array.)
As an example, the declaration
int grades[100];
declares grades to be an array containing 100 integer elements.Valid references to this array can be made by using subscripts from 0 through 99. But be careful to use valid subscripts because C does not do any checking of array bounds for you. So a reference to element number 150 of array grades, as previously declared, does not necessarily cause an error but does most likely cause unwanted, if not unpredictable, program results.
To declare an array called averages that contains 200 floating-point elements, the declaration
float averages[200];
is used. This declaration causes enough space inside the computer’s memory to be reserved to contain 200 floating-point numbers. Similarly, the declaration
int values[10];
reserves enough space for an array called values that could hold up to 10 integer num- bers.You can better conceptualize this reserved storage space by referring to Figure 7.1.
The elements of arrays declared to be of type int, float, or char can be manipulated in the same fashion as ordinary variables.You can assign values to them, display their values, add to them, subtract from them, and so on. So, if the following statements appear in a program, the array values would contain the numbers as shown in Figure 7.2.
int values[10];
values[0] = 197; values[2] = -100; values[5] = 350;
values[3] = values[0] + values[5];
values[9] = values[5] / 10;
–values[2];
The first assignment statement has the effect of storing the value 197 in values[0]. In a similar fashion, the second and third assignment statements store –100 and 350 into values[2] and values[5], respectively. The next statement adds the contents of values[0] (which is 197) to the contents of values[5] (which is 350) and stores the result of 547 in values[3]. In the following program statement, 350—the value con- tained in values[5]—is divided by 10 and the result is stored in values[9]. The last statement decrements the contents of values[2], which has the effect of changing its value from –100 to –101.
The preceding program statements are incorporated into Program 7.1. The for loop sequences through each element of the array, displaying its value at the terminal in turn.
Program 7.1 Working with an Array
#include <stdio.h>
int main (void)
{
int values[10];
int index;
values[0] = 197;
values[2] = -100;
values[5] = 350;
values[3] = values[0] + values[5];
values[9] =
values[5] / 10;
–values[2];
for ( index = 0; index < 10; ++index )
printf (“values[%i] = %i\n”, index, values[index]);
return 0;
}
Program 7.1 Output
values[0] = 197
values[1] = 0
values[2] = -101
values[3] = 547
values[4] = 0
values[5] = 350
values[6] = 0
values[7] = 0
values[8] = 0
values[9] = 35
The variable index assumes the values 0 through 9 as the last valid subscript of an array is always one less than the number of elements (due to that zeroth element). Because you never assigned values to five of the elements in the array—elements 1, 4, and 6 through 8—the values that are displayed for them are meaningless. Even though the program’s output shows these values as zero, the value of any uninitialized variable or array element is not defined. For this reason, no assumption should ever be made as to the value of an uninitialized variable or array element.
1. Using Array Elements as Counters
It’s now time to consider a slightly more practical example. Suppose you took a tele- phone survey to discover how people felt about a particular television show and you asked each respondent to rate the show on a scale from 1 to 10, inclusive. After inter- viewing 5,000 people, you accumulated a list of 5,000 numbers. Now, you want to ana- lyze the results. One of the first pieces of data you want to gather is a table showing the distribution of the ratings. In other words, you want to know how many people rated the show a 1, how many rated it a 2, and so on up to 10.
Although not an impossible chore, it would be a bit tedious to go through each response and manually count the number of responses in each rating category. In addi- tion, if you have a response that could be answered in more than 10 ways (consider the task of categorizing the age of the respondent), this approach would be even more unreasonable. So, you want to develop a program to count the number of responses for each rating. The first impulse might be to set up 10 different counters, called perhaps rating_1 through rating_10, and then to increment the appropriate counter each time the corresponding rating was entered. But once again, if you are dealing with more than
10 possible choices, this approach could become a bit tedious. And besides, an approach that uses an array provides the vehicle for implementing a much cleaner solution, even in this case.
You can set up an array of counters called ratingCounters, for example, and then you can increment the corresponding counter as each response is entered. To conserve space in this book, Program 7.2 assumes you are dealing with only 20 responses. In addi- tion, it’s always good practice to first get a program working on a smaller test case before proceeding with the full set of data because problems that are discovered in the program are much easier to isolate and debug if the amount of test data is small.
Program 7.2 Demonstrating an Array of Counters
#include <stdio.h>
int main (void)
{
int ratingCounters[11], i, response;
for ( i = 1; i <= 10; ++i )
ratingCounters[i] = 0;
printf (“Enter your responses\n”);
for ( i = 1; i <= 20; ++i ) {
scanf (“%i”, &response);
if ( response < 1 || response > 10 )
printf (“Bad response: %i\n”, response);
else
++ratingCounters[response];
}
printf (“\n\nRating Number of Responses\n”);
printf (“—— ——————-\n”);
for ( i = 1; i <= 10; ++i )
printf (“%4i%14i\n”, i, ratingCounters[i]);
return 0;
}
Program 7.2 Output
Enter your responses
6
5
8
3
9
6
5
7
15
Program 7.2 Continued
Bad response: 15
5
5
1
7
4
10
5
5
6
8
9
The array ratingCounters is defined to contain 11 elements. A valid question you might ask is, “If there are only 10 possible responses to the survey, why is the array defined to contain 11 elements rather than 10?” The answer lies in the strategy for counting the responses in each particular rating category. Because each response can be a number from 1 to 10, the program keeps track of the responses for any one particular rating by simply incrementing the corresponding array element (after first checking to make certain that the user entered a valid response between 1 and 10). For example, if a rating of 5 is typed in, the value of ratingCounters[5] is incremented by one. By employing this technique, the total number of respondents who rated the TV show a 5 are contained in ratingCounters[5].
The reason for 11 elements versus 10 should now be clear. Because the highest rating number is a 10, you must set up your array to contain 11 elements to index ratingCounters[10], remembering that because of the zeroth element, the number of elements in an array is always one more than the highest index number. Because no response can have a value of zero, ratingCounters[0] is never used. In fact, in the for loops that initialize and display the contents of the array, note that the variable i starts at 1, and thereby bypasses the initialization and display of ratingCounters[0].
As a point of discussion, you could have developed your program to use an array con- taining precisely 10 elements. Then, when each response was keyed in by the user, you could have instead incremented ratingCounters[response – 1]. This way, ratingCounters[0] would have contained the number of respondents who rated the show a 1, ratingCounters[1] the number who rated the show a 2, and so on. This is a perfectly fine approach. The only reason it was not used is because storing the number of responses of value n inside ratingCounters[n] is a slightly more straightforward approach.
2. Generating Fibonacci Numbers
Study Program 7.3, which generates a table of the first 15 Fibonacci numbers, and try to predict its output. What relationship exists between each number in the table?
Program 7.3 Generating Fibonacci Numbers
// Program to generate the first 15 Fibonacci numbers
#include <stdio.h>
int main (void)
{
int Fibonacci[15], i;
Fibonacci[0] = 0; // by definition
Fibonacci[1] = 1; // ditto
for ( i = 2; i < 15; ++i )
Fibonacci[i] = Fibonacci[i-2] + Fibonacci[i-1];
for ( i = 0; i < 15; ++i )
printf (“%i\n”, Fibonacci[i]);
return 0;
}
Program 7.3 Output
0
1
1
2
3
5
8
13
21
Program 7.3 Continued
34
55
89
144
233
377
The first two Fibonacci numbers, called F0 and F1, are defined to be 0 and 1, respective- ly. Thereafter, each successive Fibonacci number Fi is defined to be the sum of the two preceding Fibonacci numbers Fi–2 and Fi–1. So F2 is calculated by adding together the values of F0 and F1. In the preceding program, this corresponds directly to calculating Fibonacci[2] by adding the values Fibonacci[0] and Fibonacci[1]. This calculation is performed inside the for loop, which calculates the values of F2 through F14 (or, equivalently, Fibonacci[2] through Fibonacci[14]).
Fibonacci numbers actually have many applications in the field of mathematics and in the study of computer algorithms. The sequence of Fibonacci numbers historically origi- nated from the “rabbits problem”: If you start with a pair of rabbits and assume that each pair of rabbits produces a new pair of rabbits each month, that each newly born pair of rabbits can produce offspring by the end of their second month, and that rabbits never die, how many pairs of rabbits will you have after the end of one year? The answer to this problem rests in the fact that at the end of the nth month, there will be a total of Fn+2 rabbits. Therefore, according to the table from Program 7.3, at the end of the twelfth month, you will have a total of 377 pairs of rabbits.
3. Using an Array to Generate Prime Numbers
Now, it’s time to return to the prime number program that you developed in Chapter 6, “Making Decisions,” and see how the use of an array can help you to develop a more efficient program. In Program 6.10A, the criteria that you used for determining if a number was prime was to divide the prime candidate by all successive integers from 2
up to the number –1. In exercise 7 in Chapter 6, you noted two inefficiencies with this approach that could easily be corrected. But even with these changes, the approach used is still not efficient. Although such questions of efficiency might not be important when dealing with a table of prime numbers up to 50, these questions do become important, for example, when you start thinking about generating a table of prime numbers up to 1,000,000.
An improved method for generating prime numbers involves the notion that a num- ber is prime if it is not evenly divisible by any other prime number. This stems from the fact that any nonprime integer can be expressed as a multiple of prime factors. (For example, 20 has the prime factors 2, 2, and 5.) You can use this added insight to develop a more efficient prime number program. The program can test if a given integer is prime by determining if it is evenly divisible by any other previously generated prime. By now the term “previously generated” should trigger in your mind the idea that an array must be involved here.You can use an array to store each prime number as it is generated.
As a further optimization of the prime number generator program, it can be readily demonstrated that any nonprime integer n must have as one of its factors an integer that is less than or equal to the square root of n. This means that it is only necessary to deter- mine if a given integer is prime by testing it for even divisibility against all prime factors up to the square root of the integer.
Program 7.4 incorporates the previous discussions into a program to generate all prime numbers up to 50.
Program 7.4 Revising the Program to Generate Prime Numbers, Version 2
#include <stdio.h>
#include <stdbool.h>
// Modified program to generate prime numbers int main (void)
{
int p, i, primes[50], primeIndex = 2;
bool isPrime;
primes[0] = 2;
primes[1] = 3;
for ( p = 5; p <= 50; p = p + 2 ) {
isPrime = true;
for ( i = 1; isPrime && p / primes[i] >= primes[i]; ++i )
if ( p % primes[i] == 0 )
isPrime = false;
if ( isPrime == true ) {
primes[primeIndex] = p;
++primeIndex;
}
}
for ( i = 0; i < primeIndex; ++i )
printf (“%i “, primes[i]);
printf (“\n”);
return 0;
}
Program 7.4 Output
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
The expression
p / primes[i] >= primes[i]
is used in the innermost for loop as a test to ensure that the value of p does not exceed the square root of primes[i].This test comes directly from the discussions in the previ- ous paragraph. (You might want to think about the math a bit.)
Program 7.4 starts by storing 2 and 3 as the first two primes in the array primes. This array has been defined to contain 50 elements, even though you obviously don’t need that many locations for storing the prime numbers. The variable primeIndex is initially set to 2, which is the next free slot in the primes array. A for loop is then set up to run through the odd integers from 5 to 50. After the Boolean variable isPrime is set to true, another for loop is entered. This loop successively divides the value of p by all of the previously generated prime numbers that are stored in the array primes. The index variable i starts at 1 because it is not necessary to test any values of p for divisibility by primes[0] (which is 2). This is true because our program does not even consider even numbers as possible primes. Inside the loop, a test is made to see if the value of p is evenly divisible by primes[i], and if it is, then isPrime is set false. The for loop con- tinues execution so long as the value of isPrime is true and the value of primes[i] does not exceed the square root of p.
After exiting the for loop, a test of the isPrime flag determines whether to store the value of p as the next prime number inside the primes array.
After all values of p have been tried, the program displays each prime number that has been stored inside the primes array. The value of the index variable i varies from 0 through primeIndex – 1 because primeIndex was always set pointing to the next free slot in the primes array.
Source: Kochan Stephen G. (2004), Programming in C: A Complete Introduction to the C Programming Language, Sams; Subsequent edition.