ARRAYS - Penn State Brandywine Engineering阵列-宾州白兰地工程.doc

Chapter 7: ArraysThe variables used so far have all had a common characteristic: Each variable could only be used to store one value at a time. Frequently, we may have a set of values, all of the same data type, that form a logical group. A simple list containing individual items of the same scalar data type is called a one-dimensional array. In this chapter, we will study how one-dimensional arrays are declared, initialized, stored inside a computer, and used.7.1 One-Dimensional ArraysA one-dimensional array(or a list, or a vector) is a group of related values with the same data type that is stored using a group name. The group name is referred to as the array name. The items in the list can be declared as a single unit and stored under a common variable name called the array name. For example, suppose that we would like to store five exam grades in an array, named grade, the declaration statement will be:int grade5;Other examples:char code4; /an array of four character valuesfloat prices6;double amount100;Each element in an array is called an element or component of the array.The individual elements stored in the array are stored sequentially, with the first array element stored in the first reserved location, the second element stored in the second reserved location, and so on.To access individual elements in an array, you use the name of the array and the elements position. This position is called the elements subscript or index value.For a single-dimensioned array the first element has a subscript of 0. The indices of an array are said to be zero relative.For example:int grade5;grade0 refers to the first grade stored in the grade array.grade1 refers to the second grade stored in the grade array.grade0grade1grade2grade3grade4an integeran integeran integeran integeran integerelement 1element 2element 3element 4element 5Internally, the computer uses the index as an offset from the arrays starting position. The index tells the computer how many elements to skip over, starting from the beginning of the array, to get to the desired element.In-Class Exercise:1. Write array declarations for the following:a.a list of 100 floating-point voltagesb.a list of 30 characters, each representing a codec.a list of 100 integersUsing Subscripted VariablesSubscript variables can be used anywhere scalar variables are valid. For example:grade0 = 98;grade1 = grade0 - 11;The subscript contained within the brackets need not be an integer constant. Any expression that evaluates to an integer may be used as a subscript. For example:gradei grade2 * igradej - 1A for loop can be used to access the elements in an array.Example: Determine the maximum value in an arrayint prices 1000;:maximum = prices0;for (int i = 1; i maximum) maximum = prices i;In-Class Exercise:Write a for loop that can be used to display values for the complete array declared as:int grades 25;Input and Output of Array ValuesIndividual array elements can be assigned values interactively using cin object. For example:cin grade0;cin grade1 grade2 grade3;A for loop can also be used to cycle through the array for interactive data input. For example:for (int i = 0; i = 4; i+) cout gradei;Caution: C+ does not check the value of the index being used. For example, if an array has been declared as consisting of 10 elements, and you use an index of 12, C+ will not notify you of the error when the program is compiled. You will get a runtime error.During output, individual array elements can be displayed using the cout object. Again, a for loop can be used to display an array.for (int n = 5; n = 20; n+)cout n amountn;Example: Program 7-1#include int main( ) int grade5;for (int i = 0; i = 4; +i) / Enter five grades cout gradei;for (i = 0; i = 4; i+) / Print five gradescout ngrade i is gradei;cout endl;return 0; Sample Run:Enter a grade: 94Enter a grade: 95Enter a grade: 96Enter a grade: 97Enter a grade: 98grade0 is 94grade1 is 95grade2 is 96grade3 is 97grade4 is 98Example: Program 7-2#include int main( )int grade5, total = 0;for (int i = 0; i = 4; +i) / Enter five gradescout gradei;cout nThe total of the grades ;for (i = 0; i = 4; i+) / Print five gradescout gradei ;total = total + gradei;cout is total;return 0;In-Class Exercise:Write a program to input eight integer numbers into an array named temp. As each number is input, add the numbers into a total (accumulator). After all numbers are input, display the numbers and their average. 7.2 Array InitializationArray elements can be initialized within their declaration statements, enclosing their values within braces. For example:int grade5 = 95, 87, 92, 100, 80 ;If the number of initializers is less than the declared number of elements listed in square brackets, the initializers are applied starting with array element zero. For example:int grade5 = 98, 100, 80 ;will only initialize the first three elements.A unique feature of initializers is that the size of an array may be omitted when initializing values are included in the declaration statement. For example:int gallons = 16, 12, 10, 15, 19 ;char code 4 = a, b, c, d ;char code = a, b, c, d ;An Interesting Simplification:In C and C+, an array of characters can be used to store a string value. Another method of initializing a character array:char code = sample; / no braces or commasThis uses the string sample to initialize the char array, code. This creates an array named code with seven elements stored in it. (Why seven?) In-Class Exercise:Write a declaration to store the string “This is a test” into an array named strtest. Include the declaration in a program to display the message using the following loop:for (int i = 0; i NUMDISPLAY; i+)cout strtesti;where NUMDISPLAY is a named constant for the number 15.7.3 Arrays as Arguments to FunctionsIndividual array elements are passed to a called function in the same manner as individual scalar variables. For example:find_min(grades2, grades6);find_max(grades)Passing a copy of the whole array to the function would be wasteful of computer storage, especially for larger arrays. To avoid this, the called function is given direct access to the array. On the receiving side, the called function must be alerted that an array is being passed.Lets look at an example:Program 7-4: #include int find_max(int 5); / function prototypeint main( )int nums5 = 2, 18, 1, 27, 16; cout nThe maximum value is find_max(nums) endl;return 0;int find_max(int vals5) / find the maximum valueint i, max = vals0;for (i = 1; i 5; i+)if (max valsi) max = valsi; return max;The parameter declaration in find_max( ) header line actually contains extra information that is not required by the function. All that find_max( ) must know is that the parameter vals references an array of integers. Since the array has been created in main( ) and no additional storage space is needed in find_max( ), the declaration for vals can omit the size of the array. Thus, an alternative function header line is:int find_max(int vals )Note: When this array is being passed, only the address of the first element in the array is actually passed. You are passing a reference or pointer to the array. Once the function has the address of the first element, it calculates the location of the other elements based on the data type of the array.The more general form of the previous example follows:Program 7-5: #include int find_max(int , int); / function prototypeint main( )int nums5 = 2, 18, 1, 27, 16; cout nThe maximum value is find_max(nums, 5) endl;return 0; int find_max(int vals, int num_els) int i, max = vals0;for (i = 1; i num_els; i+)if (max valsi) max = valsi;return max;In-Class Exercise:Given the following function definition:#include bool sameArray(float a,/ IN: arrays to be compared float b, const int size)/ IN: size of the arraysint i = 0;/ Loop control variable/array subscriptwhile (i size 1) & (ai = bi)i+;return (ai = bi);Write a main( ) function that declares and initializes two float arrays, then uses the above function to determine if the arrays are equal or not.Reading Part of an ArraySometimes the programmer does not know what the exact size of a particular array will be, because it is unknown how many values the user needs to enter. For example, if you are writing a program to process grades, one class section may have 15 students and another may have 25 students. As a programmer, you need to allocate enough storage to handle the maximum number of scores so that the program can process the largest expected array without error.When you read the array data into memory, you should begin filling the array starting at element 0 and keep track of the number of data items that are actually being stored in the array. The portion of the array that contains actual data is called the filled subarray.In-Class Exercise:Given the following code:#include const int MAXSIZE = 14;/ Add function prototypes hereint main()int gradesMAXSIZE;int total;/ Accumulates the total gradesint numGrades;/ Counts the number of grades enteredfloat average;/ Use reference parameter here for total and numGradesreadGrades(grades, total, numGrades); displayGrades(grades);/ Add code to calculate and display the average.return (0);/ Define functions hereComplete the program so that it allows the user to enter the grades (use a sentinel to stop entry or stop at MAXSIZE), then display those grades, then calculates, and displays the average.7.4 Two-Dimensional ArraysA two-dimensional array, which is also referred to as a table, consists of both rows and columns of elements. For example:110-50849127-361This array corresponds to:int val3 4;Other examples:float prices 2 10;char code 4 100;Note: In order to identify an element in the array, you need to provide the row and column location of the element.For example:price = prices2 4;newval = 4 * (val1 3 - 1);8 51208-1Row 0Row 1Col. 1Col. 2Col. 0val 1 2NOTE: The row and column numbering starts from zero.Declaration and Processing As with single-dimensional arrays, two-dimensional arrays can be initialized from within their declaration statements. For example:int val 3 2 = 1, 0, 2 , 1, 5, 4 ;which is the same as:int val 3 2 = 1, 0, 2, 1, 5, 4 ;OR:int val 3 2 = 1, 0, 2, 1, 5, 4;Program 7-6: #include #include int main( )int i, j;int val34 = 8, 16, 9, 52, 3, 15, 27, 6, 14, 25, 2, 10;cout nDisplay of val array by explicit element: n setw(4) val00 setw(4) val01 setw(4) val02 setw(4) val03 n setw(4) val10 setw(4) val11 setw(4) val12 setw(4) val13 n setw(4) val20 setw(4) val21 setw(4) val22 setw(4) val23; cout nnDisplay of val array using a nested for loop:; for (i = 0; i 3; i+)cout n; / print a new line for each rowfor (j = 0; j 4; j+)cout setw(4) valij;return 0;Typically, for loops are used to process two-dimensional arrays. In the following program, the nested for loop is used to multiply each element in the val array by the scalar number 10 and display the resulting value.Program 7-7: #include #include int main ( )int i, j; int val 34 = 8, 16, 9, 52, 3, 15, 27, 6, 14, 25, 2, 10 ; / multiply each element by 10 and display it cout nnDisplay of multiplied elementsn; for (i = 0; i 3; i+) cout n; / start a new line for (j = 0; j 4; j+) val ij = val ij * 10;cout setw(5) val ij; / end of inner loop / end of outer loop return 0;In-Class Exercise:Write a C+ program that finds and displays the maximum value in a two-dimensional array of integers. The array should be declared as a 4 by 5 array of integers and initialized with the data: 16, 22, 99, 4, 18, -258, 4, 101, 5, 98, 105, 6, 15, 2, 45, 33, 88, 72, 16, 3As Function argumentsPassing two-dimensional arrays into functions is a process identical to passing single-dimensional arrays. The called function receives access to the entire array.Note: In the declaration, the row number can be omitted, but the column number must be included. For example:display (int 4 5) is the same as:display (int 5)Example: Program 7-8: #include #include void display (int 4); / function prototypeint main( )int val34 = 8, 16, 9, 52, 3, 15, 27, 6, 14, 25, 2, 10 ;display (val);return 0;void display (int nums 4)int row_num, col_num;for (row_num = 0; row_num 3; row_num+)cout n; / start a new linefor (col_num = 0; col_num 4; col_num+)cout setw(4) numsrow_numcol_num;Additional Examples:Array Declarations:int test 7 9;char code 26 10;and the following function calls:find_max(test);obtain (code);on the receiving side:int find_max (int nums 9)char obtain (char key 10)NOTE: If the array is a global one, there is no need to pass the array because the function could reference the array by its global name.Larger-Dimensional ArraysThis is done by listing the maximum size of all dimensions for the array. For example, the declarationint response 4106;declares a three-dimensional array. A three-dimensional array can be viewed as a book of data tables. The first subscript can be thought of as the page number of a selected table, the second subscript value as the desired row and the third subscript as the desired column. Similarly, a four dimensional array can be represented as a shelf of books, where the first dimension is used to declare a desired book on the self, and a five-dimensional array can be viewed as a bookcase filled with books where the first dimension refers to a selected shelf in the bookcase.7.7 Sorting MethodsMost programmers encounter the need to sort a list of data items at some time in their programming careers. For sorting data, two major categories of sorting techniques exist, called internal and external sorts. Internal sorts are used when the data list is not too large and the complete list can be stored within the computers memory, usually in an array. External sorts are used for much larger data sets that are stored on a large external disk or in tape files and cannot be accommodated within the computers memory as a complete unit.We will focus on two internal sort algorithms, the selection and exchange sorts. The exchange sort is also known as the bubble sort.Selection SortIn a selection sort, the smallest (or largest) value is initially selected from the complete list of data and exchanged with the first element in the list.After this first selection and exchange, the next smallest (or largest) element in the revised list is selected and exchanged with the second element in the list. This second pass only need to consider the second through last elements.For a list of n elements this process is repeated n-1 times, with each pass through the list requiring one less comparison than the previous pass.Example:Program 7-9#include #include void main(void)int nums10 = 22,5,67,98,45,32,101,99,73,10;int i, j, temp, moves, min, minInd;moves = 0;for (i = 0; i 10; i+)min = numsi;minInd = i;/ Search for minimum valuefor (j = i + 1; j 10; j+)if (numsj min)min = numsj;minInd = j;/ perform the switchif (min numsi)temp = numsi;numsi = min;numsminInd = temp;+moves; / end of outer for loopcout nThe sorted list, in ascending order, is:n;for (i = 0; i 10; +i)cout setw(4) numsi;cout n moves moves were made to