C-style Arrays

A data structure is the way data is stored in the machine and the functions used to access that data. An easy way to think of a data structure is a collection of related data items. An array is a data structure that is a collection of variables of one type that are accessed through a common name. A specific element is accessed by an index.

Array Data Structure

• A C-style array is aggregate data type.
• It can hold multiple values of a single type.
• Elements are referenced by the array name and an ordinal index.
• Each element is a value, index pair, the what, where duo.
• Indexing begins at zero.
• The array forms a contiguous list in memory.
• The name of the array holds the address of the first array element.
• We specify the array size at compile time, often with a named constant.

Example

const int SIZE = 10; double gpa[SIZE]; // holds up to SIZE gpas int i; // index into array cout << "Enter " << SIZE << " gpas: "; for(i = 0; i < SIZE; i++) cin >> gpa[i]; gpa[4] = 3.7;

Assume the input is 4.0 for everyone. Below is a pictorial representation of what gpa would look like.

     gpa:      0       1       2       3       4       5       6      7        8      9 



  
4.0 
  
4.0 
  
4.0 
  
4.0 
  
 3.7 
  
4.0 
  
4.0 
  
4.0 
  
4.0 
  
4.0 

Notes:  

• gpa is the identifier name.
• The 3.7 appears as the fifth element, in position five, at index four.
• The index value always starts at zero, not one.
• gpa[0] refers to the first element in the array.
• gpa[9] refers to the last element.
• Likewise, gpa[SIZE - 1] refers to the last element.
• gpa[10] is illegal.

How to Declare Arrays

Syntax: type identifier[number_of_elements]; Examples: char name[SIZE]; // SIZE is a global constant char st_addr[31]; char city_addr[26]; int list[100]; double cost[N]; // N is a global constant

Array indexes are always ordinals, such as integers, characters, enumerated types, etc.
The values stored in the array may be any simple type, such as a character, a numeric value, an address (later), etc.
Examples:

const int N = 50; int A[N]; // assume initialization // assign 7 to the first element and -25 to the last element in array A A[0] = 7; A[N-1] = -25; // better than A[49] = -25; // print out the 4th through 9th elements, position 3 through position 8 for(i = 3; i < 9; i++) cout << A[i] << " "; cout << endl; // read in array elements with odd indexes for(i = 1; i < N; i += 2) cin >> A[i]; // print out all positive values one per line: for(i = 0; i < N; i++) if(A[i] > 0) cout << A[i] << endl; // print out the position of all positive values one per line: for(i = 0; i < N; i++) if(A[i] > 0) cout << i << endl; // print out values between positions low and high, inclusive cin >> low >> high; for(i = low; i <= high; i++) cout << A[i] << endl;

Initializing Arrays

Method 1: Assign values at compile time.

const int N = 5; const int SIZE = 4; const int LIMIT = 31; int code[N] = {17, 46, -4, 30, 56}; const char vowel[N] = {'a', 'e', 'i', 'o', 'u'}; double cost[N-2] = {3.68, 42.0, -4.1}; int A[SIZE] = {7, -9}; // A[2] and A[3] are set to 0 int counts[100] = {0}; // initialize 100 integers to 0 double average[12] = {0.0}; // initialize 12 doubles to 0.0

Note: Initialization always begins with the first element and proceeds in order unless you specify an index.

Visually, the first four would look like this:

    code:      0      1      2      3     4   



  
17 
  
46 
  
-4 
  
30 
  
 56 

   vowel:      0     1    2     3    4   



  
a 
  
e 
  
i 
  
o 
  
 u 

    cost:       0        1       2    



  
3.68 
  
42.0 
  
-4.1 

       A:     0     1     2     3 



  
7 
  
9 
  
0 
  
0 

Method 2: Read values from input; beware of array boundaries.

const int SIZE = 4; int A[SIZE]; // indexed from zero through SIZE -1 for(i = 0; i < SIZE; i++) cin >> A[i];

Method 3: Assign a value to an element; beware of array boundaries.

if (6 < SIZE) A[6] = 43; // check: 6 < array size if (i < SIZE) A[SIZE-1] = A[i]; // check: i < SIZE if (x < SIZE) A[x] = x; // check: x < array size if (y + z < SIZE) A[y + z] = k; // check: 0 <= y + z < SIZE if (i < SIZE && A[i] < SIZE) // check: 0 <= i < array size A[A[i]] = -100; A[SIZE - 1] = function(); // assign returned value to the last element of A[]

---

Common Problem

1. Declare array to be maximum size needed, N.
2. Read data into array and count number of data items read. Stop when either a sentinel value is read or when you have read N items or until EOF.
3. Process the array (perform some computations, search for a target item, print the array, etc.) with indexes 0 through count-1.

      Take a look at the following possible solution:

#include<iostream> using namespace std; // global constants const int N = 100; const int SENTINEL = -99999; int main() { int count, // count of items actually read A[N], // make N large enough to meet the user's needs holder; // data holder to avoid storing the sentinel in A count = 0; // nothing read yet cin >> holder; // prime read // read data and count items while(count < N && holder != SENTINEL) { A[count] = holder; count++; cin >> holder; } return 0; }



• What constitutes an empty data set?
  
• What happens if the data set is empty?
  
• What if there are N + 1 or more data items?
  
• With input of   23  -2  19  -99999, what are the final values in A and count?
  
• If we had the loop header   while(A[count] != SENTINEL && count < N)   what error could occur?

________________________________________

// Rewrite with a for loop. cin >> holder; for(count = 0; count < N && holder != SENTINEL; count++) { A[count] = holder; cin >> holder; }

Input stream: 7 9 -99999 7 3 8 4 Final Values: count: A:

________________________________________

Example

// Number the elements of A, print one element per line for(i = 0; i < count; i++) cout << i + 1 << ". " << A[i] << endl;

Output if count is greater than 0: 1. <value of A[0]> 2. <value of A[1]> 3. <value of A[2]> . . . <count>. <value of A[count-1]>

But what if count holds 0?
________________________________________

Exercise
Parallel arrays are two or more arrays with the same number of elements used for storing related information about a collection of data objects.
Create 3 arrays, read data into the first 2, then store the element-wise differences between the 1st two arrays into the third array. (This is called vector subtraction.) Print the three arrays.

• Do we need more information?
• Yes! What size do we make the arrays? What type is the data?
• Try this at home. Use three parallel double arrays of size 10.

_________________________________________

Problem Read in test scores for N students and print out a horizontal histogram of the form.

100: ***         // 3 grades of 100
 99: *****       // 5 grades of 99
 98:             // 0 grades of 98
 97:             // 0 grades of 97
 96:             // 0 grades of 96
 95: *******     // 7 grades of 95
              . . .   

We will use each test score as an index into our array. With the display above, the array would hold:

               0   ...    95    96    97    98   99   100 



  
?
  
?
  
7
  
0
  
 0
  
0
  
5
  
3

Algorithm

1. Declare histo[101] -- an array of counters. Why 101?
2. Initialize counters in histo to zero.
3. Loop N times, one time for each test score.
   1. Read score.
   2. Increment histo[score] to count the score just read.
4. Print histogram
   1. Print 100: followed by the number of asterisks indicated by the value in histo[100]
   2. Repeat for 99, 98, 97, . . .
      
      

#include<iostream> #include<iomanip> using namespace std; const int N = 85; // number of tests const int N_scores = 101; // number of possible scores on test, 0 - 100 int main() { int histo[N_scores] = {0}; // array of score counters, set to zero int score, // holds individual test score i, j; // loop control variables (lcv) // input N scores, create histogram for(i = 1; i <= N; i++) { cin >> score; histo[score]++; // increment count of particular score } // Print histogram for(i = 100; i >= 0; i--) { cout << endl << setw(3) << i << ": "; for(j = 1; j <= histo[i]; j++) cout << "*"; } cout << endl; // flush output buffer return 0; }

Study this example. It encompasses many examples of (value, index) usage. Now let's refine this display.

Extend the previous problem
Add code to print out the number of A's, B's, C's, D's, and F's.

int count; // number of scores per letter grade // Print number of A's count = 0; for(i = 90; i <= 100; i++) count += histo[i]; cout << "Grades of A: " << count << endl; // Print number of B's count=0; // reset count for(i = 80; i <= 89; i++) count += histo[i]; cout << "Grades of B: " << count << endl; // Repeat for C's, D's and F's.

Question: We repeat almost the same code five times. Is there a better way?   What about a function?

Passing arrays to functions

Let's look at:

1. Passing an individual array element to a function.
2. Passing the entire array to a function.

1. Individual elements are treated as simple variables of that type and are passed to functions "by value." Both function call below have four integer arguments.

sum(w, x, y, z); sum(A[i], B[4], x, 6); A[i], B[4], x, and 6 are all integers.

2. While entire arrays are passed by value, it simulates "pass by reference" from other languages. This means that a function may modify the values in the original array. This is because the name of the array is the address in memory of the first element of the array. In other words, the array name holds the address of, or points to array[0].

// Prototype int readScores(int []); // Possible calls to function readScores num_scores1 = readScores(test1_Histo); num_scores1 = readScores(test2_Histo); // function header for function readScores int readScores(int histo[])

_________________________________________

Let's return to printing the histogram.

// Prototype -- print_count void print_count(int[], int lower, int upper, char); // Call 5 times from main program: print_count(histo, 90, 100, 'A'); print_count(histo, 80, 89, 'B'); print_count(histo, 70, 79, 'C'); print_count(histo, 60, 69, 'D'); print_count(histo, 0, 59, 'F'); // Function Definition void print_count(int histo[], int low, int high, char grade) { int i, count; count = 0; for(i = low; i <= high; i++) count += histo[i]; cout << "Grades of " << grade << ": " << count << endl; }

How would you modify the code to display course letter grades where the scores are floating point averages? Is 89.9 an A or a B?
_________________________________________

Linear Search Revisited
Search for a target in A. Return the index of the first hit if found; otherwise, return -1.

int linear_search(int A[], int target) { int index; // index of found item for(index = 0; index < N; index++) if (A[index] == target) return index; return -1; }

The function call might look like this:

if (linear_search(A, x) != -1)   cout << "Found!\n";

Try this at home: Rewrite the function with a single exit point.
________________________________________

General form of linear search:

for(index = 0; index < N; index++) // N is a global constant <body of loop>

The loop body can search for the first instance of a target, the last one in the array, count the number of occurrences, find the range of values, etc. In each case, what should the function return? What other applications can you see for the linear search?
_________________________________________

Practice Problems for integer arrays of size N
1. Write an efficient function that takes two initialized arrays and returns true if they are identical, false otherwise.
2. Write an efficient function that finds the largest and smallest elements in an array and returns their sum.
3. Write an efficient function that counts the number of negative numbers in an array.

---

---