7.txt

CS102/ECE 206 Lecture Notes: Chapter 7 /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_ o A C-style array is aggregate data type. o It can hold multiple values of a single type. o Elements are referenced by the array name and an /ordinal/ index. o Each element is a /value, index/ pair, the /what, where/ duo. o Indexing begins at zero. o The array forms a contiguous list in memory. o The name of the array holds the address of the first array element. o 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:*/ o *|gpa|* is the identifier name. o The 3.7 appears as the /fifth/ element, in position /five/, at index /four/. o The index value always starts at zero, not one. o *|gpa[0]|* refers to the first element in the array. o *|gpa[9]|* refers to the last element. o Likewise, *|gpa[SIZE - 1]|* refers to the last element. o *| 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 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; } * o What constitutes an empty data set? o What happens if the data set is empty? o What if there are N + 1 or more data items? o With input of *|23 -2 19 -99999|*, what are the final values in *|A|* and *|count|*? o 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. *||* 2. *||* 3. *||* . . . *|. |* * 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. o Do we need more information? o Yes! What size do we make the arrays? What type is the data? o _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 #include 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 * 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. ------------------------------------------------------------------------ ------------------------------------------------------------------------